|
Скажите, пожалуйста, можно ли еще получить документ о прохождении курса ("Графы и алгоритмы", декабрь 2020) после предоставления всех дополнительных необходимых документов? |
Инспектор
Вы можете этот курс.
Графы и алгоритмы
:Графы и алгоритмы
: Информация
Опубликован: 27.09.2006 | Уровень: специалист | Доступ: платный | ВУЗ: Нижегородский государственный университет им. Н.И.Лобачевского
Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею. Для большинства рассматриваемых алгоритмов даются доказательства их правильности (т.е. того, что алгоритм действительно решает поставленную задачу) и оценок трудоемкости. Умение достаточно строго обосновывать алгоритмы и оценивать их трудоемкость является существенной частью квалификации алгоритмиста. Материал первой части может быть использован и в общем курсе дискретной математики.
Дополнительные курсы |
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 11 час 17 минут | Начальные понятия теории графов
Начальные понятия теории графов. Определение графа.
Графы и бинарные отношения. Откуда берутся графы.
Число графов. Смежность, инцидентность, степени.
Некоторые специальные графы. Графы и матрицы.
Взвешенные графы. Изоморфизм. Инварианты. Операции над графами.
Локальные операции. Подграфы. Алгебраические операции.
Оглавление | - |
Тест 112 минут | - | |
Лекция 243 минуты | Маршруты, связность, расстояния
Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики
графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы.
Оглавление | - |
Тест 212 минут | - | |
Лекция 31 час 5 минут | Важнейшие классы графов
Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы.
Планарные графы.
Оглавление | - |
Тест 315 минут | - | |
Лекция 438 минут | Поиск в ширину
Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление
расстояний.
Оглавление | - |
Тест 49 минут | - | |
Лекция 543 минуты | Поиск в глубину
Процедура поиска в глубину. DFS-дерево. Глубинная нумерация.
Построение каркаса. Шарниры.
Оглавление | - |
Тест 59 минут | - | |
Лекция 645 минут | Блоки
Блоки. Двусвязность. Блоки и BC-дерево. Выявление блоков.
Оглавление | - |
Лекция 744 минуты | Пространство циклов графа
Пространство подграфов. Квазициклы. Фундаментальные циклы.
Построение базы циклов. Рационализация.
Оглавление | - |
Тест 615 минут | - | |
Лекция 838 минут | Эйлеровы и гамильтоновы циклы
Построение эйлерова цикла. Гамильтоновы пути и циклы.
Оглавление | - |
Лекция 949 минут | Независимые множества, клики, вершинные покрытия.
Независимые множества, клики, вершинные покрытия . Три задачи.
Стратегия перебора для задачи о независимом множестве.
Эвристики для задачи о независимом множестве. Приближенный
алгоритм для задачи о вершинном покрытии. Перебор максимальных
независимых множеств.
Оглавление | - |
Тест 715 минут | - | |
Лекция 1035 минут | Раскраски
Раскраска вершин. Переборный алгоритм для раскраски.
Раскраска ребер.
Оглавление | - |
Лекция 1135 минут | Рационализация переборных алгоритмов
Рационализация поиска наибольшего независимого множества. Хордальные
графы. Рационализация алгоритма для задачи о раскраске вершин.
Оглавление | - |
Тест 812 минут | - | |
Лекция 1257 минут | Паросочетания
Паросочетания и реберные покрытия. Метод увеличивающих путей.
Паросочетания в двудольных графах. Паросочетания в произвольных графах
(алгоритм Эдмондса).
Оглавление | - |
Лекция 1328 минут | Оптимальные каркасы
Задача об оптимальном каркасе. Алгоритм Прима. Алгоритм
Крускала.
Оглавление | - |
Тест 915 минут | - | |
Лекция 1440 минут | Жадные алгоритмы и матроиды
Матроиды. Теорема Радо-Эдмондса. Взвешенные паросочетания.
Оглавление | - |
Лекция 1521 минута | Кратчайшие пути
В этой лекции рассматриваются связные графы с неотрицательными весами
ребер. А также кратчайшие пути, геодезическое дерево и алгоритм Дейкстры.
Оглавление | - |
Лекция 1635 минут | Потоки
В этой лекции будем рассматривать ориентированные графы без петель
и кратных ребер: задачу о максимальном потоке и метод увеличивающих путей.
Оглавление | - |
Тест 1018 минут | - | |
5 часов | - |
Татьяна Наумович
