Вопросы
Комбинаторные алгоритмы. Определения
В экзаменационном билете 2 теоретических вопроса и 1 задача.
- Алгоритм построения пути в лабиринте с минимальным количеством изгибов
- Основные понятия теории графов. Теорема об эквивалентности различных условий в дереве
- Задача о минимальном остове. Основная лемма
- Алгоритм Борувки-Краскала
- Алгоритм Ярника-Прима-Дейкстры
- Задача о кратчайшем пути в сети. Алгоритм Форда-Беллмана
- Задача о конвертации валют
- Задача о кратчайшем пути в сети с неотрицательными весами
- Алгоритм Дейкстры
- Задача о кратчайшем пути в бесконтурной сети. Топологическая сортировка
- Сетевое планирование
- Пути между всеми парами вершин. Алгоритм Флойда
- Задача MAXMIN и MINMAX. Модификация алгоритма Дейкстры
- Потоки в сетях. Задача планирования производства
- Понятие разреза в сети. Пропускная способность разреза. Основные леммы
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона
- Потоки в сетях с несколькими источниками и стокам, с ограничениями на пропускную способность узлов
- Алгоритмы нахождения в сети потока заданной величины
- Задача о потоке минимальной стоимости. Транспортная задача как ее частный случай
- Прямой алгоритм построения потока минимальной стоимости. Поиск f-корректирующего цикла отрицательной стоимости в прямом алгоритме
- Двойственный алгоритм построения потока минимальной стоимости. Поиск f-дополняющей цепи минимальной стоимости
- Паросочетания. Теорема Бержа. Алгоритм построения наибольшего паросочетания в двудольном графе с помощью потоков
- Задача о полном паросочетании. Теорема Холла
- Алгоритм Куна
- Транспортная задача. Этапы решения транспортной задача. Методы нахождения первоначального опорного плана AND Метод потенциалов для нахождения оптимального решения