Вопросы к экзамену
- Основные понятия теории графов. Теорема об эквивалентности различных определений дерева
- Задача о минимальном остове. Основная лемма и её следствия
- Реализация алгоритма Борувки-Краскла
- Реализация алгоритма Ярника-Прима-Дейкстры
- Задача о кратчайшем пути в сети. Алгоритм Форда-Беллмана
- Задача о кратчайшем пути в сети с неотрицательными весами. Задача проводки платежей
- Алгоритм Дейкстры
- Задача о кратчайшем пути в бесконтурной сети. Топологическая сортировка
- Сетевое планирование
- Пути между всеми парами вершин. Алгоритм Флойда
- Потоки в сетях. Задача планирования производства
- Теорема о существовании максимального потока. Основные леммы
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона и его реализация
- Задача о потоке заданной величины
- Задача о потоке в сети с ограничениями снизу
- Задача о потоке минимальной стоимости. Транспортная задача как частный случай
- Прямой алгоритм построения потока минимальной стоимости. Поиск корректирующего цикла отрицательной стоимости в прямом алгоритме
- Двойственный алгоритм построения потока минимальной стоимости. Поиск дополняющей цепи минимальной стоимости
- Паросочетания. Теорема Бержа. Простой алгоритм построения наибольшего паросочетания в дувудольном графе
- Связь понятий паросочетания в двудольном графе и потока в соответствующей сети
- Алгоритм Хопкрофта-Карпа. Основные процедуры этого алгоритма
- Оценка сложности алгоритма Хопкрофта-Карпа
- Задача о полном паросочетании. Алгоритм Куна
- Задача о назначениях. Основные леммы. Операция Эгервари
- Венгерский алгоритм решения задачи о назначениях
- Задача о разбиении на наименьшее число паросочетаний. Алгоритм разбиения
- Математическая модель задачи составления учебного расписания
- Задача коммивояжера. Теорема о не существовании алгоритма с гарантированной оценкой точности в общем случае
- Алгоритм “Ближайшая вставка”. Реализация за $O(n^2)$. Теорема об оценке точности алгоритма “Ближайшая вставка”.
- Алгоритм “Остовный обход”. Реализация за $O(n^2)$. Оценка точности этого алгоритма
- Стохастический алгоритм для задачи коммивояжера. Моделирование отжига
- Вопросы, выделенные жирным, сдаются при помощи шпаргалки
- Требования к написанию шпаргалки:
- Пишется собственноручно, разборчивым почерком, с одной стороны листа А4
- На один вопрос не более 2 страниц
- На каждой странице справа вверху указывается автор
- К экзамену допускаются только те студенты, которые предъявят все 4 шпаргалки