НОУ ИНТУИТ | Графы и алгоритмы

Авторы: Владимир Алексеев, Владимир Таланов | Нижегородский государственный университет им. Н.И.Лобачевского

Форма обучения:

дистанционная

Стоимость самостоятельного обучения:

бесплатно

Доступ:

свободный

Документ об окончании:

сертификат

Вам нравится? Нравится 42 студентам

Уровень:

Специалист

Длительность:

13:45:00

Студентов:

3854

Выпускников:

206

Качество курса:

4.44 | 4.11

Купить курс [?]

Поддержать курс

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

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

Темы: Алгоритмы и дискретные структуры

Специальности: Программист, Математик

Дополнительные курсы

2 часа 30 минут

Сдать экзамен экстерном

Лекция 1

1 час 17 минут

Начальные понятия теории графов

Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты. Операции над графами. Локальные операции. Подграфы. Алгебраические операции.

Оглавление

Тест 1

12 минут

4 задания

Лекция 2

43 минуты

Маршруты, связность, расстояния

Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы.

Оглавление

Тест 2

12 минут

4 задания

Лекция 3

1 час 5 минут

Важнейшие классы графов

Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы. Планарные графы.

Оглавление

Тест 3

15 минут

5 заданий

Лекция 4

38 минут

Поиск в ширину

Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление расстояний.

Оглавление

Тест 4

9 минут

3 задания

Лекция 5

43 минуты

Поиск в глубину

Процедура поиска в глубину. DFS-дерево. Глубинная нумерация. Построение каркаса. Шарниры.

Оглавление

Тест 5

9 минут

3 задания

Лекция 6

45 минут

Блоки

Блоки. Двусвязность. Блоки и BC-дерево. Выявление блоков.

Оглавление

Лекция 7

44 минуты

Пространство циклов графа

Пространство подграфов. Квазициклы. Фундаментальные циклы. Построение базы циклов. Рационализация.

Оглавление

Тест 6

15 минут

5 заданий

Лекция 8

38 минут

Эйлеровы и гамильтоновы циклы

Построение эйлерова цикла. Гамильтоновы пути и циклы.

Оглавление

Лекция 9

49 минут

Независимые множества, клики, вершинные покрытия.

Независимые множества, клики, вершинные покрытия . Три задачи. Стратегия перебора для задачи о независимом множестве. Эвристики для задачи о независимом множестве. Приближенный алгоритм для задачи о вершинном покрытии. Перебор максимальных независимых множеств.

Оглавление

Авторизоваться

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

Дополнительные курсы

План занятий