Алгоритмы и структуры данных (продвинутый поток)

Общие сведения

• Семестр: 3 (второй курс курс)
• Форма контроля: дифференцированный зачет

Важные ссылки

• Регистрация на курс (доступ для физтех-аккаунтов)
• Материалы курсa (доступ для физтех-аккаунтов)
• Чат курса
• Таблица с оценками

Требования

• Физтех-почта (домен phystech.edu)
• Аккаунт на GitHub
• Ноутбук на занятиях

План курса

№	Часть 1. Строки
1	Префикс-функция. Линейный алгоритм нахождения. Алгоритм Кнута-Морриса-Пратта.
2	Определение Z-функции. Линейный алгоритм нахождения. Применение для поиска подстроки в строке.
3	Алгоритм Манакера. Поиск максимальной подстроки-палиндрома.
4	Алгоритм Галила-Сейфераса поиска подстроки в строки за O(n) времени и O(1) дополнительной памяти.
5	Структура данных бор. Построение бора, оценка времени и объема памяти. Разные способы хранения детей дерева. Оценка объема памяти для каждого варианта. Понятие суффиксной ссылки. Пример дерева с суффиксными ссылками.
6	Алгоритм построения бора вместе с суффиксными ссылками. Оценка времени работы. Алгоритм Ахо-Корасик. “Сжатые” суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей. Оценка времени работы при использовании “сжатых” суффиксных ссылок.
7	Дерево палиндромов. Линейный алгоритм построения дерева палиндромов.
8	Определение суффиксного массива. Построение за O(N log N) с использованием цифровой сортировки для пар. Оптимизация “одна сортировка подсчетом вместо двух”.
9	Алгоритм Арикавы-Аримуры-Касаи-Ли-Парка.
10	Суффиксное дерево. Сжатое суффиксное дерево. Доказательство линейности числа вершин и ребер в сжатом суффиксном дереве.
11	Построение суффиксного дерева. Алгоритм Укконена.
12	Суффиксный автомат. Правые контексты, их свойства. Классы эквивалентности подстрок; критерий максимальности подстроки в своем классе эквивалентности. Линейность числа вершин и ребер, достижимость оценок.
13	Суффиксный автомат. Линейный алгоритм построения.

№	Часть 2. Геометрия
1	Прямые, отрезки, плоскости. Скалярное произведение, векторное произведение, их свойства. Угол между векторами, функция atan2. Коллинеарность прямых. Проверка принадлежности точки прямой, отрезку.
2	Поиск пересечения прямых - два способа: система уравнений и векторное произведение. Поиск пересечения окружности и прямой: два способа. Проверка наличия пересечения отрезков без вычисления точки пересечения прямых.
3	Поиск ориентированной площади многоугольника: метод “векторных произведений” и “метод трапеций”.. Знак площади и проверка того факта, что вершины многоугольника заданы в порядке обхода против часовой стрелки. Поиск площади пересечения многоугольника и круга как модификация метода “векторных произведений”.
4	Проверка принадлежности точки многоугольнику. Проблема вершины на луче. Три способа решения проблемы: случайный луч, вычисление “хорошего” луча, решение с горизонтальным лучом. Проверка принадлежности точки выпуклому многоугольнику за O(log n). Поиск правой касательной из точки к выпуклому многоугольнику за O(log n).
5	Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика, Чена.
6	Convex Hull Trick: версия с добавлением в структуру точек и поиском точки с минимальной проекцией на заданное направление.
7	Convex Hull Trick: версия с добавлением в структуру прямых и поиском прямой с минимальным y при заданном х. Дерево Ли-Чао.
8	Выпуклая оболочка 3D. Построение за O(n4), за O(n2).
9	Тернарный поиск. Выпуклые функции и их свойства, необходимые для корректного применения тернарного поиска. Вложенный тернарный поиск. Примеры: задача о фотографии, задача о максимальной вложенной в выпуклый многоугольник окружности..
10	Поиск пары ближайших точек на плоскости. Алгоритм Препараты. O(n log n). Поиск треугольника с минимальным периметром за O(n log n).
11	Поиск диаметра множества на плоскости за O(n log n). Поиск накрывающего прямоугольника минимального периметра за O(n log n). Поиск накрывающего прямоугольника минимальной площади за O(n log n).
12	Поиск граней связного плоского графа за O(n log n).
13	Нахождение суммы Минковского двух выпуклых многоугольников за O(m + n).Проверка наличия пересечения двух выпуклых многоугольников и поиск расстояния между ними за O(m + n). Задача о роботе и препятствиях (“задача про коридор и столы”; требуемое время O(n2*B), где n - число препятствий; робот и препятствия - выпуклые многоугольники с не более чем В вершинами)
14	Сканирующая прямая. Поиск наибольшего креста. Проверка факта пересечения отрезков. Площадь объединения прямоугольников за O(n log n).
15	Пересечение полуплоскостей: O(n3), O(n2), O(n log n).
16	Статическая задача поиска точек в подпрямоугольнике. Решения за (O(n^5), O(log n)), (O(n^3), O(log n)), (O(n^2), O(log n)). Fractional Cascading. Времена построения и вычисления ответа на запрос.
17	KD-дерево. Времена построения и вычисления ответа на запрос. Поиск ближайших точек множества с помощью KD-дерева, “контрпример”.
18	Диаграмма Вороного. Базовые свойства: структура ячеек, связность, оценки на количества ребер и вершин. Критерий совпадения точки с вершиной ДВ, попадания на внутреннюю часть ребра.
19	Построение диаграммы Вороного: O(n3), O(n2 log n), O(n2). Алгоритм Форчуна за O(n log n).
20	Триангуляция Делоне. Определение триангуляции. Теорема Фалеса. Флипы. Неправильное ребро, критерий неправильности.
21	Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.

№	Часть 3. Вероятностные алгоритмы и Ко
1	QSort, OrderStatistics: время работы в среднем и худшем случаях. Вероятностное определение цены игры на дереве. Алгоритм RandomGameTreeEval, его среднее время работы.
2	Задача о минимальном разрезе, алгоритм Каргера.
3	Задача о минимальном разрезе, алгоритм Каргера-Штайна.
4	Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в среднем случае. Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в худшем случае.
5	Задачи APD и APSP. APD для невзвешенных неориентированных графов, алгоритм APD-MM. Свидетели булевого перемножения матриц, алгоритм BPWM. Решение задачи APSP при помощи BPWM.

Оценивание

Оценка по курсу состоит из нескольких частей:

1. Тесты
2. Контесты
3. Практические проекты
4. Лабораторная работа

Тесты

• Небольшие тесты на 10 минут в начале каждого занятия
• Вопросы по материалам прошлого занятия
• Для прохождения нужен phystech.edu-аккаунт
• За каждый тест - 10 баллов.

Контесты

• Набор задач с автоматической проверкой тестирующей системой Я.Контест (нужен phystech.edu-аккаунт)
• Всего 6 тестов - после каждой темы базового блока
• Срок решения - 2 недели
• За каждый контест - 10 баллов
• Списывание детектируется и наказуемо!

Практические проекты

• 2 проекта - консольное приложение (после ООП) и серверное приложение (после Сети-2)
• Работа над кодом в несколько итераций на GitHub (нужен аккаунт)
• Срок работы - 2 недели + 1 неделя на каждую следующую итерацию
• Список тем проектов будет позднее
• Оценка за проект: зачет / незачет + до 2 доп. баллов (wow-эффект)

Лабораторная работа

• Анализ данных с помощью Pandas и Matplotlib
• Выдается после “Инструменты визуализации”
• Срок работы - 2 недели
• Оценка - 10 баллов
• Является блокирующей! Для получения зачета за курс необходимо набрать хотя бы 1 балл

Команда курса

• Преподаватели:
  • Рухович Филипп
  • Белый Антон