Spirina.es в 10:57, 27 августа 2026

2026-08-27T10:57:53Z

← Предыдущая версия		Версия от 10:57, 27 августа 2026
Строка 59:		Строка 59:
	\| '''Продвинутая вычислительная геометрия и оптимизация.''' Поиск граней связного плоского графа. Диаграмма Вороного и её построение. Триангуляция Делоне и её свойства. Выпуклая оболочка в 3D. Convex Hull Trick и дерево Ли–Чао. Тернарный поиск и его применения.		\| '''Продвинутая вычислительная геометрия и оптимизация.''' Поиск граней связного плоского графа. Диаграмма Вороного и её построение. Триангуляция Делоне и её свойства. Выпуклая оболочка в 3D. Convex Hull Trick и дерево Ли–Чао. Тернарный поиск и его применения.
	\|}		\|}


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

			[https://docs.google.com/document/d/1fRoFCTpG1loTtAJMmbG21ky7lal4T-hr/edit?usp=sharing&ouid=111154455295475417649&rtpof=true&sd=true программа экзамена]

Spirina.es: Новая страница: «== О курсе == Программа курса с 2025 года, в течении сентября будут изменения Курс посвящён изучению продвинутых алгоритмов и структур данных для решения сложных задач на графах, строках, геометрии и комбинаторных структурах. Основное внимание уделяется...»

2026-08-27T10:43:27Z

Новая страница: «== О курсе == Программа курса с 2025 года, в течении сентября будут изменения Курс посвящён изучению продвинутых алгоритмов и структур данных для решения сложных задач на графах, строках, геометрии и комбинаторных структурах. Основное внимание уделяется...»

Новая страница

== О курсе ==
Программа курса с 2025 года, в течении сентября будут изменения

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

В курсе рассматриваются алгоритмы максимального потока и минимальной стоимости, задачи о паросочетаниях и разрезах, современные алгоритмы обработки строк, вычислительная геометрия, вероятностные алгоритмы, а также быстрые алгоритмы для графовых задач. Отдельное внимание уделяется построению алгоритмов с оптимальными или близкими к оптимальным оценками времени работы.

== Программа курса ==
'''форма контроля:''' экзамен

{| class="wikitable"
! №
! Тема
|-
| 1
| '''Потоки в сетях.''' Определение сети и потока. Величина потока и разрезы. Остаточная сеть и дополняющие пути. Теорема и метод Форда–Фалкерсона. Поиск минимального разреза.
|-
| 2
| '''Алгоритмы максимального потока.''' Алгоритмы Эдмондса–Карпа и Диница. Слоистые сети и блокирующие потоки. Масштабирование потоков. Единичные сети. Теоремы Карзанова.
|-
| 3
| '''Предпотоки и потоки минимальной стоимости.''' Метод проталкивания предпотока, операции Push и Relabel, функция Discharge, алгоритм «поднять-в-начало». Минимальная циркуляция и максимальный поток минимальной стоимости. Метод Клейна. Потенциалы Джонсона.
|-
| 4
| '''Паросочетания, пути и разрезы.''' Максимальное паросочетание и алгоритм Куна. Сведение паросочетания к задаче о потоке. Алгоритм Хопкрофта–Карпа. Теоремы Данилюка, Менгера, Уитни, Кёнига и Дилворта. Максимальное паросочетание минимального веса и венгерский алгоритм.
|-
| 5
| '''Минимальные разрезы и плотные подграфы.''' Глобальный минимальный разрез. Алгоритм Штор–Вагнера. Дерево Гомори–Ху и его построение. Задача о подграфе максимальной плотности.
|-
| 6
| '''Основы алгоритмов обработки строк.''' Префикс-функция и алгоритм Кнута–Морриса–Пратта. Z-функция и её применения. Алгоритм Манакера. Поиск подстроки за линейное время. Алгоритм Галила–Сейфераса и декомпозиция строки.
|-
| 7
| '''Боры и алгоритмы поиска множества строк.''' Структура данных «бор». Способы хранения детей. Суффиксные ссылки и их построение. Алгоритм Ахо–Корасик. Сжатые суффиксные ссылки. Дерево палиндромов и линейный алгоритм его построения.
|-
| 8
| '''Суффиксные структуры.''' Суффиксный массив и его построение. Алгоритм Арикавы–Аримуры–Касаи–Ли–Парка. Суффиксные деревья и сжатые суффиксные деревья. Алгоритм Укконена. Суффиксный автомат, правые контексты, классы эквивалентности подстрок и линейное построение.
|-
| 9
| '''Основы вычислительной геометрии.''' Точки, прямые и отрезки. Векторы и скалярное и векторное произведения. Ориентация и коллинеарность. Пересечение прямых, отрезков, окружности и прямой. Ориентированная площадь многоугольника и площадь пересечения многоугольника и круга.
|-
| 10
| '''Выпуклая геометрия.''' Проверка принадлежности точки многоугольнику. Работа с выпуклыми многоугольниками. Касательные. Выпуклая оболочка: алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика и Чена. Пара ближайших точек. Минимальный периметр треугольника. Диаметр множества точек.
|-
| 11
| '''Операции над выпуклыми объектами и геометрические структуры.''' Сумма Минковского. Пересечение и расстояние между выпуклыми многоугольниками. Минимальные охватывающие прямоугольники. Задачи о движении робота и препятствиях. Сканирующая прямая. Площадь объединения прямоугольников. Пересечение полуплоскостей.
|-
| 12
| '''Вероятностные алгоритмы.''' Случайный QuickSort и поиск порядковой статистики. Анализ среднего и худшего времени работы. Вероятностная оценка игровых деревьев. Алгоритм Каргера для поиска минимального разреза. Алгоритм Каргера–Штайна.
|-
| 13
| '''Вероятностные и быстрые алгоритмы на графах.''' Алгоритмы поиска минимального остовного дерева: Борувка и Каргер–Клейн–Тарьян. Средние и худшие оценки времени работы. Задачи APD и APSP. Быстрое булево умножение матриц и алгоритмы на его основе.
|-
| 14
| '''Дополнительные структуры и алгоритмы.''' Полиномиальные хэши строк и алгоритм Рабина–Карпа. Дерандомизация: метод условных вероятностей и малых пространств событий. Персистентные структуры данных. Онлайн-обработка геометрических задач. KD-деревья и статический поиск точек в прямоугольниках.
|-
| 15
| '''Продвинутая вычислительная геометрия и оптимизация.''' Поиск граней связного плоского графа. Диаграмма Вороного и её построение. Триангуляция Делоне и её свойства. Выпуклая оболочка в 3D. Convex Hull Trick и дерево Ли–Чао. Тернарный поиск и его применения.
|}

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

Spirina.es в 10:57, 27 августа 2026