Saint Petersburg, 199178, Russia, Line 14th (Vasilyevsky Island), 29
(812) 363-68-71, (812) 363-68-72
ru en

Алгоритмы и метод динамического программирования

2020 – 2021, VI, VIII семестр

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

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

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


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