Довідка

Практичне заняття 16. Динамічне програмування

Дізнаємось

Що таке динамічне програмування та в чому його суть.
Як виникає надлишковість обчислень у рекурсивних алгоритмах.
Які існують два основних підходи DP: згори вниз (memoization) та знизу вгору (tabulation).
Які типові задачі розв’язуються методом DP.
Як проаналізувати часову та просторову складність DP-алгоритмів.

Навчимось

Використовувати динамічне програмування для оптимізації рекурсивних задач.
Реалізовувати алгоритми з використанням мемоізації (через кешування результатів).
Створювати таблиці для обчислення результатів у порядку зростання підзадач (табуляція).
Розв’язувати типові задачі DP: Фібоначчі, рюкзак, найдовша спільна підпослідовність.
Порівнювати ефективність рекурсивних, мемоізованих і табульованих рішень.

Матеріали

Доступно тільки для зареєстрованих користувачів

Проблемні питання

Доступно тільки для зареєстрованих користувачів

Д.з.

Доступно тільки для зареєстрованих користувачів

№	Тема
3 лекції
1	Лекція 1. Поняття структур даних та їх класифікація. Формалізація поняття алгоритму. Основні напрямки в теорії алгоритмів
2	Лекція 2. Масиви. Стеки. Черги. Дек
3	Лекція 3. Зв’язні списки. Хеш-таблиці
4	Лекція 4. Пряма адресація. Хеш-функції.
5	Лекція 5. Двійкові дерева пошуку
6	Лекція 6. Сортування вибором та обмінне сортування. Сортування злиттям. Швидке сортування
7	Лекція 7. Сортування заздалегідь. Збалансовані дерева пошуку
8	Лекція 8. Послідовний пошук. Бінарний пошук. Методи, засновані на порівнянні ключів або на цифрових властивостях ключів
9	Лекція 9. Генератори псевдо випадкових чисел. Властивості випадкових та псевдо випадкових чисел. Недоліки генераторів псевдовипадкових чисел. Лінійний конгруентний метод.
10	Лекція 10. Представлення графа. Вершини. Ребра. Орієнтовані та неорієнтовані графи. Список суміжних вершин. Матриця суміжності. Пошук в ширину та в глибину. Дерева пошуку
11	Лекція 11. Властивості відрізків. Опукла комбінація. Векторний добуток. Обмежуючий прямокутник. Обчислення опуклої оболонки. Задача комівояжера. Задача про рюкзак. Задача про призначення
12	Лекція 12. Поняття хеш-функції. Метод відкритого хешування. Метод закритого кешування. Вибір хеш-функції
13	Лекція 13. Швидкість росту функцій. Логарифмічний, лінійний, квадратичний експоненціальний рости.
14	Лекція 14. Поняття про рекурсію. Умови застосування рекурсії. Аналіз рекурсивних алгоритмів. Методи розв’язання рекурсивних рівнянь. Дерево рекурсій.
15	Лекція 15. Динамічне програмування. Задача про множення матриць. Оцінка складності алгоритму задач про множення матриць.
16	Лекція 16. Жадібні алгоритми. Використання жадібних алгоритмів у програмуванні
3 практичні заняття
1	Практичне заняття 1. Вступ до структур даних та алгоритмів.
2	Практичне заняття 2. Базові структури даних
3	Практичне заняття 3. Базові структури даних. Хеш-таблиці
4	Практичне заняття 4. Базові структури даних. Дерева
5	Практичне заняття 5. Алгоритми пошуку. Лінійний пошук
6	Практичне заняття 6. Алгоритми пошуку. Бінарний пошук
7	Практичне заняття 7. Алгоритми сортування. Сортування бульбашкою
8	Практичне заняття 8. Алгоритми сортування. Сортування вибором
9	Практичне заняття 9. Алгоритми сортування. Сортування вставкою
10	Практичне заняття 10. Алгоритми сортування. Швидке сортування
11	Практичне заняття 11. Алгоритми сортування. Сортування підрахунком
12	Практичне заняття 12. Алгоритми сортування. Сортування за розрядами
13	Практичне заняття 13. Комбінаторні алгоритми
14	Практичне заняття 14. Фундаментальні алгоритми на графах та деревах
15	Практичне заняття 15. Рекурсія
16	Практичне заняття 16. Динамічне програмування
17	Практичне заняття 17. Жадібні алгоритми

Загальнонаціональна хвилина мовчання за загиблими внаслідок збройної агресії рф проти України

60