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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Поменял "е" на "ё", потому что всегда было перенаправление. Статей с упоминанием "четырех русских" нет, есть упоминание "четырёх русских".)
 
(не показано 10 промежуточных версий 5 участников)
Строка 1: Строка 1:
#перенаправление [[Дискретная математика, алгоритмы и структуры данных]]
+
== Амортизационный анализ ==
 +
* [[Амортизационный анализ]]
 +
* [[Динамический массив]]
 +
* [[Hashed Array Tree]]<tex>^\star</tex>
 +
* [[Список]]
 +
* [[Стек]]
 +
* [[Очередь]]
 +
* [[Дек]]
 +
* [[Мажорирующий элемент]]
 +
* [[Счетчик Кнута]]
 +
* [[Мастер-теорема]]<tex>^\star</tex>
 +
* [[List order maintenance]]<tex>^\star</tex>
 +
 
 +
== Персистентные структуры данных ==
 +
* [[Персистентные структуры данных]]
 +
* [[Персистентный стек]]
 +
* [[Персистентная очередь]]
 +
* [[Персистентный дек]]
 +
* [[Персистентная приоритетная очередь]]
 +
 
 +
== [[Приоритетные очереди]] ==
 +
* [[Двоичная куча]]
 +
* [[Биномиальная куча]]
 +
* [[Фибоначчиева куча]]
 +
* [[Левосторонняя куча]]
 +
* [[Тонкая куча]]
 +
* [[Толстая куча на избыточном счетчике]]
 +
* [[Куча Бродала-Окасаки]]<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>
 +
 
 +
== Запросы на отрезках ==
 +
 
 +
=== Корневая эвристика ===
 +
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: 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-ой порядковой статистики за линейное время]]
 +
* [[Поиск 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]]
 +
 
 +
== Связь между структурами данных ==
 +
* [[Связь между структурами данных]]
 +
 
 +
== Алгоритмы во внешней памяти ==
 +
* [[Алгоритмы во внешней памяти. Базовые конструкции]]
 +
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Текущая версия на 08:21, 1 декабря 2020

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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