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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 7 участников)
Строка 40: Строка 40:
 
* [[2-3 дерево]]
 
* [[2-3 дерево]]
 
* [[B-дерево]]
 
* [[B-дерево]]
 +
* [[B+-дерево]]
 
* [[Красно-черное дерево]]
 
* [[Красно-черное дерево]]
 
* [[Декартово дерево]]
 
* [[Декартово дерево]]
Строка 53: Строка 54:
 
* [[Rope]]<tex>^\star</tex>
 
* [[Rope]]<tex>^\star</tex>
 
* [[AA-дерево]]<tex>^\star</tex>
 
* [[AA-дерево]]<tex>^\star</tex>
 +
* [[Техника частичного каскадирования]] <tex>^\star</tex>
 +
* [[Centroid decomposition]] <tex>^\star</tex>
  
== Дерево отрезков ==
+
== Запросы на отрезках ==
 +
 
 +
=== Корневая эвристика ===
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 +
* [[Алгоритм Мо]]
 +
 +
=== Дерево отрезков ===
 
* [[Дерево отрезков. Построение]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков сверху]]
Строка 71: Строка 79:
  
 
== Задача о наименьшем общем предке ==
 
== Задача о наименьшем общем предке ==
* [[Алгоритм Мо]]
 
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Сведение задачи RMQ к задаче LCA]]
Строка 141: Строка 148:
 
* [[Интерполяционный поиск]]
 
* [[Интерполяционный поиск]]
 
* [[Метод Фибоначчи]]<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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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