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

Spirina.es: /* Программа курса */

2026-08-13T11:51:07Z

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

← Предыдущая версия		Версия от 11:51, 13 августа 2026
Строка 25:		Строка 25:
	! Неделя		! Неделя
	! Лекция/Семинар		! Лекция/Семинар
	\|		\|-
	\|1		\|1
	\|Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай.<br>Дерево Фенвика. Обобщение на многомерный случай.		\|Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай.<br>Дерево Фенвика. Обобщение на многомерный случай.
Строка 47:		Строка 47:
	\|Сведение задачи LCA к задаче RMQ и наоборот. Алгоритм Фарах-Колтон-Бендера.		\|Сведение задачи LCA к задаче RMQ и наоборот. Алгоритм Фарах-Колтон-Бендера.
	\|-		\|-
	\|8 \| Поиск подстроки в строке. Префикс-функция. Z-функция. Алгоритм Кнута-Морриса-Пратта.		\|8
			\|Поиск подстроки в строке. Префикс-функция. Z-функция. Алгоритм Кнута-Морриса-Пратта.
	\|-		\|-
	\|9		\|9

Spirina.es: /* Программа курса */

2026-08-13T11:50:18Z

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

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

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

Spirina.es: /* Программа курса */

2026-08-13T11:48:32Z

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

Spirina.es в 11:44, 13 августа 2026

2026-08-13T11:44:06Z

← Предыдущая версия		Версия от 11:44, 13 августа 2026
Строка 71:		Строка 71:
	\| Полиномиальный хэш. Алгоритм Рабина-Карпа.		\| Полиномиальный хэш. Алгоритм Рабина-Карпа.
	\| }		\| }


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

Spirina.es: /* Программа курса */

2026-08-13T11:43:53Z

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

← Предыдущая версия		Версия от 11:43, 13 августа 2026
Строка 23:		Строка 23:

	{\| class="wikitable"		{\| class="wikitable"
	! Неделя		! Неделя
	! ~~Тема~~		! Лекция
			! Семинар
			\|
	\| 1		\| 1
	\| Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай.<br>Дерево Фенвика. Обобщение на многомерный случай.		\| Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай.<br>Дерево Фенвика. Обобщение на многомерный случай.

Spirina.es: /* Программа курса */

2026-08-13T11:42:56Z

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

← Предыдущая версия		Версия от 11:42, 13 августа 2026
Строка 64:		Строка 64:
	\| -		\| -
	\| 14		\| 14
	\| Эвристические алгоритмы поиска подстрок. Алгоритм Бойера-Мура. \|		\| Эвристические алгоритмы поиска подстрок. Алгоритм Бойера-Мура.
	\| - \|		\| -
	\| 15		\| 15
	\| Полиномиальный хэш. Алгоритм Рабина-Карпа. \|		\| Полиномиальный хэш. Алгоритм Рабина-Карпа.
	\| } \|		\| }

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

Spirina.es: /* Программа курса */

2026-08-13T11:40:59Z

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

← Предыдущая версия		Версия от 11:40, 13 августа 2026
Строка 23:		Строка 23:

	{\| class="wikitable"		{\| class="wikitable"
	! Неделя !! Тема		! Неделя
			! Тема
	\| 1		\| 1
	\| Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай.<br>Дерево Фенвика. Обобщение на многомерный случай.		\| Sparse Table. Построение за O(nn), запрос за O(1). Обобщение на многомерный случай.<br>Дерево Фенвика. Обобщение на многомерный случай.

Spirina.es: /* Программа курса */

2026-08-13T11:40:24Z

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

← Предыдущая версия		Версия от 11:40, 13 августа 2026
Строка 23:		Строка 23:

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

Spirina.es: /* Команда курса */

2026-08-13T11:39:12Z

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

← Предыдущая версия		Версия от 11:39, 13 августа 2026
Строка 14:		Строка 14:

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

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

Spirina.es: /* Команда курса */

2026-08-13T11:38:38Z

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

← Предыдущая версия		Версия от 11:38, 13 августа 2026
Строка 10:		Строка 10:

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

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

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

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


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