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

Авторы: Владимир Алексеев, Владимир Таланов | Нижегородский государственный университет им. Н.И.Лобачевского
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
13:45:00
Студентов:
3854
Выпускников:
206
Качество курса:
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 минут
                                  -
                                  Татьяна Наумович
                                  Татьяна Наумович

                                  Скажите, пожалуйста, можно ли еще получить документ о прохождении курса ("Графы и алгоритмы", декабрь 2020) после предоставления всех дополнительных необходимых документов?
                                  Или нужно проходить заново?

                                  Петр Петров
                                  Петр Петров

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