Классификация алгоритмов

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.  Распознавание лиц

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.  Метод встречи посередине