Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [выверенная версия] |
ASA (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | = | + | # <div id="Векторные операции">'''Векторные операции'''</div> |
| − | + | ## [[Суммирование сдваиванием]] | |
| − | # [[Суммирование сдваиванием]] | + | ## [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]] |
| − | # [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]] | + | ## [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]] |
| − | # [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]] | + | ## [[Последовательно-параллельный метод суммирования]] |
| − | # [[Последовательно-параллельный метод суммирования]] | + | # <div id="Умножение матрицы на вектор">'''Умножение матрицы на вектор'''</div> |
| − | + | ## [[Умножение плотной матрицы на вектор]] | |
| − | + | # <div id="Матричные операции">'''Матричные операции'''</div> | |
| − | + | ## [[Умножение плотных матриц]] | |
| − | # [[Умножение плотной матрицы на вектор]] | + | # <div id="Разложения матриц">'''Разложения матриц'''</div> |
| − | + | ## ''Треугольные разложения'' | |
| − | + | ### [[Метод Холецкого (нахождение симметричного треугольного разложения)]] | |
| − | + | #### [[Разложение Холецкого (метод квадратного корня)]] базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы | |
| − | # [[Умножение плотных матриц]] | + | ## ''Унитарно-треугольные разложения'' |
| − | + | ### [[Метод Гивенса (вращений) QR-разложения матрицы]] | |
| − | + | ### [[Метод Хаусхолдера (отражений) QR-разложения матрицы]] | |
| − | + | ## ''Разложения на унитарные и хессенберговы матрицы'' | |
| − | + | ### [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме]] | |
| − | + | ## ''Разложения на унитарные и диагональные матрицы'' | |
| − | # [[Метод Холецкого (нахождение симметричного треугольного разложения)]] | + | ### [[Спектральное разложение (нахождение собственных значений и векторов)]] |
| − | ## [[Разложение Холецкого (метод квадратного корня)]] базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы | + | ### [[Сингулярное разложение (нахождение сингулярных значений и векторов)]] |
| − | + | # <div id="Решение систем линейных уравнений">'''Решение систем линейных уравнений'''</div> | |
| − | + | ## [[High Performance Conjugate Gradient (HPCG) benchmark]] | |
| − | + | ## [[Linpack benchmark]] | |
| − | # [[Метод Гивенса (вращений) QR-разложения матрицы]] | + | ## [[Метод Гаусса решения СЛАУ (прямой ход)]] |
| − | # [[Метод Хаусхолдера (отражений) QR-разложения матрицы]] | + | ## [[Обратная подстановка (вещественный вариант)|Обратная подстановка]] |
| − | + | # <div id="Тесты производительности компьютеров">'''Тесты производительности компьютеров'''</div> | |
| − | + | ## [[High Performance Conjugate Gradient (HPCG) benchmark]] | |
| − | + | ## [[Linpack benchmark]] | |
| − | # [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме]] | + | # <div id="Преобразование Фурье">'''Преобразование Фурье'''</div> |
| − | + | ## [[Быстрое преобразование Фурье для степеней двойки]] | |
| − | + | # <div id="Алгебра многочленов">'''Алгебра многочленов'''</div> | |
| − | + | ## [[Схема Горнера, вещественная версия, последовательный вариант|Схема Горнера]] | |
| − | # [[Спектральное разложение (нахождение собственных значений и векторов)]] | + | # <div id="Численные методы интегрирования">'''Численные методы интегрирования'''</div> |
| − | # [[Сингулярное разложение (нахождение сингулярных значений и векторов)]] | + | ## [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]] |
| − | + | ### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод прямоугольников]] | |
| − | + | ### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод трапеций]] | |
| − | + | ### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод парабол (метод Симпсона)]] | |
| − | # [[High Performance Conjugate Gradient (HPCG) benchmark]] | + | ### [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод Гаусса]] |
| − | # [[Linpack benchmark]] | + | # <div id="Алгоритмы на графах">'''Алгоритмы на графах'''</div> |
| − | # [[Метод Гаусса решения СЛАУ (прямой ход)]] | + | ## [[Алгоритм вычисления кратчайшего пути во взвешенном графе]] |
| − | # [[Обратная подстановка (вещественный вариант)|Обратная подстановка]] | + | ## [[Алгоритм обхода графа]] |
| − | + | # <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div> | |
| − | + | ## [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math> | |
| − | + | # <div id="Алгоритмы сортировки">'''Алгоритмы сортировки'''</div> | |
| − | # [[High Performance Conjugate Gradient (HPCG) benchmark]] | + | ## [[Сортировка с помощью двоичного дерева]] |
| − | # [[Linpack benchmark]] | + | ## [[Сортировка пузырьком]] |
| − | + | ## [[Сортировка слиянием (последовательный и параллельный варианты)]] | |
| − | + | # <div id="Вычислительная геометрия">'''Вычислительная геометрия'''</div> | |
| − | + | ## [[Поиск диаметра множества точек]] | |
| − | # [[Быстрое преобразование Фурье для степеней двойки]] | + | ## [[Построение выпуклой оболочки набора точек]] |
| − | + | ## [[Триангуляция Делоне]] | |
| − | + | ## [[Диаграмма Вороного]] | |
| − | + | ## [[Принадлежность точки многоугольнику]] | |
| − | # [[Схема Горнера, вещественная версия, последовательный вариант|Схема Горнера]] | + | ## [[Пересечения выпуклых многоугольников]] - трудоёмкость <math>O(n_1 + n_2)</math> |
| − | + | ## [[Пересечение звёздных многоугольников]] - трудоёмкость <math>O(n_1 * n_2)</math> | |
| − | + | # <div id="Компьютерная графика">'''Компьютерная графика'''</div> | |
| − | + | ## [[Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности]] | |
| − | # [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]] | + | ## [[Алгоритм определения видимых частей трёхмерной сцены]] |
| − | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод прямоугольников]] | + | ## [[Трассировка лучей - рендеринг реалистичных изображений]] |
| − | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод трапеций]] | + | ## [[Глобальное освещение - рассматривает прямое освещение и отражение от других объектов]] |
| − | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод парабол (метод Симпсона)]] | + | # <div id="Криптографические алгоритмы">'''Криптографические алгоритмы'''</div> |
| − | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод Гаусса]] | + | # <div id="Нейронные сети">'''Нейронные сети'''</div> |
| − | + | # <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div> | |
| − | + | ## [[Линейное программирование]] | |
| − | + | ## [[Симплекс-метод]] | |
| − | # [[Алгоритм вычисления кратчайшего пути во взвешенном графе]] | + | ## [[Метод ветвей и границ (последовательный и параллельный варианты)]] |
| − | # [[Алгоритм обхода графа]] | + | ## [[Генетические алгоритмы]] |
| − | + | ## [[Муравьиные алгоритмы]] | |
| − | + | ## [[Комбинированные алгоритмы]] | |
| − | + | ## [[Нахождение экстремума функции]] | |
| − | # [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math> | + | # <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div> |
| − | + | # <div id="Алгоритмы моделирования квантовых систем">'''Алгоритмы моделирования квантовых систем'''</div> | |
| − | + | ## ''Алгоритмы моделирования квантовых вычислений'' | |
| − | + | ### [[Однокубитное преобразование вектора-состояния]] | |
| − | # [[Сортировка с помощью двоичного дерева]] | + | ### [[Двухкубитное преобразование вектора-состояния]] |
| − | # [[Сортировка пузырьком]] | + | ### [[Моделирование квантового преобразования Фурье]] |
| − | # [[Сортировка слиянием (последовательный и параллельный варианты)]] | + | # <div id="Алгоритмы решения уравнений математической физики">'''Алгоритмы решения уравнений математической физики'''</div> |
| − | + | ## [[Уравнение Пуассона, решение дискретным преобразованием Фурье]] | |
| − | + | # <div id="Другие алгоритмы">'''Другие алгоритмы'''</div> | |
| − | |||
| − | # [[Поиск диаметра множества точек]] | ||
| − | # [[Построение выпуклой оболочки набора точек]] | ||
| − | # [[Триангуляция Делоне]] | ||
| − | # [[Диаграмма Вороного]] | ||
| − | # [[Принадлежность точки многоугольнику]] | ||
| − | # [[Пересечения выпуклых многоугольников]] - трудоёмкость <math>O(n_1 + n_2)</math> | ||
| − | # [[Пересечение звёздных многоугольников]] - трудоёмкость <math>O(n_1 * n_2)</math> | ||
| − | |||
| − | |||
| − | |||
| − | # [[Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности]] | ||
| − | # [[Алгоритм определения видимых частей трёхмерной сцены]] | ||
| − | # [[Трассировка лучей - рендеринг реалистичных изображений]] | ||
| − | # [[Глобальное освещение - рассматривает прямое освещение и отражение от других объектов]] | ||
| − | |||
| − | |||
| − | |||
| − | = | ||
| − | |||
| − | = | ||
| − | |||
| − | # [[Линейное программирование]] | ||
| − | # [[Симплекс-метод]] | ||
| − | # [[Метод ветвей и границ (последовательный и параллельный варианты)]] | ||
| − | # [[Генетические алгоритмы]] | ||
| − | # [[Муравьиные алгоритмы]] | ||
| − | # [[Комбинированные алгоритмы]] | ||
| − | # [[Нахождение экстремума функции]] | ||
| − | |||
| − | |||
| − | |||
| − | = | ||
| − | |||
| − | |||
| − | #[[Однокубитное преобразование вектора-состояния]] | ||
| − | #[[Двухкубитное преобразование вектора-состояния]] | ||
| − | #[[Моделирование квантового преобразования Фурье]] | ||
| − | |||
| − | |||
| − | # [[Уравнение Пуассона, решение дискретным преобразованием Фурье]] | ||
| − | |||
| − | |||
| − | |||
[[en:Algorithm classification]] | [[en:Algorithm classification]] | ||
Версия 16:18, 28 марта 2015
- Векторные операции
- Умножение матрицы на вектор
- Матричные операции
- Разложения матриц
- Треугольные разложения
- Метод Холецкого (нахождение симметричного треугольного разложения)
- Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- Метод Холецкого (нахождение симметричного треугольного разложения)
- Унитарно-треугольные разложения
- Разложения на унитарные и хессенберговы матрицы
- Разложения на унитарные и диагональные матрицы
- Треугольные разложения
- Решение систем линейных уравнений
- Тесты производительности компьютеров
- Преобразование Фурье
- Алгебра многочленов
- Численные методы интегрирования
- Алгоритмы на графах
- Алгоритмы поиска
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
- Алгоритмы сортировки
- Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
- Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]
- Компьютерная графика
- Криптографические алгоритмы
- Нейронные сети
- Алгоритмы оптимизации
- Алгоритмы теории игр
- Алгоритмы моделирования квантовых систем
- Алгоритмы моделирования квантовых вычислений
- Алгоритмы решения уравнений математической физики
- Другие алгоритмы
