Вопросы к зачету по курсу доц. И. М. Давыдовой

"ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ"

  1. Классификация дискретных задач оптимизации.
  2. Динамическое программирование в задаче о рюкзаке.
  3. Метод каскад.
  4. Метод последовательного анализа вариантов.
  5. Метод ветвей и границ в задаче о рюкзаке.
  6. Супермодулярность в простейшей задаче размещения.
  7. Метод последовательных расчетов.
  8. Линейное программирование в построении оценки.
  9. Замкнутые диаграммы. Вывод. Теорема двойственности.
  10. Древовидные и недревовидные замкнутые диаграммы. Примеры.
  11. Задача о раскраске графов.
  12. Дерево Ковальского.
  13. Метод плетей и границ.
  14. Двойственный метод ветвей и границ.
  15. Устойчиво разрешимые матрицы.

 

 

ЛИТЕРАТУРА

  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. 1982.
  2. Романовский И.В. Алгоритмы решения экстремальных задач. М. 1977.
  3. Давыдова И.М. Схемы перебора в задачах размещения. ЛГУ, 1985.
  4. Ху Т.Ч, Шинг М.Т. Комбинаторные алгоритмы. Н. Новгород. 2004.