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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 7 участников)
Строка 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]]
 +
 
 +
== Связь между структурами данных ==
 +
* [[Связь между структурами данных]]
 +
 
 +
== Алгоритмы во внешней памяти ==
 +
* [[Алгоритмы во внешней памяти. Базовые конструкции]]
 +
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

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