20 октября - дерево отрезков
- Дерево отрезков
- Дерево отрезков с массовыми операциями
- Двумерное дерево отрезков
- Применение: поиск максимальной возрастающей подпоследовательности, площадь объединения прямоугольников
- Sparse table
- Решение задачек
17 ноября - СНМ и декартово дерево
- СНМ
- Остовное дерево
- Декартово дерево по явному ключу
- Запросы на подотрезках в декартовом дереве
- Решение задачек
1 декабря - неявный ключ и персистентность
- Декартово дерево по неявному ключу
- Отложенные операции на декартовом дереве
- Персистентность
- Персистентное дерево отрезков и персистентный массив
- Персистентное декартово дерево
- СНМ с откатом
- Решение задачек
15 декабря - структуры данных на деревьях
- Дерево Фенвика
- Задачи lca и la, решение с помощью двоичный подъёмов
- Сведение задачи lca к задаче rmq с помощью Эйлерова обхода
- Сведение задачи rmq к задаче lca с помощью построения декартового дерева по неявному ключу
- Алгоритм Тарьяна для решения lca offline за O((n + q)*α(n)), rmq offline за O((n + q)*α(n))
- Решение задачи la за O(n), O(log n) с помощью ladder decomposition
- Алгоритм Фараха-Колтона-Бендера lca и rmq за O(n), O(1)
- Решение задачи la за O(n), O(1) с помощью метода четырёх русских
- Применение lca - запросы на путях в дереве без изменений, heavy-light decomposition
- Решение задачек
29 декабря - жадные алгоритмы на графах
- Матроиды, примеры матроидов
- Теорема и алгоритм Радо-Эдмонса
- Поиск минимального остовного дерева с помощью аглоритма Краскала
- Поиск максимального парасочетания в двудольном графе с помошью алгоритма Куна, минимальное по весу вершин в одной доли максимальное парасочетание
- Разбор задач на жадные алгоритмы
- Решение задачек
12 января 2019 - игры
- Выигрышные и проигрышные позиции в играх на ациклических графах
- Выигрышны, проигрышные и ничейные позиции в играх на произвольных графах
- Функция Шпрага-Гранди, сумма игр.
- Решение задачек
Следующее занятие - 2 феврвля
|
|