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

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. Схема Горнера

9 Численные методы интегрирования

1. Метод прямоугольников
2. Метод трапеций
3. Метод парабол (метод Симпсона)
4. Метод Гаусса

10 Алгоритмы на графах

1. Алгоритм вычисления кратчайшего пути во взвешенном графе
2. Алгоритм обхода графа

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. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов

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

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

19 Алгоритмы моделирования квантовых систем

19.1 Алгоритмы моделирования квантовых вычислений

1. Однокубитное преобразование вектора-состояния
2. Двухкубитное преобразование вектора-состояния
3. Моделирование квантового преобразования Фурье