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

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

Мета вивчення дисципліни «Теорія алгоритмів» – формування та розвиток компетентностей спрямованих на розв’язування складних спеціалізованих задач та практичних проблем у галузі комп’ютерних наук для адекватного моделювання предметних областей і створення програмних та інформаційних систем за рахунок використання формальних мов і  моделей алгоритмічних обчислень, проектування, розроблення й аналізу алгоритмів, оцінювання їх ефективності та складності, розв’язності та нерозв’язності алгоритмічних проблем. 

Практичне значення та використання отриманих знань дисципліни «Теорія алгоритмів» - отримання здобувачами базової вищої освіти теоретичних знань, спеціальних умінь і практичних навичок з аналізу та оцінки ефективності існуючих базових алгоритмів з використанням відповідних структур даних а саме:
– отримати знання основних понять та визначень теорії алгоритмів, типів алгоритмів та основних структур даних
– отримати знання математичних основ аналізу алгоритмів, а саме: оволодіння методами асимптотичного аналізу складності алгоритмів; отримання знань щодо класифікації алгоритмів відповідно до класів складності; отримання навичок щодо розробки критеріїв для порівняльної оцінки якості алгоритмів; оволодіння навичками щодо розробки алгоритмічного рішення проблеми або  формальних доказів алгоритмічної нерозв'язності завдань
– отримати знання побудови та функціонування алгоритмів основних класів, а саме алгоритми сортування, алгоритми на графах, лінійного та бінарного пошуку, алгоритми пошуку на строках тощо 

Основні результати навчання
ПРН1. Застосовувати знання основних форм і законів абстрактно-логічного мислення, основ методології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук. 
ПРН2. Використовувати сучасний математичний апарат неперервного та дискретного аналізу, лінійної алгебри, аналітичної геометрії, в професійній діяльності для розв’язання задач теоретичного та прикладного характеру в процесі проектування та реалізації об’єктів інформатизації
ПРН5. Проектувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.

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

1 тиждень. 
Лекція 1 «Основні поняття та визначення теорії алгоритмів: предмет теорії алгоритмів». Отримання завдання на розрахунково-графічну роботу. Проведення аналізу та підбору літературних джерел. 
Лабораторне заняття 1 «Квадратичні алгоритми сортування». 

2 тиждень 
Лекція 2 «Основні етапи проектування та аналізу алгоритмів»
Виконання розрахунково-графічної роботи. Частина 1

3 тиждень. 
Лекція 3 «Типи алгоритмів та основні типи задач»
Лабораторне заняття 2 «Логарифмічні алгоритми сортування».
Виконання розрахунково-графічної роботи. Частина 1
    
4 тиждень. 
Лекція 4 «Базові структури даних: лінійні структури даних, графи, дерева, множини, словники, абстрактні типи даних»
Виконання розрахунково-графічної роботи. Частина 1

5 тиждень. 
Лекція 5 «Математичні основи аналізу алгоритмів»
Лабораторне заняття 3 «Алгоритм пірамідального сортування». 
Виконання розрахунково-графічної роботи. Частина 1

6 тиждень. 
Лекція 6 «Приклади дослідження ефективності алгоритмів, поняття ітерації та рекурсії» 
Виконання розрахунково-графічної роботи. Частина 1

7 тиждень. 
Лекція 7 «Квадратичні алгоритми сортування, обмінні алгоритми сортування, сортування вибором». 
Лабораторне заняття 4  «Побудова мінімального кістякового дерева».
Виконання розрахунково-графічної роботи. Частина 1

8 тиждень 
Лекція 8 «Логарифмічні алгоритми сортування:пірамідальне сортування, сортування злиттям, швидке сортування».
Виконання розрахунково-графічної роботи. Частина 1
Модульна контрольна робота 1

9 тиждень. 
Лекція 9 «Алгоритми на графах: приклади завдань, матриці суміжності та інцидентності, списки суміжності». 
Лабораторне заняття 5  «Пошук найкоротшого шляху в графі». 
Виконання розрахунково-графічної роботи. Частина 2

10 тиждень. 
Лекція 10 «Систематичний перебір вершин графа: обходи графів у глибину та в ширину»
Виконання розрахунково-графічної роботи. Частина 2

11 тиждень. 
Лекція 11 «Зважені графи: алгоритм и Пріма та Крускала».
Лабораторне заняття 6  «Робота з деревами пошуку».
Виконання розрахунково-графічної роботи. Частина 2

12 тиждень. . 
Лекція 12 «Пошук найкоротшого шляху у графі алгоритм Беллмана-Форда, Дейкстри, та Флойда». 
Виконання розрахунково-графічної роботи. Частина 2

13 тиждень. 
Лекція 13 «Алгоритми лінійного та бінарного пошуку, бінарне дерево пошуку».
Лабораторне заняття 7 «Робота з хеш-таблицями»
Виконання розрахунково-графічної роботи. Частина 2

14 тиждень. 
Лекція 14 «Способи балансування бінарних дерев пошуку: червоно-чорні дерева»  
Захист розрахунково-графічної роботи

15 тиждень.
Лекція 15 «Основні відомості про хеш-таблиці: відкрите та закрите хешування»
Захист розрахунково-графічної роботи
Модульна контрольна робота 2

Самостійна робота здобувача відбувається впродовж семестру та складається з підготовки до аудиторних занять, контрольних заходів, індивідуальних завдань.
Консультації: здійснюються викладачем впродовж семестру згідно розкладу

Оцінювання результатів навчання

Оцінювання результатів навчання з дисципліни здійснюється за накопичувальною системою, яка дає можливість здобувачеві протягом семестру отримати максимально 100 балів.

Модуль 1
Лабораторна робота 1 – Лабораторна робота 4 по 5 балів – 20 балів.
Модульна контрольна робота 1 – 20 балів. 
Модульна контрольна робота 1 складається з теоретичної частини (2 запитання) та практичної частини (2 задачі). Бездоганна відповідь на теоретичне питання оцінюється 5 балами. Правильне розв’язання задачі оцінюється в 5 балів. 
Виконання першої частини РГР 10 балів
Модуль 2
Лабораторна робота 5 (5 балів), Лабораторна робота 6 (10 балів) Лабораторна робота 7 (5 балів) – 20 балів. 
Модульна контрольна робота 2 – 20 балів.
Виконання другої частини РГР 5 балів 
Захист розрахунково-графічної роботи – 5 балів. 
Модульна робота 2 складається з теоретичної частини (2 запитання) та практичної частини (2 задачі). Бездоганна відповідь на теоретичне питання оцінюється 5 балами. Правильне розв’язання задачі оцінюється в 5 балів.

Посилання на рекомендовані джерела
1. Data Structures and Algorithms [Електронний ресурс], Автори: Alfred V. Aho, Bell Laboratories, Murray Hill, New Jersey John E. Hopcroft, Cornell University, Ithaca, New York, Jeffrey D. Ullman, Stanford University, Stanford, California, Режим доступу: https://dokumen.tips/documents/data-structures-and-algorithms-alfred-v-a...
2. Горлова Т.М. Теорія алгоритмів. [Електронний ресурс]: конспект лекцій для студентів напряму підготовки 6.050101 «Комп'ютерні науки» денної та заочної форм навчання / Т.М. Горлова, К.Є. Бобрівник, Н.В. Ліманська – К.:НУХТ, 2015. – 95 с. Режим доступу: http://library.nuft.edu.ua/ebook/file/M51.21.pdf
3. Коваль В.С., Струбицький П.Р. Алгоритми і структури даних. – Навчальний посібник Тернопіль: ФОП Шпак В. Б. – 2017. – 74 с. Режим доступу: http://dspace.wunu.edu.ua/bitstream/316497/41016/1/%D0%BD%D0%B0%D0%B2%D1...
4. Algorithms and Data Structures by Niklaus Wirth  [Електронний ресурс] Автор Вирт Н. Режим доступуhttps://people.inf.ethz.ch/wirth/AD