Алгоритмы 5ML весна 2022

Материал из CSC Wiki
Перейти к:навигация, поиск

Правила сдачи курса

Оценка курса выставляется по 10-балльной шкале и состоит из 3 компонентов:

  1. Экзамен .
  2. Теоретические домашние задания , сдача всех обязательных соответствует значению , значение может быть больше единицы.
  3. Контесты , сдача всех обязательных соответствует значению , значение может быть больше единицы.


Кроме обязательных задач бывают и дополнительные. Они не учитываются в теоретическом максимуме при расчёте итогового балла.

Лекции

Лектор: Пётр Смирнов

Программа

Конспект (не в точности соответствует лекциям)

Третий модуль

(1) 17 января. Сильная связность. Эйлеровость.
  • Сильная связность, КСС, конденсация. Алгоритм выделения компонент сильной связности.
  • Эйлеров цикл. Алгоритм нахождения.
(2) 24 января. 2-SAT. Паросочетания в двудольных графах.
  • Задача выполнимости. CNF-SAT, 2-SAT. Алгоритм решения за линейное время.
  • Паросочетания. Теорема Бержа.
  • Паросочетания в двудольных графах:
    • dfs;
    • базовый алгоритм, улучшенный алгоритм;
    • алгоритм Куна, оптимизация «чистить пометки реже», оптимизация «жадная инициализация»;
    • оптимизация «перемешивание рёбер».
(3) 31 января. VC, IS, Clique. Потоки в графах.
  • Соотношения между M, VC, IS, Clique в произвольных графах.
  • Теорема Кёнига для двудольных графов. Нахождение VC, IS, Clique в двудольном графе.
  • Потоки в графах: мотивация, определения, леммы, теорема и алгоритм Форда-Фалкерсона.

Доски с лекции: VC, IS, Clique, потоки.

(4) 7 февраля. Потоки-2. Запросы на отрезках.

Потоки

  • Хранение транспортной сети, реализация алгоритма Форда-Фалкерсона (с пропусканием единицы и пропусканием по максимуму).
  • Тест, на котором ФФ работает долго.
  • Алгоритм Эдмондса-Карпа, время работы (без доказательства).
  • ФФ с масштабированием. Реализация, оценка времени работы.

Запросы на отрезках

  • Массив
  • Префиксные суммы
  • Sparse table
  • Дерево отрезков с изменением в точке

Доски с лекции: потоки-2, запросы на отрезках.

(5) 14 февраля. Дерево отрезков. LCA.

Дерево отрезков:

  • Доказательство времени работы дерева отрезков
  • Изменение в точке сверху, снизу
  • Построение дерева отрезков за линейное время
  • Изменение на отрезке (отложенные/ленивые операции)
  • Неявное дерево отрезков
  • Сжатие координат

LCA:

  • Расстояние между вершинами в дереве
  • Двоичные подъёмы
  • Два способа решения LCA за (nlogn, log n).

Доски с лекции: дерево отрезков, LCA.

(6) 21 февраля. Эйлеров обход. Декартово дерево

Эйлеров обход:

  • Два типа эйлерова обхода
  • Решение LCA за <nlog n, 1> и за <n, log n>
  • Запросы на поддеревьях

Декартово дерево:

  • Определение
  • Merge, Split
  • Build, Add
  • Информация о поддереве, обновление, SplitBySize
  • Декартово дерево по неявному ключу

Доски с лекции: эйлеров обход, декартово дерево — 1, декартово дерево — 2.

(7) 28 февраля. Декартово дерево. Персистентность. Корневая декомпозиция.

Доски с лекции: массовые операции в декартовом дереве, персистентность-1, персистентность-2, корневая декомпозиция.

(8) 14 марта. Введение в теорию сложности - 1.

Доски с лекции: разрешимость, P и NP, NPh, NPc, BH.

(9) 21 марта. Введение в теорию сложности - 2. Meet in the middle.

Доски с лекции: NP-полнота CircuitSAT, NP-полнота 3-SAT, зачем нужна Сложность, Meet in the middle.

---> вы находитесь здесь <---
(Э) 28 и 30 марта. Экзамен.

Список вопросов.

Литература

Онлайн-курсы

Практика

Задачи

Условия задач

Технические советы для написания кода в контестах

Решения теордз нужно присылать в виде pdf-файла на почту для домашек, указанную ниже. Можно использовать TeX-шаблон для домашек.

[1] Никита Гаевой

Аудитория 2.3.

Контакты:

  • Telegram/VK для вопросов (если не хочется писать на почту): @nikgaevoy
  • Тема для писем с домашками: SPb HSE HW Masters Algorithms
  • Почта для домашек: nikgaevoy@gmail.com

Дедлайны по теоретическому ДЗ:

  • мягкий дедлайн в 23:59 вторника
  • жёсткий дедлайн в 23:59 среды, исправления можно присылать до начала пары

Таблица с результатами

[2] Даниил Орешников

Аудитория 254.

Контакты:

Дедлайны по теоретическому ДЗ:

  • мягкий дедлайн в 23:59 вторника
  • жёсткий дедлайн в 10:50 четверга (до начала пары)

Таблица с результатами