Графы и алгоритмы: Информация

Авторы: Владимир Алексеев, Владимир Таланов | Нижегородский государственный университет им. Н.И.Лобачевского
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Стоимость обучения с персональным тьютором:
500 руб. [?]
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
13:45:00
Студентов:
3294
Выпускников:
105
Качество курса:
4.44 | 4.11
Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею. Для большинства рассматриваемых алгоритмов даются доказательства их правильности (т.е. того, что алгоритм действительно решает поставленную задачу) и оценок трудоемкости. Умение достаточно строго обосновывать алгоритмы и оценивать их трудоемкость является существенной частью квалификации алгоритмиста. Материал первой части может быть использован и в общем курсе дискретной математики.
Специальности: Программист, Математик
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 17 минут
Начальные понятия теории графов
Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты. Операции над графами. Локальные операции. Подграфы. Алгебраические операции.
-
Лекция 2
43 минуты
Маршруты, связность, расстояния
Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы.
-
Лекция 3
1 час 5 минут
Важнейшие классы графов
Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы. Планарные графы.
-
Лекция 4
38 минут
Поиск в ширину
Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление расстояний.
-
Лекция 5
43 минуты
Поиск в глубину
Процедура поиска в глубину. DFS-дерево. Глубинная нумерация. Построение каркаса. Шарниры.
-
Лекция 6
45 минут
Блоки
Блоки. Двусвязность. Блоки и BC-дерево. Выявление блоков.
-
Лекция 7
44 минуты
Пространство циклов графа
Пространство подграфов. Квазициклы. Фундаментальные циклы. Построение базы циклов. Рационализация.
-
Лекция 8
38 минут
Эйлеровы и гамильтоновы циклы
Построение эйлерова цикла. Гамильтоновы пути и циклы.
-
Лекция 9
49 минут
Независимые множества, клики, вершинные покрытия.
Независимые множества, клики, вершинные покрытия . Три задачи. Стратегия перебора для задачи о независимом множестве. Эвристики для задачи о независимом множестве. Приближенный алгоритм для задачи о вершинном покрытии. Перебор максимальных независимых множеств.
-
Лекция 10
35 минут
Раскраски
Раскраска вершин. Переборный алгоритм для раскраски. Раскраска ребер.
-
Лекция 11
35 минут
Рационализация переборных алгоритмов
Рационализация поиска наибольшего независимого множества. Хордальные графы. Рационализация алгоритма для задачи о раскраске вершин.
-
Лекция 12
57 минут
Паросочетания
Паросочетания и реберные покрытия. Метод увеличивающих путей. Паросочетания в двудольных графах. Паросочетания в произвольных графах (алгоритм Эдмондса).
-
Лекция 13
28 минут
Оптимальные каркасы
Задача об оптимальном каркасе. Алгоритм Прима. Алгоритм Крускала.
-
Лекция 14
40 минут
-
Лекция 15
21 минута
Кратчайшие пути
В этой лекции рассматриваются связные графы с неотрицательными весами ребер. А также кратчайшие пути, геодезическое дерево и алгоритм Дейкстры.
-
Лекция 16
35 минут
Потоки
В этой лекции будем рассматривать ориентированные графы без петель и кратных ребер: задачу о максимальном потоке и метод увеличивающих путей.
-
1 час 40 минут
-
Петр Петров
Петр Петров

произведение графов К(2)*О(4) фактически 4 отдельных графа К(2)?

Александр Лаврентьев
Александр Лаврентьев

много инструкций вида if - then - else

Например Procedure DFS(a) опишите каким образом следует понимать вложенность инструкций. Как в языке С ? 

т.е. следующее 

if (...) then (...)

if (...) then (...)

else(...)

 

раскрывается как 

if (...) then (...)

if (...) then (...)

         else(...)

или так :

if (...) then

 {  (...)

     if (...) then (...)

              else(...)

}

обьясните пожалуйста.

 

 

Дмитрий Крюков
Дмитрий Крюков
Россия, Москва
Андрей Посохов
Андрей Посохов
Россия, Санкт-Петербург