Теорія алгоритмів і ефективні обчислення

Анотація навчальної дисципліни
Курс "Теорія алгоритмів і ефективні обчислення" призначений для формування фундаментальних знань з теорії алгоритмів та навичок розробки ефективних програмних рішень.
У курсі розглядаються основні концепції теорії алгоритмів, методи оцінки складності алгоритмів та принципи їх оптимізації. Значна увага приділяється вивченню класичних алгоритмічних структур даних: масивів, зв'язних списків, стеків, черг, дерев та графів.
Детально вивчаються різноманітні алгоритми сортування: від простих (бульбашкове сортування, сортування вставками, сортування вибором) до ефективних (швидке сортування, сортування злиттям, пірамідальне сортування). Досліджуються їх порівняльні характеристики та оптимальні сфери застосування.
Окремий розділ присвячено алгоритмам пошуку: бінарний пошук у відсортованих масивах, алгоритми текстового пошуку (прямий пошук, алгоритм Кнута-Морріса-Пратта, алгоритм Боєра-Мура), пошук у бінарних деревах пошуку та збалансованих деревах.
Вивчаються базові алгоритми на графах: обхід у глибину та ширину, пошук найкоротших шляхів (алгоритм Дейкстри, алгоритм Флойда-Воршелла), побудова мінімального кістякового дерева (алгоритми Прима та Крускала).
Курс також охоплює методи хешування та розв'язання колізій, алгоритми динамічного програмування, жадібні алгоритми, методи розділяй і володарюй, основи NP-повноти та теорії складності обчислень.
Практична частина курсу включає реалізацію вивчених алгоритмів мовою програмування, аналіз їх ефективності на різних наборах даних та порівняння теоретичних оцінок з практичними результатами. Особлива увага приділяється формуванню навичок вибору оптимальних алгоритмів та структур даних для розв'язання практичних задач, а також розвитку алгоритмічного мислення.

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

Для денної форми здобуття освіти
Опитування на лекціях, перевірка лабораторних робіт, модульні контрольні роботи, залік

Модуль 1 - 50 балів
Лабораторні роботи – сумарно 30 балів, модульна контрольна робота – 20 балів.
 
Модуль 2 - 50 балів
Лабораторні роботи – сумарно 30 балів, модульна контрольна робота – 20 балів.
 
Для заочної форми здобуття освіти
Перевірка лабораторних робіт, контрольна робота, залік
Лабораторні роботи – сумарно 60 балів, контрольна робота – 40 балів.

 
Політика освітнього процесу та умови допуску до підсумкового контролю
Здобувач зобов’язаний своєчасно та якісно виконувати всі отримані завдання; за необхідністю з метою з’ясування всіх незрозумілих під час самостійної та індивідуальної роботи питань відвідувати консультації викладача. Дотримуватись принципів академічної доброчесності.
Виконаний не свій варіант завдання здобувачем не оцінюється.
Робота, яка виконана після встановлених викладачем термінів, не приймається.
Відсутність здобувача на контрольній роботі відповідає оцінці «0». 
Складання/перескладання заліків – за встановленим деканатом розкладом.
Під час лекції здійснювати телефонні дзвінки забороняється.
Заборонено використання будь-яких підручників, посібників, конспектів лекцій, шпаргалок під час проходження модульних контролів з дисципліни.