5
правок
Изменения
м
Поменял "е" на "ё", потому что всегда было перенаправление. Статей с упоминанием "четырех русских" нет, есть упоминание "четырёх русских".
== Основные определения теории графов Амортизационный анализ ==* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, циклАмортизационный анализ]]* [[Лемма о рукопожатияхДинамический массив]]* [[Ориентированный графHashed Array Tree]]<tex>^\star</tex>* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графаСписок]]* [[Теорема о существовании простого пути в случае существования путиСтек]]* [[Теорема о существовании простого цикла в случае существования циклаОчередь]]* [[Матрица смежности графаДек]]* [[Связь степени матрицы смежности и количества путейМажорирующий элемент]]* [[Матрица инцидентности графаСчетчик Кнута]]* [[Циклическое пространство графаМастер-теорема]]<tex>^\star</tex>* [[Фундаментальные циклы графа]]* [[Дерево, эквивалентные определенияList order maintenance]]<tex>^\star</tex>
== Персистентные структуры данных ==
* [[Персистентные структуры данных]]
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[Персистентная приоритетная очередь]]
== Связность в графах ==* [[Отношение связности, компоненты связностиПриоритетные очереди]]==* [[Отношение реберной двусвязностиДвоичная куча]]* [[Отношение вершинной двусвязностиБиномиальная куча]]* [[Граф компонент реберной двусвязностиФибоначчиева куча]]* [[Граф блоков-точек сочлененияЛевосторонняя куча]]* [[Точка сочленения, эквивалентные определенияТонкая куча]]* [[Мост, эквивалентные определенияТолстая куча на избыточном счетчике]]* [[kКуча Бродала-связность]]* [[Теорема Менгера]]* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершиныОкасаки]]<tex>^\star</tex>
== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[СНМ с операцией удаления за О(1)]]<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]]* [[Двойственный граф планарного графаАлгоритм Мо]]
== Раскраски графов = Дерево отрезков ===* [[Раскраска графаДерево отрезков. Построение]]* [[Двудольные графы и раскраска Реализация запроса в 2 цветадереве отрезков сверху]]* [[Хроматический многочлен]]** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленовРеализация запроса в дереве отрезков снизу]]** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременностьНесогласованные поддеревья. Реализация массового обновления]]* [[Формула ЗыковаМногомерное дерево отрезков]]* [[Формула УитниСжатое многомерное дерево отрезков]]
== Обход в глубину Дерево Фенвика ==* [[Обход в глубину, цвета вершинДерево Фенвика]]* [[Лемма о белых путяхВстречное дерево Фенвика]]* [[Использование обхода в глубину Дерево Фенвика для проверки связностинекоммутативных операций]]* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]* [[Использование обхода в глубину для топологической сортировки]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент вершинной двусвязности]]* [[Использование обхода в глубину для поиска мостов]]* [[Построение компонент реберной двусвязностиМногомерное дерево Фенвика]]
== Кратчайшие пути в графах Задача о наименьшем общем предке ==* [[Обход в ширинуСведение задачи LCA к задаче RMQ]]* [[Сведение задачи RMQ к задаче LCA]]* [[Метод двоичного подъема]]* [[Решение RMQ с помощью разреженной таблицы]]* [[Двумерная разреженная таблица]]* [[Алгоритм ФордаФарака-БеллманаКолтона и Бендера]](решение +/-1 RMQ с помощью метода четырех русских)* [[Алгоритм ДейкстрыХьюи]]* [[Heavy-light декомпозиция]]* [[Алгоритм ФлойдаШибера-Вишкина]]<tex>^\star</tex>* [[Алгоритм ДжонсонаТарьяна поиска LCA за O(1) в оффлайн]]<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>
== Поиск подстроки в строке [[Динамическое программирование]] ===== Классические задачи динамического программирования ===* [[Наивный алгоритм поиска подстроки Кратчайший путь в строкеациклическом графе]]* [[Поиск подстроки Задача о числе путей в строке с использованием хеширования. Алгоритм Рабина-Карпаациклическом графе]]* [[Поиск наибольшей общей подстроки двух строк с использованием хешированияЗадача о расстановке знаков в выражении]]* [[Префикс-функцияЗадача о порядке перемножения матриц]]* [[Алгоритм Кнута-Морриса-ПраттаЗадача о наибольшей общей подпоследовательности]]* [[Z-функцияЗадача о наибольшей возрастающей подпоследовательности]]* [[Автомат для поиска образца в текстеБыстрый поиск наибольшей возрастающей подпоследовательности]]** [[БорЗадача коммивояжера, ДП по подмножествам]]* [[Алгоритм АхоЗадача о редакционном расстоянии, алгоритм Вагнера-КорасикФишера]]*[[Задача о рюкзаке]]
== Словарные структуры данных =Способы оптимизации методов динамического программирования ===*[[Метод четырёх русских для умножения матриц]]*[[Применение метода четырёх русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>* [[Суффиксный борЗадача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]* [[Сжатое суффиксное деревоMeet-in-the-middle]]<tex>^\star</tex>* [[Алгоритм УкконенаConvex hull trick]]
== Задача о наименьшем общем предке = Другие задачи ===* [[Метод двоичного подъемаЗадача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>* [[Сведение задачи LCA к задаче RMQЗадача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]*[[Задача о наибольшей подпоследовательности-палиндроме]]* [[Решение RMQ с помощью разреженной таблицыЗадача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>* [[Алгоритм Фарака-Колтона и БендераЗадача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>*[[Динамическое программирование по профилю]] (решение +<tex>^\star</-1 RMQ с помощью метода четырех русских)tex>*[[Динамика по поддеревьям]]*[[Level Ancestor problem]] == Криптографические алгоритмы ==*[[RSA]] == Связь между структурами данных ==* [[Сведение задачи RMQ к задаче LCAСвязь между структурами данных]]
== Суффиксный массив Алгоритмы во внешней памяти ==* [[Суффиксный массив]]* [[Построение суффиксного массива с помощью стандартных методов сортировки]]* [[Алгоритм цифровой сортировки]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]]* [[Алгоритм Касаи и дрАлгоритмы во внешней памяти.]]* [[Алгоритм поиска подстроки в строке с помощью суффиксного массиваБазовые конструкции]]
[[Категория: Алгоритмы и структуры данных]]
