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

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

    Свернуть всё Развернуть всё

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

    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

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