День 01. Матроиды

  1. Матроиды, определение, примеры (графовый, матричный, универсильный, разноцветный, трансверсальный матроид)
  2. Жадный алгоритм Радо-Эдмондса поиска базы минимального веса
  3. Пересечение матроидов
  4. Граф замен для одного матроида, лемма о графе замен (без доказательства)
  5. Граф замен для двух матроидов, поиск дополняющего пути
  6. Теорема Эдмондса-Лоулера и барьер, доказательство корректности алгоритма

День 02, Фурье

Быстрое преобразование Фурье и всякие мелочи.

  1. Умножение больших чисел, умножение многочленов, мотивация и сведение первого ко второму.
  2. Введение в комплексные числа
  3. Многочлены
  4. FFT над целыми числами.
  5. Полезные задачи

День 03. Автоматы и регулярные выражения

  1. DFA и ε-NFA, эквивалентность
  2. ε-переходы, их удаление
  3. Минимизация автомата и проверка на эквивалентность
  4. Алгоритм Хопкрофта минимизации за O(nlog n).
  5. Регулярные языки и регулярные выражения
  6. Сведение RegEx к ϵ-NFA и DFA к RegEx

День 04. Потоки

  1. Определение транспортной сети, потока, разреза.
  2. Равенство потока через любой разрез
  3. Определение остаточной сети, методы хранения
  4. Эквивалентность максимального потока, минимального разреза и отсутствия пути в остаточной сети.
  5. Алгоритм Форда-Фалкерсона
  6. Масштабирование
  7. Алгоритм Эдмонса-Карпа
  8. Определение блокирующего потока
  9. Алгоритм Диница
  10. Масштабирование в алгоритме Диница

День 05, Суффиксный Автомат

  1. Думаем об автомате
  2. Примеры.
  3. Алгоритм построения, дописывая буковки по одной.
  4. Связи с суфдеревом
  5. Задачи ??

День 06. Distributed

  1. Splay
  2. Доказываем время работы
  3. Разное
  4. Link Cut Tree

День 08. Игры

  1. Поиск выиграшных и проиграшных позиций в ациклических играх. DFS
  2. Поиск выиграшных и проиграшных позиций в циклических играх. Ретро анализ
  3. Определение суммы игр, нима
  4. Доказательство эквивалентности ациклической игры ниму. функция Шпрага-Гранди
  5. Теорема Смита для суммы циклических игр. Алгоритм Смита