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

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

Описание

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

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

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

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

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

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

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

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

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

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

Лекция 1. Куча
  1. Двоичная куча

  2. Левосторонняя куча

  3. Биномиальная куча

  4. Фибоначчиева куча

Лекция 2. Дерево отрезков
  1. Запросы на массиве. Полуинтервал \([\ell;r)\). sum(l, r) — сумма на отрезке, префиксные суммы.

  2. Дерево отрезков sum(l, r) и set(i, x), идея, реализация на указателях.

  3. Что можно вместо sum? Достаточное условие — ассоциативность операции и наличие нуля. Определение моноида. Полугруппа, как получить из полугруппы моноид. Дерево отрезков работает на полугруппе. Примеры:

    а) абелева группа (\(+\), \(\times_{\mathbb R\setminus\{0\}}\), \(\oplus\), \(+_{\mathbb R[x]}\), сложение и умножение можно по простому модулю, а иногда и не простому);

    б) абелев моноид (\(+_{\mathbb N_0}\), \(\times\), \(\times_{\mathbb R[x]}\), \(\wedge\), \(\vee\), \(\gcd\), \(\mathrm{lcm}\));

    в) абелева полугруппа (необратимые элементы абелевых моноидов: 1) явно выкинуть единицу: \(+_{\mathbb N}\), \(\wedge_{\mathbb N_0}\), \(\vee_{\mathbb N}\); 2) идеал в любом кольце: чётные целые числа по умножению, многочлены, кратные какому-то многочлену, многочлены с чётным свободным членом);

    г) группа (перестановки \(S_n\), биективные преобразования множества, обратимые матрицы/линейные отображения \(\mathrm{GL}(n, \mathbb R)\));

    д) моноид (квадратные матрицы \(\mathcal M_{n \times n}\), верхнетреугольные матрицы, все преобразования на множестве);

    е) полугруппа (необратимые элементы моноидов: обратимые матрицы, небиективные отображения; отображение \(a\cdot b=a\)).

  4. Массовые операции изменения. Две операции sum(l, r) и update(l, r, x), первая находит \(\bigoplus\limits_{i=\ell}^{r-1}x_i\), вторая применяет \(x_i:=x_i\otimes x\) для всех \(i\in[\ell;r)\). Удобный случай: дистрибутивность \(\oplus\) и \(\otimes\): \((a\oplus b)\otimes c=(a\otimes c)\oplus(b\otimes c)\). Примеры: \((\min, P_2)\), \((\min, +)\), \((+, \cdot)\) (здесь \(P_2(x, y)=y\)).

    1) Почему нельзя сделать так, как в прошлом дереве отрезков?

    2) Как понять изменение в вершине без вычисления изменений в детях? Дистрибутивность помогает.

    3) Идея lazy propagation.

    4) От некоторых условий можно избавляться. Можно избавиться от дистрибутивности, заменив её тем, что \(\bigoplus\limits_{i=\mathrm{node}{.}\ell}^{\mathrm{node}{.}r-1}{x_i\otimes x}\) можно выразить через \(\bigoplus\limits_{i=\mathrm{node}{.}\ell}^{\mathrm{node}{.}r-1}{x_i}\), \(\mathrm{node}{.}\ell\) и \(\mathrm{node}{.}r\).

    5) Мы пользуемся декомпозируемостью \(f(a, b, c)=g(g(a, b), c)\). От неё тоже можно избаавиться.

  5. Метод заметающей/сканирующей прямой, комбинация с деревом отрезков. Задача о плотнейшем покрытии прямоугольниками.

  6. Персистентное дерево отрезков.

Лекция 3. Дерево поиска
  1. Дерево поиска. Инвариант АВЛ-дерева

  2. Splay-дерево, операция splay, потенциал

  3. Операции split и merge в splay-дереве

  4. Дерево по неявному ключу — концепция, реализация при помощи splay-дерева

Лекция 4. LCA и RMQ
  1. Задача LCA поиска нижайшего общего предка двух вершин в подвешенном дереве. Решение с \(\mathcal O(n\log n)\) препроцессинга и памяти, \(\mathcal O(1)\) на запрос: двоичные подъёмы.

  2. Задача RMQ поиска минимума на подотрезках массива. Сведение LCA к RMQ за \(\mathcal O(n)\): эйлеров обход.

  3. LCA и RMQ с \(\mathcal O(n)\) препроцессинга и памяти, \(\mathcal O(\log n)\) на запрос: дерево отрезков.

  4. LCA и RMQ с \(\mathcal O(n\log n)\) препроцессинга и памяти, \(\mathcal O(1)\) на запрос: разреженная таблица.

  5. LCA и частный случай RMQ с \(\mathcal O(n)\) препроцессинга и памяти, \(\mathcal O(1)\) на запрос: алгоритм Фараха-Колтона, Бендера.

Семинар 4. LCA и RMQ

Разбор прошлого домашнего задания

Задача 1. Роман Чулков

Задача 2. Эмиль Рахимов

Задача 4. Денис Рахманкин

Задачи с практики

  1. Дано подвешенное дерево на \(n\) вершинах. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{up}(u,k)\): найти предка \(u\), расстояние до которого равно \(k\).

  2. Дано подвешенное дерево на \(n\) вершинах, на каждом ребре написано число. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{path\_min}(u,v)\): найти минимум на пути от \(u\) до \(v\).

  3. Дана полугруппа \((X,\otimes)\) и подвешенное дерево на \(n\) вершинах, на каждом ребре написан элемент \(X\); операции над элементами полугруппы занимают \(\mathcal O(1)\) памяти и времени. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{path\_prod}(u,v)\): найти тензорное произведение элементов на всех рёбрах пути от \(u\) до \(v\) (взятых именно в том порядке, в котором они лежат на пути).

  4. Дано подвешенное дерево на \(n\) вершинах, на каждом ребре написано положительное число — длина ребра. Постройте за \(\mathcal O(n\log n)\) структуру данных, которая за \(\mathcal O(\log n)\) отвечает на запрос \(\mathrm{path\_mid}(u,v)\): определить вершину или ребро, где находится середина пути (в метрическом смысле) от \(u\) до \(v\).

  5. Сведите RMQ к LCA. Формально, дан массив \(\left\{a_i\right\}\) из \(n\) целых чисел, постройте за \(\mathcal O(n)\) структуру данных, использующую алгоритм Фараха-Колтона, Бендера, которая за \(\mathcal O(1)\) отвечает на запрос \(\min(\ell,r)\): найти минимум в массиве от \(a_\ell\) до \(a_{r-1}\). [не успели разобрать]