Вопросы к экзамену по курсу доц. Г. В. Давыдова

"Теория трудноразрешимых задач"

  1. Задачи класса P и NP.
  2. Задача выполнимости.
  3. Теорема Кука.
  4. Полиномиальные подклассы выполнимости.
  5. NP полные подклассы выполнимости.
  6. Задача о 3-сочетаниях.
  7. Задача вершинного покрытия.
  8. Задача о гамильтоновом цикле.
  9. Задача о разбиении.
  10. Задача о раскраске графа в 3 цвета.
  11. Динамическое программирование и псевдополиномиальные задачи.
  12. Сильная NP полнота.
  13. Интерпретация шаблонов.
  14. Генерирование шаблонов.
  15. Генерирование трудных примеров.

 

 

ЛИТЕРАТУРА

  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. 1982.
  2. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. Н. Новгород. 2004.
  3. Davydov G.V., Davydova I.M. Dual Algorithms in Discrete Optimization. Amer. Math. Soc. Transl., v. 178, 1996