Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
| [выверенная версия] | [досмотренная версия] |
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]] | ||
Версия 13:03, 17 декабря 2015
- Векторные операции
- Матрично-векторные операции
- Матричные операции
- Разложения матриц
- Треугольные разложения
- Метод Гаусса (нахождение LU-разложения)
- Метод Гаусса без перестановок
- LU-разложение методом Гаусса
- Компактная схема метода Гаусса и её модификации
- Компактная схема метода Гаусса для плотной матрицы
Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации
- Метод Гаусса с перестановками
- Метод Гаусса с выбором ведущего элемента по столбцу
- Метод Гаусса с выбором ведущего элемента по строке
- Метод Гаусса с выбором ведущего элемента по главной диагонали
- Метод Гаусса с выбором ведущего элемента по всей матрице
- Метод Гаусса без перестановок
- Метод Холецкого (нахождение симметричного треугольного разложения)
Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- Известные треугольные разложения для матриц специального вида
- Метод Гаусса (нахождение LU-разложения)
- Унитарно-треугольные разложения
- Разложения на унитарные и хессенберговы матрицы
- Разложения на унитарные и диагональные матрицы
- Треугольные разложения
- Решение систем линейных уравнений
- Прямые методы решения СЛАУ
- Linpack benchmark
- Методы решения СЛАУ с матрицами специального вида
- Методы решения СЛАУ с треугольными матрицами
- Прямая подстановка (вещественный вариант)
- Обратная подстановка (вещественный вариант)
- Методы решения СЛАУ с двухдиагональными матрицами
Методы решения СЛАУ с трёхдиагональными матрицами
- Методы, основанные на стандартном LU-разложении матрицы
- Другие методы
- Методы решения СЛАУ с блочно-треугольными матрицами
- Блочная прямая подстановка (вещественный вариант)
- Блочная обратная подстановка (вещественный вариант)
- Методы решения СЛАУ с блочно-двухдиагональными матрицами
- Методы решения СЛАУ с блочно-трёхдиагональными матрицами
- Методы, основанные на стандартном LU-разложении матрицы
- Другие методы
- Методы решения СЛАУ с треугольными матрицами
- Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
- Итерационные методы решения СЛАУ
- Прямые методы решения СЛАУ
- Тесты производительности компьютеров
- Преобразование Фурье
- Алгебра многочленов
- Численные методы интегрирования
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
- Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
- Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
- Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
- Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
- Алгоритмы на графах
- Обход графа
- Поиск кратчайшего пути от одной вершины (SSSP)
- Поиск в ширину (BFS) (для невзвешенных графов)
- Алгоритм Дейкстры
- Алгоритм Беллмана-Форда
- Алгоритм Δ-шагания
- Поиск кратчайшего пути для всех пар вершин (APSP)
- Поиск транзитивного замыкания орграфа
- Определение диаметра графа
- Построение минимального остовного дерева (MST)
- Поиск изоморфных подграфов
- Связность в графах
- Алгоритм Шилоаха-Вишкина поиска компонент связности
- Система непересекающихся множеств
- Алгоритм Тарьяна поиска компонент сильной связности
- Алгоритм DCSC поиска компонент сильной связности
- Алгоритм Тарьяна поиска компонент двусвязности
- Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
- Алгоритм Тарьяна поиска «мостов» в графе
- Определение вершинной связности графа
- Алгоритм Габова определения рёберной связности графа
- Поиск максимального потока в транспортной сети
- Поиск потока минимальной стоимости в транспортной сети
- Задача о назначениях
- Вычисление betweenness centrality
- Алгоритмы поиска
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
- Алгоритмы сортировки
- Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
- Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]
- Компьютерная графика
- Криптографические алгоритмы
- Нейронные сети
- Алгоритмы оптимизации
- Алгоритмы теории игр
- Алгоритмы моделирования квантовых систем
- Алгоритмы моделирования квантовых вычислений
- Алгоритмы решения уравнений математической физики
- Другие алгоритмы
