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

Перейти к: навигация, поиск

Содержание

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. Уровень задачиЗадача разложения матриц
  2. Уровень задачиТреугольные разложения
    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. Уровень алгоритмаРазложение Холецкого (метод квадратного корня)
  3. Известные треугольные разложения для матриц специального вида
  4. Уровень задачиУнитарно-треугольные разложения
    1. Уровень задачиQR-разложения плотных неособенных матриц
      1. Уровень методаМетод Гивенса (вращений) QR-разложения матрицы
        1. Уровень алгоритмаМетод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)
      2. Уровень методаМетод Хаусхолдера (отражений) QR-разложения матрицы
        1. Уровень алгоритмаМетод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант
      3. Уровень методаМетод ортогонализации
        1. Уровень алгоритмаКлассический метод ортогонализации
        2. Уровень алгоритмаМетод ортогонализации с переортогонализацией
      4. Уровень методаМетод треугольного разложения матрицы Грама
    2. Уровень задачиМетоды QR-разложения плотных хессенберговых матриц
      1. Уровень алгоритмаМетод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)
      2. Уровень алгоритмаМетод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)
  5. Уровень задачиРазложения, содержащие матрицу, подобную исходной
    1. Уровень задачиРазложения, содержащие хессенбергову матрицу, унитарно подобную исходной
      1. Уровень методаМетод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме
        1. Уровень алгоритмаКлассический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме
      2. Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме
        1. Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме
    2. Уровень задачиРазложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной
      1. Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду
        1. Уровень алгоритмаМетод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду
        2. Уровень алгоритмаМетод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду
      2. Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме
    3. Уровень задачиСпектральное разложение (нахождение собственных значений и векторов)
      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. Уровень алгоритмаАлгоритм Ланцоша для точной арифметики (без переортогонализации)
  6. Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной
    1. Разложения на две унитарные и одну двухдиагональную матрицы
      1. Уровень алгоритмаМетод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме
      2. Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме
    2. Разложения на две унитарные и одну диагональную матрицы
      1. Уровень задачиСингулярное разложение (нахождение сингулярных значений и векторов)
        1. Методы нахождения сингулярных чисел двухдиагональных матриц
          1. Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы
            1. Уровень алгоритмаИтерация алгоритма dqds
        2. Уровень методаМетод Якоби (вращений) для нахождения сингулярных значений неособенных матриц
          1. Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором
          2. Метод Якоби для нахождения сингулярных значений со специальным подбором вращений
        3. QR-алгоритм в приложении к сингулярному разложению

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. Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы
        1. Уровень алгоритмаИтерация алгоритма dqds
    2. Уровень методаМетод Якоби (вращений) для нахождения сингулярных значений неособенных матриц
      1. Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором
      2. Метод Якоби для нахождения сингулярных значений со специальным подбором вращений
    3. QR-алгоритм в приложении к сингулярному разложению

1.5 Алгебра многочленов

  1. Уровень алгоритмаСхема Горнера, вещественная версия, последовательный вариант

2 Алгоритмы на списках и массивах

2.1 Алгоритмы поиска

  1. Линейный поиск
  2. Уровень алгоритмаДвоичный поиск

2.2 Алгоритмы сортировки

  1. Сортировка с помощью двоичного дерева
  2. Сортировка пузырьком
  3. Сортировка слиянием (последовательный и параллельный варианты)

2.3 Алгоритмы на графах

  1. Обход графа
    1. Уровень алгоритмаПоиск в ширину (BFS)
      1. Реализация Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка Graph500 MPI.
      2. Реализация C++: Boost Graph Library (функции first search.html breadth first search, first visit.html breadth first visit).
      3. Реализация C++, MPI: parallel/doc/html/index.html Parallel Boost Graph Library (функция parallel/doc/html/breadth first search.html breadth first search).
      4. Реализация Java: WebGraph (класс ParallelBreadthFirstVisit), многопоточная реализация.
      5. Реализация Python: NetworkX (функция first search.bfs edges.html bfs edges).
      6. Реализация RCC for CPU
      7. Реализация RCC for GPU
      8. Реализация GAP
      9. Реализация Litra
      10. Реализация Java: WebGraph (класс ParallelBreadthFirstVisit), многопоточная реализация.
    2. Уровень алгоритмаПоиск в глубину (DFS)
  2. Уровень задачиПоиск кратчайшего пути от одной вершины (SSSP)
    1. Уровень алгоритмаПоиск в ширину (BFS)
      1. Реализация Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка Graph500 MPI.
      2. Реализация C++: Boost Graph Library (функции first search.html breadth first search, first visit.html breadth first visit).
      3. Реализация C++, MPI: parallel/doc/html/index.html Parallel Boost Graph Library (функция parallel/doc/html/breadth first search.html breadth first search).
      4. Реализация Java: WebGraph (класс ParallelBreadthFirstVisit), многопоточная реализация.
      5. Реализация Python: NetworkX (функция first search.bfs edges.html bfs edges).
      6. Реализация RCC for CPU
      7. Реализация RCC for GPU
      8. Реализация GAP
      9. Реализация Litra
      10. Реализация Java: WebGraph (класс ParallelBreadthFirstVisit), многопоточная реализация.
    2. Уровень алгоритмаАлгоритм Дейкстры
      1. Реализация C++, MPI: parallel/doc/html/index.html Parallel Boost Graph Library:
        1. Реализация Функция parallel/doc/html/dijkstra shortest paths.html#eager-dijkstra-s-algorithm eager dijkstra shortest paths – непосредственная реализация алгоритма Дейкстры;
        2. Реализация Функция parallel/doc/html/dijkstra shortest paths.html#crauser-et-al-s-algorithm crauser et al shortest paths – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.[1]
      2. Реализация C++: Boost Graph Library (функции shortest paths.html dijkstra shortest paths, shortest paths no color map.html dijkstra shortest paths no color map), сложность [math]O(m + n \ln n)[/math]
      3. Реализация Python: NetworkX (функция paths.weighted.single source dijkstra.html single source dijkstra).
      4. Реализация Python/C++: NetworKit (класс networkit.graph.Dijkstra).
    3. Уровень алгоритмаАлгоритм Беллмана-Форда
      1. Реализация C++: Boost Graph Library (функция ford shortest.html bellman ford shortest).
      2. Реализация Python: NetworkX (функция paths.weighted.bellman ford.html bellman ford).
      3. Реализация OpenMP Stinger
      4. Реализация Nvidia nvGraph
      5. Реализация Graph500 MPI
      6. Реализация Ligra
      7. Реализация Java: JGraphT (класс BellmanFordShortestPath).
    4. Уровень алгоритмаАлгоритм Δ-шагания
      1. Реализация C++, MPI: parallel/doc/html/index.html Parallel Boost Graph Library (функция parallel/doc/html/dijkstra shortest paths.html#delta-stepping-algorithm delta stepping shortest paths).
      2. Реализация Gap
  3. Уровень задачиПоиск кратчайшего пути для всех пар вершин (APSP)
    1. Уровень алгоритмаАлгоритм Джонсона
    2. Уровень алгоритмаАлгоритм Флойда-Уоршелла
  4. Уровень задачиПоиск транзитивного замыкания орграфа
    1. Уровень алгоритмаАлгоритм Пурдома
  5. Уровень алгоритмаОпределение диаметра графа
  6. Уровень задачиПостроение минимального остовного дерева (MST)
    1. Уровень алгоритмаАлгоритм Борувки
      1. Реализация RCC for GPU
      2. Реализация RCC for CPU
      3. Реализация C++, MPI: parallel/doc/html/index.html Parallel Boost Graph Library
    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. Вычисление центральности вершин

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. Уровень алгоритмаРаспознавание лиц

4.3.2 Алгоритмы теории игр

5 Прикладные задачи из разных областей

5.1 Алгоритмы оптимизации

  1. Линейное программирование
  2. Симплекс-метод
  3. Метод ветвей и границ
  4. Генетические алгоритмы
  5. Муравьиные алгоритмы
  6. Комбинированные алгоритмы
  7. Уровень алгоритмаСтохастическое двойственное динамическое программирование (SDDP)

5.2 Решение систем нелинейных уравнений

  1. Уровень алгоритмаМетод Ньютона для систем нелинейных уравнений

5.3 Численные методы интегрирования

  1. Уровень алгоритмаКвадратурные формулы
  2. Уровень алгоритмаКвадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)

5.4 Алгоритмы решения уравнений математической физики

  1. Уровень алгоритмаУравнение Пуассона, решение дискретным преобразованием Фурье

6 Криптографические алгоритмы

  1. Уровень алгоритмаМетод встречи посередине

7 Другие алгоритмы

  1. Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.