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

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

Версия 13:10, 15 марта 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 Другие алгоритмы