Изменения

== Основные определения теории графов Амортизационный анализ ==* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, циклАмортизационный анализ]]* [[Лемма о рукопожатияхДинамический массив]]* [[Ориентированный графHashed Array Tree]]<tex>^\star</tex>* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графаСписок]]* [[Теорема о существовании простого пути в случае существования путиСтек]]* [[Теорема о существовании простого цикла в случае существования циклаОчередь]]* [[Матрица смежности графаДек]]* [[Связь степени матрицы смежности и количества путейМажорирующий элемент]]* [[Матрица инцидентности графаСчетчик Кнута]]* [[Циклическое пространство графаМастер-теорема]]<tex>^\star</tex>* [[Фундаментальные циклы графа]]* [[Дерево, эквивалентные определенияList order maintenance]]<tex>^\star</tex>

== Связность в графах ==* [[Отношение связности, компоненты связностиПриоритетные очереди]]==* [[Отношение реберной двусвязностиДвоичная куча]]* [[Отношение вершинной двусвязностиБиномиальная куча]]* [[Граф компонент реберной двусвязностиФибоначчиева куча]]* [[Граф блоков-точек сочлененияЛевосторонняя куча]]* [[Точка сочленения, эквивалентные определенияТонкая куча]]* [[Мост, эквивалентные определенияТолстая куча на избыточном счетчике]]* [[kКуча Бродала-связность]]* [[Теорема Менгера]]* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершиныОкасаки]]<tex>^\star</tex>

== Остовные деревья [[Поисковые структуры данных]] ==* [[Матрица КирхгофаУпорядоченное множество]]* [[Дерево поиска, наивная реализация]]* [[АВЛ-дерево]]* [[2-3 дерево]]* [[B-дерево]]* [[B+-дерево]]* [[Красно-черное дерево]]* [[Декартово дерево]]* [[Декартово дерево по неявному ключу]]* [[Splay-дерево]]* [[Взвешенное дерево]]* [[Tango-дерево]]<tex>^\star</tex>* [[Рандомизированное бинарное дерево поиска]]* [[Связь матрицы Кирхгофа и матрицы инцидентностиДерево ван Эмде Боаса]]* [[Подсчет числа остовных деревьев Список с помощью матрицы Кирхгофапропусками]]* [[Fusion tree]]<tex>^\star</tex>* [[Сверхбыстрый цифровой бор]]* [[Rope]]<tex>^\star</tex>* [[AA-дерево]]<tex>^\star</tex>* [[Количество помеченных деревьевТехника частичного каскадирования]]<tex>^\star</tex>* [[Коды ПрюфераCentroid decomposition]]<tex>^\star</tex>

== Обходы графов Запросы на отрезках ==* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]* [[Покрытие ребер графа путями]]* [[Алгоритм построения Эйлерова цикла]]* [[Произвольно вычерчиваемые из заданной вершины графы]]* [[Гамильтоновы графы]]* [[Теорема Хватала]]* Следствия теоремы Хватала: ** [[Теорема Дирака]]** [[Теорема Оре]]* [[Турниры]]* [[Теорема Редеи-Камиона]]

== Укладки графов = Корневая эвристика ===* [[Укладка графа Статистики на плоскостиотрезках. Корневая эвристика]]* [[Формула Эйлера]]* [[Непланарность K5 и K3Корневая декомпозиция с операциями: get,3|Непланарность <tex>K_5</tex> и <tex>K_{3insert,3}</tex>]]* [[Укладка дерева]]* [[Укладка графа с планарными компонентами реберной двусвязности]]* [[Укладка графа с планарными компонентами вершинной двусвязности]]* [[Теорема Понтрягина-Куратовскогоerase]]* [[Двойственный граф планарного графаАлгоритм Мо]]

== Раскраски графов =Дерево отрезков ===* [[Дерево отрезков. Построение]]* [[Реализация запроса в дереве отрезков сверху]]* [[Реализация запроса в дереве отрезков снизу]]* [[Несогласованные поддеревья. Реализация массового обновления]]* [[Многомерное дерево отрезков]]* [[Сжатое многомерное дерево отрезков]] == Дерево Фенвика ==* [[Дерево Фенвика]]* [[Встречное дерево Фенвика]]* [[Дерево Фенвика для некоммутативных операций]]* [[Многомерное дерево Фенвика]] == Задача о наименьшем общем предке ==* [[Сведение задачи LCA к задаче RMQ]]* [[Сведение задачи RMQ к задаче LCA]]* [[Метод двоичного подъема]]* [[Решение RMQ с помощью разреженной таблицы]]* [[Раскраска графаДвумерная разреженная таблица]]* [[Двудольные графы Алгоритм Фарака-Колтона и раскраска Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)* [[Алгоритм Хьюи]]* [[Heavy-light декомпозиция]]* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>* [[Алгоритм Тарьяна поиска LCA за O(1) в 2 цветаоффлайн]]<tex>^\star</tex>* [[Хроматический многочленLink-Cut Tree]]<tex>^\star</tex>*[[Rake-Compress деревья]]<tex>^\star</tex> == Хеширование ==* [[Хроматический многочлен#Хроматический многочлен полного графаХеш-таблица]]* [[Разрешение коллизий]]* [[Хеширование кукушки]]* [[Идеальное хеширование]]* [[Перехеширование]]* [[Фильтр Блума]]* [[Quotient filter]]<tex>^\star</tex>* [[Универсальное семейство хеш-функций]]* [[Расширяемое хеширование]]<tex>^\star</tex> == [[Сортировки]] ===== Квадратичные сортировки ===* [[Сортировка выбором]]* [[Сортировка пузырьком]]* [[Сортировка вставками]]=== Сортировки на сравнениях ===* [[Сортировка Шелла]]<tex>^\star</tex>* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Сортировка слиянием]]* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]* [[Терпеливая сортировка]]<tex>^\star</tex>* [[Timsort]]<tex>^\star</tex>* [[Smoothsort]]<tex>^\star</tex>* [[Теорема о нижней оценке для сортировки сравнениями]] === Многопоточные сортировки ===* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>* [[PSRS-сортировка]]<tex>^\star</tex>=== Другие сортировки ===* [[Поиск k-ой порядковой статистики]]* [[Поиск k-ой порядковой статистики за линейное время]]* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>* [[Сортировка подсчетом]]* [[Цифровая сортировка]]* [[Карманная сортировка]]* [[Сортировка Хана]]<tex>^\star</tex>* [[Задача флага Нидерландов]]<tex>^\star</tex>* [[Блинная сортировка]]<tex>^\star</tex> == Сортирующие сети ==* [[Сортирующие сети]]* [[0-1 принцип |Хроматический многочлен полного графаПроверка сети компараторов на то, что она сортирующая. 0-1 принцип]]* [[Сортирующие сети для квадратичных сортировок]]* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>* [[Сеть Бетчера]] == Алгоритмы поиска ==* [[Целочисленный двоичный поиск]]* [[Поиск в матрице]]<tex>^\star</tex>* [[Вещественный двоичный поиск]]* [[Троичный поиск]]* [[Поиск с помощью золотого сечения]]* [[Интерполяционный поиск]]* [[Метод Фибоначчи]]<tex>^\star</tex> == [[Динамическое программирование]] ===== Классические задачи динамического программирования ===*[[Кратчайший путь в ациклическом графе]]*[[Задача о числе путей в ациклическом графе]]*[[Задача о расстановке знаков в выражении]]* [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графаЗадача о порядке перемножения матриц]]*[[Задача о наибольшей общей подпоследовательности]]* [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дереваЗадача о наибольшей возрастающей подпоследовательности]]*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старшийЗадача коммивояжера, второй коэффициентыДП по подмножествам]]*[[Задача о редакционном расстоянии, знакомпеременностьалгоритм Вагнера-Фишера]]*[[Задача о рюкзаке]] === Способы оптимизации методов динамического программирования ===* [[Хроматический многочлен#Рекуррентные формулы Метод четырех русских для хроматических многочленов|Рекуррентные формулы для хроматических многочленовумножения матриц]]*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]*[[Meet-in-the-middle]]<tex>^\star</tex>*[[Convex hull trick]] === Другие задачи ===*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]*[[Задача о наибольшей подпоследовательности-палиндроме]]*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>*[[Динамическое программирование по профилю]]<tex>^\star</tex>*[[Динамика по поддеревьям]]*[[Level Ancestor problem]] == Криптографические алгоритмы ==*[[RSA]] == Связь между структурами данных ==* [[Формула ЗыковаСвязь между структурами данных]] == Алгоритмы во внешней памяти ==* [[Формула УитниАлгоритмы во внешней памяти. Базовые конструкции]]