Обсяг дисципліни, годин (кредитів ЄКТС): 3 кредити (90 год.)
Мета дисципліни:
– вивчення основ представлення даних у комп’ютері та основ побудови алгоритмів для розв’язання інженерних та економічних задач, що складають основу підготовки фахівця комп’ютерних технологій;
– формування у студентів навичок створення алгоритмів для розв’язування практичних інженерних та економіко-математичних задач;
– вивчення теоретичних положень і практичних методів представлення різних даних у комп’ютері.
Завдання дисципліни:
вивчення та реалізація різних алгоритмів і структур даних, а також розуміння їх ефективності та застосування.
Попередні умови для вивчення даної дисципліни:
Курс інформатики та математики в обсязі середньої школи, вміння користуватися засобами комп’ютерної техніки на рівні користувача.
Навчальні цілі дисципліни полягають у формуванні у студентів:
інтегративної компетентності:
формування загальних уявлень про алгоритми та структуру даних.
загальних компетентностей:
| ЗК 11 | |
| ОК 16 | + |
фахових компетентностей:
| СК 15 | СК 16 | |
| ОК 16 | + | + |
Програмні результати навчання:
| ПРН 31 | ПРН 35 | ПРН 317 | В 8 | В 16 | |
| ОК 16 | ++ | + | +++ | + | +++ |
В результаті вивчення дисципліни студент повинен
знати:
1. Основні поняття та принципи: базові концепції алгоритмів та структур даних. Відмінності між різними типами структур даних та їх застосування.
- Складність алгоритмів: оцінка часової та просторової складності алгоритмів. Аналіз та порівняння ефективності різних алгоритмів.
- Базові структури даних: масиви, списки, стек, черга, двостороння черга. Переваги та недоліки кожної структури, а також їх застосування в різних ситуаціях.
- Зв’язані списки: однозв’язані, двозв’язані, кругові списки. Принципи роботи та реалізація основних операцій (вставка, видалення, пошук).
- Дерева: бінарні дерева пошуку, AVL-дерева, червоно-чорні дерева, B-дерева. Принципи роботи, балансування дерев, обходи дерев (in-order, pre-order, post-order).
- Графи: Представлення графів (матриця суміжності, список суміжності). Основні алгоритми роботи з графами: пошук в ширину (BFS), пошук в глибину (DFS), алгоритми найкоротших шляхів (Дейкстра, Флойд-Воршелл).
- Сортування: основні алгоритми сортування: сортування вставками, вибором, злиттям, швидке сортування, пірамідальне сортування (heap sort). Принципи роботи алгоритмів та їх складність.
- Динамічне програмування: основні концепції динамічного програмування.
- Принципи розробки алгоритмів: розділяй і володарюй, жадібні алгоритми, динамічне програмування.
вміти:
— Оцінювати часову та просторову складність алгоритмів.
— Порівнювати ефективність різних алгоритмів для розв’язання однакових задач.
— Вибирати та використовувати відповідні структури даних.
— Застосовувати базові структури даних (масиви, списки, стеки, черги) у відповідних задачах.
— Обирати оптимальні структури даних для конкретних випадків застосування.
— Розробляти та реалізовувати алгоритми.
— Реалізовувати основні алгоритми сортування та пошуку.
— Використовувати алгоритми на графах для розв’язання задач маршрутизації та знаходження найкоротших шляхів.
— Розуміти та використовувати зв’язані структури даних.
— Реалізовувати та використовувати однозв’язані, двозв’язані та кругові списки.
— Працювати з деревами (бінарні дерева пошуку, AVL-дерева, червоно-чорні дерева).
— Працювати з алгоритмами на рядках.
— Реалізовувати алгоритми пошуку підрядків та алгоритми стиснення даних.
— Використовувати динамічне програмування.
— Розуміти принципи динамічного програмування та застосовувати їх для розв’язання оптимізаційних задач.
— Розв’язувати задачі, що потребують комбінування алгоритмів та структур даних:
— Інтегрувати різні структури даних та алгоритми для розв’язання складних прикладних задач.
— Використовувати знання про структури даних та алгоритми для оптимізації програмного забезпечення.
Зміст дисципліни (тематика):
Змістовий модуль 1. Обробка даних та їх структур.
Тема 1. (2 год.) Поняття задачі. Аналіз процесу розв’язання задачі. Поняття алгоритму, даних та аналізу алгоритму. Основні етапи розробки алгоритмів
Тема 2. (2 год.) Способи представлення алгоритмів
Тема 3. (2 год.) Поняття про базові алгоритмічні конструкції
Тема 4. (2 год.) Рекурсія. Рекурсивні алгоритми
Тема 5. (2 год.) Оцінка ефективності алгоритмів
Тема 6. (2 год.) Поняття структури даних. Класифікація структур даних. Прості структури даних
Змістовий модуль 2. Обробка динамічних структур даних
Тема 7. (2 год.) Масиви
Тема 8. (2 год.) Динамічні структури даних: список, стек, дек, черга
Тема 9. (2 год.) Графи. Деякі алгоритми на графах
Тема 10. (4 год.) Алгоритми пошуку числових даних
Тема 11. (4 год.) Алгоритми пошуку підрядка в рядку
Тема 12. (2 год.) Алгоритми сортування. Детальний аналіз алгоритму швидкого сортування
Тема 13. (2 год.) Криптографічні алгоритми та захист інформації в умовах війни. Розробка програмного забезпечення для людей з обмеженими можливостями
Види робіт:
лекції, самостійна робота, лабораторні заняття
Форма підсумкового контролю: іспит