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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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