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

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

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

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

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

Требования

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

План курса

№	Тема
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 (б/д).

Оценивание

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

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 балл

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

• Преподаватели:
  • Степанов Илья