Динамическое программирование
Алгоритмы и структуры данных, часть 1


Что: Лекция
Когда: Четверг, 29 ноября 2012, 18:30–19:50
Где: ФМЛ 239, Актовый зал

Описание

Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти.