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

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

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

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

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

{|  class="wikitable"
|- 
! №
! Тема
|-

|1|| Полиномиальное хеширование.

|-

|2|| Алгоритм Рабина—Карпа.

|-

|3|| Префикс-функция: определение, алгоритм нахождения за O(I s I) и применение для нахождения вхождений шаблона в текст.

|-

|4|| Зет-функция: определение, алгоритм нахождения за O(I s I) и применение для нахождения вхождений шаблона в текст.

|-

|5|| Бор, построение бора по набору слов.

|-

|6|| Способы хранения бора: преимущества и недостатки.

|-

|7|| Хранение множества слов/чисел с помощью бора. Добавление и проверка наличия. Опционально: удаление.

|-

|8|| Алгоритм Ахо—Корасик: определение суффиксных ссылок (link) и переходов по буквам (to).

|-

|9|| Алгоритм Ахо—Корасик: реализация, корректность, асимптотика.

|-

|10|| Подсчёт числа вхождений словарных слов в текст с помощью алгоритма Ахо—Корасик.

|-

|11|| Определение суффиксного массива и массива lcp.

|-

|12|| Алгоритм построения суффиксного массива строки длины n за O(n log n).

|-

|13|| Алгоритм Касаи нахождения массива lcp по построенному суффиксному массиву длины n за O(n).

|-

|14|| Проверка равенства подстрок в строке: ответ на запрос за O(1) с помощью sparse table и суффиксного массива.

|-

|15|| Суффиксное дерево: определение, представление в памяти, наивный алгоритм построения.

|-

|16|| Суффиксная ссылка в суффиксном дереве. Суффиксная ссылка вершины. Процедура getLink.

|-

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

|-

|18|| Детерминированный конечный автомат. Принимаемые слова, распознаваемый язык. Суффиксный автомат строки s: определение.

|-

|19|| Правый контекст слова относительно языка. Эквивалентность слов.

|-

|20|| Утверждение об устройстве классов эквивалентности (относительно языка, состоящего из всех суффиксов s).

|-

|21|| Суффиксный автомат: обозначения [x], longest(C), len(C), link(C). Формула для ICI. 22. [1] Критерий того, что u = longest([u]).

|-

|23|| Суффиксный автомат: устройство рёбер, ведущих в вершину v.

|-

|24|| Алгоритм построения суффиксного автомата: характеристика новых классов при дописывании символа c; изменение множества рёбер при дописывании символа c в трёх случаях; проставление len и link у всех вершин.

|-

|25|| Алгоритм построения суффиксного автомата: реализация.

|-

|26|| Алгоритм построения суффиксного автомата: асимптотика.

|-

|27|| Алгоритм Евклида: корректность, реализация, асимптотика.

|-

|28|| Расширенный алгоритм Евклида (нахождение решения ax + by = (a, b) в целых x, y).

|-

|29|| Решето Эратосфена: нахождение всех простых среди {1, 2, . . . , n} за O(n log log n).

|-

|30|| Улучшенное решето Эратосфена: нахождение минимального простого делителя для всех чисел из {1, 2, . . . , n}. Нахождение всех простых из этого же множества.

|-

|31|| Обратное к a по модулю m: достаточное условие существования, алгоритм нахождения.

|-

|32|| Криптографический протокол Диффи—Хеллмана генерации общего секретного ключа. Неформальное доказательство надёжности протокола.

|-

|33|| Криптографический протокол RSA одностороннего общения. Неформальное доказательство надёжности протокола.

|-

|34|| Алгоритм Штрассена: постановка задачи, идея решения, асимптотика.

|-

|35|| Перемножение двух многочленов за O(n log n) с использованием быстрого преобразования Фурье как чёрного ящика.

|-

|36|| Быстрое преобразование Фурье: рекурсивный алгоритм.

|-

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

|-

|38|| Быстрое преобразование Фурье: избавление от рекурсии.

|-

|39|| Примитив точки, вектора, прямой. Построение прямой по двум точкам.

|-

|40|| Расстояние от точки до прямой, проекция. Пересечение двух прямых.

|-

|41|| Примитив окружности. Пересечение прямой и окружности. Пересечение двух окружностей.    

|-

|42|| Ушная триангуляция многоугольника: лемма о двух ушах.

|-

|43|| Алгоритм триангуляции многоугольника за O(n 2 ), где n — число вершин.

|-

|44|| Выпуклая оболочка конечного множества точек: определение и доказательство того, что выпуклая оболочка — многоугольник.

|-

|45|| Построение выпуклой оболочки заворачиванием подарка за O(nh).

|-

|46|| Построение выпуклой оболочки сортировкой точек по координатам за O(n log n).

|-

|47|| Построение выпуклой оболочки сортировкой точек по полярному углу за O(n log n).

|-

|48|| Максимум скалярного произведения с фиксированным вектором, нахождение за O(log n).

|-

|49|| Динамическая выпуклая оболочка: вставка точек за O∗ (log n).

|-

|50|| Диаметр конечного множества точек за O(n log n).

|-

|51|| Сумма Минковского: определение и доказательство того, что сумма Минковского двух выпуклых многоугольников — выпуклый многоугольник.

|-

|52|| Нахождение суммы Минковского двух выпуклых многоугольников за линейное время.

|-

|53|| Проверка принадлежности точки многоугольнику: решение с помощью суммы ориентированных углов.

|-

|54|| Проверка принадлежности точки многоугольнику: решение с горизонтальным лучом. Модификации: случайный луч, луч, заведомо не содержащий вершин многоугольника.

|-

|55|| Пересечение полуплоскостей: алгоритм за O(n 2 ).

|-

|56|| Пересечение полуплоскостей: алгоритм за O(n log n).

|-

|57|| Post office problem: постановка. Определение диаграммы Вороного. Алгоритм построения за O(n 2 log n). Вид каждой ячейки диаграммы.

|-

|58|| Связность диаграммы Вороного. Число вершин и рёбер в диаграмме.

|-

|59|| Критерий того, что точка является вершиной диаграммы Вороного. Критерий того, что серединный перпендикуляр к pipj участвует в диаграмме Вороного.

|-

|60|| Описание алгоритма Форчуна, два типа событий. Асимптотика.

|-

|61|| Определение триангуляции. Мотивировка: моделирование ландшафта. Число треугольников и рёбер в триангуляции.

|-

|62|| Определение графа Делоне, его свойство. Критерий того, что три сайта являются вершинами одной грани графа Делоне (б/д). Критерий того, что два сайта соединены ребром в графе Делоне (б/д). Определение триангуляции Делоне.

|-

|63|| Флип ребра. Нелегальное ребро, критерий легальности (б/д). Проверка легальности в терминах определителя (б/д).

|-

|64|| Легальная триангуляция, легализация триангуляции. Критерии триангуляции Делоне (б/д). Максимизация минимального угла в триангуляции Делоне.

|-

|65|| Рандомизированный алгоритм построения триангуляции Делоне: описание, асимптотика (б/д).

|-

|66|| Триангуляция Делоне: процедура legalizeEdge, реализация.

|-

|67|| Триангуляция Делоне: решение задачи локализации.

|-

|68|| Триангуляция Делоне: обработка точек p−2, p−1 (б/д).

|}

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

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

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

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

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

== Команда курса ==
* Преподаватели:
** Степанов Илья