Алгоритмы и структуры данных III. Основной поток 2026

О курсе

На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

В течение семестра студенты научатся эффективно искать вхождения слов в тексты, а также строить сложные суффиксные структуры для обработки различных запросов и изменений над большими текстами. Кульминацией этой части курса станет построение суффиксного автомата для строки, наиболее мощной структуры данных для представления текстовой информации (например, в биоинформатике).

В теоретико-числовом блоке будет рассмотрено несколько классических алгоритмов (извлечение корня, дискретное логарифмирование) в конечных полях, а также алгоритм факторизации. Здесь также даётся материал по быстрому преобразованию Фурье, которое предлагает изящный способ перемножать длинные числа и работать с многочленами и функциональными рядами.

В разделе о геометрии будут разобраны классические простые алгоритмы наподобие выпуклой оболочки и суммы Минковского. Все вопросы здесь критически важны для реализации собственных геометрических и физических движков (при разработке игр или моделировании систем). Из продвинутых алгоритмов разбираются техники пересечения полуплоскостей, построения диаграммы Вороного, триангуляции Делоне и выпуклой оболочки точек в трёхмерном пространстве.

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

Лектор: Степанов Илья Данилович

Семинаристы: Сбродов Егор Алексеевич

Вашкевич Егор Сергеевич

Степанов Илья Данилович

Программа курса

В семестре 15 лекций и 30 семинаров (практических занятий).

Формы контроля: экзамен

Неделя	Лекции!
1	Хеширование и поиск образца в строке
2	Префикс-функция, Z-функция и палиндромы
3	Боры и алгоритм Ахо — Корасик
4	Суффиксный массив и массив LCP
5	Дерево палиндромов
6	Конечные автоматы и суффиксный автомат
7	Суффиксное дерево и связь суффиксных структур
8	Быстрое преобразование Фурье
9	Алгоритмы над многочленами и линейные рекурренты
10	Теория чисел и алгоритмы над конечными полями
11	Вычислительная геометрия: базовые примитивы
12	Триангуляция многоугольников и выпуклая оболочка
13	Алгоритмы на выпуклых многоугольниках
14	Принадлежность точки многоугольнику и пересечение полуплоскостей
15	Диаграммы Вороного и триангуляция Делоне

Коммуникация

За каждой группой закреплён семинарист и ассистент, к которым можно обращаться за помощью.

Прогресс студентов

Таблица с оценками доступна студентам в канале дисциплины

Критерии оценивания и формы контроля успеваемости

За курс предусмотрены две оценки: за зачёт и за экзамен. Оценки независимы и никак не влияют друг на друга. Оценка за зачёт ставится за работу в семестре: за сдачу теоретических и практических домашних задач, а также за активность на семинарах и помощь в развитии курса (исправление опечаток в условиях, подготовка более сильных тестов к задачам, разработка собственных задач и пр.). Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.

В течение семестра планируются 5 домашних заданий, разбитых по темам:

1. базовые строковые алгоритмы [7–28 сентября];
2. суффиксные строковые структуры [28 сентября – 24 октября];
3. алгоритмы в теории чисел [21 октября – 15 ноября];
4. базовые алгоритмы в геометрии [1 ноября – 21 ноября];
5. продвинутые алгоритмы в геометрии [28 ноября – 15 декабря].

В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума.

Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи.

Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).

Правила курса

Подробнее о правилах курса здесь

Материалы курса

лекции потока осень 2024

Примерная программа экзамена

Литература:

1. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 2014
2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов – «Мир», 1979
3. Препарата Ф., Шеймос М. Вычислительная геометрия: введение – «Мир», 1989
4. Gusfield D. Algorithms on Strings, Trees, and Sequences – Cambridge University Press, 1997
5. De Berg M. et al. Computational Geometry. Algorithms and Applications – Springer, 2008