Algorithm classification: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Новая страница: «# <div id="Векторные операции">'''Векторные операции'''</div> ## ''Суммирование сдваиванием'' ### {{level…»)
 
Строка 1: Строка 1:
−
# <div id="Векторные операции">'''Векторные операции'''</div>
+
# <div id="Векторные операции">'''Vector operations'''</div>
−
## ''Суммирование сдваиванием''
+
## ''Pairwise summation''
−
### {{level|Нахождение суммы элементов массива сдваиванием}}
+
### {{level|Summing an array by pairwise summation}}
−
### {{level|Нахождение частных сумм элементов массива сдваиванием}}
+
### {{level|Finding partial sums of an array by pairwise summation}}
−
## {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}}
+
## {{level|Uniform norm of a vector: Real version, serial-parallel variant}}
−
## {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}}
+
## {{level|Dot product: Real version, serial-parallel variant}}
−
## {{level|Последовательно-параллельный метод суммирования}}
+
## {{level|Serial-parallel summation method}}
−
# <div id="Матрично-векторные операции">'''Матрично-векторные операции'''</div>
+
# <div id="Матрично-векторные операции">'''Matrix-vector operations'''</div>
−
## {{level|Умножение плотной матрицы на вектор}}
+
## {{level|Dense matrix-vector multiplication}}
−
# <div id="Матричные операции">'''Матричные операции'''</div>
+
# <div id="Матричные операции">'''Matrix operations'''</div>
−
## {{level|Умножение плотных матриц}}
+
## {{level|Dense matrix multiplication}}
−
# <div id="Разложения матриц">'''Разложения матриц'''</div>
+
# <div id="Разложения матриц">'''Matrix factorizations'''</div>
−
## ''Треугольные разложения''
+
## ''Triangular decompositions''
−
### Метод Гаусса (нахождение LU-разложения)
+
### Gaussian elimination (finding the LU decomposition)
−
#### {{level|Метод Гаусса без перестановок}}
+
#### {{level|Gaussian elimination without pivoting}}
−
##### LU-разложение методом Гаусса
+
##### LU decomposition via Gaussian elimination
−
##### Компактная схема метода Гаусса и её модификации
+
##### Compact scheme for Gaussian elimination and its modifications
−
###### Компактная схема метода Гаусса для плотной матрицы
+
###### Compact scheme for Gaussian elimination: Dense matrix
−
###### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации}}
+
###### {{level|Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix}}
−
####### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант}}
+
####### {{level|Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant}}
−
####### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}
+
####### {{level|Stone doubling algorithm for the LU decomposition of a tridiagonal matrix}}
−
####### {{level|Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы}}
+
####### {{level|Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix}}
−
#### Метод Гаусса с перестановками
+
#### Gaussian elimination with pivoting
−
##### Метод Гаусса с выбором ведущего элемента по столбцу
+
##### Gaussian elimination with column pivoting
−
##### Метод Гаусса с выбором ведущего элемента по строке
+
##### Gaussian elimination with row pivoting
 
##### Метод Гаусса с выбором ведущего элемента по главной диагонали
 
##### Метод Гаусса с выбором ведущего элемента по главной диагонали
 
##### Метод Гаусса с выбором ведущего элемента по всей матрице
 
##### Метод Гаусса с выбором ведущего элемента по всей матрице

Версия 14:35, 8 апреля 2016

  1. Vector operations
    1. Pairwise summation
      1. Summing an array by pairwise summation
      2. Finding partial sums of an array by pairwise summation
    2. Uniform norm of a vector: Real version, serial-parallel variant
    3. Dot product: Real version, serial-parallel variant
    4. Serial-parallel summation method
  2. Matrix-vector operations
    1. Dense matrix-vector multiplication
  3. Matrix operations
    1. Dense matrix multiplication
  4. Matrix factorizations
    1. Triangular decompositions
      1. Gaussian elimination (finding the LU decomposition)
        1. Gaussian elimination without pivoting
          1. LU decomposition via Gaussian elimination
          2. Compact scheme for Gaussian elimination and its modifications
            1. Compact scheme for Gaussian elimination: Dense matrix
            2. Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix
              1. Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant
              2. Stone doubling algorithm for the LU decomposition of a tridiagonal matrix
              3. Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix
        2. Gaussian elimination with pivoting
          1. Gaussian elimination with column pivoting
          2. Gaussian elimination with row pivoting
          3. Метод Гаусса с выбором ведущего элемента по главной диагонали
          4. Метод Гаусса с выбором ведущего элемента по всей матрице
      2. Уровень метода Метод Холецкого (нахождение симметричного треугольного разложения)
        1. Уровень алгоритма Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
      3. Известные треугольные разложения для матриц специального вида
    2. Унитарно-треугольные разложения
      1. Уровень метода Метод Гивенса (вращений) QR-разложения матрицы
      2. Уровень метода Метод Хаусхолдера (отражений) QR-разложения матрицы
    3. Разложения на унитарные и хессенберговы матрицы
      1. Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме
      2. Метод Гивенса (вращений) приведения матрицы к хессенберговой (двухдиагональной) форме
    4. Разложения на унитарные и диагональные матрицы
      1. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
      2. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
  5. Решение систем линейных уравнений
    1. Прямые методы решения СЛАУ
      1. Уровень алгоритма Linpack benchmark
      2. Методы решения СЛАУ с матрицами специального вида
        1. Методы решения СЛАУ с треугольными матрицами
          1. Уровень алгоритма Прямая подстановка (вещественный вариант)
          2. Уровень алгоритма Обратная подстановка (вещественный вариант)
          3. Методы решения СЛАУ с двухдиагональными матрицами
            1. Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей
            2. Метод сдваивания Стоуна для решения двухдиагональных СЛАУ
            3. Последовательно-параллельный вариант обратной подстановки
        2. Уровень задачи Методы решения СЛАУ с трёхдиагональными матрицами
          1. Методы, основанные на стандартном LU-разложении матрицы
            1. Уровень метода Прогонка
              1. Уровень алгоритма Прогонка, точечный вариант
              2. Повторная прогонка, точечный вариант
            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
  6. Решения спектральных задач
    1. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
      1. Уровень метода QR-алгоритм
      2. Метод Гивенса (вращений) для решения спектральной задачи у симметричных матриц
    2. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
  7. Тесты производительности компьютеров
    1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
    2. Уровень алгоритма Linpack benchmark
  8. Преобразование Фурье
    1. Уровень метода Быстрое преобразование Фурье для степеней двойки
  9. Алгебра многочленов
    1. Уровень алгоритма Схема Горнера, вещественная версия, последовательный вариант
  10. Численные методы интегрирования
    1. Уровень алгоритма Квадратурные формулы
    2. Уровень алгоритма Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
      1. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
      2. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
      3. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
      4. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
  11. Алгоритмы на графах
    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
  12. Алгоритмы поиска
    1. Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
  13. Алгоритмы сортировки
    1. Сортировка с помощью двоичного дерева
    2. Сортировка пузырьком
    3. Сортировка слиянием (последовательный и параллельный варианты)
  14. Вычислительная геометрия
    1. Поиск диаметра множества точек
    2. Построение выпуклой оболочки набора точек
    3. Триангуляция Делоне
    4. Диаграмма Вороного
    5. Принадлежность точки многоугольнику
    6. Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
    7. Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]
  15. Компьютерная графика
    1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
    2. Алгоритм определения видимых частей трёхмерной сцены
    3. Трассировка лучей - рендеринг реалистичных изображений
    4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
  16. Криптографические алгоритмы
  17. Нейронные сети
  18. Алгоритмы оптимизации
    1. Линейное программирование
    2. Симплекс-метод
    3. Метод ветвей и границ (последовательный и параллельный варианты)
    4. Генетические алгоритмы
    5. Муравьиные алгоритмы
    6. Комбинированные алгоритмы
    7. Нахождение экстремума функции
  19. Алгоритмы теории игр
  20. Алгоритмы моделирования квантовых систем
    1. Алгоритмы моделирования квантовых вычислений
      1. Уровень алгоритма Однокубитное преобразование вектора-состояния
      2. Уровень алгоритма Двухкубитное преобразование вектора-состояния
      3. Моделирование квантового преобразования Фурье
  21. Алгоритмы решения уравнений математической физики
    1. Уровень алгоритма Уравнение Пуассона, решение дискретным преобразованием Фурье
  22. Другие алгоритмы
Источник — https://algowiki-project.org/w/ru/index.php?title=Algorithm_classification&oldid=3420