Дополнительные главы алгоритмов, часть 1
Санкт-Петербург, осень 2019
Описание
Это курс по алгоритмам для тех, кто уже что-то знает про алгоритмы. Мы постараемся поглубже разобраться как работают основные алгоритмы и структуры данных, а также изучим несколько алгоритмов посложнее.
Практика по курсу будет разбита на две части: решение теоретических задач и задач на программирование.
Для начала прохождения курса вы должны знать следующие темы:
- Анализ времени работы алгоритмов, амортизационный анализ
- Базовые структуры данных: двоичная куча, дерево отрезков, дерево поиска
- Базовые алгоритмы на графах: обход в глубину, обход в ширину
- Базовые алгоритмы на строках: КМП, хеши
Примерное содержание курса:
- Cтруктуры данных: кучи, дерево отрезков, дерево поиска
- Запросы на деревьях
- Декомпозиция графа
- Кратчайшие пути в графах
- Игры на графах
- Потоки, паросочетания
- Алгоритмы на строках
- Быстрое преобразование Фурье
Оценка будет складываться из:
- Теоретические задачи (50%)
- Задачи на программирование (50%)
Преподаватели
Список лекций
1. Кучи
- Левосторонняя куча
- Биномиальная куча
- Фибоначчиева куча
2. Дерево отрезков
- Дерево отрезков, отложенные операции
- Метод заметающей прямой
- Персистентное дерево
4. LCA и RMQ
- Двоичные подъемы
- Сведение LCA к RMQ
- Решение RMQ(+-1) за O(1) с предподсчетом за O(n)
- Сведение RMQ к LCA
- Двоичные подъемы + лесенки
- Микро-макро эвристика
5. Heavy-Light декомпозиция, Link-cut дерево
- Heavy-Light декомпозиция
- Link-cut дерево
- O(log n) со Splay деревом