Классификация алгоритмов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][выверенная версия]
(Перенаправление на Служебная:Pma tree)
 
(не показано 97 промежуточных версий 10 участников)
Строка 1: Строка 1:
# <div id="Векторные операции">'''Векторные операции'''</div>
+
#redirect [[Special:Pma_tree]]
## ''Суммирование сдваиванием''
+
__TOC__
### [[Нахождение суммы элементов массива сдваиванием]]
+
= Задачи алгебры =
### [[Нахождение частных сумм элементов массива сдваиванием]]
+
==Матричные и векторные операции==
## [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]]
+
===Векторные операции===
## [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]
+
# {{level|Суммирование сдваиванием}}
## [[Последовательно-параллельный метод суммирования]]
+
## {{level|Нахождение суммы элементов массива сдваиванием}}
# <div id="Матрично-векторные операции">'''Матрично-векторные операции'''</div>
+
## {{level|Нахождение частных сумм элементов массива сдваиванием}}
## [[Умножение плотной матрицы на вектор]]
+
# {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}}
# <div id="Матричные операции">'''Матричные операции'''</div>
+
# {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}}
## [[Умножение плотных матриц]]
+
# {{level|Последовательно-параллельный метод суммирования}}
# <div id="Разложения матриц">'''Разложения матриц'''</div>
+
=== Умножения матриц на вектор ===
## ''Треугольные разложения''
+
==== Умножения неособенных матриц на вектор ====
### Метод Гаусса (нахождение LU-разложения)
+
# {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}}
#### [[Метод Гаусса без перестановок]]
+
==== Умножения матриц специального вида на вектор ====
##### LU-разложение методом Гаусса
+
# {{level|Преобразование Фурье}}
##### Компактная схема метода Гаусса и её модификации
+
## {{level|Быстрое преобразование Фурье для составной размерности}}
###### Компактная схема метода Гаусса для плотной матрицы
+
### {{level|Быстрое преобразование Фурье для степеней двойки}}
###### [[Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации]]
+
#### {{level|Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки}}
####### [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант]]
+
#### {{level|Быстрое преобразование Фурье для чётных степеней двойки}}
####### [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]]
+
### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}}
####### [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы]]
+
## {{level|Быстрое преобразование Фурье для простой размерности}}
#### Метод Гаусса с перестановками
+
===Матричные операции===
##### Метод Гаусса с выбором ведущего элемента по столбцу
+
# {{level|Умножение плотных матриц}}
##### Метод Гаусса с выбором ведущего элемента по строке
+
## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}}
##### Метод Гаусса с выбором ведущего элемента по всей матрице
+
## {{level|Метод Штрассена}}
### [[Метод Холецкого (нахождение симметричного треугольного разложения)]]
+
==Разложения матриц==
#### [[Разложение Холецкого (метод квадратного корня)]] базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
+
{{level|Задача разложения матриц}}
### [[Известные треугольные разложения для матриц специального вида]]
+
# {{level|Треугольные разложения}}
## ''Унитарно-треугольные разложения''
+
## {{level|Метод Гаусса (нахождение LU-разложения)}}
### [[Метод Гивенса (вращений) QR-разложения матрицы]]
+
### {{level|LU-разложение методом Гаусса без перестановок}}
### [[Метод Хаусхолдера (отражений) QR-разложения матрицы]]
+
#### {{level|LU-разложение методом Гаусса}}
## ''Разложения на унитарные и хессенберговы матрицы''
+
#### {{level|Компактная схема метода Гаусса и её модификации}}
### [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме]]
+
##### {{level|Компактная схема метода Гаусса для плотной матрицы}}
## ''Разложения на унитарные и диагональные матрицы''
+
##### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации}}
### [[Спектральное разложение (нахождение собственных значений и векторов)]]
+
###### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант}}
### [[Сингулярное разложение (нахождение сингулярных значений и векторов)]]
+
###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}
# <div id="Решение систем линейных уравнений">'''Решение систем линейных уравнений'''</div>
+
###### {{level|Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы}}
## Прямые методы решения СЛАУ
+
### {{level|LU-разложение методом Гаусса с перестановками}}
### [[Linpack benchmark]]
+
#### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по столбцу}}
### Методы решения СЛАУ с матрицами специального вида
+
#### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по строке}}
#### Методы решения СЛАУ с треугольными матрицами
+
#### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по главной диагонали}}
##### [[Прямая подстановка (вещественный вариант)|Прямая подстановка]]
+
#### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по всей матрице}}
##### [[Обратная подстановка (вещественный вариант)|Обратная подстановка]]
+
## {{level|Метод Холецкого (нахождение симметричного треугольного разложения)}}
##### Методы решения СЛАУ с двухдиагональными матрицами
+
### {{level|Разложение Холецкого (метод квадратного корня)}} базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
###### [[Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей]]
+
# {{level|Известные треугольные разложения для матриц специального вида}}
###### [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ]]
+
# {{level|Унитарно-треугольные разложения}}
###### [[Последовательно-параллельный вариант обратной подстановки]]
+
## {{level|QR-разложения плотных неособенных матриц}}
#### [[Методы решения СЛАУ с трёхдиагональными матрицами]]
+
### {{level|Метод Гивенса (вращений) QR-разложения матрицы}}
##### Методы, основанные на стандартном LU-разложении матрицы
+
#### {{level|Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)}}
###### [[Прогонка]]
+
### {{level|Метод Хаусхолдера (отражений) QR-разложения матрицы}}
####### [[Прогонка, точечный вариант|Классическая монотонная прогонка]]
+
#### {{level|Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант}}
####### [[Повторная прогонка, точечный вариант|Повторная прогонка для новой правой части, классическая схема]]
+
### {{level|Метод ортогонализации}}
###### [[Метод сдваивания Стоуна]]
+
#### {{level|Классический метод ортогонализации}}
###### [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]]
+
#### {{level|Метод ортогонализации с переортогонализацией}}
##### Другие методы
+
### {{level|Метод треугольного разложения матрицы Грама}}
###### [[Метод редукции]]
+
## {{level|Методы QR-разложения плотных хессенберговых матриц}}
###### [[Метод циклической редукции]]
+
### {{level|Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)}}
####### [[Полный метод циклической редукции]]
+
### {{level|Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)}}
####### [[Повторный метод циклической редукции для новой правой части]]
+
# {{level|Разложения, содержащие матрицу, подобную исходной}}
###### [[Метод окаймления]]
+
## {{level|Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной}}
#### Методы решения СЛАУ с блочно-треугольными матрицами
+
### {{level|Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}
##### [[Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка]]
+
#### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}
##### [[Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка]]
+
### {{level|Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}
##### Методы решения СЛАУ с блочно-двухдиагональными матрицами
+
#### {{level|Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}
###### [[Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей]]
+
## {{level|Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной}}
###### [[Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ]]
+
### {{level|Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду}}
###### [[Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ]]
+
#### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}
#### [[Методы решения СЛАУ с блочно-трёхдиагональными матрицами]]
+
#### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}
##### Методы, основанные на стандартном LU-разложении матрицы
+
### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}}
###### [[Блочная прогонка]]
+
## {{level|Спектральное разложение (нахождение собственных значений и векторов)}}
###### [[Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками]]
+
# {{level|Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной}}
##### Другие методы
+
## {{level|Разложения на две унитарные и одну двухдиагональную матрицы}}
###### [[Блочный метод циклической редукции]]
+
### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}}
###### [[Блочный метод окаймления]]
+
### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}}
### [[Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы]]
+
## {{level|Разложения на две унитарные и одну диагональную матрицы}}
## Итерационные методы решения СЛАУ
+
### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}
### [[High Performance Conjugate Gradient (HPCG) benchmark]]
+
#### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}}
# <div id="Тесты производительности компьютеров">'''Тесты производительности компьютеров'''</div>
+
##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}}
## [[High Performance Conjugate Gradient (HPCG) benchmark]]
+
###### {{level|Итерация алгоритма dqds}}
## [[Linpack benchmark]]
+
 
# <div id="Преобразование Фурье">'''Преобразование Фурье'''</div>
+
==Решение систем линейных уравнений==
## [[Быстрое преобразование Фурье для степеней двойки]]
+
# {{level|Прямые методы решения СЛАУ}}
# <div id="Алгебра многочленов">'''Алгебра многочленов'''</div>
+
## {{level|Linpack benchmark}}
## [[Схема Горнера, вещественная версия, последовательный вариант|Схема Горнера]]
+
## {{level|Методы решения СЛАУ с матрицами специального вида}}
# <div id="Численные методы интегрирования">'''Численные методы интегрирования'''</div>
+
### {{level|Методы решения СЛАУ с треугольными матрицами}}
## [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]]
+
#### {{level|Прямая подстановка (вещественный вариант)}}
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод прямоугольников]]
+
#### {{level|Обратная подстановка (вещественный вариант)}}
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод трапеций]]
+
#### {{level|Методы решения СЛАУ с двудиагональными матрицами}}
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод парабол (метод Симпсона)]]
+
##### {{level|Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей}}
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод Гаусса]]
+
##### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}
# <div id="Алгоритмы на графах">'''Алгоритмы на графах'''</div>
+
##### {{level|Последовательно-параллельный вариант обратной подстановки}}
## Обход графа
+
### {{level|Методы решения СЛАУ с трёхдиагональными матрицами}}
### [[Поиск в ширину (BFS)]]
+
#### {{level|Методы, основанные на стандартном LU-разложении матрицы}}
### [[Поиск в глубину (DFS)]]
+
##### {{level|Прогонка}}
## [[Поиск кратчайшего пути от одной вершины (SSSP)]]
+
###### {{level|Прогонка, точечный вариант}}
### [[Поиск в ширину (BFS)]] (для невзвешенных графов)
+
###### {{level|Классическая монотонная прогонка, повторный вариант}}
### [[Алгоритм Дейкстры]]
+
##### {{level|Метод сдваивания Стоуна}}
### [[Алгоритм Беллмана-Форда]]
+
###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}
### [[Алгоритм Δ-шагания]]
+
###### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}
## [[Поиск кратчайшего пути для всех пар вершин (APSP)]]
+
##### {{level|Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками}}
### [[Алгоритм Джонсона]]
+
#### Другие методы
### [[Алгоритм Флойда-Уоршелла]]
+
##### {{level|Метод редукции}}
## [[Поиск транзитивного замыкания орграфа]]
+
###### {{level|Полный метод редукции}}
### [[Алгоритм Пурдома]]
+
###### {{level|Повторный метод редукции для новой правой части}}
## [[Определение диаметра графа]]
+
##### {{level|Встречная прогонка}}
## [[Построение минимального остовного дерева (MST)]]
+
###### {{level|Встречная прогонка, точечный вариант}}
### [[Алгоритм Борувки]]
+
###### {{level|Повторная встречная прогонка, точечный вариант}}
### [[Алгоритм Крускала]]
+
##### {{level|Метод циклической редукции}}
### [[Алгоритм Прима]]
+
###### {{level|Полный метод циклической редукции}}
### [[Алгоритм GHS]]
+
###### {{level|Повторный метод циклической редукции для новой правой части}}
## [[Поиск изоморфных подграфов]]
+
##### {{level|Метод окаймления}}
### [[Алгоритм Ульмана]]
+
### Методы решения СЛАУ с блочно-треугольными матрицами
### [[Алгоритм VF2]]
+
#### {{level|Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка}}
## [[Связность в графах]]
+
#### {{level|Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка}}
### [[Алгоритм Шилоаха-Вишкина поиска компонент связности]]
+
#### Методы решения СЛАУ с блочно-двухдиагональными матрицами
### [[Система непересекающихся множеств]]
+
##### {{level|Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей}}
### [[Алгоритм Тарьяна поиска компонент сильной связности]]
+
##### {{level|Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ}}
### [[Алгоритм DCSC поиска компонент сильной связности]]
+
##### {{level|Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ}}
### [[Алгоритм Тарьяна поиска компонент двусвязности]]
+
### {{level|Методы решения СЛАУ с блочно-трёхдиагональными матрицами}}
### [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности]]
+
#### Методы, основанные на стандартном LU-разложении матрицы
### [[Алгоритм Тарьяна поиска «мостов» в графе]]
+
##### {{level|Блочная прогонка}}
### [[Определение вершинной связности графа]]
+
##### {{level|Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}}
### [[Алгоритм Габова определения рёберной связности графа]]
+
#### Другие методы
## [[Поиск максимального потока в транспортной сети]]
+
##### {{level|Встречная прогонка, блочный вариант}}
### [[Алгоритм Форда-Фалкерсона]]
+
##### {{level|Блочный метод циклической редукции}}
### [[Алгоритм проталкивания предпотока]]
+
##### {{level|Блочный метод окаймления}}
## [[Поиск потока минимальной стоимости в транспортной сети]]
+
## {{level|Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы}}
## [[Задача о назначениях]]
+
# Итерационные методы решения СЛАУ
### [[Венгерский алгоритм]]
+
## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
### [[Алгоритм аукциона]]
+
## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}}
### [[Алгоритм Гопкрофта-Карпа]]
+
## {{level|Алгоритм_Качмажа}}
## [[Вычисление betweenness centrality|Вычисление центральности вершин]]
+
 
# <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div>
+
==Решения спектральных задач==
## [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math>
+
# {{level|Спектральное разложение (нахождение собственных значений и векторов)}}
# <div id="Алгоритмы сортировки">'''Алгоритмы сортировки'''</div>
+
## {{level|QR-алгоритм}}
## [[Сортировка с помощью двоичного дерева]]
+
### {{level|QR-алгоритм, используемый в SCALAPACK}}
## [[Сортировка пузырьком]]
+
#### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}
## [[Сортировка слиянием (последовательный и параллельный варианты)]]
+
#### {{level|QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK}}
# <div id="Вычислительная геометрия">'''Вычислительная геометрия'''</div>
+
### {{level|QR-алгоритм для симметричных матриц, используемый в SCALAPACK}}
## [[Поиск диаметра множества точек]]
+
#### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}
## [[Построение выпуклой оболочки набора точек]]
+
#### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}
## [[Триангуляция Делоне]]
+
### {{level|QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK}}
## [[Диаграмма Вороного]]
+
#### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}
## [[Принадлежность точки многоугольнику]]
+
#### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}
## [[Пересечения выпуклых многоугольников]] - трудоёмкость <math>O(n_1 + n_2)</math>
+
## {{level|Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц}}
## [[Пересечение звёздных многоугольников]] - трудоёмкость <math>O(n_1 * n_2)</math>
+
### {{level|Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице}}
# <div id="Компьютерная графика">'''Компьютерная графика'''</div>
+
### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением}}
## [[Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности]]
+
### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами}}
## [[Алгоритм определения видимых частей трёхмерной сцены]]
+
## {{level|Метод Ланцоша}}
## [[Трассировка лучей - рендеринг реалистичных изображений]]
+
### {{level|Алгоритм Ланцоша для точной арифметики (без переортогонализации)}}
## [[Глобальное освещение - рассматривает прямое освещение и отражение от других объектов]]
+
# {{level|Частичная спектральная задача}}
# <div id="Криптографические алгоритмы">'''Криптографические алгоритмы'''</div>
+
## {{level|Метод бисекций}}
# <div id="Нейронные сети">'''Нейронные сети'''</div>
+
# {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}
# <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div>
+
## {{level|Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц}}
## [[Линейное программирование]]
+
### {{level|Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором}}
## [[Симплекс-метод]]
+
### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}}
## [[Метод ветвей и границ (последовательный и параллельный варианты)]]
+
## {{level|QR-алгоритм в приложении к сингулярному разложению}}
## [[Генетические алгоритмы]]
+
==Алгебра многочленов==
## [[Муравьиные алгоритмы]]
+
# {{level|Схема Горнера, вещественная версия, последовательный вариант}}
## [[Комбинированные алгоритмы]]
+
 
## [[Нахождение экстремума функции]]
+
= Алгоритмы на списках и массивах =
# <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div>
+
==Алгоритмы поиска==
# <div id="Алгоритмы моделирования квантовых систем">'''Алгоритмы моделирования квантовых систем'''</div>
+
# {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, <math>O(n)</math>
## ''Алгоритмы моделирования квантовых вычислений''
+
# {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, <math>O(\log(n))</math>
### [[Однокубитное преобразование вектора-состояния]]
+
==Алгоритмы сортировки==
### [[Двухкубитное преобразование вектора-состояния]]
+
# {{level|Сортировка с помощью двоичного дерева}}
### [[Моделирование квантового преобразования Фурье]]
+
# {{level|Сортировка пузырьком}}
# <div id="Алгоритмы решения уравнений математической физики">'''Алгоритмы решения уравнений математической физики'''</div>
+
# {{level|Сортировка слиянием (последовательный и параллельный варианты)}}
## [[Уравнение Пуассона, решение дискретным преобразованием Фурье]]
+
==Алгоритмы на графах==
# <div id="Другие алгоритмы">'''Другие алгоритмы'''</div>
+
# Обход графа
 +
## {{level|Поиск в ширину (BFS)}}
 +
## {{level|Поиск в глубину (DFS)}}
 +
# {{level|Поиск кратчайшего пути от одной вершины (SSSP)}}
 +
## {{level|Поиск в ширину (BFS)}} (для невзвешенных графов)
 +
## {{level|Алгоритм Дейкстры}}
 +
## {{level|Алгоритм Беллмана-Форда}}
 +
## {{level|Алгоритм Δ-шагания}}
 +
# {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}}
 +
## {{level|Алгоритм Джонсона}}
 +
## {{level|Алгоритм Флойда-Уоршелла}}
 +
# {{level|Поиск транзитивного замыкания орграфа}}
 +
## {{level|Алгоритм Пурдома}}
 +
# {{level|Определение диаметра графа}}
 +
# {{level|Построение минимального остовного дерева (MST)}}
 +
## {{level|Алгоритм Борувки}}
 +
## {{level|Алгоритм Крускала}}
 +
## {{level|Алгоритм Прима}}
 +
## {{level|Алгоритм GHS}}
 +
# {{level|Поиск изоморфных подграфов}}
 +
## {{level|Алгоритм Ульмана}}
 +
## {{level|Алгоритм VF2}}
 +
# {{level|Связность в графах}}
 +
## {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}}
 +
## {{level|Система непересекающихся множеств}}
 +
## {{level|Алгоритм Тарьяна поиска компонент сильной связности}}
 +
## {{level|Алгоритм DCSC поиска компонент сильной связности}}
 +
## {{level|Алгоритм Тарьяна поиска компонент двусвязности}}
 +
## {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}}
 +
## {{level|Алгоритм Тарьяна поиска «мостов» в графе}}
 +
## {{level|Определение вершинной связности графа}}
 +
## {{level|Алгоритм Габова определения рёберной связности графа}}
 +
# {{level|Поиск максимального потока в транспортной сети}}
 +
## {{level|Алгоритм Форда-Фалкерсона}}
 +
## {{level|Алгоритм проталкивания предпотока}}
 +
# {{level|Поиск потока минимальной стоимости в транспортной сети}}
 +
# {{level|Задача о назначениях}}
 +
## {{level|Венгерский алгоритм}}
 +
## {{level|Алгоритм аукциона}}
 +
## {{level|Алгоритм Гопкрофта-Карпа}}
 +
# {{level|Вычисление betweenness centrality|Вычисление центральности вершин}}
 +
=Вычислительная геометрия=
 +
# {{level|Поиск диаметра множества точек}}
 +
# {{level|Построение выпуклой оболочки набора точек}}
 +
# {{level|Триангуляция Делоне}}
 +
# {{level|Диаграмма Вороного}}
 +
# {{level|Принадлежность точки многоугольнику}}
 +
# {{level|Пересечения выпуклых многоугольников}}
 +
# {{level|Пересечение звёздных многоугольников}}
 +
==Компьютерная графика==
 +
# {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}}
 +
# {{level|Алгоритм определения видимых частей трёхмерной сцены}}
 +
# {{level|Трассировка лучей - рендеринг реалистичных изображений}}
 +
# {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}}
 +
 
 +
=Исследование и моделирование компьютеров=
 +
==Тесты производительности компьютеров==
 +
# {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 +
# {{level|Linpack benchmark}}
 +
==Алгоритмы моделирования квантовых систем==
 +
# {{level|Алгоритмы моделирования квантовых вычислений}}
 +
## {{level|Однокубитное преобразование вектора-состояния}}
 +
## {{level|Двухкубитное преобразование вектора-состояния}}
 +
## {{level|Моделирование квантового преобразования Фурье}}
 +
==Алгоритмы машинного обучения==
 +
# {{level|Алгоритм k средних (k-means)}}
 +
===Нейронные сети===
 +
# {{level|Распознавание образов}}
 +
## {{level|Распознавание текста}}
 +
## {{level|Распознавание речи}}
 +
## {{level|Распознавание лиц}}
 +
===Алгоритмы теории игр===
 +
 
 +
= Прикладные задачи из разных областей =
 +
==Алгоритмы оптимизации==
 +
# {{level|Линейное программирование}}
 +
# {{level|Симплекс-метод}}
 +
# {{level|Метод ветвей и границ}}
 +
# {{level|Генетические алгоритмы}}
 +
# {{level|Муравьиные алгоритмы}}
 +
# {{level|Комбинированные алгоритмы}}
 +
# {{level|Стохастическое двойственное динамическое программирование (SDDP)}}
 +
==Решение систем нелинейных уравнений==
 +
# {{level|Метод Ньютона для систем нелинейных уравнений}}
 +
==Численные методы интегрирования==
 +
# {{level|Квадратурные формулы}}
 +
# {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}}
 +
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]]
 +
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]]
 +
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]]
 +
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]]
 +
==Алгоритмы решения уравнений математической физики==
 +
# {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}}
 +
=Криптографические алгоритмы=
 +
# {{level|Метод встречи посередине}}
 +
=Другие алгоритмы=
  
 
[[en:Algorithm classification]]
 
[[en:Algorithm classification]]
 +
 +
[[Категория:Алгоритмы|*]]

Текущая версия на 22:20, 25 декабря 2018

Перенаправление на:

Содержание

1 Задачи алгебры

1.1 Матричные и векторные операции

1.1.1 Векторные операции

  1. Уровень метода Суммирование сдваиванием
    1. Уровень алгоритма Нахождение суммы элементов массива сдваиванием
    2. Уровень алгоритма Нахождение частных сумм элементов массива сдваиванием
  2. Уровень алгоритма Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
  3. Уровень алгоритма Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
  4. Уровень алгоритма Последовательно-параллельный метод суммирования

1.1.2 Умножения матриц на вектор

1.1.2.1 Умножения неособенных матриц на вектор

  1. Уровень алгоритма Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)

1.1.2.2 Умножения матриц специального вида на вектор

  1. Преобразование Фурье
    1. Быстрое преобразование Фурье для составной размерности
      1. Уровень метода Быстрое преобразование Фурье для степеней двойки
        1. Уровень алгоритма Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки
        2. Быстрое преобразование Фурье для чётных степеней двойки
      2. Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)
    2. Быстрое преобразование Фурье для простой размерности

1.1.3 Матричные операции

  1. Уровень задачи Умножение плотных матриц
    1. Уровень алгоритма Перемножение плотных неособенных матриц (последовательный вещественный вариант)
    2. Метод Штрассена

1.2 Разложения матриц

Уровень задачи Задача разложения матриц

  1. Уровень задачи Треугольные разложения
    1. Уровень метода Метод Гаусса (нахождение LU-разложения)
      1. Уровень метода LU-разложение методом Гаусса без перестановок
        1. Уровень алгоритма LU-разложение методом Гаусса
        2. Уровень метода Компактная схема метода Гаусса и её модификации
          1. Компактная схема метода Гаусса для плотной матрицы
          2. Уровень метода Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации
            1. Уровень алгоритма Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант
            2. Уровень алгоритма Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы
            3. Уровень метода Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы
      2. Уровень метода LU-разложение методом Гаусса с перестановками
        1. Уровень алгоритма LU-разложение методом Гаусса с выбором ведущего элемента по столбцу
        2. Уровень алгоритма LU-разложение методом Гаусса с выбором ведущего элемента по строке
        3. Уровень алгоритма LU-разложение методом Гаусса с выбором ведущего элемента по главной диагонали
        4. Уровень алгоритма LU-разложение методом Гаусса с выбором ведущего элемента по всей матрице
    2. Уровень метода Метод Холецкого (нахождение симметричного треугольного разложения)
      1. Уровень алгоритма Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
  2. Известные треугольные разложения для матриц специального вида
  3. Уровень задачи Унитарно-треугольные разложения
    1. Уровень задачи QR-разложения плотных неособенных матриц
      1. Уровень метода Метод Гивенса (вращений) QR-разложения матрицы
        1. Уровень алгоритма Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)
      2. Уровень метода Метод Хаусхолдера (отражений) QR-разложения матрицы
        1. Уровень алгоритма Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант
      3. Уровень метода Метод ортогонализации
        1. Уровень алгоритма Классический метод ортогонализации
        2. Уровень алгоритма Метод ортогонализации с переортогонализацией
      4. Уровень метода Метод треугольного разложения матрицы Грама
    2. Уровень задачи Методы QR-разложения плотных хессенберговых матриц
      1. Уровень метода Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)
      2. Уровень метода Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)
  4. Уровень задачи Разложения, содержащие матрицу, подобную исходной
    1. Уровень задачи Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной
      1. Уровень метода Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме
        1. Уровень алгоритма Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме
      2. Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме
        1. Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме
    2. Уровень задачи Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной
      1. Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду
        1. Уровень алгоритма Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду
        2. Уровень алгоритма Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду
      2. Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме
    3. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
  5. Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной
    1. Разложения на две унитарные и одну двухдиагональную матрицы
      1. Уровень алгоритма Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме
      2. Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме
    2. Разложения на две унитарные и одну диагональную матрицы
      1. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
        1. Методы нахождения сингулярных чисел двухдиагональных матриц
          1. Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы
            1. Уровень алгоритма Итерация алгоритма dqds

1.3 Решение систем линейных уравнений

  1. Прямые методы решения СЛАУ
    1. Уровень алгоритма Linpack benchmark
    2. Методы решения СЛАУ с матрицами специального вида
      1. Методы решения СЛАУ с треугольными матрицами
        1. Уровень алгоритма Прямая подстановка (вещественный вариант)
        2. Уровень алгоритма Обратная подстановка (вещественный вариант)
        3. Методы решения СЛАУ с двудиагональными матрицами
          1. Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей
          2. Уровень алгоритма Метод сдваивания Стоуна для решения двудиагональных СЛАУ
          3. Последовательно-параллельный вариант обратной подстановки
      2. Уровень задачи Методы решения СЛАУ с трёхдиагональными матрицами
        1. Методы, основанные на стандартном LU-разложении матрицы
          1. Уровень метода Прогонка
            1. Уровень алгоритма Прогонка, точечный вариант
            2. Уровень алгоритма Классическая монотонная прогонка, повторный вариант
          2. Уровень метода Метод сдваивания Стоуна
            1. Уровень алгоритма Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы
            2. Уровень алгоритма Метод сдваивания Стоуна для решения двудиагональных СЛАУ
          3. Уровень метода Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками
        2. Другие методы
          1. Метод редукции
            1. Полный метод редукции
            2. Повторный метод редукции для новой правой части
          2. Встречная прогонка
            1. Уровень алгоритма Встречная прогонка, точечный вариант
            2. Уровень алгоритма Повторная встречная прогонка, точечный вариант
          3. Метод циклической редукции
            1. Уровень алгоритма Полный метод циклической редукции
            2. Повторный метод циклической редукции для новой правой части
          4. Метод окаймления
      3. Методы решения СЛАУ с блочно-треугольными матрицами
        1. Блочная прямая подстановка (вещественный вариант)
        2. Блочная обратная подстановка (вещественный вариант)
        3. Методы решения СЛАУ с блочно-двухдиагональными матрицами
          1. Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей
          2. Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ
          3. Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ
      4. Методы решения СЛАУ с блочно-трёхдиагональными матрицами
        1. Методы, основанные на стандартном LU-разложении матрицы
          1. Уровень алгоритма Блочная прогонка
          2. Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками
        2. Другие методы
          1. Уровень алгоритма Встречная прогонка, блочный вариант
          2. Блочный метод циклической редукции
          3. Блочный метод окаймления
    3. Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
  2. Итерационные методы решения СЛАУ
    1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
    2. Уровень алгоритма Стабилизированный метод бисопряженных градиентов (BiCGStab)
    3. Уровень алгоритма Алгоритм_Качмажа

1.4 Решения спектральных задач

  1. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
    1. Уровень метода QR-алгоритм
      1. Уровень алгоритма QR-алгоритм, используемый в SCALAPACK
        1. Уровень алгоритма Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме
        2. Уровень алгоритма QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK
      2. Уровень алгоритма QR-алгоритм для симметричных матриц, используемый в SCALAPACK
        1. Уровень алгоритма Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду
        2. QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK
      3. Уровень алгоритма QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK
        1. Уровень алгоритма Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду
        2. QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK
    2. Уровень метода Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц
      1. Уровень алгоритма Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице
      2. Уровень алгоритма Метод Якоби (вращений) для симметричных матриц с циклическим исключением
      3. Уровень алгоритма Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами
    3. Метод Ланцоша
      1. Уровень алгоритма Алгоритм Ланцоша для точной арифметики (без переортогонализации)
  2. Частичная спектральная задача
    1. Метод бисекций
  3. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
    1. Уровень метода Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц
      1. Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором
      2. Метод Якоби для нахождения сингулярных значений со специальным подбором вращений
    2. QR-алгоритм в приложении к сингулярному разложению

1.5 Алгебра многочленов

  1. Уровень алгоритма Схема Горнера, вещественная версия, последовательный вариант

2 Алгоритмы на списках и массивах

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

  1. Линейный поиск - находит элемент в любом списке, [math]O(n)[/math]
  2. Двоичный поиск - находит элемент в отсортированном списке, [math]O(\log(n))[/math]

2.2 Алгоритмы сортировки

  1. Сортировка с помощью двоичного дерева
  2. Сортировка пузырьком
  3. Сортировка слиянием (последовательный и параллельный варианты)

2.3 Алгоритмы на графах

  1. Обход графа
    1. Уровень алгоритма Поиск в ширину (BFS)
    2. Уровень алгоритма Поиск в глубину (DFS)
  2. Уровень задачи Поиск кратчайшего пути от одной вершины (SSSP)
    1. Уровень алгоритма Поиск в ширину (BFS) (для невзвешенных графов)
    2. Уровень алгоритма Алгоритм Дейкстры
    3. Уровень алгоритма Алгоритм Беллмана-Форда
    4. Уровень алгоритма Алгоритм Δ-шагания
  3. Уровень задачи Поиск кратчайшего пути для всех пар вершин (APSP)
    1. Уровень алгоритма Алгоритм Джонсона
    2. Уровень алгоритма Алгоритм Флойда-Уоршелла
  4. Уровень задачи Поиск транзитивного замыкания орграфа
    1. Уровень алгоритма Алгоритм Пурдома
  5. Уровень алгоритма Определение диаметра графа
  6. Уровень задачи Построение минимального остовного дерева (MST)
    1. Уровень алгоритма Алгоритм Борувки
    2. Уровень алгоритма Алгоритм Крускала
    3. Уровень алгоритма Алгоритм Прима
    4. Уровень алгоритма Алгоритм GHS
  7. Уровень задачи Поиск изоморфных подграфов
    1. Уровень алгоритма Алгоритм Ульмана
    2. Уровень алгоритма Алгоритм VF2
  8. Уровень задачи Связность в графах
    1. Уровень алгоритма Алгоритм Шилоаха-Вишкина поиска компонент связности
    2. Уровень алгоритма Система непересекающихся множеств
    3. Уровень алгоритма Алгоритм Тарьяна поиска компонент сильной связности
    4. Уровень алгоритма Алгоритм DCSC поиска компонент сильной связности
    5. Уровень алгоритма Алгоритм Тарьяна поиска компонент двусвязности
    6. Уровень алгоритма Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
    7. Уровень алгоритма Алгоритм Тарьяна поиска «мостов» в графе
    8. Уровень алгоритма Определение вершинной связности графа
    9. Уровень алгоритма Алгоритм Габова определения рёберной связности графа
  9. Уровень задачи Поиск максимального потока в транспортной сети
    1. Уровень алгоритма Алгоритм Форда-Фалкерсона
    2. Уровень алгоритма Алгоритм проталкивания предпотока
  10. Уровень задачи Поиск потока минимальной стоимости в транспортной сети
  11. Уровень задачи Задача о назначениях
    1. Уровень алгоритма Венгерский алгоритм
    2. Уровень алгоритма Алгоритм аукциона
    3. Уровень алгоритма Алгоритм Гопкрофта-Карпа
  12. Вычисление betweenness centrality

3 Вычислительная геометрия

  1. Поиск диаметра множества точек
  2. Построение выпуклой оболочки набора точек
  3. Триангуляция Делоне
  4. Диаграмма Вороного
  5. Принадлежность точки многоугольнику
  6. Пересечения выпуклых многоугольников
  7. Пересечение звёздных многоугольников

3.1 Компьютерная графика

  1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
  2. Алгоритм определения видимых частей трёхмерной сцены
  3. Трассировка лучей - рендеринг реалистичных изображений
  4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов

4 Исследование и моделирование компьютеров

4.1 Тесты производительности компьютеров

  1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
  2. Уровень алгоритма Linpack benchmark

4.2 Алгоритмы моделирования квантовых систем

  1. Алгоритмы моделирования квантовых вычислений
    1. Уровень алгоритма Однокубитное преобразование вектора-состояния
    2. Уровень алгоритма Двухкубитное преобразование вектора-состояния
    3. Моделирование квантового преобразования Фурье

4.3 Алгоритмы машинного обучения

  1. Уровень алгоритма Алгоритм k средних (k-means)

4.3.1 Нейронные сети

  1. Распознавание образов
    1. Распознавание текста
    2. Распознавание речи
    3. Уровень алгоритма Распознавание лиц

4.3.2 Алгоритмы теории игр

5 Прикладные задачи из разных областей

5.1 Алгоритмы оптимизации

  1. Линейное программирование
  2. Симплекс-метод
  3. Метод ветвей и границ
  4. Генетические алгоритмы
  5. Муравьиные алгоритмы
  6. Комбинированные алгоритмы
  7. Уровень алгоритма Стохастическое двойственное динамическое программирование (SDDP)

5.2 Решение систем нелинейных уравнений

  1. Уровень алгоритма Метод Ньютона для систем нелинейных уравнений

5.3 Численные методы интегрирования

  1. Уровень алгоритма Квадратурные формулы
  2. Уровень алгоритма Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
    1. Метод прямоугольников
    2. Метод трапеций
    3. Метод парабол (метод Симпсона)
    4. Метод Гаусса

5.4 Алгоритмы решения уравнений математической физики

  1. Уровень алгоритма Уравнение Пуассона, решение дискретным преобразованием Фурье

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

  1. Уровень алгоритма Метод встречи посередине

7 Другие алгоритмы