Вопросы к зачету по курсу доц. И. М. Давыдовой
"ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ"
Классификация дискретных задач оптимизации.
Динамическое программирование в задаче о рюкзаке.
Метод каскад.
Метод последовательного анализа вариантов.
Метод ветвей и границ в задаче о рюкзаке.
Супермодулярность в простейшей задаче размещения.
Метод последовательных расчетов.
Линейное программирование в построении оценки.
Замкнутые диаграммы. Вывод. Теорема двойственности.
Древовидные и недревовидные замкнутые диаграммы. Примеры.
Задача о раскраске графов.
Дерево Ковальского.
Метод плетей и границ.
Двойственный метод ветвей и границ.
Устойчиво разрешимые матрицы.
ЛИТЕРАТУРА
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. 1982.
Романовский И.В. Алгоритмы решения экстремальных задач. М. 1977.
Давыдова И.М. Схемы перебора в задачах размещения. ЛГУ, 1985.
Ху Т.Ч, Шинг М.Т. Комбинаторные алгоритмы. Н. Новгород. 2004.