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

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

Мета вивчення дисципліни:
Формування у здобувачів здатності розробляти, аналізувати та оптимізувати алгоритми для розв’язання складних задач обробки даних із використанням сучасних підходів теорії алгоритмів.
Практичне значення та використання отриманих знань:
Отримані в межах дисципліни знання та навички мають практичне значення для розв’язання прикладних задач у сфері інформаційних технологій та інтелектуального аналізу даних. Здобувачі вищої освіти набувають здатності обґрунтовано обирати, проєктувати та реалізовувати алгоритми для ефективної обробки великих обсягів даних, оптимізації обчислювальних процесів і підвищення продуктивності програмних систем.
Результати навчання застосовуються при:
- розробці програмного забезпечення та алгоритмічних компонентів інформаційних систем;
- розв’язанні задач пошуку, сортування, оптимізації та аналізу структур даних;
- побудові та оптимізації алгоритмів для задач Data Science, зокрема аналізу графів, потокових даних та великих масивів інформації;
- застосуванні сучасних алгоритмічних підходів (жадібні алгоритми, динамічне програмування, функціональні структури даних) у практичних задачах;
- проведенні досліджень ефективності алгоритмів та виборі оптимальних рішень.
Отримані компетентності можуть бути використані у професійній діяльності фахівців з програмної інженерії, аналізу даних, штучного інтелекту, а також у науково-дослідній роботі.
Тематика та види навчальних занять

Для денної форми здобуття освіти

Лекційні заняття
Лекція 1. «Вступ до теорії алгоритмів. Оцінка складності».
Лекція 2. «Асимптотичні нотації».
Лекція 3. «Орієнтовані структури даних».
Лекція 4. «Рекурсія».
Лекція 5. «Динамічне програмування».
Лекція 6. «Впорядковані структури».
Лекція 7. «Сортування».
Лекція 8. «Червоно-чорні дерева».
Лекція 9. «Балансування дерев».
Лекція 10. «Функціональні структури».
Лекція 11. «Оптимізаційні задачі».
Лекція 12. «Жадібні алгоритми».
Лекція 13. «Апроксимаційні алгоритми».
Лекція 14. «Алгоритми для Data Science».
Лекція 15. «Сучасні напрямки теорії алгоритмів».

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

Лабораторна робота №2. «Графи».
Мета роботи: Освоєння реалізації структури даних “граф”, і основних операцій над цією структурою.

Лабораторна робота №3. «Мін-купа».
Мета роботи: Освоєння реалізації структури даних “мін-купа”, і основних операцій над цією структурою.

Лабораторна робота №4. «Функціональне червоно-чорне дерево».
Мета роботи: Освоєння функціонального підходу виправлення порушень червоно-чорного дерева.

Лабораторна робота №5. «Модифікація червоно-чорного дерева».
Мета роботи: Освоєння функціонального і імперативного підходу вставки в червоно-чорне дерево

Лабораторна робота №6. «Алгоритм Дійкстри ч.1».
Мета роботи: Одержання досвіду з принципом роботи алгоритму Дійкстри, який застосовується для знаходження найкоротших шляхів від однієї вершини графа до всіх інших.

Лабораторна робота №7. «Алгоритм Дійкстри ч.2».
Мета роботи: Виявлення недоліків наївної імплементації алгоритму Дійкстри, і їх виправлення шляхом використання оптимальних структур данних
Для заочної форми здобуття освіти
Лекційні заняття
Лекція 1. «Структури даних та базові алгоритми.».
Лекція 2. «Графи та складні алгоритми.».
Лабораторні роботи
Лабораторна робота №1. «Структури даних та базові алгоритми».
Мета роботи: Засвоєння реалізації та аналізу ефективності базових структур даних, а також застосування алгоритмічних підходів до організації та обробки даних з оцінюванням їх часової та просторової складності.
Лабораторна робота №2. «Графи та складні алгоритми».
Мета роботи: Засвоєння реалізації та застосування складних алгоритмів, зокрема алгоритмів на графах, збалансованих дерев та методів розв’язання оптимізаційних задач, а також аналізу їх ефективності при обробці даних

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

Для денної форми здобуття освіти
Розрахунково-графіна робота

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

Для заочної форми здобуття освіти

Розрахунково-графіна робота

Мета розрахунково-графічної роботи – закріплення знань з основ теорії алгоритмів, структур даних та методів аналізу ефективності алгоритмів, а також формування практичних навичок розробки, реалізації та порівняльного аналізу алгоритмічних рішень для задач обробки даних. Здобувач отримує індивідуальне завдання на установчій сесії.
Пояснювальна записка містить 15–20 сторінок.
Кількість розділів – 3. Графічна частина – результати роботи алгоритмів у вигляді схем, графів, таблиць та візуалізацій (у електронному вигляді), додаток з лістингом коду.

Змістовна послідовність виконання роботи.
1. Визначення допустимої обчислювальної просторової і часової складності реалізації поставленої задачі.
2. Розбиття поставленої задачі на підзадачі, і вибір структур даних для отриманих підзадач.
3. Розробка алгоритмів роботи модулів і загальної системи, їїх графічна візуалізація.
4. Оцінка теоретичної просторової і часової складності розроблених алгоритмів.
5.Реалізація розроблених алгоритмів.
6. Перевірка працездатності виконаної реалізації.
7. Оцінка реальної просторової і часової складності, яка була досягнута при реалізації розроблених алгоритмів.
Захист розрахунково-графічної роботи – протягом останнього навчального тижня семестру.

Контрольна робота

Завдання для виконання контрольної роботи здобувач отримує на установчій лекції.
Робота містить 5 теоретичних питань та 2 практичних завдання.
Обсяг відповіді на кожне теоретичне питання: не менше, ніж 2 сторінки машинописного тексту. Текст відповіді повинен бути виконаний самостійно, а не скопійованим з навчального посібника.
Практичне завдання №1 «Аналіз і оцінка просторової і часової складності наданої компонентів наданої програми». Практичне завдання №2. «Реалізація потокового сортування».
Термін надання виконаної контрольної роботи на перевірку – не пізніше, ніж за місяць до початку сесії.
Форми контрольних заходів та оцінювання результатів навчання

Для денної форми здобуття освіти

Поточний контроль полягає у виконанні
1) 7-ми лабораторних робіт. Захист лабораторної роботи 1-5 оцінюються по 3 бали кожна 6, 7 - в 5 балів кожна;
2) Розрахунково-графічної роботи. Бездоганне виконання оцінюється у 15 балів. Захист роботи – 10 балів.
3) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної і практичної частин та проводяться у формі комп'ютерного тестування. Бездоганне виконання кожної модульної контрольної роботи становить 25 балів.
Підсумковий контроль – екзамен. Екзамен усний. Максимальна оцінка, яку може отримати студент – 100 балів.

Для заочної форми здобуття освіти

Захист контрольної роботи. Бездоганне виконання контрольної роботи оцінюється у 30 балів. При її захисті студент може отримати до 10 балів.
Захист розрахунково-графічної роботи. Бездоганне виконання розрахунково-графічної роботи оцінюється у 30 балів. Захист роботи – 10 балів.
Захист лабораторних робіт 1, 2 оцінюється по 10 балів кожна.
Підсумковий контроль – екзамен. Екзамен усний. Максимальна оцінка, яку може отримати студент – 100 балів.