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