3. Динамическое программирование

Суббота, 29 сентября 2018, 16:20–17:55
НГУ, ауд. 2128
Список тем / 24 записи
    1.
    Лекция 1. Сложность и модели вычислений
    2.
    1. Вводное занятие
    3.
    Лекция 2. Сортировки
    4.
    2. Разное
    5.
    Лекция 3. Кучи (начало)
    6.
    3. Динамическое программирование
    7.
    Лекция 4. Кучи (продолжение)
    8.
    Семинар 4. Динамическое программирование
    9.
    Лекция 5. Порядковые статистики
    10.
    Семинар 5. Тестирование
    11.
    Лекция 6. Хеширование
    12.
    Семинар 6. Быстрое преобразование Фурье
    13.
    Лекция 7. Деревья поиска
    14.
    Семинар 7. Хеширование, итераторы
    15.
    Лекция 8. Деревья поиска: продолжение
    16.
    Семинар 8. Метод заметающей прямой
    17.
    Лекция 9. Задачи RMQ и LCA
    18.
    Семинар 9. Дерево отрезков
    19.
    Лекция 10. Система непересекающихся множеств
    20.
    Семинар 10. Разное
    21.
    Лекция 11. Структуры данных для геометрического поиска
    22.
    Семинар 11. Дерево поиска с неявным ключом
    23.
    Лекция 12. Задача о динамической связности в ненаправленном графе
    24.
    Семинар 12. Параллельные алгоритмы

Описание

Расстояние редактирования. Разрешаем редактировать обе строки. Добавления не нужны. Динамика: R[i, j] - расстояние между i-префиксом и j-префиксом. Смотрим на последние символы, разбираем случаи. Рекуррентная формула.

Задача о рюкзаке (Knapsack). Множество состояний и рекуррентная формула. Обратный ход (кратко).

Задача о порядке перемножения матриц. Множество состояний и рекуррентная формула. Обратный ход (кратко).