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

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

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

    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

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