2017.A-AA

Темы прочитанных лекций в 2017.Август.АА/A-ML

1. Персистентные структуры данных
2. Быстрое преобразование Фурье
3. Максимальный поток и минимальный разрез
4. Потоки минимальной стоимости
5. Матроиды, базовые понятия и теоремы
6. Пересечение и объединение матроидов
7. Геометрия, базовые примитивы и применения
8. Геометрия, продвинутые алгоритмы
9. LCA, LA
10. HLD, Centroid decomposition
11. Суффиксный автомат
12. Морской бой A1 vs. A2
13. Приближенные алгоритмы и оптимизации ДП

День 01, лекция

Персистентные структуры данных

1. Что такое персистентность (частичная, полная, ...)
2. Примеры персистентных структур данных
   • Линейные структуры данных: персистентный стек, персистентный массив
   • Персистентное дерево отрезков
   • Персистентное декартово дерево
3. Примеры задач на персистентные СД
   • К-я порядковая статистика на отрезке
   • Копирование отрезка из одной части массив в другую
4. (*) Частичная персистентность за O(1), скетч

День 02, лекция

Быстрое преобразование Фурье и всякие мелочи.

1. Умножение больших чисел, умножение многочленов, мотивация и сведение первого ко второму.
2. Введение в комплексные числа
   • Определение, умножение и сложение
   • Тригонометрическая форма
   • Умножение, возведение в степень в тригонометрической форме
   • Извлечение корня
   • Структура множества корней, умножение корней из 1 между собой, связь с корнями меньшего порядка
3. Многочлены
   • Теорема Безу, единственность многочлена по парам (x,f(x)), конструктивное построение
   • Умножение многочленов как умножение значений в точках, определение ДПФ
   • Быстрое преобразование фурье для 2^n, сведение к меньшим задачам.
   • Обратное преобразование Фурье, сведение к прямому
   • Эффективная реализация FFT
4. FFT над целыми числами.
   • Определение группы, примеры
   • Группа (Z/pZ)*
   • Циклическая группа, первообразный корень в (Z/pZ)*, без доказательства цикличности
   • ФФТ-Модуль (998244353 = 1 + 2^23 7 17) подгруппы, завершение рассказа о целых числах
5. Полезные задачи
   • Скалярное произведение строки на большую строку.

День 03, лекция

Максимальный поток и минимальный разрез.

1. Базовые определения
   • Сети, пропускные способности
   • Поток, свойства потока, величина потока
   • Остаточная сеть
   • Разрез, стоимость разреза, поток через разрез
2. Теорема Форда-Фалкерсона о равенстве максимального потока и минимального разреза
   • Лемма про отношение величины любого потока и любого разреза
   • Конструктивное построение потока, равного разрезу
   • Алгоритм Форда-Фалкерсона нахождения максимального потока
3. Декомпозиция потока
4. Алгоритм Эдмондса-Карпа
5. Схема алгоритмов с масштабированием
6. Алгоритм Диница

День 04, лекция

Потоки со стоимостью и венгерский алгоритм.

1. Базовые определения
2. Связь минимальности потока и отсутствия циклов отрицательной стоимости в остаточной сети
3. Оптимизированный алгоритм Форда-Беллмана
4. Потенциалы Джонсона
5. Поиск потока минимальной стоимости с использованием алгоритма Дейкстры
6. Венгерский алгоритм

День 05, лекция

Матроиды, часть 1

1. Определения: независимые множества, аксиомы матроидов, база, цикл
2. Примеры матроидов
3. Прямая сумма матроидов
4. Теорема о базах
5. Теорема о циклах

День 06, лекция

Матроиды, часть 2

1. Пересечение матроидов
   • Граф замен
   • Теорема о корректности
   • Алгоритм построения базы
   • Примеры
2. Объединение матроидов
   • Доказательство, что объединение -- матроид
   • Сведение к пересечению матроидов

День 07, лекция

Геометрия, часть 1

1. Базовые примитивы, скалярное/векторные произведения
2. Предикат "точка внутри окружности, описанной вокруг треугольника"
3. Сортировка по углу
4. Алгоритмы построения выпуклой оболочки
5. Вращающиеся калиперы
   • Диаметр множества
   • Минимальный объемлющий прямоугольник
6. Двоичный поиск по выпуклому многоугольнику
   • Ближайшая точка к выпуклому многоугольнику
   • Касательные к многоугольнику

День 08, лекция

Геометрия, часть 2

1. Сумма Минковского
2. Пересечение полуплоскостей, предикат проверки трех прямых на выпуклость
3. Ушная триангуляция
4. Минимальная объемлющая окружность, рандомизированный алгоритм
5. 3D геометрия, примитивы
6. Два алгоритма построения выпуклой оболочки за O(N^2)

День 09, лекция

LCA & LA

1. LCA
   • Постановка задачи, предикат is_parent, решение за O(n)
   • Двоичные подъёмы
   • Алгоритм Тарьяна
   • Решение за < n*log(n), 1 >
2. Алгоритм Фарака-Колтона и Бендера
   • RMQ -> LCA (дек. дерево)
   • LCA -> RMQ+-1
   • RMQ +- 1 за < n, 1 > методом четырех русских
3. LA
   • Постановка задачи, решение через двоичные подъёмы.
   • Алгоритм Вишкина (< n, log > через спуск)
   • Лестницы (удлинённые long-path-decomposition)
   • Применение метода четырех русских для сжатия деревьев размера <= log(n)/4

День 10, лекция

1. Centroid decomposition

   • Определение центроида дерева, существование и нахождение
   • Определение центроидной декомпозиции, построение
   • Свойства дерева центроидной декомпозиции
     • Глубина O(\log n) (=> O(n \log n) на построение)
     • Единственность центроида на пути (как LCA в дереве ц.д.)
     • Алгоритмы нахождения LCA (O(\log n) линейный поиск, O(\log log n) дв подъёмы, O(1) спарсы)
     • Доказательство количества центроидов (1-2)

2. Задачки на центроиды

   • min на пути (O(LCA))
   • Разделяй и властвуй как centroid decomp от бамбука
   • максимальный путь в дереве по весу (веса на рёбрах), O(n log n).
     • Динамика f(i) = max path: l(path) = i
   • максимальный ограниченный путь в дереве (то же самое но ищем путь длины <= l), O(n \log n)
     • Динамика f(i) = max path: l(path) <= i
     • Приливаем small-to-large чтобы не было проблем с пересчётом
   • "Покраска близких" (узнать цвет вершины, покрасить все вершины len(u, v) <= l в цвет c)
     • Offline, всё чтение строго после присвоений O((m + n) log n)
     • Запросы в произвольном порядке O(log^2 n) на запрос
     • Запросы в произвольном порядке O(log n) на запись, O(log^2 n) на чтение

3. Heavy-light decomposition

   • Определение декомпозиции Heavy-Light
   • функция на пути => 2 функции на вертикальном пути => кусочки каких-то путей HLD
   • Про поддеревья и пути (ALL in one SegmTree)

4. Задачки на HLD

   • Разбить дерево на вертикальные пути, так чтобы максимальное число путей, которые войдут в декомпозицию, от листа до корня было бы минимально
   • Динамическое добавление новых вершин в предыдущей задаче
   • f(v) = \sum_{i=0}^{v-1} w_{lca(v,i)}, вычислить все f(v) за быстро.

День 11, лекция

Суффиксный автомат

1. Конечные автоматы, определение, примеры.
2. Суффиксный автомат, определение, пример.
3. Правые контексты, свойства
   • вложены или не пересекаются
   • пересечение правых контекстов у строк - тогда одна суффикс другой
4. Дерево правых контекстов, оценка на число вершин
5. Модификация правых контекстов, при добавлении новой буквы к слову.
   • расщепление вершины, лемма о самом длинном суффиксе, который встречался ранее
6. Алгоритм построения
7. Схема доказательства линейности времени работы

День 13, лекция

Приближенные алгоритмы

1. Мотивация
   • Бывает NP, но хочется что-то посчитать быстро, даже если не совсем точно.
   • В частности будем искать решения не хуже, чем в f(n) раз.
2. MAX3SAT
   • 7/8, вероятность успеха.
3. VertexCover
   • Жадный Алгоритм (for ребро, если нет в текущем множестве, то возьмём 2 конца).
   • Доказательство, что он хуже не более чем в 2 раза.
4. TSP, 2-OPT
   • Постановка, неравенство треугольника, его существенность (сведение HAMCYCLE)
   • Решение через MST (обошли, скосили)
5. TSP, 1.5-OPT (Cristofildes).
   • Парсоч на нечётных вершинах в дереве (MST + парсоч).
   • C(парсоч) <= 1/2 C(OPT)
   • Веса 1-2 с неравенством треугольника, это NP-hard
   • если C <= 321/320 - \eps для \forall \eps
6. MaxClique
   • Получить решение не хуже, чем O(n^{0.99}) от оптимального это NP.
   • Что-то сделать можно: Разделить N вершин на групп размера k, прочекать каждую (nk2^k), k = c log(n) => P.
   • Оптимальность: пусть ans, тогда есть группа, где ans/(n/k) => мы нашли ans' >= ans (k/n).
7. SetCover
   • Постановка задачи
   • Жадный алгоритм
   • Доказательство двоичного логарифма
   • На самом деле натуральный (без доказательства)
   • Пример, когда лог

Оптимизации ДП

1. Кнут
   • c(i, i) = 0
   • c(i, j) = w(i, j) + min_{i < k <= j} (c(i, k - 1) + c(k, j))
   • w(i, j) удовлетворяет монотонности & QI
2. Кнут-2
   • d[k][i] = min_{0 <= t < i} d[k - 1][t] + c(t + 1, i), задача про почтовые отделения.
3. CHT
   • Идея, задача
4. D&C
   • Идея, задача
5. \lambda
   • Идея, задача