Алгоритми та структури даних

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

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

Практичне значення та використання отриманих знань :
- оволодіти навичками програмування базових алгоритмів з різними структурами даних;
- оволодіти  умінням вибирати ефективну структуру даних для поставленої задачі; 
- оволодіти  умінням розробляти алгоритм відповідно для структури даних; 
- оволодіти навичками використання рекурсивних структур даних та рекурсивних алгоритмів;
- оволодіти  умінням вирішення задач аналізу складності алгоритмів та програм.

Основні результати навчання

ПРН05. Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення.
ПРН11. Вибирати вихідні дані для проектування, керуючись формальними методами опису вимог та моделювання.
ПРН12. Застосовувати на практиці ефективні підходи щодо проектування програмного забезпечення.
ПРН13. Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань.
ПРН18. Знати та вміти застосовувати інформаційні технології обробки, зберігання та передачі даних. 

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

1 тиждень
Лекція 1. Поняття та класифікація алгоритмів обробки даних. Поняття обчислювальної складності алгоритмів і методи її оцінки. Основні класи алгоритмів.
Практичне заняття 1. Рекурсивні алгоритми та оцінка їхньої складності.
Самостійна робота здобувача вищої освіти.
Консультації
2 тиждень
Лекція 2. Алгоритмічні стратегії. Комбінування декількох алгоритмічних стратегій. Ітераційні алгоритми. Рекурсивні алгоритми. Зворотні алгоритми. Стратегія гілок і границь (Branch and bound algorithms). Стратегія розподіляй і володарюй. Динамічне програмування. Стратегія жадності (Greedy algorithms). Стратегія грубої сили (Brute force algorithms). Використання евристики. 
Самостійна робота здобувача вищої освіти.
Консультації

3 тиждень
Лекція 3. Структури даних у пам’яті комп’ютера. Масиви, множини, структури, бітові структури, таблиці, стеки, черги, лінійні списки. Базові алгоритми для роботи зі списками. 
Практичне заняття 2. Програмне опрацювання структур даних (списки, черги, стеки). 
Самостійна робота здобувача вищої освіти.
Консультації.

4 тиждень
Лекція 4. Різновиди списків та базові алгоритми роботи з ними. 
Самостійна робота здобувача вищої освіти.
Консультації

5 тиждень
Лекція 5. Нелінійні структури даних. Визначення дерева. Бінарне дерево. Подання дерев у пам’яті комп’ютера. Бінарні дерева: Ідеально збалансовані дерева. Дерева пошуку. Збалансоване АВЛ-дерева. Червоно-чорні дерева. 
Практичне заняття 3. Нелінійні структури даних.
Самостійна робота здобувача вищої освіти.
Консультації

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

7 тиждень
Лекція 7. Автомати. 
Практичне заняття 4. Синхронні та асинхронні автомати. 
Самостійна робота здобувача вищої освіти.
Консультації

8 тиждень
Лекція 8. Графи. Представлення графів у пам’яті комп’ютера. Алгоритми обходу графів.
Модульна контрольна робота 1.
Самостійна робота здобувача вищої освіти.
Консультації

9 тиждень
Лекція 9. Алгоритми пошуку в тексті. Brute Force, алгоритм Рабіна-Карпа сортування рядків, Кнут–Моріc–Пратта та інші.
Практичне заняття 5. Алгоритми текстового пошуку.
Самостійна робота здобувача вищої освіти.
Консультації

10 тиждень
Лекція 10. Алгоритми пошуку. Послідовний пошук, бінарний пошук.
Самостійна робота здобувача вищої освіти.
Консультації

11 тиждень
Лекція 11.  Алгоритми сортування масивів. Алгоритми сортування: вставки, Shellsort, злиття (mergesort), Quick sort, Radix-sort. Оцінка складності алгоритмів сортування.
Практичне заняття 6. Алгоритми сортування масивів.
Самостійна робота здобувача вищої освіти.
Консультації

12 тиждень
Лекція 12. Пірамідальне сортування, зовнішнє сортування.
Самостійна робота здобувача вищої освіти.
Консультації

13 тиждень
Лекція 13. Поняття хешування. Хеш-таблиці. Колізії. Алгоритми хешування. Відкрите і закрите хешування.
Практичне заняття 7. Хеш-таблиці.
Самостійна робота здобувача вищої освіти.
Консультації

14 тиждень
Лекція 14. Фундаментальні алгоритми на графах. Пошук найкоротшого шляху графа.
Самостійна робота здобувача вищої освіти, консультації.

15 тиждень
Лекція 15. Алгоритми нечіткого пошуку в тексті. Відстань Левенштейна. 
Модульна контрольна робота 2.
Самостійна робота здобувача вищої освіти.
Консультації

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

Оцінювання результатів навчання з дисципліни здійснюється за накопичувальною системою, яка дає можливість здобувачеві протягом семестру отримати максимально 100 балів.
Модуль 1
Оцінка за виконання практичних робіт (1 – 3) – максимально 20 балів за модуль. 
Модульна контрольна робота 1 – бездоганне виконання 30 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання завдання). 
Модуль 2
Оцінка за виконання практичних робіт (4 – 7) – максимально 20 балів за модуль.
Модульна контрольна робота 2 – бездоганне виконання 30  балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання завдання). 

Посилання на рекомендовані джерела

1.    Структури даних: практикум : навч.-метод. посібник [Електронне видання] / О. Г. Трофименко, Ю. В. Прокоп, О. Г. Янковський. – Одеса : Фенікс, 2022. – 115 с. ISBN 978-966-928-807-3
2.    Ільман В.М., Іванов О.П, Панік Л.О. Алгоритми, дані і структури: навч. посібн. : Дніпр. нац. ун-т залізн. трансп.ім. акад. В.Лазаряна. Дніпро: Дніпро 2019, 134 с. URL: http://eadnurt.diit.edu.ua/bitstream/123456789/11146/1/Ilman_et_al_2019.pdf.  
3.    Креневич А.П. Алгоритми і структури даних. Підручник. – К.: ВПЦ "Київський Університет", 2021. – 200 с. http://www.mechmat.univ.kiev.ua/wp-content/uploads/2021/09/pidruchnyk-al....
4.    Bullinaria John. Lecture Notes for Data Structures and Algorithms // School of Computer Science, University of Birmingham, UK, 2018. URL : https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf 
5.    Roughgarden T. Algorithms illuminated. Part 2. Graph Algorithms and Data Structure. San Francisco, 2018. URL :  https://www.pdfdrive.com/algorithms-illuminated-part-2-graph-algorithms-...