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

Мета вивчення дисципліни
Формування у здобувачів вищої освіти системи знань та вмінь щодо основних абстрактних типів та структур даних, базових алгоритмів, оцінки складності алгоритмів.
Практичне значення та використання отриманих знань
Формування у студентів розуміння основ алгоритмів і структур даних, які є ключовими для розробки ефективного програмного забезпечення. Студенти отримують навички роботи з базовими алгоритмами, вибору ефективних структур даних для поставленої задачі, а також їх адаптації під конкретні вимоги програмних систем. Розглядаються поняття складності алгоритмів, яке дозволяє аналізувати продуктивність рішень і забезпечувати оптимальне використання ресурсів. Вивчення рекурсивних алгоритмів і структур відкриває можливості для вирішення задач, які передбачають ієрархічну або циклічну логіку.
Таким чином, дисципліна знайомить студентів з основними концепціями, методами і процесами, що дозволяють створювати ефективні алгоритми: від розуміння принципів функціонування структур даних, таких як списки, дерева, графи, до практичного застосування алгоритмів сортування, пошуку і аналізу.
Тематика та види навчальних занять
Для денної форми здобуття освіти
Лекційні заняття
Лекція 1. Вступ до теорії алгоритмів. Поняття алгоритму: визначення та приклади. Алгоритми в програмуванні: базові поняття та роль у розробці ПЗ. Огляд основних класів алгоритмів
Лекція 2. Поняття обчислювальної складності. Що таке складність алгоритму. Часова та просторова складність: основні поняття. Вступ до асимптотичних позначень (O, Ω, Θ).
Лекція 3. Структури даних у пам’яті комп’ютера. Масиви, списки, стекі, черги. Важливість структур даних у розробці програмного забезпечення. Базові операції та їх реалізація.
Лекція 4. Алгоритми роботи з масивами. Послідовний та бінарний пошук. Вставка, видалення, обхід. Складність алгоритмів для масивів.
Лекція 5. Різновиди списків та алгоритми роботи з ними. Двобічні, циклічні та зв'язані списки. Алгоритми додавання, видалення та пошуку в різних типах списків.
Лекція 6. Стек і черга.
Лекція 7. Рекурсія в алгоритмах. Принципи та реалізація рекурсії. Приклади рекурсивних алгоритмів: факторіал, обхід дерева.
Лекція 8. Алгоритми пошуку.
Лекція 9. Алгоритми сортування. Основні методи сортування: вставки, злиття, швидке сортування (Quicksort). Складність алгоритмів сортування. Застосування сортування в програмуванні.
Лекція 10. Основи роботи з деревами. Поняття дерева та його використання в програмуванні. Бінарні дерева: структури та базові алгоритми (вставка, пошук, видалення). Застосування дерев у розробці ПЗ.
Лекція 11. Пірамідальне сортування та зовнішнє сортування. Сортування пірамідою (Heapsort). Алгоритми зовнішнього сортування для великих обсягів даних.
Лекція 12. Хеш-таблиці. Основи хешування та його роль в алгоритмах. Приклади використання хеш-таблиць у програмуванні.
Лекція 13. Вступ до графів. Основні поняття: вершини, ребра, шляхи. Представлення графів у пам’яті комп’ютера. Використання графів у розробці ПЗ.
Лекція 14. Алгоритми обходу графів. Пошук в глибину (DFS) та пошук в ширину (BFS). Використання алгоритмів обходу в реальних задачах. Практичні приклади в програмуванні.
Лекція 15. Основні алгоритми на графах. Пошук найкоротшого шляху: алгоритм Дейкстри. Алгоритми мінімального остовного дерева: алгоритм Прима. Застосування в мережах та оптимізації.
Практичні заняття
Практичне заняття №1. Блоки алгоритмів, умови. Загальні положення. Алгоритми та оцінка їхньої складності.
Мета заняття: Ознайомити студентів із основними структурними блоками алгоритмів (лінійними, розгалуженнями, циклами). Навчити складати алгоритми з використанням умов та базових операцій. Надати знання щодо оцінки складності алгоритмів.
Практичне заняття №2. Структури даних. Списки. Двозв'язковий список. Кільцевий список. Стек. Черга.
Мета заняття: Ознайомити студентів із базовими структурами даних: списками, двозв’язковими та кільцевими списками, стеком і чергою. Надати практичні навички реалізації та роботи зі списками, стеком і чергою.
Практичне заняття №3. Алгоритми сортування. Загальні положення. Сортування простими включеннями. Сортування простим вибором. Сортування простим обміном.
Мета заняття: Ознайомити студентів із основними поняттями алгоритмів сортування та їхньою класифікацією. Навчити реалізовувати алгоритми сортування простими включеннями, простим вибором і простим обміном. Надати навички вибору найбільш підходящого методу сортування для різних типів даних і задач.
Практичне заняття №4. Алгоритми покриття. Постановка завдання покриття. Алгоритм повного перебору.
Мета заняття: Ознайомити студентів із задачами покриття та їхньою постановкою в алгоритмічному контексті. Навчити реалізовувати алгоритм повного перебору для розв’язання задач покриття.
Практичне заняття №5. Алгоритми на графах. Загальні положення. Алгоритми знаходження оптимального шляху. Хвильовий алгоритм побудови найкоротшого шляху у зваженому графі. Дерево. Остів.
Мета заняття: Ознайомити студентів із основними поняттями графів: вершини, ребра, зважені та незважені графи. Навчити реалізовувати алгоритми знаходження оптимального шляху, зокрема хвильовий алгоритм для побудови найкоротшого шляху у зваженому графі. Ознайомити з поняттям дерева та його різновидами.
Практичне заняття №6. Рекурсивні алгоритми та оцінка їхньої складності. Загальні положення.
Мета заняття: Ознайомити студентів із принципами рекурсії та її використанням у алгоритмах. Навчити розробляти рекурсивні алгоритми для вирішення класичних задач.
Практичне заняття №7. Хеш-таблиці. Загальні положення. Завдання для самостійної роботи.
Мета заняття: Ознайомити студентів із поняттям хеш-таблиці як структури даних для швидкого пошуку, вставки та видалення елементів.
Для заочної форми здобуття освіти
Лекційні заняття
Лекція 1. Основи алгоритмів і структур даних. Алгоритми: загальні поняття. Структури даних. Ефективність алгоритмів.
Лекція 2. Рекурсія, базові алгоритми та їх зв’язок зі структурами даних. Використання структур даних. Стек. Черга. Дерева. Графи.

Практичні заняття
Практичне заняття №1. Блоки алгоритмів, умови. Загальні положення. Алгоритми та оцінка їхньої складності.
Мета заняття: Ознайомити студентів із базовими поняттями алгоритмів та їх структурою. Навчити будувати прості алгоритми із використанням умов і циклів. Розвинути вміння аналізувати складність алгоритмів, оцінювати їх ефективність.
Індивідуальна робота
Форми контрольних заходів та оцінювання результатів навчання

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