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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(→‎Алгоритмы на графах: Алгоритм Пурдома)
Строка 62: Строка 62:
 
### [[Алгоритм Флойда-Уоршелла]]
 
### [[Алгоритм Флойда-Уоршелла]]
 
## [[Поиск транзитивного замыкания орграфа]]
 
## [[Поиск транзитивного замыкания орграфа]]
 +
### [[Алгоритм Пурдома]]
 
## [[Определение диаметра графа]]
 
## [[Определение диаметра графа]]
 
## [[Построение минимального остовного дерева (MST)]]
 
## [[Построение минимального остовного дерева (MST)]]

Версия 16:06, 11 июня 2015

  1. Векторные операции
    1. Суммирование сдваиванием
      1. Нахождение суммы элементов массива сдваиванием
      2. Нахождение частных сумм элементов массива сдваиванием
    2. Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
    3. Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
    4. Последовательно-параллельный метод суммирования
  2. Умножение матрицы на вектор
    1. Умножение плотной матрицы на вектор
  3. Матричные операции
    1. Умножение плотных матриц
  4. Разложения матриц
    1. Треугольные разложения
      1. Метод Гаусса (накождение LU-разложения)
        1. Метод Гаусса без перестановок
          1. LU-разложение методом Гаусса
          2. Компактная схема метода Гаусса
            1. Компактная схема метода Гаусса для плотной матрицы
            2. Компактная схема метода Гаусса для трёхдиагональной матрицы
        2. Метод Гаусса с перестановками
          1. Метод Гаусса с выбором ведущего элемента по столбцу
          2. Метод Гаусса с выбором ведущего элемента по строке
          3. Метод Гаусса с выбором ведущего элемента по всей матрице
      2. Метод Холецкого (нахождение симметричного треугольного разложения)
        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. Обход графа
      1. Поиск в ширину (BFS)
      2. Поиск в глубину (DFS)
    2. Поиск кратчайшего пути от одной вершины (SSSP)
      1. Поиск в ширину (BFS) (для невзвешенных графов)
      2. Алгоритм Дейкстры
      3. Алгоритм Беллмана-Форда
      4. Алгоритм Δ-шагания
    3. Поиск кратчайшего пути для всех пар вершин (APSP)
      1. Алгоритм Флойда-Уоршелла
    4. Поиск транзитивного замыкания орграфа
      1. Алгоритм Пурдома
    5. Определение диаметра графа
    6. Построение минимального остовного дерева (MST)
      1. Алгоритм Борувки
      2. Алгоритм Крускала
      3. Алгоритм Прима
      4. Алгоритм GHS
    7. Поиск изоморфных подграфов
    8. Связность в графах
      1. Алгоритм Шилоаха-Вишкина поиска компонент связности
      2. Система непересекающихся множеств
      3. Алгоритм Тарьяна поиска компонент сильной связности
      4. Алгоритм DCSC поиска компонент сильной связности
      5. Алгоритм Тарьяна поиска компонент двусвязности
      6. Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
      7. Алгоритм Тарьяна поиска «мостов» в графе
      8. Определение вершинной связности графа
      9. Алгоритм Габова определения рёберной связности графа
    9. Поиск максимального потока в транспортной сети
      1. Алгоритм Форда-Фалкерсона
      2. Алгоритм проталкивания предпотока
    10. Поиск потока минимальной стоимости в транспортной сети
    11. Задача о назначениях
      1. Венгерский алгоритм
      2. Алгоритм аукциона
      3. Алгоритм Гопкрофта-Карпа
    12. Вычисление центральности вершин
  11. Алгоритмы поиска
    1. Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
  12. Алгоритмы сортировки
    1. Сортировка с помощью двоичного дерева
    2. Сортировка пузырьком
    3. Сортировка слиянием (последовательный и параллельный варианты)
  13. Вычислительная геометрия
    1. Поиск диаметра множества точек
    2. Построение выпуклой оболочки набора точек
    3. Триангуляция Делоне
    4. Диаграмма Вороного
    5. Принадлежность точки многоугольнику
    6. Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
    7. Пересечение звёздных многоугольников - трудоёмкость [math]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. Другие алгоритмы