Вопросы к экзамену по курсу доц. Г. В. Давыдова
"Теория трудноразрешимых задач"
Задачи класса
P
и
NP
.
Задача выполнимости.
Теорема Кука.
Полиномиальные подклассы выполнимости.
NP
полные подклассы выполнимости.
Задача о 3-сочетаниях.
Задача вершинного покрытия.
Задача о гамильтоновом цикле.
Задача о разбиении.
Задача о раскраске графа в 3 цвета.
Динамическое программирование и псевдополиномиальные задачи.
Сильная
NP
полнота.
Интерпретация шаблонов.
Генерирование шаблонов.
Генерирование трудных примеров.
ЛИТЕРАТУРА
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. 1982.
Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. Н. Новгород. 2004.
Davydov G.V., Davydova I.M. Dual Algorithms in Discrete Optimization. Amer. Math. Soc. Transl., v. 178, 1996