Изменения

Дискретная математика, алгоритмы и структуры данных

259 байт добавлено, 18:28, 15 октября 2014

→‎Динамическое программирование

== [[Динамическое программирование]] ==

=== Классические задачи динамического программирования ===

*[[Кратчайший путь в ациклическом графе]]

*[[Задача о числе путей в ациклическом графе]]

*[[Задача о порядке перемножения матриц]]

*[[Задача о наибольшей возрастающей подпоследовательности]]

*[[Метод четырех русских для умножения матриц]]

*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]

*[[Задача коммивояжера, ДП по подмножествам]]

*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]

*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]

*[[Задача о расстоянии Дамерау-Левенштейна]]

*[[Задача о рюкзаке]]

=== Способы оптимизации методв динамического программирования ===

*[[Метод четырех русских для умножения матриц]]

*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]

*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]

*[[Meet-in-the-middle]]

=== Другие задачи ===

*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]

*[[Задача о наибольшей подпоследовательности-палиндроме]]

*[[Meet-in-the-middle]]

*[[Динамическое программирование по профилю]]

*[[Задача о рюкзаке]]

*[[Динамика по поддеревьям|Динамика по поддеревьям, задачо о паросочетание максимального веса в дереве]]

3622

правки