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

Направление 010100 Математика


Профили Дискретная математика и приложения,

Вычислительная математика и информатика,

Общий, специализация: Математические методы в экономике


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


Программа

дисциплины Алгоритмы на графах


Семестр 8


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

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

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

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


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

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

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

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


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

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

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

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

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