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

Вид материала

Программа дисциплины

Подобный материал:

• Задачи анализа топологии, 366.95kb.
• Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов, 12.79kb.
• Алгоритмы на графах, 47.29kb.
• Алгоритмы на графах Поиск по графу, 428.23kb.
• Тематический план n п/п Раздел дисциплины Семестр Неделя семестра, 96.94kb.
• «Численные методы в химии» Общая трудоёмкость дисциплины составляет, 22.46kb.
• Лекция 12: Алгоритмы на графах и деревьях, 395.7kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
• 2 семестр 2 курса, 56.57kb.
• Рабочая программа дисциплины Графы и алгоритмы Направление подготовки, 133.78kb.

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


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

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

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


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


Программа

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


Семестр 8


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

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

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

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

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

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