Лектор: Лепин Виктор Васильевич
Экзаменационные вопросы по курсу "Исследование операций"
4-й курс, 7-й семестр 2001-2002 учебного года.
- Понятия, принципы и средства ИО.
- Путь с минимальным количеством промежуточных вершин.
- Кратчайшие пути. Алгоритм Дейкстры.
- Кратчайшие пути. Алгоритм Форда-Беллмана.
- Построение кратчайшего остовного дерева.
- Дерево кратчайших путей (критерий существования).
- Кратчайшие пути с ограничениями на время проезда.
- Кратчайшие пути в графе между всеми парами вершин.
- Циклы минимальной средней стоимости. Алгоритм Карпа.
- Диаграмма ПЕРТ.
- Задача о потоке минимальной стоимости.
- Вполне унимодулярные матрицы и матрицы с сетевым свойством.
- Подзадачи о потоке минимальной стоимости.
- Задача о максимальном потоке. Алгоритм Форда-Фалкерсона. Теорема об увеличивающем пути.
- Теорема Холла.
- Алгоритм пересчета пропускных способностей.
- Алгоритм Диница нахождения максимального потока в сети.
- Алгоритм Диница для сетей с единичными пропускными способностями.
- Алгоритм Диница для простых сетей.
- Алгоритм Карзанова нахождения максимального потока в сети. Алгоритмы Push и Pull.
- Алгоритм Карзанова нахождения максимального потока в сети. Алгоритм насыщения и доказательство его трудоемкости.
- Алгоритм Карзанова нахождения максимального потока в сети. Доказательство трудоемкости.
- Минимальный разрез и максимальный поток в плоской сети.
- Рёберная связность. Алгоритм Метьюла.
- Максимальные паросочетания в произвольных графах.
- Теоремы о максимальных паросочетаниях в произвольных графах. Модифицированный поиск в ширину.
- Теоремы о максимальных паросочетаниях в произвольных графах. Модифицированный поиск в ширину. Перекрестные ребра. Цветок. Трудоемкость идентификации плохого перекрестного ребра и построения цветка.
- Техника срезания цветка. Теорема Эдмонса. Алгоритм нахождения максимального паросочетания.
- Задача о назначениях. Теорема Кана. Венгерский алгоритм.
- Классы P, NP, co-NP, NP-полнота, NP-трудность.
- NP-трудность ЦЛП.
- NP-трудность Сумма подмножества, Ранец, С-процессорное расписание.
- Алгоритм динамического программирования для Ранца.
- Приближённый алгоритм для задачи о ранце.
- Приближённый алгоритм для задачи с-процессорное расписание без прерываний.
- Какие оптимизационные задачи имеют полностью полиномиальные приближённые схемы.
- NP-трудность в сильном смысле.
- Доказать, что задача коммивояжера является NP- трудной в сильном смысле.
- Доказать, что задача о ранце не является NP- трудной в сильном смысле.
- Абсолютное приближение. Раскраска планарного графа.
- Абсолютное приближение. Задача о ранце.
- Планарное независимое множество.
- Псевдополиномиальные алгоритмы.
- Задача коммивояжера с неравенством треугольника. Алгоритм использующий минимальное остовное дерево.
- Задача коммивояжера с неравенством треугольника. Алгоритм Кристофидеса.
- Задача бункерная упаковка. Алгоритм "первый подходящий" и его оценка.
- Задача бункерная упаковка. Теорема о не существовании полиномиального алгоритма с отношением приближения < 1.5.
- Приближенное решение задачи о вершинном покрытии.
- 3-х мерное сочетание. Алгоритм с отношением приближения 3.
- 3-х мерное сочетание. Алгоритм с отношением приближения 2.
- Максимальная выполнимость. Max-2-Вып - NP-трудная.
- Приближённый алгоритм для Максимальной выполнимости.
- Вероятностно проверяемые доказательства.
- Max-3-Вып не имеет ПВПС.
- Независимое множество не имеет ПВПС.
- Независимое множество не имеет ПА с константным приближением.
- Вершинное покрытие не имеет ПВПС.
- Целочисленность и нелинейность
- Формулировка задачи коммивояжера как задачи ЦЛП.
- ЦЛП. Метод ветвей и границ.
- ЦЛП. Методы отсечений.