Tinkoff Generation

Алгоритмы. Параллель A. План занятий второго полугодия

11 января 2020 Геометрия #1

  1. Расстояние от точки до прямой.

  2. Пересечение прямых.

  3. Пересечение прямой и окружности.

  4. Пересечение двух окружностей.

  5. Поиск касательных к окружности.

  6. Проверка на принадлежность точки многоугольнику за \(O(n)\). Два способа: сумма углов и луч.

  7. Алгоритм Джарвиса.

  8. Алгоритм Грэхема.

  9. Алгоритм Эндрю.

  10. Алгоритм Чана.

  11. Поиск пары пересекающихся отрезков за \(O(n \log n)\).

  12. Локализация точки в выпуклом многоугольнике за \(O(\log n)\) на запрос.

  13. Поиск касательных из точки к выпуклому многоугольнику за \(O(\log n)\) на запрос.

  14. Пересечение прямой с выпуклым многоугольником за \(O(\log n)\) на запрос.

  15. Локализация точки в невыпуклом многоугольнике за \(O(\log n)\) на запрос.

  16. Поиск двух ближайших точек в 2D.

  17. Пересечение полуплоскостей за \(O(n^2)\).

18 января 2020 Регион

25 января 2020 Геометрия #2

  1. Поиск двух ближайших точек в 3D.

  2. Вращающийся scanline. Запросы количества точек в полуплоскости. \(O(n^2 + q \log n)\). Возможность применения корневой.

  3. Сумма Минковского и ее применения.

  4. Квадродерево.

  5. Проецирование на случайную прямую.

  6. Проверка на непустоту пересечения полуплоскостей за \(O(n)\).

  7. Поиск минимальной покрывающей окружности за \(O(n)\).

  8. Пересечение полуплоскостей за \(O(n \log n)\).

  9. Триангуляция методом отрезания ушей за \(O(n^2)\)

  10. Диаграмма Вороного за \(O(n^2)\).

  11. Диаграмма Вороного за \(O(n \log n)\).

  12. Триангуляция Делоне.

01 февраля 2020 Строки #2

  1. Суффиксный массив за \(O(n)\).

  2. Дерево палиндромов.

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

  4. Суффиксное дерево.

8 февраля 2020 Графы #2

  1. Минимальные остовы.

  2. Алгоритм Прима.

  3. Алгоритм Крускала.

  4. Алгоритм Борувки.

  5. Поиск мостов онлайн.

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

  7. СНМ.

15 февраля 2020 Математика #3

  1. Теорема Люка.

  2. Функция Мёбиуса.

  3. Свертка Дирихле.

  4. Первообразный корень и его поиск.

  5. Поиск квадратного корня по простому модулю за \(O(\log p)\).

  6. Троичная сбалансированная система счисления.

  7. Битовые свертки: xor

  8. Hockey-stick identity и подсчет различных сумм в треугольнике Паскаля.

  9. Алгоритм Карацубы.

  10. Введение в комплексные числа. Применение комплексных чисел в геометрии.

  11. Быстрое преобразование Фурье.

  12. Теоретико-числовое преобразование Фурье.

  13. Применение Фурье к решению задач.

22 февраля 2020 Потоки #1

  1. Теорема Форда-Фалкерсона и соответствующий алгоритм.

  2. Алгоритм Эдмондса-Карпа.

  3. Масштабирование для Форда-Фалкерсона и Эдмондса-Карпа.

  4. Декомпозиция потока за \(O(E^2)\) и за \(O(VE)\).

  5. LR-потоки.

29 февраля 2020 Потоки #2

  1. Алгоритм Диница.

  2. Масштабирование для Диница.

  3. Оценки Карзанова.

  4. Поиск величины максимального потока в планарном графе.

  5. Стоимостные потоки. Форд-Беллман на очереди, Дейкстра с потенциалами.

7 марта 2020 Открытая

14 марта 2020 Интерактивки Контест

21 марта 2020 Неточные алгоритмы

  1. Алгоритм отжига.

  2. Генетический алгоритм.

  3. Монте-Карло.

  4. Потоковый алгоритм поиска количества различных.

28 марта 2020 Структуры данных #4

  1. Что такое амортизированное время работы?

  2. Метод потенциалов.

  3. Splay-дерево.

  4. Link-cut.

  5. ДО + (ДД/Splay) для dynamic records.

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

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

4 апреля 2020 Паросочетания

  1. Венгерский алгоритм.

  2. Алгоритм сжатия соцветий (поиск максимальных паросочетаний в произвольных графах).

  3. Взвешенное паросочетание в произвольном графе.

11 апреля 2020 Всеросс

18 апреля 2020 Графы #3

  1. Алгоритм двух китайцев.

  2. Дерево доминаторов.

  3. Гамма-алгоритм проверкии графа на планарность.

25 апреля 2020 Потоки #3

  1. Алгоритм проталкивания предпотока

  2. Алгоритм проталкивания предпотока для стоимостного потока

  3. Алгоритм Каргера-Штейна

  4. Алгоритм Штор-Вагнера

2 мая 2020 Матроиды

  1. Определение и основные утверждения. Примеры матроидов.

  2. Алгоритм Радо-Эдмондса поиска базы минимального веса.

  3. Пересечение матроидов.

09 мая 2020 Алгоритмы во внешней памяти

  1. Общие представления. Задачи поиска минимума, переворота, сортировки, join.

  2. List ranking.

  3. Список с возможностью перехода к \(k\)-му следующему за \(O(k/B)\).

  4. B-дерево.

  5. Heap во внешней памяти.

  6. BFS во внешней памяти.

  7. Мин. остов во внешней памяти.

16 мая 2020 Распараллеленные алгоритмы