ТерверКГГЛОИФизика
Shift + колёсико

Вопросы к экзамену

  1. Основные понятия теории графов. Теорема об эквивалентности различных определений дерева
  2. Задача о минимальном остове. Основная лемма и её следствия
  3. Реализация алгоритма Борувки-Краскла
  4. Реализация алгоритма Ярника-Прима-Дейкстры
  5. Задача о кратчайшем пути в сети. Алгоритм Форда-Беллмана
  6. Задача о кратчайшем пути в сети с неотрицательными весами. Задача проводки платежей
  7. Алгоритм Дейкстры
  8. Задача о кратчайшем пути в бесконтурной сети. Топологическая сортировка
  9. Сетевое планирование
  10. Пути между всеми парами вершин. Алгоритм Флойда
  11. Потоки в сетях. Задача планирования производства
  12. Теорема о существовании максимального потока. Основные леммы
  13. Теорема Форда-Фалкерсона
  14. Алгоритм Форда-Фалкерсона и его реализация
  15. Задача о потоке заданной величины
  16. Задача о потоке в сети с ограничениями снизу
  17. Задача о потоке минимальной стоимости. Транспортная задача как частный случай
  18. Прямой алгоритм построения потока минимальной стоимости. Поиск корректирующего цикла отрицательной стоимости в прямом алгоритме
  19. Двойственный алгоритм построения потока минимальной стоимости. Поиск дополняющей цепи минимальной стоимости
  20. Паросочетания. Теорема Бержа. Простой алгоритм построения наибольшего паросочетания в дувудольном графе
  21. Связь понятий паросочетания в двудольном графе и потока в соответствующей сети
  22. Алгоритм Хопкрофта-Карпа. Основные процедуры этого алгоритма
  23. Оценка сложности алгоритма Хопкрофта-Карпа
  24. Задача о полном паросочетании. Алгоритм Куна
  25. Задача о назначениях. Основные леммы. Операция Эгервари
  26. Венгерский алгоритм решения задачи о назначениях
  27. Задача о разбиении на наименьшее число паросочетаний. Алгоритм разбиения
  28. Математическая модель задачи составления учебного расписания
  29. Задача коммивояжера. Теорема о не существовании алгоритма с гарантированной оценкой точности в общем случае
  30. Алгоритм “Ближайшая вставка”. Реализация за $O(n^2)$. Теорема об оценке точности алгоритма “Ближайшая вставка”.
  31. Алгоритм “Остовный обход”. Реализация за $O(n^2)$. Оценка точности этого алгоритма
  32. Стохастический алгоритм для задачи коммивояжера. Моделирование отжига