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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обновление тем до состояния на 08.12.2010)
 
(не показано 39 промежуточных версий 13 участников)
Строка 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]]
 +
 
 +
=== Другие задачи ===
 +
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
 +
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 +
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 +
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 +
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 +
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 +
*[[Динамика по поддеревьям]]
 +
*[[Level Ancestor problem]]
 +
 
 +
==  Криптографические алгоритмы ==
 +
*[[RSA]]
 +
 
 +
== Связь между структурами данных ==
 +
* [[Связь между структурами данных]]
 +
 
 +
== Алгоритмы во внешней памяти ==
 +
* [[Алгоритмы во внешней памяти. Базовые конструкции]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Текущая версия на 12:50, 23 июня 2019

Амортизационный анализ[править]

Персистентные структуры данных[править]

Приоритетные очереди[править]

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

Поисковые структуры данных[править]

Запросы на отрезках[править]

Корневая эвристика[править]

Дерево отрезков[править]

Дерево Фенвика[править]

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

Хеширование[править]

Сортировки[править]

Квадратичные сортировки[править]

Сортировки на сравнениях[править]

Многопоточные сортировки[править]

Другие сортировки[править]

Сортирующие сети[править]

Алгоритмы поиска[править]

Динамическое программирование[править]

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

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

Другие задачи[править]

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

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

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