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