Алгоритмы и структуры данных (продвинутый поток) — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(→‎План курса)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 19: Строка 19:
 
|-  
 
|-  
 
! №
 
! №
−
! Тема
+
! Часть 1. Строки
 
|-
 
|-
  
−
|1|| Асимптотические обозначения: O, Ω, Θ. Независимость от стартового индекса.
+
|1|| Префикс-функция. Линейный алгоритм нахождения. Алгоритм Кнута-Морриса-Пратта.
  
 
|-
 
|-
  
−
|2|| Сумма на отрезке в статическом массиве: префиксные суммы.
+
|2|| Определение Z-функции. Линейный алгоритм нахождения. Применение для поиска подстроки в строке.
  
 
|-
 
|-
  
−
|3|| Проверка вхождения числа в отсортированный массив: бинарный поиск.
+
|3|| Алгоритм Манакера. Поиск максимальной подстроки-палиндрома.
  
 
|-
 
|-
  
−
|4|| Структура данных стек: реализация на указателях, использование std::stack.
+
|4|| Алгоритм Галила-Сейфераса поиска подстроки в строки за O(n) времени и O(1) дополнительной памяти.
  
 
|-
 
|-
  
−
|5|| Поиск ближайшего меньшего/большего слева/справа в статическом массиве.
+
|5|| Структура данных бор. Построение бора, оценка времени и объема памяти. Разные способы хранения детей дерева. Оценка объема памяти для каждого варианта. Понятие суффиксной ссылки. Пример дерева с суффиксными ссылками.
  
 
|-
 
|-
  
−
|6|| Поддержка минимума в стеке.
+
|6|| Алгоритм построения бора вместе с суффиксными ссылками. Оценка времени работы. Алгоритм Ахо-Корасик. “Сжатые” суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей. Оценка времени работы при использовании “сжатых” суффиксных ссылок.
  
 
|-
 
|-
  
−
|7|| Реализация очереди на двух стеках.
+
|7|| Дерево палиндромов. Линейный алгоритм построения дерева палиндромов.
  
 
|-
 
|-
  
−
|8|| Поддержка минимума в очереди.
+
|8|| Определение суффиксного массива. Построение за O(N log N) с использованием цифровой сортировки для пар. Оптимизация “одна сортировка подсчетом вместо двух”.
  
 
|-
 
|-
  
−
|9|| Проверка правильности скобочной последовательности с несколькими типами скобок.
+
|9|| Алгоритм Арикавы-Аримуры-Касаи-Ли-Парка.
  
 
|-
 
|-
  
−
|10|| Доказательство формулы: log(n!) = Θ(n log n).
+
|10|| Суффиксное дерево. Сжатое суффиксное дерево. Доказательство линейности числа вершин и ребер в сжатом суффиксном дереве.
  
 
|-
 
|-
  
−
|11|| Нижняя оценка на число сравнений в сортировке сравнениями.
+
|11|| Построение суффиксного дерева. Алгоритм Укконена.
  
 
|-
 
|-
  
−
|12|| Сортировка слиянием (Merge Sort).
+
|12|| Суффиксный автомат. Правые контексты, их свойства. Классы эквивалентности подстрок; критерий максимальности подстроки в своем классе эквивалентности. Линейность числа вершин и ребер, достижимость оценок.
  
 
|-
 
|-
  
−
|13|| Поиск числа инверсий в массиве.
+
|13|| Суффиксный автомат. Линейный алгоритм построения.
 +
|}
  
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Часть 2. Геометрия
 
|-
 
|-
  
−
|14|| Нерекурсивная реализация сортировки слиянием.
+
|1|| Прямые, отрезки, плоскости. Скалярное произведение, векторное произведение, их свойства.  Угол между векторами, функция atan2. Коллинеарность прямых. Проверка принадлежности точки прямой, отрезку.
  
 
|-
 
|-
  
−
|15|| Быстрая сортировка (Quick Sort). Асимптотика — б/д.
+
|2|| Поиск пересечения прямых - два способа: система уравнений и векторное произведение. Поиск пересечения окружности и прямой: два способа. Проверка наличия пересечения отрезков без вычисления точки пересечения прямых.
  
 
|-
 
|-
  
−
|16|| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — б/д.
+
|3|| Поиск ориентированной площади многоугольника: метод “векторных произведений” и “метод трапеций”.. Знак площади и проверка того факта, что вершины многоугольника заданы в порядке обхода против часовой стрелки. Поиск площади пересечения многоугольника и круга как модификация метода “векторных произведений”.
−
|-
 
−
 
 
−
 
 
−
|-
 
−
 
 
−
|17|| Детерминированный алгоритм поиска k-й порядковой статистики за O(n), где n — длина массива.
 
−
 
 
−
|-
 
−
 
 
−
|18|| Детерминированный алгоритм быстрой сортировки за O(n log n), где n — длина массива.
 
−
 
 
−
|-
 
−
 
 
−
|19|| Стабильная сортировка подсчётом. Сортировка пар чисел.
 
−
 
 
−
|-
 
−
 
 
−
|20|| Цифровая сортировка (LSD).
 
−
 
 
−
|-
 
−
 
 
−
|21|| Двоичная куча: определение и представление в массиве. Требование кучи.
 
−
 
 
−
|-
 
−
 
 
−
|22|| Операции siftUp и siftDown с доказательством корректности.
 
−
 
 
−
|-
 
−
 
 
−
|23|| Выражение insert, getMin, extractMin и decreaseKey через siftUp и siftDown.
 
−
 
 
−
|-
 
−
 
 
−
|24|| Построение кучи (heapify) за линейное время (сходимостью ряда можно пользоваться б/д).
 
−
 
 
−
|-
 
−
 
 
−
|25|| Сортировка кучей с привлечением O(1) дополнительной памяти (Heap Sort). Несуществование кучи (основанной на сравнениях), обрабатывающей insert и extractMin за O(1).
 
−
 
 
−
|-
 
−
 
 
−
|26|| Технические сложности и их преодоление для операции decreaseKey в куче.
 
−
 
 
−
|-
 
−
 
 
−
|27|| Удаление из кучи по значению.
 
−
 
 
−
|-
 
−
 
 
−
|28|| Удаление из кучи по указателю.
 
−
 
 
−
|-
 
−
 
 
−
|29|| Биномиальное дерево, биномиальная куча: определение.
 
−
 
 
−
|-
 
−
 
 
−
|30|| Операции merge, insert, getMin, extractMin и decreaseKey в биномиальной куче.
 
−
 
 
−
|-
 
−
 
 
−
|31|| Амортизационный анализ, учётное время работы: определение.
 
−
 
 
−
|-
 
−
 
 
−
|32|| Метод монеток (бухгалтерский учёт).
 
−
 
 
−
|-
 
−
 
 
−
|33|| Структура данных вектор, реализация на массиве и оценка асимптотики методом монеток.
 
−
 
 
−
|-
 
−
 
 
−
|34|| Метод потенциалов.
 
−
 
 
−
|-
 
−
 
 
−
|35|| Вставка в биномиальной куче в отсутствие других операций, применение метода потенциалов.
 
−
 
 
−
|-
 
−
 
 
−
|36|| Sparse Table: модельная задача, построение за O(n log n), ответ на запрос за O(1).
 
−
 
 
−
|-
 
−
 
 
−
|37|| Дерево отрезков: модельная задача. Обработка запросов с доказательством времени работы.
 
−
 
 
−
|-
 
−
 
 
−
|38|| Дерево отрезков: двоичный спуск, поиск k-го нуля на отрезке массива за O(log n).
 
−
 
 
−
|-
 
−
 
 
−
|39|| Дерево отрезков, отложенные операции: присвоение константы на отрезке, операция push.
 
−
 
 
−
|-
 
−
 
 
−
|40|| Количество чисел на отрезке, значения которых лежат в отрезке: Fractional Cascading.
 
−
 
 
−
|-
 
−
 
 
−
|41|| Персистентный массив.
 
−
 
 
−
|-
 
−
 
 
−
|42|| Персистентное дерево отрезков.
 
−
 
 
−
|-
 
−
 
 
−
|43|| Количество чисел на отрезке, значения которых лежат в отрезке: решение с персистентным деревом отрезков.
 
−
 
 
−
|-
 
−
 
 
−
|44|| Динамическое дерево отрезков.
 
−
 
 
−
|-
 
−
 
 
−
|45|| Онлайн vs. оффлайн: сжатие координат.
 
−
 
 
−
|-
 
−
 
 
−
|46|| Онлайн vs. оффлайн: дерево поиска оффлайн.
 
−
 
 
−
|-
 
−
 
 
−
|47|| Онлайн vs. оффлайн: количество чисел на отрезке, значения которых лежат в отрезке.
 
−
 
 
−
|-
 
−
 
 
−
|48|| Дерево Фенвика: классическая задача, операции update и getSum.
 
−
 
 
−
|-
 
−
 
 
−
|49|| Обобщение дерева Фенвика на б´oльшие размерности. Изменение асимптотики.
 
−
 
 
−
|-
 
−
 
 
−
|50|| Обратное дерево Фенвика: максимум на отрезке и изменение (увеличение) в точке (update — без реализации).
 
−
 
 
−
|-
 
−
 
 
−
|51|| Дерево Фенвика деревьев Фенвика.
 
  
 
|-
 
|-
  
−
|52|| Дерево поиска: определения и операции (без реализации) find, insert, erase, а также опциональные merge и split.
+
|4|| Проверка принадлежности точки многоугольнику. Проблема вершины на луче. Три способа решения проблемы: случайный луч, вычисление “хорошего” луча, решение с горизонтальным лучом. Проверка принадлежности точки выпуклому многоугольнику за O(log n). Поиск правой касательной из точки к выпуклому многоугольнику за O(log n).
  
 
|-
 
|-
  
−
|53|| Наивное дерево поиска, обработка операций.
+
|5|| Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика, Чена.
  
 
|-
 
|-
  
−
|54|| AVL-дерево: определение.
+
|6|| Convex Hull Trick: версия с добавлением в структуру точек и поиском точки с минимальной проекцией на заданное направление.
  
 
|-
 
|-
  
−
|55|| Оценка глубины AVL-дерева на n вершинах.
+
|7|| Convex Hull Trick: версия с добавлением в структуру прямых и поиском прямой с минимальным y при заданном х. Дерево Ли-Чао.
  
 
|-
 
|-
  
−
|56|| Устранение дисбаланса в AVL-дереве для случая ∆(a) = −2.
+
|8|| Выпуклая оболочка 3D. Построение за O(n4), за O(n2).
  
 
|-
 
|-
  
−
|57|| AVL-дерево: реализация операций insert и erase.
+
|9|| Тернарный поиск. Выпуклые функции и их свойства, необходимые для корректного применения тернарного поиска. Вложенный тернарный поиск. Примеры: задача о фотографии, задача о максимальной вложенной в выпуклый многоугольник окружности..
  
 
|-
 
|-
  
−
|58|| Splay-дерево: определение и практическая значимость.
+
|10|| Поиск пары ближайших точек на плоскости. Алгоритм Препараты. O(n log n). Поиск треугольника с минимальным периметром за O(n log n).
  
 
|-
 
|-
  
−
|59|| Splay-дерево: операции zig, zig-zig и zig-zag, операция splay.
+
|11|| Поиск диаметра множества на плоскости за O(n log n). Поиск накрывающего прямоугольника минимального периметра за O(n log n). Поиск накрывающего прямоугольника минимальной площади за O(n log n).
  
 
|-
 
|-
  
−
|60|| Амортизированное время работы операции splay с помощью метода потенциалов.
+
|12|| Поиск граней связного плоского графа за O(n log n).
  
 
|-
 
|-
  
−
|61|| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
+
|13|| Нахождение суммы Минковского двух выпуклых многоугольников за O(m + n).Проверка наличия пересечения двух выпуклых многоугольников и поиск расстояния между ними за O(m + n). Задача о роботе и препятствиях (“задача про коридор и столы”; требуемое время O(n2*B), где n - число препятствий; робот и препятствия - выпуклые многоугольники с не более чем В вершинами)
  
 
|-
 
|-
  
−
|62|| B-дерево: определение и практическая значимость.
+
|14|| Сканирующая прямая. Поиск наибольшего креста. Проверка факта пересечения отрезков. Площадь объединения прямоугольников за O(n log n).
  
 
|-
 
|-
  
−
|63|| Оценка глубины B-дерева на n ключах при фиксированном параметре t.
+
|15|| Пересечение полуплоскостей: O(n3), O(n2), O(n log n).
  
 
|-
 
|-
  
−
|64|| Реализация операции insert в B-дереве.
+
|16|| Статическая задача поиска точек в подпрямоугольнике. Решения за (O(n^5), O(log n)), (O(n^3), O(log n)), (O(n^2), O(log n)). Fractional Cascading. Времена построения и вычисления ответа на запрос.
  
 
|-
 
|-
  
−
|65|| Реализация операции erase в B-дереве.
+
|17|| KD-дерево. Времена построения и вычисления ответа на запрос. Поиск ближайших точек множества с помощью KD-дерева, “контрпример”.
  
 
|-
 
|-
  
−
|66|| Декартово дерево: определение и теорема о глубине (б/д).
+
|18|| Диаграмма Вороного. Базовые свойства: структура ячеек, связность, оценки на количества ребер и вершин. Критерий совпадения точки с вершиной ДВ, попадания на внутреннюю часть ребра.
  
 
|-
 
|-
  
−
|67|| Реализация операций merge и split в декартовом дереве.
+
|19|| Построение диаграммы Вороного: O(n3), O(n2 log n), O(n2). Алгоритм Форчуна за O(n log n).
  
 
|-
 
|-
  
−
|68|| Выражение insert и erase в декартовом дереве через merge и split.
+
|20|| Триангуляция Делоне. Определение триангуляции. Теорема Фалеса. Флипы. Неправильное ребро, критерий неправильности.
  
 
|-
 
|-
  
−
|69|| Декартово дерево по неявному ключу: в массиве вставить, удалить элемент, узнать сумму на отрезке.
+
|21|| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
 +
|}
  
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Часть 3. Вероятностные алгоритмы и Ко
 
|-
 
|-
  
−
|70|| Красно-чёрное дерево: определение.
+
|1|| QSort, OrderStatistics: время работы в среднем и худшем случаях. Вероятностное определение цены игры на дереве. Алгоритм RandomGameTreeEval, его среднее время работы.
  
 
|-
 
|-
  
−
|71|| Оценка глубины красно-чёрного дерева на n ключах.
+
|2|| Задача о минимальном разрезе, алгоритм Каргера.
  
 
|-
 
|-
  
−
|72|| Реализация операции insert в красно-чёрном дереве.
+
|3|| Задача о минимальном разрезе, алгоритм Каргера-Штайна.
  
 
|-
 
|-
  
−
|73|| Реализация операции erase в красно-чёрном дереве.
+
|4|| Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в среднем случае. Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в худшем случае.
  
 
|-
 
|-
  
−
|74|| Сравнительный анализ различных реализаций дерева поиска: наивное, AVL-, splay-, B-, декартово и красно-чёрное дерево.
+
|5|| Задачи APD и APSP. APD для невзвешенных неориентированных графов, алгоритм APD-MM. Свидетели булевого перемножения матриц, алгоритм BPWM. Решение задачи APSP при помощи BPWM.
 
|}
 
|}
  

Текущая версия на 17:47, 4 декабря 2022

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

  • Семестр: 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 балл

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

  • Преподаватели:
    • Рухович Филипп
    • Белый Антон
Источник — «http://wiki.atp-fivt.org/index.php?title=Алгоритмы_и_структуры_данных_(продвинутый_поток)&oldid=1501»