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

О курсе

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

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

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

Руководитель курса: Ибрагимов Булат Ленарович

Лектор курса:Бердашкевич Роман Евгеньевич

Семинаристы:Вандакуров Артем Сергеевич
Погадаев Никита Максимович

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

Темы лекций и семинаров распределены на 15 учебных недель.

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

Неделя	Лекция	Семинар		1	Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай. Дерево Фенвика. Обобщение на многомерный случай.	-	2	Дерево отрезков. Построение за O(n), реализация запросов “снизу вверх”. Обобщение на многомерный случай. Дерево отрезков. Реализация запросов “сверху вниз”. Обновление на отрезке. Обобщение на многомерный случай.	-	3	Декартово дерево. Операции Merge и Split. Анализ времени работы.	-	4	Задачи RMQ/RSQ для произвольного набора ключей. Решение с помощью бинарных деревьев поиска: запрос, обновление значений на подотрезке ключей, вставка, удаление.	-	5	Порядковые статистики в бинарных деревьях поиска. Деревья поиска по неявному ключу. Решение RMQ/RSQ на массиве с помощью деревьев по неявному ключу.	-	6	Задача LCA. Решение с помощью двоичных подъемов.	-	7	Сведение задачи LCA к задаче RMQ и наоборот. Алгоритм Фарах-Колтон-Бендера.	-	Поиск подстроки в строке. Префикс-функция. Z-функция. Алгоритм Кнута-Морриса-Пратта.	-	9	z--s преобразования.	-	10	Бор. Алгоритм Ахо-Корасик.	-	11	Суффиксный автомат. Построение за O(n). Применения.	-	12	Суффиксное дерево. Построение с помощью суффиксного автомата. Применения.	-	13	Суффиксный массив. Алгоритм Кассаи. Применения. LCP. Применения.	-	14	Эвристические алгоритмы поиска подстрок. Алгоритм Бойера-Мура.	-	15	Полиномиальный хэш. Алгоритм Рабина-Карпа.	} Коммуникация **Чат курса:** ссылка будет добавлена ближе к началу семестра. Прогресс студентов **Таблица с оценками:** ссылка будет добавлена ближе к началу семестра. Критерии оценивания и формы контроля успеваемости Оценка складывается: 70% Домашние задания 30% контрольные работы За работу на семинарах можно получить дополнительный балл к оценке. На курсе 2-3 домашних работы. В каждой домашней работе есть набор обязательных задач необходимых для получения минимальной положительной оценки за курс. Задачи можно сдавать после дедлайна со штрафом 50%. Списывание ограничивает оценку за задание - не более уд(4) вне зависимости от числа самостоятельно решенных задач. Второй факт списывания - неуд за задание (пересдача курса).