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