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

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

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

Для денної форми здобуття освіти
Лекційні заняття
Лекція 1. Вступ до теорії алгоритмів. Формалізація поняття алгоритму. Основні етапи комп'ютерного вирішення завдань.
Лекція 2. Математичні основи аналізу алгоритмів. Асимптотичні позначення. Швидкість росту функцій.
Лекція 3. Алгоритми сортування. Прості сортування як спосіб швидкої реалізації алгоритму. Складні сортування як спосіб створення ефективних алгоритмів. Сортування підрахунком. Порозрядне сортування.
Лекція 4.Швидке сортування (QuickSort). Сортування злиттям. Пірамідальне сортування (HeapSort)
Лекція 5. Базові структури даних. Зв'язковий список. Стек. Черга. Дек.
Лекція 6. Задача пошуку. Лінійний та бінарний пошук.
Лекція 7. Пошук з використанням хеш- таблиць. Основи хеш-таблиць. Хеш-функції. Дозвіл колізій.
Лекція 8. Графи: способи їх зберігання і обходи (в ширину і в глибину).
Лекція 9 Пошук мінімального остовного дерева у графі.
Лекція 10. Алгоритми пошуку найкоротших шляхів та оптимальних маршрутів у графах.
Лекція 11. Кінцевий автомат. Взаємне перетворення автоматів. Перетворення автомата Мура в Мілі.
Лекція 12. Реакція автомата на вхідне слово для автомата Мілі та для автомата Мура.
Лекція 13. Основи теорії обчислюваності. Машина Тюринга.
Лекція 14. Алгоритмічні стратегії.
Лекція 15. Класи складності P й NP.

Лабораторні заняття
Лабораторне заняття №1. Аналіз алгоритмів.
Мета заняття – уміти використовувати результати проведеного аналізу ефективності алгоритмів для розв’язання прикладних задач.
Лабораторне заняття №2. Алгоритми сортування. Прості та покращені алгоритми сортування.
Мета заняття – оволодіти практичними навичками реалізації алгоритмів сортування та порівняння їх.
Лабораторне заняття №3. Базові структури даних.
Мета заняття – оволодіти практичними навичками використання базових структур даних для вирішення прикладних завдань.
Лабораторне заняття №4. Задача пошуку. Реалізація бінарного пошуку.
Мета заняття – оволодіти практичними навичками реалізації алгоритму бінарного пошуку.
Лабораторне заняття №5. Реалізація пошуку з використанням хеш- таблиць.
Мета заняття – оволодіти практичними навичками реалізації хеш таблиць..
Лабораторне заняття №6. Графи: способи їх зберігання і обходу . Алгоритм Дейкстри.
Мета заняття – оволодіти практичними навичками програмування алгоритму Дейкстри
Лабораторне заняття №7. Розв'язання задачі машиною Тюринга
Мета заняття – оволодіти практичними навичками розв'язання задачі машиною Тюринга.

Консультації здійснюються впродовж семестру згідно встановленого розкладу.
Індивідуальна робота
Для денної форми здобуття освіти
Курсова робота
Мета курсової роботи є закріплення теоретичного матеріалу та здобуття практичних навичок розробки та аналізу ефективності алгоритмічного рішення конкретної прикладної задачі. Робота передбачає вибір структур даних, що забезпечують максимальну швидкодію, а також проведення порівняльного оцінювання обчислювальної складності алгоритму на різних масивах даних.

Здобувач отримує завдання на першому тижні першого семестру.
Пояснювальна записка містить 30-40 сторінок Кількість розділів – 3.
Змістовна послідовність виконання роботи.
1. Аналіз постановки задачі: формалізація вхідних та вихідних даних, визначення обмежень та вимог до програмного продукту.
2. Огляд існуючих алгоритмів, що можуть бути використані для розв’язання задачі. Обґрунтування вибору структур, які забезпечат мінімальні витрати ресурсів.
3. Реалізація коду: Опис ключових функцій, класів та модулів програми.
4. Тестування на контрольних прикладах та порівняльний аналіз ефективності алгоритма.

Захист курсової роботи – протягом останнього навчального тижня семестру.

Форми контрольних заходів та оцінювання результатів навчання

Для денної форми здобуття освіти
Поточний контроль полягає у виконанні
1) 7-ми індивідуальних поточних завдань. Індивідуальні поточні завдання виконуються на компʼютері відповідно до мети та завдань лабораторних занять. Бездоганне виконання індивідуальних поточних завдань №1,№7 оцінюється у 5 балів; індивідуальних поточних завдань №2 - №6 – 8 балів.
2) курсової роботи. Бездоганне виконання оцінюється у 60 балів. Захист роботи – 40 балів.
3) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної і практичної частин та проводяться у письмовій формі. Бездоганне виконання кожної модульної контрольної роботи становить 25 балів.
Підсумковий контроль – екзамен в усній формі. Максимальна оцінка, яку може отримати студент – 100 балів. Мінімальна оцінка, яка дозволяє отримати «задовільно» - 60 балів.