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

О курсе

Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем. В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии.

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

• классические линейные алгоритмы,
• принцип бинарного поиска,
• основные алгоритмы сортировки.

Далее курс переходит к систематическому изучению структур данных, включая:

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

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

Пререквизиты:

Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов. От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса.

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

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

Семинаристы:

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

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

Формы контроля: Дифференцированный зачет и экзамен

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

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

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

Чат курса (Telegram)

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

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

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

За курс предусмотрены две независимые оценки: за зачёт и за экзамен.

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему все задачи. Решить всё возможно: в семестре будет много бонусных задач, которые идут в зачёт Ожидаемый максимальный балл ~150.

Если в течение семестра студент не набирает баллов на уд 3, он получает пересдачу. На пересдачу можно сдавать те же самые практические (в первую очередь задачи без код-ревью) и теоретические задачи. Начать дорешивать можно сразу после зачётной недели и вплоть до пересдачи в начале следующего семестра.

Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.

В течение семестра планируются 5–6 домашних заданий. Выдаются примерно каждые три недели сроком на три недели.

1. введение, бинарный поиск;
2. сортировки;
3. кучи, линейные контейнеры;
4. дерево отрезков, дерево Фенвика;
5. деревья поиска;
6. хеш-таблицы.

В каждой теме планируется большой контест и небольшое теоретическое задание.

1. Теоретические задания Теоретические домашние задания сдаются устно семинаристу.

Формат предполагает:

• объяснение решения,
• ответы на уточняющие вопросы,
• демонстрацию понимания используемых идей и методов.

2. Практические задания Практические задачи делятся на два типа:

Задачи с код-ревью

Чтобы задача считалась решённой:

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

Дополнительные правила:

• число итераций ревью не ограничено;
• при этом ассистент может отказать в дальнейшем ревью, если считает, что было сделано чрезмерное количество некачественных попыток.

Задачи без код-ревью

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

Устная защита решений

Для части задач из контестов предусмотрена устная защита. Цель защиты:

• подтвердить самостоятельность решения,
• проверить понимание алгоритма и структуры кода.

Такая система позволяет оценить:

• теоретическую подготовку,
• практические навыки программирования,
• глубину понимания алгоритмов.

Бонусы

Семинарист может ставить небольшие бонусы за активность на семинарах. Уточняйте правила их выставления у семинаристов. Если понимаете, что в какой-то задаче очень слабые тесты (заходят решения, которые не должны), можете подготовить более сильные тесты. Их добавят в систему, а вам дадут бонусные баллы.

Штрафы

Ближе к концу семестра будет проведена проверка на списывание (антиплагиат). Пойманные на списывании получат штраф к баллам за семестр, включая автоматический «неуд». Списыванием может быть рассчитано и независимое использование одного и того же открытого кода. Поэтому пишите полностью свой код, не прибегая к помощи готовых библиотек. Исключение — код, приводимый на лекциях и семинарах.

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

Более подробно и во избежание спорных ситуаций в конце семестра читайте о правилах курса здесь

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

лекции потока 2024 года

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

Литература:

1. Абрамов С. А. Лекции о сложности алгоритмов. МЦНМО, 2020.
2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. «Мир», 1980.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979.
4. Кнут Д. Э. Искусство программирования, Т. 1. «ИД Вильямс», 2018.
5. Кнут Д. Э. Искусство программирования, Т. 3. «ИД Вильямс», 2018.
6. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР, 1962, 145(2).
7. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4).
8. Кормен Т. и др. Алгоритмы. Построение и анализ. «ИД Вильямс», 2011.