Алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Матроиды)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 12 участников)
Строка 1: Строка 1:
−
== Основные определения теории графов ==
+
== Амортизационный анализ ==
−
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+
* [[Амортизационный анализ]]
−
* [[Лемма о рукопожатиях]]
+
* [[Динамический массив]]
−
* [[Ориентированный граф]]
+
* [[Hashed Array Tree]]<tex>^\star</tex>
−
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
+
* [[Список]]
−
* [[Теорема о существовании простого пути в случае существования пути]]
+
* [[Стек]]
−
* [[Теорема о существовании простого цикла в случае существования цикла]]
+
* [[Очередь]]
−
* [[Матрица смежности графа]]
+
* [[Дек]]
−
* [[Связь степени матрицы смежности и количества путей]]
+
* [[Мажорирующий элемент]]
−
* [[Матрица инцидентности графа]]
+
* [[Счетчик Кнута]]
−
* [[Циклическое пространство графа]]
+
* [[Мастер-теорема]]<tex>^\star</tex>
−
* [[Фундаментальные циклы графа]]
+
* [[List order maintenance]]<tex>^\star</tex>
−
* [[Дерево, эквивалентные определения]]
 
  
 +
== Персистентные структуры данных ==
 +
* [[Персистентные структуры данных]]
 +
* [[Персистентный стек]]
 +
* [[Персистентная очередь]]
 +
* [[Персистентный дек]]
 +
* [[Персистентная приоритетная очередь]]
  
−
== Связность в графах ==
+
== [[Приоритетные очереди]] ==
−
* [[Отношение связности, компоненты связности]]
+
* [[Двоичная куча]]
−
* [[Отношение реберной двусвязности]]
+
* [[Биномиальная куча]]
−
* [[Отношение вершинной двусвязности]]
+
* [[Фибоначчиева куча]]
−
* [[Граф компонент реберной двусвязности]]
+
* [[Левосторонняя куча]]
−
* [[Граф блоков-точек сочленения]]
+
* [[Тонкая куча]]
−
* [[Точка сочленения, эквивалентные определения]]
+
* [[Толстая куча на избыточном счетчике]]
−
* [[Мост, эквивалентные определения]]
+
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
−
* [[k-связность]]
 
−
* [[Теорема Менгера]]
 
−
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
  
 +
== Система непересекающихся множеств ==
 +
* [[СНМ (наивные реализации) | Наивные реализации]]
 +
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 +
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 +
* [[СНМ с операцией удаления за О(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>
  
−
== Обходы графов ==
+
== Запросы на отрезках ==
−
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
−
* [[Покрытие ребер графа путями]]
 
−
* [[Алгоритм построения Эйлерова цикла]]
 
−
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
−
* [[Гамильтоновы графы]]
 
−
* [[Теорема Хватала]]
 
−
* Следствия теоремы Хватала:
 
−
** [[Теорема Дирака]]
 
−
** [[Теорема Оре]]
 
−
* [[Турниры]]
 
−
* [[Теорема Редеи-Камиона]]
 
  
−
== Укладки графов ==
+
=== Корневая эвристика ===
−
* [[Укладка графа на плоскости]]
+
* [[Статистики на отрезках. Корневая эвристика]]
−
* [[Формула Эйлера]]
+
* [[Корневая декомпозиция с операциями: get, insert, erase]]
−
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
+
* [[Алгоритм Мо]]
−
* [[Укладка дерева]]
 
−
* [[Укладка графа с планарными компонентами реберной двусвязности]]
 
−
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
−
* [[Теорема Понтрягина-Куратовского]]
 
−
* [[Двойственный граф планарного графа]]
 
  
−
== Раскраски графов ==
+
=== Дерево отрезков ===
−
* [[Раскраска графа]]
+
* [[Дерево отрезков. Построение]]
−
* [[Двудольные графы и раскраска в 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>
−
* [[Теорема о декомпозиции]]
 
−
* [[Теорема о декомпозиционном барьере]]
 
−
* [[Блокирующий поток]]
 
−
* [[Схема алгоритма Диница]]
 
−
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
−
* [[Алгоритм масштабирования потока]]
 
−
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 
  
−
== Задача о потоке минимальной стоимости ==
+
== [[Динамическое программирование]] ==
−
* [[Поток минимальной стоимости]]
+
=== Классические задачи динамического программирования ===
−
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
+
*[[Кратчайший путь в ациклическом графе]]
−
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
+
*[[Задача о числе путей в ациклическом графе]]
−
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
+
*[[Задача о расстановке знаков в выражении]]
−
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
+
*[[Задача о порядке перемножения матриц]]
−
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
+
*[[Задача о наибольшей общей подпоследовательности]]
−
* [[Венгерский алгоритм решения задачи о назначениях]]
+
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
 +
*[[Задача коммивояжера, ДП по подмножествам]]
 +
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 +
*[[Задача о рюкзаке]]
  
−
== Поиск подстроки в строке ==
+
=== Способы оптимизации методов динамического программирования ===
−
* [[Наивный алгоритм поиска подстроки в строке]]
+
*[[Метод четырёх русских для умножения матриц]]
−
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
+
*[[Применение метода четырёх русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
−
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
+
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
−
* [[Префикс-функция]]
+
*[[Meet-in-the-middle]]<tex>^\star</tex>
−
* [[Алгоритм Кнута-Морриса-Пратта]]
+
*[[Convex hull trick]]
−
* [[Z-функция]]
 
−
* [[Автомат для поиска образца в тексте]]
 
−
* [[Бор]]
 
−
* [[Алгоритм Ахо-Корасик]]
 
  
−
== Словарные структуры данных ==
+
=== Другие задачи ===
−
* [[Суффиксный бор]]
+
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
−
* [[Сжатое суффиксное дерево]]
+
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
−
* [[Алгоритм Укконена]]
+
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 +
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 +
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 +
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 +
*[[Динамика по поддеревьям]]
 +
*[[Level Ancestor problem]]
  
−
== Задача о наименьшем общем предке ==
+
== Криптографические алгоритмы ==
−
* [[Метод двоичного подъема]]
+
*[[RSA]]
−
* [[Сведение задачи LCA к задаче RMQ]]
 
−
* [[Решение RMQ с помощью разреженной таблицы]]
 
−
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
 
−
* [[Сведение задачи RMQ к задаче LCA]]
 
  
−
== Суффиксный массив ==
+
== Связь между структурами данных ==
−
* [[Суффиксный массив]]
+
* [[Связь между структурами данных]]
−
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
−
* [[Алгоритм цифровой сортировки]]
 
−
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
−
* [[Алгоритм Касаи и др.]]
 
−
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
  
−
== Матроиды ==
+
== Алгоритмы во внешней памяти ==
−
* [[Определение матроида]]
+
* [[Алгоритмы во внешней памяти. Базовые конструкции]]
−
* [[Примеры матроидов]]
 
−
* [[Прямая сумма матроидов]]
 
−
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
−
* [[Жадный алгоритм поиска базы минимального веса]]
 
−
* [[Теорема о базах]]
 
−
* [[Аксиоматизация матроида базами]]
 
−
* [[Теорема о циклах]]
 
−
* [[Аксиоматизация матроида циклами]]
 
−
* [[Ранговая функция, полумодулярность]]
 
−
* [[Двойственный матроид]]
 
−
* [[Примеры матроидов: графовый матроид]]
 
−
* [[Оператор замыкания для матроидов]]
 
−
* [[Пересечение матроидов, определение, примеры]]
 
−
* [[Лемма о паросочетании в графе замен]]
 
−
* [[Лемма о единственном паросочетании в графе замен]]
 
−
* [[Граф замен для двух матроидов]]
 
−
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
−
* [[Доказательство теоремы Эдмондса-Лоулера]]
 
−
* [[Объединение матроидов, проверка множества на независимость]]
 
−
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Текущая версия на 19:33, 4 сентября 2022

Амортизационный анализ

Персистентные структуры данных

Приоритетные очереди

Система непересекающихся множеств

Поисковые структуры данных

Запросы на отрезках

Корневая эвристика

Дерево отрезков

Дерево Фенвика

Задача о наименьшем общем предке

Хеширование

Сортировки

Квадратичные сортировки

Сортировки на сравнениях

Многопоточные сортировки

Другие сортировки

Сортирующие сети

Алгоритмы поиска

Динамическое программирование

Классические задачи динамического программирования

Способы оптимизации методов динамического программирования

Другие задачи

Криптографические алгоритмы

Связь между структурами данных

Алгоритмы во внешней памяти

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных&oldid=85461»