Календарный план

  • Общая информация

    Требования к программам-решениям

    1. Решения должны быть оформлены в виде одного файла.

    2. Все решения должны считывать входные данные из файла input.txt и записывать результат(ы) в файл output.txt, расположенные в одном каталоге с программой.

    3. Формат входных и выходных данных должен соблюдаться в соответствии с описанием задачи.

    Процесс сдачи задачи

    1. Решение отправляется в ejudge.

    2. Если ejudge сообщает о том, что все тесты пройдены, то нужно прийти и обсудить решение задачи с преподавателем.

    Регистрация на ejudge

    1. Идем на сайт http://ejudge.mmcs.sfedu.ru и жмем вход.

    2. Выбираем контест "Практика по курсу "Алгоритмы на графах".

    3. После регистрации в пункте "Информация о пользователе" надо нажать кнопку редактировать и в поле "Имя участника" указать ФИО полностью.

  • Лекция 1

    Вводная лекция. 

    На лекции обсуждаются термины из теории графов, которые будут использоваться в дальнейшем.

    Д/З.

    1. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
    2. Квадрат 8 на 8 выложили из спичек. Какое наименьшее число спичек надо убрать, чтобы с любого поля можно было пройти на любое другое, не перепрыгивая через спички?
    3. У князя Гвидона было трое сыновей. Среди его потомков 93 имели каждый по 2 сына и ни одной дочери, а все прочие умерли бездетными. Сколько всего потомков было у Гвидона?




    • Лекция 2

      Представление графов на компьютере.

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

      • Лекция 3

        Поиск в глубину. Определение двудольности. Построение эйлерового цикла. Проверка ацикличности. Поиск наименьшего общего предка (lca).

        Построение остовного дерева (дерева поиска в ширину). Время входа и выхода.


      • Лекция 4

        Определение компонент сильной связности. Определение мостов.

        • Лекция 5

          Правильная нумерация. Ориентированные ациклические графы (DAG). Алгоритм построения правильной нумерации через поиск источников в графе. 

        • Лекция 6

          Количество остовных деревьев. Теорема Кирхгофа.

          Построение минимального остовного дерева. Алгоритмы Краскала и Прима.

          • Лекция 7

            Поиск кратчайших расстояний на графе. Алгоритм Беллмана-Форда. Алгоритмы Дейкстры и его модификации.  Дерево кратчайших расстояний.

            • Лекция 8

              Алгоритм А*. Системы разностных ограничений.

              Задача о поиске кратчайших путей между всеми парами вершин. Алгоритм "перемножения матриц". Алгоритм Флойда-Уоршела.

              Транзитивное замыкание.


              • Лекция 9

                Потоки в сетях. Метод Форда-Фалкерсона.


                • Лекция 10

                  Алгоритм Эдмондса-Карпа. Алгоритм Диница.

                  • Лекция 11

                    min cost - max flow

                    Паросочетания. Алгоритм Куна.

                    • Лекция 12

                      Алгоритм Тата и алгоритм Рабина-Вазирани.

                      • Лекция 13

                        Алгоритм путей, деревьев и цветов.

                        • Лекция 14

                          Венгерский алгоритм.