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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Другие задачи)
(не показано 16 промежуточных версий 9 участников)
Строка 1: Строка 1:
== Основные определения теории графов ==
+
== Амортизационный анализ ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+
* [[Амортизационный анализ]]
* [[Лемма о рукопожатиях]]
+
* [[Динамический массив]]
* [[Ориентированный граф]]
+
* [[Hashed Array Tree]]<tex>^\star</tex>
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
+
* [[Список]]
* [[Теорема о существовании простого пути в случае существования пути]]
+
* [[Стек]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
+
* [[Очередь]]
* [[Матрица смежности графа]]
+
* [[Дек]]
* [[Связь степени матрицы смежности и количества путей]]
+
* [[Мажорирующий элемент]]
* [[Матрица инцидентности графа]]
+
* [[Счетчик Кнута]]
* [[Циклическое пространство графа]]
+
* [[Мастер-теорема]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]
+
* [[List order maintenance]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
 
  
== Связность в графах ==
+
== Персистентные структуры данных ==
* [[Отношение связности, компоненты связности]]
+
* [[Персистентные структуры данных]]
* [[Отношение реберной двусвязности]]
+
* [[Персистентный стек]]
* [[Отношение вершинной двусвязности]]
+
* [[Персистентная очередь]]
* [[Граф компонент реберной двусвязности]]
+
* [[Персистентный дек]]
* [[Граф блоков-точек сочленения]]
+
* [[Персистентная приоритетная очередь]]
* [[Точка сочленения, эквивалентные определения]]
 
* [[Мост, эквивалентные определения]]
 
* [[k-связность]]
 
* [[Теорема Менгера]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
  
== Остовные деревья ==
+
== [[Приоритетные очереди]] ==
* [[Матрица Кирхгофа]]
+
* [[Двоичная куча]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
+
* [[Биномиальная куча]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
+
* [[Фибоначчиева куча]]
* [[Количество помеченных деревьев]]
+
* [[Левосторонняя куча]]
* [[Коды Прюфера]]
+
* [[Тонкая куча]]
 +
* [[Толстая куча на избыточном счетчике]]
 +
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
  
== Обходы графов ==
+
== Система непересекающихся множеств ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
+
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[Покрытие ребер графа путями]]
+
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[Алгоритм построения Эйлерова цикла]]
+
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
+
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
* [[Гамильтоновы графы]]
 
* [[Теорема Хватала]]
 
* Следствия теоремы Хватала:
 
** [[Теорема Дирака]]
 
** [[Теорема Оре]]
 
* [[Турниры]]
 
* [[Теорема Редеи-Камиона]]
 
  
== Укладки графов ==
+
== [[Поисковые структуры данных]] ==
* [[Укладка графа на плоскости]]
+
* [[Упорядоченное множество]]
* [[Формула Эйлера]]
+
* [[Дерево поиска, наивная реализация]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</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>
  
== Раскраски графов ==
+
== Запросы на отрезках ==
* [[Раскраска графа]]
 
* [[Двудольные графы и раскраска в 2 цвета]]
 
* [[Хроматический многочлен]]
 
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
 
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
 
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
 
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
 
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
 
* [[Формула Зыкова]]
 
* [[Формула Уитни]]
 
  
== Обход в глубину ==
+
=== Корневая эвристика ===
* [[Обход в глубину, цвета вершин]]
+
* [[Статистики на отрезках. Корневая эвристика]]
* [[Лемма о белых путях]]
+
* [[Корневая декомпозиция с операциями: get, insert, erase]]
* [[Использование обхода в глубину для проверки связности]]
+
* [[Алгоритм Мо]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 
* [[Использование обхода в глубину для поиска точек сочленения]]
 
* [[Построение компонент вершинной двусвязности]]
 
* [[Использование обхода в глубину для поиска мостов]]
 
* [[Построение компонент реберной двусвязности]]
 
  
== Кратчайшие пути в графах ==
+
=== Дерево отрезков ===
* [[Обход в ширину]]
+
* [[Дерево отрезков. Построение]]
* [[Алгоритм Форда-Беллмана]]
+
* [[Реализация запроса в дереве отрезков сверху]]
* [[Алгоритм Дейкстры]]
+
* [[Реализация запроса в дереве отрезков снизу]]
* [[Алгоритм Флойда]]
+
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Алгоритм Джонсона]]
+
* [[Многомерное дерево отрезков]]
 +
* [[Сжатое многомерное дерево отрезков]]
  
== Остовные деревья ==
+
== Дерево Фенвика ==
* [[Лемма о безопасном ребре]]
+
* [[Дерево Фенвика]]
* [[Алгоритм Прима]]
+
* [[Встречное дерево Фенвика]]
* [[Алгоритм Краскала]]
+
* [[Дерево Фенвика для некоммутативных операций]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
+
* [[Многомерное дерево Фенвика]]
* [[Алгоритм двух китайцев]]
 
  
== Задача о паросочетании ==
+
== Задача о наименьшем общем предке ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
+
* [[Сведение задачи 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-ой порядковой статистики за линейное время]]
* [[Z-функция]]
+
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
* [[Автомат для поиска образца в тексте]]
+
* [[Сортировка подсчетом]]
* [[Бор]]
+
* [[Цифровая сортировка]]
* [[Алгоритм Ахо-Корасик]]
+
* [[Карманная сортировка]]
 +
* [[Сортировка Хана]]<tex>^\star</tex>
 +
* [[Задача флага Нидерландов]]<tex>^\star</tex>
 +
* [[Блинная сортировка]]<tex>^\star</tex>
  
== Словарные структуры данных ==
+
== Сортирующие сети ==
* [[Суффиксный бор]]
+
* [[Сортирующие сети]]
* [[Сжатое суффиксное дерево]]
+
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Алгоритм Укконена]]
+
* [[Сортирующие сети для квадратичных сортировок]]
 +
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 +
* [[Сеть Бетчера]]
  
== Задача о наименьшем общем предке ==
+
== Алгоритмы поиска ==
* [[Метод двоичного подъема]]
+
* [[Целочисленный двоичный поиск]]
* [[Сведение задачи LCA к задаче RMQ]]
+
* [[Поиск в матрице]]<tex>^\star</tex>
* [[Решение RMQ с помощью разреженной таблицы]]
+
* [[Вещественный двоичный поиск]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
+
* [[Троичный поиск]]
* [[Сведение задачи RMQ к задаче LCA]]
+
* [[Поиск с помощью золотого сечения]]
 +
* [[Интерполяционный поиск]]
 +
* [[Метод Фибоначчи]]<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]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
* [[Алгоритм цифровой сортировки]]
 
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
* [[Алгоритм Касаи и др.]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
  
== Матроиды ==
+
== Связь между структурами данных ==
* [[Определение матроида]]
+
* [[Связь между структурами данных]]
* [[Примеры матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
* [[Жадный алгоритм поиска базы минимального веса]]
 
* [[Теорема о базах]]
 
* [[Аксиоматизация матроида базами]]
 
* [[Теорема о циклах]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Лемма о паросочетании в графе замен]]
 
* [[Лемма о единственном паросочетании в графе замен]]
 
* [[Граф замен для двух матроидов]]
 
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Теорема Эдмондса-Лоулера]]
 
* [[Объединение матроидов, проверка множества на независимость]]
 
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
 
* [[Алгоритм построения базы в объединении матроидов]]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Версия 15:33, 25 мая 2019

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировки

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

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

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

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

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

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

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

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

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

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

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

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