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

Материал из Алговики
Перейти к: навигация, поиск
  1. Векторные операции
    1. Суммирование сдваиванием
      1. Нахождение суммы элементов массива сдваиванием
      2. Нахождение частных сумм элементов массива сдваиванием
    2. Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
    3. Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
    4. Последовательно-параллельный метод суммирования
  2. Матрично-векторные операции
    1. Умножение плотной матрицы на вектор
  3. Матричные операции
    1. Умножение плотных матриц
  4. Разложения матриц
    1. Треугольные разложения
      1. Метод Гаусса (нахождение LU-разложения)
        1. Метод Гаусса без перестановок
          1. LU-разложение методом Гаусса
          2. Компактная схема метода Гаусса и её модификации
            1. Компактная схема метода Гаусса для плотной матрицы
            2. Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации
              1. Уровень алгоритма Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант
              2. Уровень алгоритма Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы
              3. Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы
        2. Метод Гаусса с перестановками
          1. Метод Гаусса с выбором ведущего элемента по столбцу
          2. Метод Гаусса с выбором ведущего элемента по строке
          3. Метод Гаусса с выбором ведущего элемента по главной диагонали
          4. Метод Гаусса с выбором ведущего элемента по всей матрице
      2. Уровень метода Метод Холецкого (нахождение симметричного треугольного разложения)
        1. Уровень алгоритма Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
      3. Известные треугольные разложения для матриц специального вида
    2. Унитарно-треугольные разложения
      1. Уровень задачи QR-разложения плотных неособенных матриц
        1. Уровень алгоритма Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный вариант)
        2. Уровень алгоритма Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный вариант
        3. Уровень метода Метод ортогонализации
          1. Уровень алгоритма Классический метод ортогонализации
          2. Уровень алгоритма Метод ортогонализации с переортогонализацией
      2. Методы QR-разложения плотных хессенберговых матриц
        1. Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)
    3. Подобные разложения на унитарные и хессенберговы матрицы
      1. Уровень алгоритма Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме
      2. Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме
    4. Симметричные разложения на унитарные и трёхдиагональные матрицы
      1. Уровень алгоритма Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду
      2. Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме
    5. Разложения на унитарные и двухдиагональные матрицы
      1. Уровень алгоритма Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме
      2. Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме
    6. Разложения на унитарные и диагональные матрицы
      1. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
      2. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
  5. Решение систем линейных уравнений
    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. Уровень алгоритма Алгоритм_Качмажа
  6. Решения спектральных задач
    1. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
      1. Уровень метода QR-алгоритм
        1. Уровень алгоритма QR-алгоритм, используемый в SCALAPACK
        2. Уровень алгоритма QR-алгоритм для симметричных матриц, используемый в SCALAPACK
      2. Уровень метода Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц
      3. Уровень алгоритма Алгоритм Ланцоша для точной арифметики (без переортогонализации)
      4. Частичная спектральная задача
        1. Метод бисекций
    2. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
      1. Уровень метода Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц
      2. QR-алгоритм в приложении к сингулярному разложению
  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. Линейный поиск - находит элемент в любом списке, O(n)
    2. Двоичный поиск - находит элемент в отсортированном списке, O(log(n))
  13. Алгоритмы сортировки
    1. Сортировка с помощью двоичного дерева
    2. Сортировка пузырьком
    3. Сортировка слиянием (последовательный и параллельный варианты)
  14. Вычислительная геометрия
    1. Поиск диаметра множества точек
    2. Построение выпуклой оболочки набора точек
    3. Триангуляция Делоне
    4. Диаграмма Вороного
    5. Принадлежность точки многоугольнику
    6. Пересечения выпуклых многоугольников - трудоёмкость O(n_1 + n_2)
    7. Пересечение звёздных многоугольников - трудоёмкость O(n_1 * n_2)
  15. Компьютерная графика
    1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
    2. Алгоритм определения видимых частей трёхмерной сцены
    3. Трассировка лучей - рендеринг реалистичных изображений
    4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
  16. Криптографические алгоритмы
  17. Нейронные сети
  18. Алгоритмы оптимизации
    1. Линейное программирование
    2. Симплекс-метод
    3. Метод ветвей и границ (последовательный и параллельный варианты)
    4. Генетические алгоритмы
    5. Муравьиные алгоритмы
    6. Комбинированные алгоритмы
    7. Нахождение экстремума функции
  19. Алгоритмы теории игр
  20. Алгоритмы моделирования квантовых систем
    1. Алгоритмы моделирования квантовых вычислений
      1. Уровень алгоритма Однокубитное преобразование вектора-состояния
      2. Уровень алгоритма Двухкубитное преобразование вектора-состояния
      3. Моделирование квантового преобразования Фурье
  21. Алгоритмы решения уравнений математической физики
    1. Уравнение Пуассона, решение дискретным преобразованием Фурье
  22. Другие алгоритмы