Реферат: Программа дисциплины Комбинаторные алгоритмы Семестры

Направление 010200 Математика и компьютерные науки

Профиль Все профили


Степень бакалавр

Программа

дисциплины Комбинаторные алгоритмы


Семестры 4, 5


Цель дисциплины:

Курс посвящен

изучению классических алгоритмов решения оптимизационных задач на графах и сетях с применением различных приемов программирования;

построению новых и модификации и комбинации известных алгоритмов для решения конкретных задач (для конкретных конфигураций компьютеров);

оценке эффективности указанных алгоритмов.


Задачи дисциплины:

дать навыки постановки и решения задач оптимизации на графах;

научить выбору адекватных алгоритмов для решения вышеуказанных задач;

отработать умения по программной реализации алгоритмов на персональном компьютере.


Разделы курса, темы, их краткое содержание

Основные понятия теории графов. Машинное представление графов. Матрицы смежностей, списки смежностей, массив смежности.

Поиск. Поиск в глубину в графе. Поиск в ширину в графе. Случайный поиск. Построения путей в графах. Деревья поиска. Поиск в лабиринте. Задача о построении пути с минимальным числом поворотов.

Задача о минимальном остове. Алгоритмы Прима-Ярника-Дейкстры и Борувки-Краскла. Структуры данных задач НАЙТИ-ОБЪЕДИНИТЬ в алгоритме Борувки-Краскла. Штейнеровы деревья. Практические интерпретации задачи о минимальном остове.

Задачи о кратчайших путях, а именно, min-сумм, max-сумм, maxmin-задачи. Алгоритмы Форда-Беллмана и Дейкстры. Кратчайшие пути в бесконтурных сетях. Сетевые графики планирования работ. Расчеты основных характеристик в методе критического пути. Пути между всеми парами вершин. Алгоритм Флойда. Динамическое программирование.

Потоки в сетях. Задача о максимальном потоке. Алгоритм Форда-Фалкерсона. Теорема Эдмондса-Карпа. Потоки в сеятх с ограничениями снизу. Задача о потоке минимальной стоимости, прямой и двойственный алгоритмы ее решения. Транспортная задача.

Паросочетания в двудольных графах. Задача о наибольшем паросочетании. Модификация алгоритма Форда-Фалкерсона. Алгоритм Хопкрофта-Карпа. Оценка сложности алгоритма Хопкрофта – Карпа. Задача о полном паросочетании. Алгоритм Куна. Задача о назначениях. Венгерский алгоритм. Задача о разбиении на наименьшее число паросочетаний. Теорема Мендельсона-Далмеджа. Задача составления расписания.

Задача коммивояжера. Метод ветвей и границ. Алгоритмы с гарантированной оценкой точности: минимальная вставка и остовный обход.

Общая схема стохастических алгоритмов. Стохастический алгоритм решения задачи коммивояжера. Моделирование отжига.