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

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][непроверенная версия]
(-> список алгоритмов на графах)
Строка 71: Строка 71:
 
## [[Поиск транзитивного замыкания орграфа]]
 
## [[Поиск транзитивного замыкания орграфа]]
 
## [[Связность в графах]]
 
## [[Связность в графах]]
 +
### [[Алгоритм Шилоаха-Вишкина поиска компонент связности]]
 +
### [[Система непересекающихся множеств]]
 
### [[Поиск компонент сильной связности орграфа]]
 
### [[Поиск компонент сильной связности орграфа]]
 
### [[Алгоритм Тарьяна поиска «шарниров» в графе]]
 
### [[Алгоритм Тарьяна поиска «шарниров» в графе]]

Версия 12:14, 2 июня 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. Алгоритм Δ-шагания
      5. Алгоритм Торупа
    3. Поиск кратчайшего пути для всех пар вершин (APSP)
      1. Алгоритм Флойда-Уоршелла
    4. Определение диаметра графа
    5. Построение минимального остовного дерева (MST)
      1. Алгоритм Борувки
      2. Алгоритм Крускала
      3. Алгоритм Прима
      4. Алгоритм GHS
    6. Поиск изоморфных подграфов графа
    7. Поиск транзитивного замыкания орграфа
    8. Связность в графах
      1. Алгоритм Шилоаха-Вишкина поиска компонент связности
      2. Система непересекающихся множеств
      3. Поиск компонент сильной связности орграфа
      4. Алгоритм Тарьяна поиска «шарниров» в графе
      5. Алгоритм Тарьяна поиска «мостов» в графе
      6. Определение числа вершинной связности графа
      7. Определение числа рёберной связности графа
    9. Поиск максимального потока в нагруженном графе
      1. Алгоритм Форда-Фалкерсона
      2. Алгоритм проталкивания предпотока
    10. Поиск потока минимальной стоимости в нагруженном графе
    11. Задача о назначениях
      1. Алгоритм аукциона
      2. Алгоритм Гопкрофта-Карпа
    12. Вычисление центральности вершин
      1. Вычисление betweenness centrality
      2. Вычисление percolation centrality
  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. Другие алгоритмы