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

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

Документы

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

• Лекция 12: Алгоритмы на графах и деревьях, 395.7kb.
• Задачи на графах. 17 Задачи на графах., 255.85kb.
• Задачи на графах. 16 Задачи на графах., 319.52kb.
• Удк 681 001. 63 Эволюционные процедуры решения комбинаторных задач на графах, 135.09kb.
• Задачи анализа топологии, 366.95kb.
• Программа дисциплины Алгоритмы на графах Семестр, 13.21kb.
• 1. Элементы теории графов Введение в теорию графов: основные понятия и определения., 32.17kb.
• Программа дисциплины Комбинаторные алгоритмы Семестры, 18.74kb.
• Алгоритмы на графах. Обходы графов. Кратчайшие пути. Остовные деревья, 114.51kb.
• Требования к реализации программы оценки : все методы должны быть применимы для перебора, 53.14kb.

Алгоритмы на графах

Класс: 10

Руководитель: Кудряшова Екатерина Максимовна

Количество часов: 68

Информация о курсе

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

Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею.

Курс содержит большую практическую часть, предполагающую разбор и анализ задач, решение которых основано на применении алгоритмов на графах.

Основные разделы курса:

• Начальные понятия теории графов
  
• Маршруты, связность, расстояния
  
• Важнейшие классы графов
  
• Поиск в ширину
  
• Поиск в глубину
  
• Эйлеровы и гамильтоновы циклы
  
• Независимые множества, клики, вершинные покрытия.
  
• Раскраски
  
• Рационализация переборных алгоритмов
  
• Паросочетания
  
• Оптимальные каркасы
  
• Жадные алгоритмы и матроиды
  
• Кратчайшие пути
  
• Потоки
  

Необходимая начальная подготовка:

• знание языка структурированного программирования (н-р, Pascal);
  
• знание основных алгоритмов обработки массивов;
  
• знание техники применения рекурсии.