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

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

== Важные ссылки ==
* '''Регистрация на курс''' (доступ для физтех-аккаунтов)
* '''Материалы курсa''' (доступ для физтех-аккаунтов)
* '''Чат курса'''
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''

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

== План курса ==

{|  class="wikitable"
|- 
! №
! Часть 1. Строки
|-

|1|| Префикс-функция. Линейный алгоритм нахождения. Алгоритм Кнута-Морриса-Пратта.

|-

|2|| Определение Z-функции. Линейный алгоритм нахождения. Применение для поиска подстроки в строке.

|-

|3|| Алгоритм Манакера. Поиск максимальной подстроки-палиндрома.

|-

|4|| Алгоритм Галила-Сейфераса поиска подстроки в строки за O(n) времени и O(1) дополнительной памяти.

|-

|5|| Структура данных бор. Построение бора, оценка времени и объема памяти. Разные способы хранения детей дерева. Оценка объема памяти для каждого варианта. Понятие суффиксной ссылки. Пример дерева с суффиксными ссылками.

|-

|6|| Алгоритм построения бора вместе с суффиксными ссылками. Оценка времени работы. Алгоритм Ахо-Корасик. “Сжатые” суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей. Оценка времени работы при использовании “сжатых” суффиксных ссылок.

|-

|7|| Дерево палиндромов. Линейный алгоритм построения дерева палиндромов.

|-

|8|| Определение суффиксного массива. Построение за O(N log N) с использованием цифровой сортировки для пар. Оптимизация “одна сортировка подсчетом вместо двух”.

|-

|9|| Алгоритм Арикавы-Аримуры-Касаи-Ли-Парка.

|-

|10|| Суффиксное дерево. Сжатое суффиксное дерево. Доказательство линейности числа вершин и ребер в сжатом суффиксном дереве.

|-

|11|| Построение суффиксного дерева. Алгоритм Укконена.

|-

|12|| Суффиксный автомат. Правые контексты, их свойства. Классы эквивалентности подстрок; критерий максимальности подстроки в своем классе эквивалентности. Линейность числа вершин и ребер, достижимость оценок.

|-

|13|| Суффиксный автомат. Линейный алгоритм построения.
|}

{|  class="wikitable"
|- 
! №
! Часть 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|| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
|}

{|  class="wikitable"
|- 
! №
! Часть 3. Вероятностные алгоритмы и Ко
|-

|1|| QSort, OrderStatistics: время работы в среднем и худшем случаях. Вероятностное определение цены игры на дереве. Алгоритм RandomGameTreeEval, его среднее время работы.

|-

|2|| Задача о минимальном разрезе, алгоритм Каргера.

|-

|3|| Задача о минимальном разрезе, алгоритм Каргера-Штайна.

|-

|4|| Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в среднем случае. Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в худшем случае.

|-

|5|| Задачи APD и APSP. APD для невзвешенных неориентированных графов, алгоритм APD-MM. Свидетели булевого перемножения матриц, алгоритм BPWM. Решение задачи APSP при помощи BPWM.
|}

== Оценивание ==
Оценка по курсу состоит из нескольких частей:
# Тесты
# Контесты
# Практические проекты
# Лабораторная работа

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

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

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

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

== Команда курса ==
* Преподаватели:
** Рухович Филипп
** Белый Антон