Дополнительные главы алгоритмов, часть 1
Санкт-Петербург, осень 2018
Описание
Это курс по алгоритмам для тех, кто уже что-то знает про алгоритмы. Мы постараемся поглубже разобраться как работают основные алгоритмы и структуры данных, а также изучим несколько алгоритмов посложнее.
Практика по курсу будет разбита на две части: решение теоретических задач и задач на программирование.
Для начала прохождения курса вы должны знать следующие темы:
- Анализ времени работы алгоритмов, амортизационный анализ
- Базовые структуры данных: двоичная куча, дерево отрезков, дерево поиска
- Базовые алгоритмы на графах: обход в глубину, обход в ширину
- Базовые алгоритмы на строках: КМП, хеши
Примерное содержание курса:
- Cтруктуры данных: кучи, дерево отрезков, дерево поиска
- Запросы на деревьях
- Декомпозиция графа
- Кратчайшие пути в графах
- Игры на графах
- Потоки, паросочетания
- Алгоритмы на строках
- Быстрое преобразование Фурье
Оценка будет складываться из:
- Теоретические задачи (50%)
- Задачи на программирование (50%)
Преподаватели
Список лекций
- Левосторонняя куча
- Биномиальная куча
- Куча Фибоначчи
- Дерево отрезков. Операции, применение
- Операции на отрезке. Ленивое проталкивание
- Органичения на операции, примеры
- Персистентное дерево
- Дерево поиска
- Неявный ключ. Rope
- Splay-дерево. Динамическая оптимальность
- Двоичные подъемы
- Сведение LCA к RMQ
- Решение RMQ(+-1) за O(1) с предподсчетом за O(n)
- Сведение RMQ к LCA
- Двоичные подъемы + лесенки
- Микро-макро эвристика
- Heavy-Light декомпозиция
- Link-cut дерево
- O(log n) со Splay деревом
Центроидная декомпозиция
- Центроид. Алгоритм нахождения
- Рекурсивная декомпозиция
- Ответы на запросы
- Euler Tour Tree
- Задача проверки связности на изменяющемся графе
Обход в глубину
Мосты, точки сочленения
Топологическая сортировка
Конденсация графа
2-SAT
Эйлеров цикл
Лемма о разрезе
Алгоритмы Краскала, Прима, Борувки
Ориентированные графы, алгоритм Эдмонса
Игры на ациклических графах
Игры на графах с циклами. Ретроанализ
Сумма игр. Теория Шпрага-Гранди
Sparse Table для произвольных ассоциативных функций
Skapegoat Tree
Минимальное ориентированное остовное дерево за \(O(n \log n + m)\).