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

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][выверенная версия]
м
Строка 51: Строка 51:
 
##### [[Метод циклической редукции]]
 
##### [[Метод циклической редукции]]
 
##### [[Метод окаймления]]
 
##### [[Метод окаймления]]
###### [[Последовательно-параллельный вариант прогонки]]
+
##### [[Последовательно-параллельный вариант прогонки]]
 
### [[Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы]]
 
### [[Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы]]
 
## Итерационные методы решения СЛАУ
 
## Итерационные методы решения СЛАУ

Версия 16:24, 8 июля 2015

  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. Метод Гаусса с перестановками
          1. Метод Гаусса с выбором ведущего элемента по столбцу
          2. Метод Гаусса с выбором ведущего элемента по строке
          3. Метод Гаусса с выбором ведущего элемента по всей матрице
      3. Метод Холецкого (нахождение симметричного треугольного разложения)
        1. Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
    2. Унитарно-треугольные разложения
      1. Метод Гивенса (вращений) QR-разложения матрицы
      2. Метод Хаусхолдера (отражений) QR-разложения матрицы
    3. Разложения на унитарные и хессенберговы матрицы
      1. Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме
    4. Разложения на унитарные и диагональные матрицы
      1. Спектральное разложение (нахождение собственных значений и векторов)
      2. Сингулярное разложение (нахождение сингулярных значений и векторов)
  5. Решение систем линейных уравнений
    1. Прямые методы решения СЛАУ
      1. Linpack benchmark
      2. Решения СЛАУ с матрицами специального вида
        1. Решения СЛАУ с треугольными матрицами
          1. Метод Гаусса решения СЛАУ (прямой ход)
          2. Обратная подстановка
          3. Решения СЛАУ с двухдиагональными матрицами
            1. Обратная подстановка в СЛАУ с двухдиагональной матрицей
            2. Метод сдваивания Стоуна для решения двухдиагональных СЛАУ
        2. Решения СЛАУ с трёхдиагональными матрицами
          1. Прогонка
          2. Метод сдваивания Стоуна
          3. Метод циклической редукции
          4. Метод окаймления
          5. Последовательно-параллельный вариант прогонки
      3. Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
    2. Итерационные методы решения СЛАУ
      1. High Performance Conjugate Gradient (HPCG) benchmark
  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. Алгоритм Джонсона
      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. Вычисление центральности вершин
  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. Другие алгоритмы