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

2026-08-27T10:30:40Z

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

← Предыдущая версия		Версия от 10:30, 27 августа 2026
Строка 8:		Строка 8:

	'''осенний семестр'''		'''осенний семестр'''

	'''форма контроля:''' экзамен		'''форма контроля:''' экзамен

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

2026-08-27T10:30:31Z

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

← Предыдущая версия		Версия от 10:30, 27 августа 2026
Строка 8:		Строка 8:

	'''осенний семестр'''		'''осенний семестр'''
			'''форма контроля:''' экзамен

	{\| class="wikitable"		{\| class="wikitable"

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

2026-08-27T10:13:38Z

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

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

			'''осенний семестр'''

	{\| class="wikitable"		{\| class="wikitable"
	! Неделя		! Неделя

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

2026-08-27T10:04:34Z

← Предыдущая версия		Версия от 10:04, 27 августа 2026
Строка 170:		Строка 170:
	\|}		\|}

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

	Домашние задания в формате задач трёх типов:		Домашние задания в формате задач трёх типов:

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

2026-08-27T10:04:16Z

@@ Строка 1: / Строка 1: @@
 {| class="wikitable"
 ! Неделя
@@ Строка 162: / Строка 169: @@
 *** Достижение O(log n) с использованием splay-дерева.
 |}

Spirina.es: Новая страница: «{| class="wikitable" ! Неделя ! Лекции/семинары |- | 1 | '''Введение. Понятие эффективности алгоритма:''' * общеизвестные подходы, “парадокс Merge Sort”; * формальные определения: O-нотация (O-, \Theta-, \Omega-). Решение асимптотических уравнений. * Мастер-теорема. |- | 2 | '''Амортизацио...»

2026-08-27T09:54:50Z

Новая страница: «{| class="wikitable" ! Неделя ! Лекции/семинары |- | 1 | '''Введение. Понятие эффективности алгоритма:''' * общеизвестные подходы, “парадокс Merge Sort”; * формальные определения: O-нотация (O-, \Theta-, \Omega-). Решение асимптотических уравнений. * Мастер-теорема. |- | 2 | '''Амортизацио...»

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

{| class="wikitable"
! Неделя
! Лекции/семинары
|-
| 1
| '''Введение. Понятие эффективности алгоритма:'''
* общеизвестные подходы, “парадокс Merge Sort”;
* формальные определения: O-нотация (O-, \Theta-, \Omega-). Решение асимптотических уравнений.
* Мастер-теорема.
|-
| 2
| '''Амортизационный анализ:'''
* вариации:
** “в среднем”;
** метод бухгалтерского учета;
** метод потенциалов.
* Примеры амортизированных структур данных и анализа их эффективности.
** очередь на двух стеках;
** вектор.
* Персистентность как пример ситуации, когда амортизация не работает. Персистентная очередь на “шести” стеках.
|-
| 3
| '''Сортировки:'''
* квадратичные сортировки: вставками, выбором, пузырьком;
* сортировка в различных моделях. Нижняя оценка в модели камушков. Дерево решений;
* сортировка слиянием как пример оптимальной сортировки;
** алгоритм слияния двух отсортированных массивов за линейное время с использованием O(1) дополнительной памяти;
|-
| 4
| '''Сортировки:'''
* Сортировка кучей:
** двоичная куча: внутреннее устройство, методы SiftUp, SiftDown, Insert, GetMin, ExtractMin, Delete;
** построение кучи из n элементов за O(n);
** сортировка кучей. Оценки времени и памяти.
* быстрая сортировка:
** общая реализация;
** различные способы выбора pivot-а: детерминированные, случайный;
** поиск К-ой порядковой статистики. Алгоритм Флойда - Блюма - Пратта - Ривеста - Тарьяна.
|-
| 5
| '''Сортировки:'''
* основы RAM-модели, целочисленных алгоритмов. Kirkpatrick sort;
* “линейные” сортировки:
** сортировка подсчетом;
** поразрядная сортировка: MSD, LSD;
** сортировка строк.
|-
| 6
| '''Сортировки:'''
* TimSort (сортировка Тима Петерса). Оценка времени работы;
* внешняя сортировка. Устройство жёсткого диска. Метод k-путевого слияния;
|-
| 7
| '''Сливаемые кучи, их методы, оценки эффективности:'''
* биномиальная:
* левацкая;
* косая;
* Фибоначчи;
|-
| 8
| '''Сливаемые кучи, их методы, оценки эффективности:'''
* Soft Heap:
** точный инвариант;
** примеры использования: К-я порядковая статистика за O(n), near-sort за O(n log 1/eps);
** внутреннее устройство, доказательство инварианта, оценка времени работы методов.
* Целочисленные алгоритмы и структуры данных:
** Atomic Heap: сведение к Q-heap.
|-
| 9
| '''Сбалансированные двоичные деревья поиска:'''
* понятие двоичного дерева поиска, “”базовая” реализация методов Search, Insert, Erase;
* методы балансировки:
** “Честные”: АВЛ-дерево, красно-черное дерево, B-дерево. Сравнение по времени (“константе”), по памяти;
** Амортизированный: Splay-tree:
*** Асимптотика в терминах произвольно заданных положительных весов вершин
|-
| 10
| '''Сбалансированные двоичные деревья поиска:'''
* методы балансировки:
** Вероятностный: декартово дерево:
*** Построение дерева по заданным n отсортированным ключам и приоритетам за O(n);
* Двоичные деревья “по неявному ключу” для всех вышеперечисленных деревьев:
** операции Split/Merge; вставка/удаление элемента по позиции, циклический сдвиг;
** технология отложенных операций: присваивание/прибавление на подотрезке, разворот подотрезка.
|-
| 11
| '''Задачи RSQ/RMQ и их аналоги для различных функций:'''
* static RSQ: префиксные суммы;
* static RMQ:
** разреженная таблица;
** Disjoint sparse table для неидемпотентных функций;
** Метод четырех русских: алгоритм Фарах-Колтона и Бендера асимптотически оптимального решение задач static RMQ и static LCA.
*** решение задачи static RMQ без сведения к static LCA.
|-
| 12
| '''Задачи RSQ/RMQ и их аналоги для различных функций:'''
* изменение в точке:
** дерево отрезков:
*** “тупые” решения, возможность их применения;
*** применение SQRT-декомпозиции;
*** SQRT-декомпозиция с k слоями; дерево отрезков как предельная версия SQRT-декомпозиции;
*** операции “снизу” в дереве отрезков;
** дерево Фенвика:
*** классическая версия для коммутативной ассоциативной обратимой операции;
*** встречное дерево Фенвика для НЕкоммутативной НЕассоциативной операции;
*** прибавление на отрезке для дерева Фенвика;
*** применения: “Фенвик Фенвиков”, “казахский Фенвик”.
|-
| 13
| '''Задачи RSQ/RMQ и их аналоги для различных функций:'''
* Многомерные RSQ/RMQ:
** многомерные Static RSQ/RMQ;
** Изменение в точке для многомерных RSQ/RMQ;
** технология прибавлений на подпараллелепипеде для многомерных RSQ на базе дерева Фенвика или дерева отрезков с операцией снизу;
** kD-дерево, присваивание на подпараллелепипеде;
|-
| 14
| '''Задачи RSQ/RMQ и их аналоги для различных функций:'''
* Технология отложенных операций в дереве отрезков с операциями “сверху”:
** классические применения: присваивание/прибавление на отрезке;
** отложенное создание вершин: динамическое дерево отрезков;
** сливаемые деревья отрезков:
*** задача о сортировке на подотрезках;
** Segment Tree Beats:
*** %= C на отрезке, сумма на отрезке, изменение в точке;
*** min= на отрезке, сумма на отрезке, изменение в точке. Усложения: присваивание на отрезке, прибавление на отрезке.
*** прибавление на отрезке, исторический максимум в точке;
*** изменение в точке, сумма максимумов на префиксах на подотрезке;
|-
| 15
| '''Алгоритмы и структуры данных на деревьях:'''
* структура дерева:
** понятие диаметра, центра, центроида. Единственность центра. Поиск диаметра, центра, центроидов;
** Задача об изоморфизме деревьев, ее решение за O(n log n) без использования хэшей;
|-
| 16
| '''Алгоритмы и структуры данных на деревьях:'''
* Задача Level Ancestor Queries:
** метод двоичных подъемов для задачи LCA и LAQ;
** альтернативные методы решения LAQ:
*** longest path decomposition;
*** ladder decomposition;
*** их комбинация за O(n log n)/O(1);
*** Метод четырех русских: решение задачи LAQ за O(n)/O(1).
|-
| 17
| '''Алгоритмы и структуры данных на деревьях:'''
* Центроидная декомпозиция:
** задачи о поиске пути длины k во взвешенном дереве с помощью центроидной декомпозиции и с помощью “переливайки”.
** решение задачи о “присваивании в радиусе” на взвешенном дереве.
|-
| 18
| '''Алгоритмы и структуры данных на деревьях:'''
* Задача RSQ/RMQ с массовыми операциями на дереве:
** Heavy-light decomposition:
*** классическая версия с деревом отрезков за O(log^2); различные реализации;
*** ускорение до O(log n):
**** “честного” времени: балансировка по весу поддеревьев;
**** “амортизированного”: splay-дерево
** Link-cut tree: добавление операции изменения структуры дерева, его корня:
*** общая структура, O(log^2 n) на операцию с использованием произвольного дерева поиска;
*** Достижение O(log n) с использованием splay-дерева.
|}

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

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

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

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

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

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