Теорія алгоритмів

ID: 6006
Навчальна дисципліна професійної підготовки
Edition: 
2020.
Number of ECTS credits: 
6.00.
Contains term paper
Final form of control: 
Exam. Protection of course work.
Teacher: 
к.ф.-м.н., доц. Шпінарева І.М.
Number of classroom classes: 
16 годин лекційних занять, 44 годин лабораторних робіт..

Анотація навчальної дисципліни

Мета дисципліни:

є оволодіння здобувачами основних класів алгоритмів, оволодіння методикою їх аналізу та розробки; вивчення здобувачами вищої освіти типових абстрактних структур даних, що мають широке застосування при розробці прикладних програм та методів їх обробки та закріплення навичок роботи з ними..

Задачі дисципліни:
  • розкриття поняття алгоритму, його властивості та різні підходи; 
  • розкриття поняття складності алгоритму та методи розробки ефективних алгоритмів; 
  • набуття практичних навичок визначення складності алгоритмів та використання методів розробки ефективних алгоритмів.

 

Програмні компетентності

  • Здатність до абстрактного мислення, аналізу та синтезу.
  • Здатність застосовувати знання у практичних ситуаціях.
  • Здатність до пошуку, оброблення та узагальнення інформації з різних джерел.
  • Здатність оцінювати та забезпечувати якість виконуваних робіт.
  • Здатність аналізувати об’єкт проектування або функціонування та його предметну область.
  • Здатність застосовувати інформаційні технології у ході створення, впровадження та експлуатації системи менеджменту якості та оцінювати витрати на її розроблення та забезпечення.
  • Здатність вибору, проектування, розгортання інтегрування, управління, адміністрування та супроводжування ІСТ та інфокомунікацій, сервісів та інфраструктури організації.
  • Здатність використовувати сучасні технології проектування в розробці алгоритмічного та програмного забезпечення ІСТ.
  • Здатність оволодіти сучасними технологіями програмування та тестування програмного забезпечення.
  • Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних моделей і методів.
  • Програмні результати навчання
  • Застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проектування і використання ІСТ.
  • Використовувати базові знання інформатики й сучасних ІСТ, навички програмування, технології безпечної роботи в комп'ютерних мережах, методи створення баз даних та інтернетресурсів, технології розроблення алгоритмів і комп’ютерних програм мовами високого рівня із застосуванням об’єктно-орієнтованого програмування для розв’язання задач проектування і використання ІСТ. 
  • Демонструвати знання сучасного рівня технологій інформаційних систем, практичні навички програмування та використання прикладних і спеціалізованих комп’ютерних систем та середовищ з метою їх запровадження у професійній діяльності.

 

Кількість аудиторних занять

16 годин лекційних занять, 44 годин лабораторних робіт.

 

Форми організації освітнього процесу та види навчальних занять

  • Л – лекційні заняття;
  • ЛР – лабораторні роботи;
  • СРС – самостійна робота здобувача вищої освіти;
  • КР – курсова робота;
  • МКР – модульна контрольна робота;
  • К – консультації.

 

Тематика та види навчальних занять

  • 1 тиждень 
    • Л1. Вступ до теорії алгоритмів. Інтуїтивне визначення алгоритму. Методика розробки алгоритмів. Основні етапи комп'ютерного вирішення завдань. Аналіз алгоритмів [1, c. 13 - 15].  
    • ЛР1.  Аналіз алгоритмів та алгоритмічні стратегії [1, c. 13 - 15].  
    • СРС. К. 
  • 2 тиждень 
    • ЛР2-3  Аналіз алгоритмів: Евкліда, решето Еротосфени, числа Фібоначчі [1, c. 13 - 15].  
    • СРС. К. 
  • 3 тиждень
    • Л2. Алгоритми сортування. Прості сортування як спосіб швидкої реалізації алгоритму. Складні сортування як спосіб створення ефективних алгоритмів. Швидке сортування QuickSort. Сортування злиттям. Сортування підрахунком. Порозрядне сортування [4, 72-84].
    • ЛР4.  Алгоритми сортування. Прості та покращені алгоритми сортування[4, 72-84].
    • СРС. К. 
  • 4 тиждень 
    • ЛР5-6. Алгоритми сортування. Прості та покращені алгоритми сортування[4, 72-84].
    • СРС. К. 
  • 5 тиждень
    • Л3. Базові структури алгоритмів. Зв'язковий список. Стек. Черга. Дек. Загальне уявлення структури даних [3, 38-42, 4, 96-115].
    • ЛР7. Зв'язковий список [3, 38-42, 4, 96-115].  
    • СРС. К. 
  • 6 тиждень
    • ЛР 8-9. Задача пошуку. Лінійний та бінарний пошук. [3, 127-148]
    • СРС. К. 
  • 7 тиждень
    • Л4. Задача пошуку. Лінійний та бінарний пошук. Алгоритм бінарного пошуку. Складнощі роботи алгоритму бінарного пошуку [3, 127-148]
    • ЛР10. Реалізація бінарного пошуку. [3, 127-148,4]
    • СРС. К. 
  • 8 тиждень
    • ЛР11-12. Реалізація пошуку з використанням хеш- таблиць [1,4, 239-242]. 
    • МКР1. СРС. К. 
  • 9 тиждень
    • Л5. Пошук з використанням хеш- таблиць. Основи хеш-таблиць. Хеш-функції. Дозвіл колізій [4, 239-242].
    • ЛР13. Реалізація колізій в хеш- таблиці [1,4, 239-242,5].  
    • СРС. К. 
  • 10 тиждень
    • ЛР14-15.  Графи: способи їх зберігання і обходу (в ширину і в глибину) [1,3, 83-120, 5]
    • СРС. К. 
  • 11 тиждень
    • Л6. Графи: способи їх зберігання і обходи (в ширину і в глибину). Пошук циклів у графі. Алгоритми пошуку найкоротших шляхів та оптимальних маршрутів у графах [3, 83-120, 5]
    • ЛР16.  Алгоритм Дейкстри [1,3, 83-120, 5]
    • СРС. К. 
  • 12 тиждень
    • ЛР17-18. Автомат  Мура [1,4, 90-96]
    • СРС. К. 
  • 13 тиждень
    • Л7. Кінцевий автомат. Взаємне перетворення автоматів. Перетворення автомата Мура в Мілі. Реакція автомата на вхідне слово. Визначення реакції на вхідне слово для автомата Мілі. Визначення реакції на вхідне слово для автомата Мура [4, 90-96]
    • ЛР19. Автомат  Міля [1,4, 90-96]
    • СРС. К. 
  • 14 тиждень 
    • ЛР20-21. Перетворення автомата Мура в Мілі [1,4, 90-96]
    • СРС. К. 
  • 15 тиждень
    • Л8. Машини Тьюрінга. Принцип роботи машини Тьюринга. Табличне представлення роботи МТ.[1, c.41-54]
    • ЛР22. Розв'язання задачі машини Тюрінга.[1, c.41-54]
    • МКР2. СРС. К.

 

Індивідуальна робота

Виконується КР. 

Мета КР: систематизувати, розширити та закріпити теоретичні знання здобувачів вищої освіти з дисципліни «Теорія алгоритмів».  

  • 1–7 тижні Отримання завдання. Перетворення автоматів Мілі у Мура.
  • 8–14 тижні Розв’язання задачі машини Тюрінга. 
  • 15 тиждень Захист роботи.

 

Самостійна робота

Самостійна робота складає 120 години. Розподіл самостійної роботи за видами навчальних робіт:

  • 1) підготовка до лекційних занять – 24 годин;
  • 2) підготовка до лабораторних робіт та до виконання модульних контрольних завдань – разом 36 годин;
  • 3) виконання КР – 30 годин;
  • 4) підготовка до екзамену – 30 годин

 

Процедура оцінювання

Система оцінювання рівня навчальних досягнень ґрунтується на принципах ЄКТС та є накопичувальною. Дисципліна поділяється на два семестрові модулі. Здобувачі протягом семестру готуються до лекційних та лабораторних робіт, виконують 2 модульні контрольні роботи.

Модульні контрольні роботи № 1 та № 2 виконуються у письмовій формі. Модульна робота складається з теоретичної частини (2 запитання) та практичної частини (1 задача). Відповідь на кожне теоретичне питання оцінюється максимум 10 балами. Правильне розв’язання задачі оцінюється в 5 балів.

Кожний модуль оцінюється у максимально можливі 25 балів.

Семестровий модуль № 1

  • ЛР1- ЛР4.  Оцінка за виконання –25 балів. Термін виконання – 1-8 тиждень.
  • МК1. Модульна контрольна робота – 25 балів (8 тиждень). Перескладання можливе протягом 9–11 тижнів за розкладом консультацій.

Семестровий модуль № 2

  • ЛР5- ЛР8.  Оцінка за виконання – 25 балів. Термін виконання – 9-15 тиждень.
  • МК2. Модульна контрольна робота – 25 балів (15 тиждень). 

Курсова оцінюється окремо у максимально можливі 100 балів:

  • Семестровий модуль № 1 КР(ч.1).– 50 балів 
  • Семестровий модуль № 2 КР(ч.2).– 50 балів.

Підсумковим контролем з дисципліни в першому семестрі є екзамен, білет до якого складається з теоретичної частини (2 запитання по 25 балів) та практичної частини (1 задача – 50 балів). Максимальна оцінка за правильні відповіді на всі питання екзаменаційного білету становить 100 балів. 

 

Умови допуску до підсумкового контролю

До екзамену допускаються здобувачі вищої освіти, які виконали всі види навчальних елементів навчальної дисципліни на не менш, ніж на 60 %.

Екзамен відбувається за всіма тематичними (змістовними) модулями дисципліни.

Складання/перескладання екзаменів організується за встановленим деканатом розкладом.

 

Політика освітнього процесу

Здобувач зобов’язаний своєчасно та якісно виконувати всі отримані завдання; за необхідністю з метою з’ясування всіх не зрозумілих під час самостійної та індивідуальної роботи питань, відвідувати консультації викладача. 

Дотримуватись принципів академічної доброчесності. 

Виконаний не свій варіант завдання здобувачем не оцінюється.

Робота, яка виконана після встановлених викладачем термінів, не приймається.

Відсутність здобувача на екзамені або на контрольній роботі відповідає оцінці «0».

Складання/перескладання екзаменів – за встановленим деканатом розкладом.

Під час лекції здійснювати телефонні дзвінки забороняється.

Заборонено використання будь-яких підручників, посібників, конспектів лекцій, шпаргалок під час проходження модульних контролів з дисципліни

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

  1. Методичні вказівки до виконання лабораторних робіт студентів з дисципліни “Теорія алгоритмів”, для студентів II курсу денної та заочної форм навчання спеціальності - 126 Інформаційні системи та технології / Укладачі: І.М.Шпінарева, М.Д. Рудніченко, Н.О. Шибаєва.– Одеса: ОНПУ, 2020. – 57 с. (Електронна версія), Реєстраційний номер № MВ11558 -9.10.2020 
  2. Методичні вказівки до виконання РГР студентів з дисципліни “Теорія алгоритмів”, для студентів II курсу денної та заочної форм навчання спеціальності - 126 Інформаційні системи та технології / Укладачі: Н.О. Шибаєва, І.М.Шпінарева – Одеса: ОНПУ, 2020. – 33 с. (Електронна версія), Реєстраційний номер № MВ11557 -9.10.2020 
  3. Левітін В.Алгоритми Введення в розробку і аналіз. М.: "Вільямс", 2006. - 576 с. 
  4. Robert Lafore Data Structures and Algorithms in Java 2nd Edition. 2nd ed. - SPb .: Peter , 2013. - 704 p.
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms Third Edition The MIT Press Cambridge, Massachusetts London, England, 2009 -1296р.