Информация по курсу

Раздел 1: Метод динамического программирования
1. Одномерное динамическое программирование.
2. Концепция динамического программирования.
3. Двумерное динамическое программирование.
4. Общая задача динамического программирования.
5. Динамика «сверху вниз» и «снизу вверх». Мемоизация.
6. Преобразования решения задачи динамическим программированием.
7. Монотонность по параметру, выделение параметра "время" для экономии памяти.
8. Динамическое программирование по профилю.

Раздел 2: Алгоритмы динамического программирования
1. Наибольшие подпоследовательности
2. Строки и шаблоны
3. Расстояние Левенштейна
4. Алгоритмы замощения
5. Динамическое программирование по подмножествам. Задача коммивояжёра.
6. Динамическое программирование по дереву. Сбор информации о поддеревьях.
7. Алгоритм Флойда-Уоршелла
8. Алгоритм Беллмана-Форда

Программа курса

Семинаристы