Алгоритмы и структуры данных III. Основной поток 2026
О курсе
Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем. В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии.
В первом (осеннем) семестре основное внимание будет сосредоточено на разнообразных структурах данных, которые нужны будут в роли «чёрных ящиков» для более продвинутых алгоритмов. Для формирования необходимой базы в начале курса разбираются:
- классические линейные алгоритмы,
- принцип бинарного поиска,
- основные алгоритмы сортировки.
Далее курс переходит к систематическому изучению структур данных, включая:
- линейные структуры,
- кучи (приоритетные очереди),
- деревья отрезков,
- деревья поиска,
- хеш-таблицы,
- а также ряд менее стандартных, но практически значимых подходов к организации данных.
Курс ориентирован как на студентов, изучающих его в рамках обязательной программы, так и на всех, кто заинтересован в углублённом понимании алгоритмов и стремится научиться разрабатывать эффективные и масштабируемые программные решения.
Пререквизиты:
Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов. От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса.
Команда курса
Лектор: Степанов Илья Данилович
Семинаристы: Сбродов Егор Алексеевич
Вашкевич Егор Сергеевич
Степанов Илья Данилович
Программа курса
В семестре 15 лекций и 30 семинаров (практических занятий).
Формы контроля: Дифференцированный зачет и экзамен
| Неделя | Лекции | |
|---|---|---|
| 1 | Хеширование и поиск образца в строке | |
| 2 | Префикс-функция, Z-функция и палиндромы | |
| 3 | Боры и алгоритм Ахо — Корасик | |
| 4 | Суффиксный массив и массив LCP | |
| 5 | Дерево палиндромов | |
| 6 | Конечные автоматы и суффиксный автомат | |
| 7 | Суффиксное дерево и связь суффиксных структур | |
| 8 | Быстрое преобразование Фурье | |
| 9 | Алгоритмы над многочленами и линейные рекурренты | |
| 10 | Теория чисел и алгоритмы над конечными полями | |
| 11 | Вычислительная геометрия: базовые примитивы | |
| 12 | Триангуляция многоугольников и выпуклая оболочка | |
| 13 | Алгоритмы на выпуклых многоугольниках | |
| 14 | Принадлежность точки многоугольнику и пересечение полуплоскостей | |
| 15 | Диаграммы Вороного и триангуляция Делоне |
Коммуникация
За каждой группой закреплён семинарист и ассистент, к которым можно обращаться за помощью.
Прогресс студентов
Таблица с оценками, доступная студентам
Критерии оценивания и формы контроля успеваемости
В конце семестра экзамен.
Правила курса
Более подробно и во избежание спорных ситуаций в конце семестра читайте о правилах курса здесь
Материалы курса
лекции потока 2024 года
Примерная программа экзамена
Литература:
- Абрамов С. А. Лекции о сложности алгоритмов. МЦНМО, 2020.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. «Мир», 1980.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979.
- Кнут Д. Э. Искусство программирования, Т. 1. «ИД Вильямс», 2018.
- Кнут Д. Э. Искусство программирования, Т. 3. «ИД Вильямс», 2018.
- Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР, 1962, 145(2).
- Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4).
- Кормен Т. и др. Алгоритмы. Построение и анализ. «ИД Вильямс», 2011.