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

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Важные ссылки)
(План курса)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 4: Строка 4:
  
 
== Важные ссылки ==
 
== Важные ссылки ==
* '''[Регистрация на курс]''' (доступ для физтех-аккаунтов)
+
* '''Регистрация на курс''' (доступ для физтех-аккаунтов)
* '''[Материалы курсa]''' (доступ для физтех-аккаунтов)
+
* '''Материалы курсa''' (доступ для физтех-аккаунтов)
* '''[Чат курса]'''
+
* '''Чат курса'''
 
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''
 
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''
  
Строка 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 — длина массива.
+
|4|| Проверка принадлежности точки многоугольнику. Проблема вершины на луче. Три способа решения проблемы: случайный луч, вычисление “хорошего” луча, решение с горизонтальным лучом. Проверка принадлежности точки выпуклому многоугольнику за O(log n). Поиск правой касательной из точки к выпуклому многоугольнику за O(log n).
  
 
|-
 
|-
  
|18|| Детерминированный алгоритм быстрой сортировки за O(n log n), где n — длина массива.
+
|5|| Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика, Чена.
  
 
|-
 
|-
  
|19|| Стабильная сортировка подсчётом. Сортировка пар чисел.
+
|6|| Convex Hull Trick: версия с добавлением в структуру точек и поиском точки с минимальной проекцией на заданное направление.
  
 
|-
 
|-
  
|20|| Цифровая сортировка (LSD).
+
|7|| Convex Hull Trick: версия с добавлением в структуру прямых и поиском прямой с минимальным y при заданном х. Дерево Ли-Чао.
  
 
|-
 
|-
  
|21|| Двоичная куча: определение и представление в массиве. Требование кучи.
+
|8|| Выпуклая оболочка 3D. Построение за O(n4), за O(n2).
  
 
|-
 
|-
  
|22|| Операции siftUp и siftDown с доказательством корректности.
+
|9|| Тернарный поиск. Выпуклые функции и их свойства, необходимые для корректного применения тернарного поиска. Вложенный тернарный поиск. Примеры: задача о фотографии, задача о максимальной вложенной в выпуклый многоугольник окружности..
  
 
|-
 
|-
  
|23|| Выражение insert, getMin, extractMin и decreaseKey через siftUp и siftDown.
+
|10|| Поиск пары ближайших точек на плоскости. Алгоритм Препараты. O(n log n). Поиск треугольника с минимальным периметром за O(n log n).
  
 
|-
 
|-
  
|24|| Построение кучи (heapify) за линейное время (сходимостью ряда можно пользоваться б/д).
+
|11|| Поиск диаметра множества на плоскости за O(n log n). Поиск накрывающего прямоугольника минимального периметра за O(n log n). Поиск накрывающего прямоугольника минимальной площади за O(n log n).
  
 
|-
 
|-
  
|25|| Сортировка кучей с привлечением O(1) дополнительной памяти (Heap Sort). Несуществование кучи (основанной на сравнениях), обрабатывающей insert и extractMin за O(1).
+
|12|| Поиск граней связного плоского графа за O(n log n).
  
 
|-
 
|-
  
|26|| Технические сложности и их преодоление для операции decreaseKey в куче.
+
|13|| Нахождение суммы Минковского двух выпуклых многоугольников за O(m + n).Проверка наличия пересечения двух выпуклых многоугольников и поиск расстояния между ними за O(m + n). Задача о роботе и препятствиях (“задача про коридор и столы”; требуемое время O(n2*B), где n - число препятствий; робот и препятствия - выпуклые многоугольники с не более чем В вершинами)
  
 
|-
 
|-
  
|27|| Удаление из кучи по значению.
+
|14|| Сканирующая прямая. Поиск наибольшего креста. Проверка факта пересечения отрезков. Площадь объединения прямоугольников за O(n log n).
  
 
|-
 
|-
  
|28|| Удаление из кучи по указателю.
+
|15|| Пересечение полуплоскостей: O(n3), O(n2), O(n log n).
  
 
|-
 
|-
  
|29|| Биномиальное дерево, биномиальная куча: определение.
+
|16|| Статическая задача поиска точек в подпрямоугольнике. Решения за (O(n^5), O(log n)), (O(n^3), O(log n)), (O(n^2), O(log n)). Fractional Cascading. Времена построения и вычисления ответа на запрос.
  
 
|-
 
|-
  
|30|| Операции merge, insert, getMin, extractMin и decreaseKey в биномиальной куче.
+
|17|| KD-дерево. Времена построения и вычисления ответа на запрос. Поиск ближайших точек множества с помощью KD-дерева, “контрпример”.
  
 
|-
 
|-
  
|31|| Амортизационный анализ, учётное время работы: определение.
+
|18|| Диаграмма Вороного. Базовые свойства: структура ячеек, связность, оценки на количества ребер и вершин. Критерий совпадения точки с вершиной ДВ, попадания на внутреннюю часть ребра.
  
 
|-
 
|-
  
|32|| Метод монеток (бухгалтерский учёт).
+
|19|| Построение диаграммы Вороного: O(n3), O(n2 log n), O(n2). Алгоритм Форчуна за O(n log n).
  
 
|-
 
|-
  
|33|| Структура данных вектор, реализация на массиве и оценка асимптотики методом монеток.
+
|20|| Триангуляция Делоне. Определение триангуляции. Теорема Фалеса. Флипы. Неправильное ребро, критерий неправильности.
  
 
|-
 
|-
  
|34|| Метод потенциалов.
+
|21|| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
 
+
|}
|-
 
 
 
|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.
 
 
 
|-
 
 
 
|53|| Наивное дерево поиска, обработка операций.
 
 
 
|-
 
 
 
|54|| AVL-дерево: определение.
 
 
 
|-
 
 
 
|55|| Оценка глубины AVL-дерева на n вершинах.
 
 
 
|-
 
 
 
|56|| Устранение дисбаланса в AVL-дереве для случая ∆(a) = −2.
 
 
 
|-
 
 
 
|57|| AVL-дерево: реализация операций insert и erase.
 
 
 
|-
 
 
 
|58|| Splay-дерево: определение и практическая значимость.
 
 
 
|-
 
 
 
|59|| Splay-дерево: операции zig, zig-zig и zig-zag, операция splay.
 
 
 
|-
 
 
 
|60|| Амортизированное время работы операции splay с помощью метода потенциалов.
 
 
 
|-
 
 
 
|61|| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
 
 
 
|-
 
 
 
|62|| B-дерево: определение и практическая значимость.
 
 
 
|-
 
 
 
|63|| Оценка глубины B-дерева на n ключах при фиксированном параметре t.
 
 
 
|-
 
 
 
|64|| Реализация операции insert в B-дереве.
 
 
 
|-
 
 
 
|65|| Реализация операции erase в B-дереве.
 
 
 
|-
 
 
 
|66|| Декартово дерево: определение и теорема о глубине (б/д).
 
 
 
|-
 
 
 
|67|| Реализация операций merge и split в декартовом дереве.
 
 
 
|-
 
 
 
|68|| Выражение insert и erase в декартовом дереве через merge и split.
 
 
 
|-
 
 
 
|69|| Декартово дерево по неявному ключу: в массиве вставить, удалить элемент, узнать сумму на отрезке.
 
  
 +
{|  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 балл

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

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