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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 49: Строка 49:
  
 
# [[Быстрое преобразование Фурье для степеней двойки]]
 
# [[Быстрое преобразование Фурье для степеней двойки]]
 +
 +
== Алгоритмы на графах ==
 +
 +
# [[Алгоритм вычисления кратчайшего пути во взвешенном графе]]
 +
# [[Алгоритм обхода графа]]
 +
 +
== Алгоритмы поиска ==
 +
 +
# [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math>
 +
 +
== Алгоритмы сортировки ==
 +
 +
# [[Сортировка с помощью двоичного дерева]]
 +
# [[Сортировка пузырьком]]
 +
# [[Сортировка слиянием (последовательный и параллельный варианты)]]
 +
 +
== Вычислительная геометрия ==
 +
 +
# [[Поиск диаметра множества точек]]
 +
# [[Построение выпуклой оболочки набора точек]]
 +
# [[Триангуляция Делоне]]
 +
# [[Диаграмма Вороного]]
 +
# [[Принадлежность точки многоугольнику]]
 +
# [[Пересечения выпуклых многоугольников]] - трудоёмкость <math>O(n_1 + n_2)</math>
 +
# [[Пересечение звёздных многоугольников]] - трудоёмкость <math>O(n_1 * n_2)</math>
 +
 +
== Компьютерная графика ==
 +
 +
# [[Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности]]
 +
# [[Алгоритм определения видимых частей трёхмерной сцены]]
 +
# [[Трассировка лучей - рендеринг реалистичных изображений]]
 +
# [[Глобальное освещение - рассматривает прямое освещение и отражение от других объектов]]
 +
 +
== Криптографические алгоритмы ==
 +
 +
== Нейронные сети ==
 +
 +
== Алгоритмы оптимизации ==
 +
 +
# [[Линейное программирование]]
 +
# [[Симплекс-метод]]
 +
# [[Метод ветвей и границ (последовательный и параллельный варианты)]]
 +
# [[Генетические алгоритмы]]
 +
# [[Муравьиные алгоритмы]]
 +
# [[Комбинированные алгоритмы]]
 +
# [[Нахождение экстремума функции]]
 +
 +
== Алгоритмы теории игр ==
  
 
== Другие алгоритмы ==
 
== Другие алгоритмы ==

Версия 16:09, 10 ноября 2014

1 Векторные операции

  1. Суммирование сдваиванием
  2. Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
  3. Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
  4. Последовательно-параллельный метод суммирования

2 Умножение матрицы на вектор

  1. Умножение плотной матрицы на вектор

3 Матричные операции

  1. Умножение плотных матриц

4 Разложения матриц

4.1 Треугольные разложения

  1. Метод Холецкого (нахождение симметричного треугольного разложения)

4.2 Унитарно-треугольные разложения

  1. Метод Гивенса (вращений) QR-разложения матрицы
  2. Метод Хаусхолдера (отражений) QR-разложения матрицы

4.3 Разложения на унитарные и хессенберговы матрицы

  1. Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме

4.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. Алгоритм вычисления кратчайшего пути во взвешенном графе
  2. Алгоритм обхода графа

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

  1. Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]

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

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

11 Вычислительная геометрия

  1. Поиск диаметра множества точек
  2. Построение выпуклой оболочки набора точек
  3. Триангуляция Делоне
  4. Диаграмма Вороного
  5. Принадлежность точки многоугольнику
  6. Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
  7. Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]

12 Компьютерная графика

  1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
  2. Алгоритм определения видимых частей трёхмерной сцены
  3. Трассировка лучей - рендеринг реалистичных изображений
  4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов

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

14 Нейронные сети

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

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

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

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

Источник — https://algowiki-project.org/w/ru/index.php?title=Классификация_алгоритмов&oldid=706