Дополнительные главы алгоритмов, часть 1

Санкт-Петербург, осень 2018

Описание

Это курс по алгоритмам для тех, кто уже что-то знает про алгоритмы. Мы постараемся поглубже разобраться как работают основные алгоритмы и структуры данных, а также изучим несколько алгоритмов посложнее.

Практика по курсу будет разбита на две части: решение теоретических задач и задач на программирование.

Для начала прохождения курса вы должны знать следующие темы:

  • Анализ времени работы алгоритмов, амортизационный анализ
  • Базовые структуры данных: двоичная куча, дерево отрезков, дерево поиска
  • Базовые алгоритмы на графах: обход в глубину, обход в ширину
  • Базовые алгоритмы на строках: КМП, хеши

Примерное содержание курса:

  • Cтруктуры данных: кучи, дерево отрезков, дерево поиска
  • Запросы на деревьях
  • Декомпозиция графа
  • Кратчайшие пути в графах
  • Игры на графах
  • Потоки, паросочетания
  • Алгоритмы на строках
  • Быстрое преобразование Фурье

Оценка будет складываться из:

  • Теоретические задачи (50%)
  • Задачи на программирование (50%)

Преподаватели

Список лекций

Кучи
  • Левосторонняя куча
  • Биномиальная куча
  • Куча Фибоначчи
Дерево отрезков
  • Дерево отрезков. Операции, применение
  • Операции на отрезке. Ленивое проталкивание
  • Органичения на операции, примеры
  • Персистентное дерево
Дерево поиска
  • Дерево поиска
  • Неявный ключ. Rope
  • Splay-дерево. Динамическая оптимальность
LCA + RMQ, LA
  • Двоичные подъемы
  • Сведение LCA к RMQ
  • Решение RMQ(+-1) за O(1) с предподсчетом за O(n)
  • Сведение RMQ к LCA
  • Двоичные подъемы + лесенки
  • Микро-макро эвристика
Heavy-Light декомпозиция, Link-cut дерево
  • Heavy-Light декомпозиция
  • Link-cut дерево
  • O(log n) со Splay деревом
Центроидная декомпозиция

Центроидная декомпозиция

  • Центроид. Алгоритм нахождения
  • Рекурсивная декомпозиция
  • Ответы на запросы
Euler Tour Tree, динамическая связность
  • Euler Tour Tree
  • Задача проверки связности на изменяющемся графе
Мосты, точки сочленения, компоненты сильной связности
  • Обход в глубину

  • Мосты, точки сочленения

  • Топологическая сортировка

  • Конденсация графа

2-SAT, Эйлеров цикл
  • 2-SAT

  • Эйлеров цикл

Минимальное остовное дерево
  • Лемма о разрезе

  • Алгоритмы Краскала, Прима, Борувки

  • Ориентированные графы, алгоритм Эдмонса

Игры на графах
  • Игры на ациклических графах

  • Игры на графах с циклами. Ретроанализ

  • Сумма игр. Теория Шпрага-Гранди

Невошедшее
  • Sparse Table для произвольных ассоциативных функций

  • Skapegoat Tree

Бонусная лекция

Минимальное ориентированное остовное дерево за \(O(n \log n + m)\).