План лекций группы A

Глава 1. RMQ, LCA и другие

  1. Дерево отрезков
    1. Определение, примеры
    2. Реализация запроса и обновление снизу
    3. Реализация запроса и обновление сверху
    4. Реализация модификации на отрезке
    5. Обобщение на случай ассоциативных полуколец
    6. Задача поиска k-й порядковой статистики на отрезке
    7. Многомерное дерево отрезков
    8. Решение задачи о точках на карте
  2. Дерево Фенвика
    1. Определение, примеры
    2. Построение на месте (без использования дополнительной памяти)
    3. Задача RSQ
    4. Модификация для некоммутативных операций
    5. Многомерное дерево Фенвика
Упражнение Доказать правильность алгоритма поиска обновляемых индексов в дереве Фенвика
  1. Задача о наименьшем общем предке в дереве (LCA)
    1. Определение, примеры
    2. Offline - версия задачи, алгоритм Ахо-Хопкрофта-Ульмана-Тарьяна, O(n)
    3. Online - версия задачи, сведение к +/-1RMQ, (n, log n)
    4. Метод Sprace Table, (n log n, 1)
    5. Алгоритм четырех русских перемножения булевых мартиц, O(n3/log n)
    6. Использование идеи четырех русских в задаче LCA для получения оценки (n, 1) (алгоритм Фараха-Колтона - Бендера)
    7. Построение декартова дерева за O(n)
    8. Решение статической задачи RMQ за (n, 1) сведением к задаче LCA
    3.14 Система непересекающихся множеств
Упражнение Найти обобщение алгоритма четырех русских для алгоритма Флойда, O(n3/log n)

Глава 2. Словарные структуры данных

  1. Суффиксные массивы
    1. Определение, примеры, наивный алгоритм
    2. Построение суффиксного массива за O(n log n)
    3. Поиск образца в тексте с использованием суффиксных массивов, O(m log n)
    4. Улучшение оценки до O(m + log n)
  2. Суффиксное дерево
    1. Определение, примеры, наивный алгоритм, линейность суффиксного дерева
    2. Алгоритм Укконена 1.0, O(n3); эвристики способов 1 и 3; Укконен 2.0, O(n2)
    3. Суффиксные ссылки, skip/count (скачок по счетчику)
    4. Укконен за линейное время (ход алгоритма, доказательство оценки)
    5. Примеры
      1. Поиск образца в тексте за
      2. Поиск lcp(t[i..n], t[j..n])
      3. Поиск lcf (longest common factor) двух строк
      4. Поиск количества различных подстрок строки S
      5. Поиск максимального подпалиндрома
      6. Поиск максимальных повторов
  3. Суффиксный автомат
    1. Конечные автоматы
    2. Примеры для КМП, Ахо-Корасик
    3. Определение, примеры суффиксного автомата
    4. Теория правых контекстов, основная теорема
    5. Алгоритм построения суффиксного автомата за линейное время
    6. Алгоритм Дюваля

Глава 3, дополнительная

  1. Алгоритм двоичного подъема, LCA online, (n log n, log n)
  2. Построение и использование Z-функции

Глава 4. Задача о максимальном потоке и ее приложения

  1. Задача о максимальном потоке
    1. Определение, примеры
    2. Разрезы, связь с величиной потока
    3. Теорема Форда-Фалкерсона
    4. Градиентный метод поиска максимального потока
    5. Алгорита Эдмондса-Карпа
    6. Алгоритм масштабирования потока
  2. Метод блокирующего потока
    1. Алгоритм Диница поиска макимального потока
    2. Алгоритм Диница поиска блокирующего потока
    3. Алгоритм Малхотра-Кумара-Махешвари
  3. Паросочетание в двудольном графе
    1. Определение, примеры
    2. Сведение к задаче о максимальном потоке
    3. Алгоритм Куна
    4. Минимальное контролирующее множество, максимальное независимое множество
    5. Теорема о декомпозиции потока
    6. Первая теорема Карзанова, алгоритм Хопкрофта-Карпа
    7. Вторая теорема Карзанова
  4. Поток минимальной стоимости
    1. Определение, примеры
    2. Теорема о потоке миниммальной стоимости
    3. Потенциалы Джонсона
    4. Релизация алгоритмами Дейкстры и Форда-Беллмана
    5. Решение задачи о поиске невест
  5. Задача о назначениях
    1. Опредедение, сведение к задаче о потоке минимальной стоимости
    2. Венгерский алгоритм

Глава 5. Игры

  1. Игры на графах
    1. Игры на ациклических графах
    2. Анализ игры на графе с циклами. Ретро-анализ
    3. Полугруппа игр, эквивалентность по Гранди, симметричная стратегия
    4. Классификация игр на ациклических графах, функция Гранди
    5. Игры на графах с циклами
    6. Теория Смита
    7. Лемма об эквивалентности ниму
    8. Алгоритм Смита
    9. Лемма о проигрышной сумме
    10. Полная классификация игр на графах с точки зрения экивалентности по Гранди
ура, экзамен!