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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
← Предыдущая правкаСледующая правка →
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
== Векторные операции ==
# <div id="Векторные операции">'''Векторные операции'''</div>
 
## [[Суммирование сдваиванием]]
# [[Суммирование сдваиванием]]
## [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]]
# [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]]
## [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]
# [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]
## [[Последовательно-параллельный метод суммирования]]
# [[Последовательно-параллельный метод суммирования]]
# <div id="Умножение матрицы на вектор">'''Умножение матрицы на вектор'''</div>
 
## [[Умножение плотной матрицы на вектор]]
== Умножение матрицы на вектор ==
# <div id="Матричные операции">'''Матричные операции'''</div>
 
## [[Умножение плотных матриц]]
# [[Умножение плотной матрицы на вектор]]
# <div id="Разложения матриц">'''Разложения матриц'''</div>
 
## ''Треугольные разложения''
== Матричные операции ==
### [[Метод Холецкого (нахождение симметричного треугольного разложения)]]
 
#### [[Разложение Холецкого (метод квадратного корня)]] базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
# [[Умножение плотных матриц]]
## ''Унитарно-треугольные разложения''
 
### [[Метод Гивенса (вращений) QR-разложения матрицы]]
== Разложения матриц ==
### [[Метод Хаусхолдера (отражений) QR-разложения матрицы]]
 
## ''Разложения на унитарные и хессенберговы матрицы''
=== Треугольные разложения ===
### [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме]]
 
## ''Разложения на унитарные и диагональные матрицы''
# [[Метод Холецкого (нахождение симметричного треугольного разложения)]]
### [[Спектральное разложение (нахождение собственных значений и векторов)]]
## [[Разложение Холецкого (метод квадратного корня)]] базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
### [[Сингулярное разложение (нахождение сингулярных значений и векторов)]]
 
# <div id="Решение систем линейных уравнений">'''Решение систем линейных уравнений'''</div>
=== Унитарно-треугольные разложения ===
## [[High Performance Conjugate Gradient (HPCG) benchmark]]
 
## [[Linpack benchmark]]
# [[Метод Гивенса (вращений) QR-разложения матрицы]]
## [[Метод Гаусса решения СЛАУ (прямой ход)]]
# [[Метод Хаусхолдера (отражений) QR-разложения матрицы]]
## [[Обратная подстановка (вещественный вариант)|Обратная подстановка]]
 
# <div id="Тесты производительности компьютеров">'''Тесты производительности компьютеров'''</div>
=== Разложения на унитарные и хессенберговы матрицы ===
## [[High Performance Conjugate Gradient (HPCG) benchmark]]
 
## [[Linpack benchmark]]
# [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме]]
# <div id="Преобразование Фурье">'''Преобразование Фурье'''</div>
 
## [[Быстрое преобразование Фурье для степеней двойки]]
=== Разложения на унитарные и диагональные матрицы ===
# <div id="Алгебра многочленов">'''Алгебра многочленов'''</div>
 
## [[Схема Горнера, вещественная версия, последовательный вариант|Схема Горнера]]
# [[Спектральное разложение (нахождение собственных значений и векторов)]]
# <div id="Численные методы интегрирования">'''Численные методы интегрирования'''</div>
# [[Сингулярное разложение (нахождение сингулярных значений и векторов)]]
## [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]]
 
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод прямоугольников]]
== Решение систем линейных уравнений ==
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод трапеций]]
 
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод парабол (метод Симпсона)]]
# [[High Performance Conjugate Gradient (HPCG) benchmark]]
### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод Гаусса]]
# [[Linpack benchmark]]
# <div id="Алгоритмы на графах">'''Алгоритмы на графах'''</div>
# [[Метод Гаусса решения СЛАУ (прямой ход)]]
## [[Алгоритм вычисления кратчайшего пути во взвешенном графе]]
# [[Обратная подстановка (вещественный вариант)|Обратная подстановка]]
## [[Алгоритм обхода графа]]
 
# <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div>
== Тесты производительности компьютеров ==
## [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math>
 
# <div id="Алгоритмы сортировки">'''Алгоритмы сортировки'''</div>
# [[High Performance Conjugate Gradient (HPCG) benchmark]]
## [[Сортировка с помощью двоичного дерева]]
# [[Linpack benchmark]]
## [[Сортировка пузырьком]]
 
## [[Сортировка слиянием (последовательный и параллельный варианты)]]
== Преобразование Фурье ==
# <div id="Вычислительная геометрия">'''Вычислительная геометрия'''</div>
 
## [[Поиск диаметра множества точек]]
# [[Быстрое преобразование Фурье для степеней двойки]]
## [[Построение выпуклой оболочки набора точек]]
 
## [[Триангуляция Делоне]]
== Алгебра многочленов ==
## [[Диаграмма Вороного]]
 
## [[Принадлежность точки многоугольнику]]
# [[Схема Горнера, вещественная версия, последовательный вариант|Схема Горнера]]
## [[Пересечения выпуклых многоугольников]] - трудоёмкость <math>O(n_1 + n_2)</math>
 
## [[Пересечение звёздных многоугольников]] - трудоёмкость <math>O(n_1 * n_2)</math>
== Численные методы интегрирования ==
# <div id="Компьютерная графика">'''Компьютерная графика'''</div>
 
## [[Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности]]
# [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]]
## [[Алгоритм определения видимых частей трёхмерной сцены]]
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод прямоугольников]]
## [[Трассировка лучей - рендеринг реалистичных изображений]]
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод трапеций]]
## [[Глобальное освещение - рассматривает прямое освещение и отражение от других объектов]]
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод парабол (метод Симпсона)]]
# <div id="Криптографические алгоритмы">'''Криптографические алгоритмы'''</div>
## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод Гаусса]]
# <div id="Нейронные сети">'''Нейронные сети'''</div>
 
# <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div>
== Алгоритмы на графах ==
## [[Линейное программирование]]
 
## [[Симплекс-метод]]
# [[Алгоритм вычисления кратчайшего пути во взвешенном графе]]
## [[Метод ветвей и границ (последовательный и параллельный варианты)]]
# [[Алгоритм обхода графа]]
## [[Генетические алгоритмы]]
 
## [[Муравьиные алгоритмы]]
== Алгоритмы поиска ==
## [[Комбинированные алгоритмы]]
 
## [[Нахождение экстремума функции]]
# [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math>
# <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div>
 
# <div id="Алгоритмы моделирования квантовых систем">'''Алгоритмы моделирования квантовых систем'''</div>
== Алгоритмы сортировки ==
## ''Алгоритмы моделирования квантовых вычислений''
 
### [[Однокубитное преобразование вектора-состояния]]
# [[Сортировка с помощью двоичного дерева]]
### [[Двухкубитное преобразование вектора-состояния]]
# [[Сортировка пузырьком]]
### [[Моделирование квантового преобразования Фурье]]
# [[Сортировка слиянием (последовательный и параллельный варианты)]]
# <div id="Алгоритмы решения уравнений математической физики">'''Алгоритмы решения уравнений математической физики'''</div>
 
## [[Уравнение Пуассона, решение дискретным преобразованием Фурье]]
== Вычислительная геометрия ==
# <div id="Другие алгоритмы">'''Другие алгоритмы'''</div>
 
# [[Поиск диаметра множества точек]]
# [[Построение выпуклой оболочки набора точек]]
# [[Триангуляция Делоне]]
# [[Диаграмма Вороного]]
# [[Принадлежность точки многоугольнику]]
# [[Пересечения выпуклых многоугольников]] - трудоёмкость <math>O(n_1 + n_2)</math>
# [[Пересечение звёздных многоугольников]] - трудоёмкость <math>O(n_1 * n_2)</math>
 
== Компьютерная графика ==
 
# [[Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности]]
# [[Алгоритм определения видимых частей трёхмерной сцены]]
# [[Трассировка лучей - рендеринг реалистичных изображений]]
# [[Глобальное освещение - рассматривает прямое освещение и отражение от других объектов]]
 
== Криптографические алгоритмы ==
 
== Нейронные сети ==
 
== Алгоритмы оптимизации ==
 
# [[Линейное программирование]]
# [[Симплекс-метод]]
# [[Метод ветвей и границ (последовательный и параллельный варианты)]]
# [[Генетические алгоритмы]]
# [[Муравьиные алгоритмы]]
# [[Комбинированные алгоритмы]]
# [[Нахождение экстремума функции]]
 
== Алгоритмы теории игр ==
 
== Алгоритмы моделирования квантовых систем ==
 
=== Алгоритмы моделирования квантовых вычислений ===
#[[Однокубитное преобразование вектора-состояния]]
#[[Двухкубитное преобразование вектора-состояния]]
#[[Моделирование квантового преобразования Фурье]]
 
== Алгоритмы решения уравнений математической физики ==
# [[Уравнение Пуассона, решение дискретным преобразованием Фурье]]
 
 
== Другие алгоритмы ==


[[en:Algorithm classification]]
[[en:Algorithm classification]]

Версия от 13:18, 28 марта 2015

  1. Векторные операции
    1. Суммирование сдваиванием
    2. Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
    3. Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
    4. Последовательно-параллельный метод суммирования
  2. Умножение матрицы на вектор
    1. Умножение плотной матрицы на вектор
  3. Матричные операции
    1. Умножение плотных матриц
  4. Разложения матриц
    1. Треугольные разложения
      1. Метод Холецкого (нахождение симметричного треугольного разложения)
        1. Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
    2. Унитарно-треугольные разложения
      1. Метод Гивенса (вращений) QR-разложения матрицы
      2. Метод Хаусхолдера (отражений) QR-разложения матрицы
    3. Разложения на унитарные и хессенберговы матрицы
      1. Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме
    4. Разложения на унитарные и диагональные матрицы
      1. Спектральное разложение (нахождение собственных значений и векторов)
      2. Сингулярное разложение (нахождение сингулярных значений и векторов)
  5. Решение систем линейных уравнений
    1. High Performance Conjugate Gradient (HPCG) benchmark
    2. Linpack benchmark
    3. Метод Гаусса решения СЛАУ (прямой ход)
    4. Обратная подстановка
  6. Тесты производительности компьютеров
    1. High Performance Conjugate Gradient (HPCG) benchmark
    2. Linpack benchmark
  7. Преобразование Фурье
    1. Быстрое преобразование Фурье для степеней двойки
  8. Алгебра многочленов
    1. Схема Горнера
  9. Численные методы интегрирования
    1. Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
      1. Метод прямоугольников
      2. Метод трапеций
      3. Метод парабол (метод Симпсона)
      4. Метод Гаусса
  10. Алгоритмы на графах
    1. Алгоритм вычисления кратчайшего пути во взвешенном графе
    2. Алгоритм обхода графа
  11. Алгоритмы поиска
    1. Двоичный поиск - находит элемент в отсортированном списке, [math]\displaystyle{ O(log(n)) }[/math]
  12. Алгоритмы сортировки
    1. Сортировка с помощью двоичного дерева
    2. Сортировка пузырьком
    3. Сортировка слиянием (последовательный и параллельный варианты)
  13. Вычислительная геометрия
    1. Поиск диаметра множества точек
    2. Построение выпуклой оболочки набора точек
    3. Триангуляция Делоне
    4. Диаграмма Вороного
    5. Принадлежность точки многоугольнику
    6. Пересечения выпуклых многоугольников - трудоёмкость [math]\displaystyle{ O(n_1 + n_2) }[/math]
    7. Пересечение звёздных многоугольников - трудоёмкость [math]\displaystyle{ O(n_1 * n_2) }[/math]
  14. Компьютерная графика
    1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
    2. Алгоритм определения видимых частей трёхмерной сцены
    3. Трассировка лучей - рендеринг реалистичных изображений
    4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
  15. Криптографические алгоритмы
  16. Нейронные сети
  17. Алгоритмы оптимизации
    1. Линейное программирование
    2. Симплекс-метод
    3. Метод ветвей и границ (последовательный и параллельный варианты)
    4. Генетические алгоритмы
    5. Муравьиные алгоритмы
    6. Комбинированные алгоритмы
    7. Нахождение экстремума функции
  18. Алгоритмы теории игр
  19. Алгоритмы моделирования квантовых систем
    1. Алгоритмы моделирования квантовых вычислений
      1. Однокубитное преобразование вектора-состояния
      2. Двухкубитное преобразование вектора-состояния
      3. Моделирование квантового преобразования Фурье
  20. Алгоритмы решения уравнений математической физики
    1. Уравнение Пуассона, решение дискретным преобразованием Фурье
  21. Другие алгоритмы
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Классификация_алгоритмов&oldid=1486