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

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