Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
[досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) м |
Frolov (обсуждение | вклад) м (→Задачи алгебры) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
__TOC__ | __TOC__ | ||
− | =Векторные операции= | + | = Задачи алгебры = |
+ | ==Матричные и векторные операции== | ||
+ | ===Векторные операции=== | ||
# {{level|Суммирование сдваиванием}} | # {{level|Суммирование сдваиванием}} | ||
## {{level|Нахождение суммы элементов массива сдваиванием}} | ## {{level|Нахождение суммы элементов массива сдваиванием}} | ||
Строка 7: | Строка 9: | ||
# {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}} | # {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}} | ||
# {{level|Последовательно-параллельный метод суммирования}} | # {{level|Последовательно-параллельный метод суммирования}} | ||
− | = | + | === Умножения матриц на вектор === |
− | == Умножения неособенных матриц на вектор == | + | ==== Умножения неособенных матриц на вектор ==== |
# {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}} | # {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}} | ||
− | == Умножения матриц специального вида на вектор == | + | ==== Умножения матриц специального вида на вектор ==== |
# {{level|Преобразование Фурье}} | # {{level|Преобразование Фурье}} | ||
## {{level|Быстрое преобразование Фурье для составной размерности}} | ## {{level|Быстрое преобразование Фурье для составной размерности}} | ||
Строка 18: | Строка 20: | ||
### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}} | ### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}} | ||
## {{level|Быстрое преобразование Фурье для простой размерности}} | ## {{level|Быстрое преобразование Фурье для простой размерности}} | ||
− | + | ===Матричные операции=== | |
− | =Матричные операции= | ||
# {{level|Умножение плотных матриц}} | # {{level|Умножение плотных матриц}} | ||
## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}} | ## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}} | ||
## {{level|Метод Штрассена}} | ## {{level|Метод Штрассена}} | ||
− | =Разложения матриц= | + | ==Разложения матриц== |
{{level|Задача разложения матриц}} | {{level|Задача разложения матриц}} | ||
# {{level|Треугольные разложения}} | # {{level|Треугольные разложения}} | ||
Строка 77: | Строка 78: | ||
##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}} | ##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}} | ||
###### {{level|Итерация алгоритма dqds}} | ###### {{level|Итерация алгоритма dqds}} | ||
− | =Решение систем линейных уравнений= | + | ==Решение систем линейных уравнений== |
# {{level|Прямые методы решения СЛАУ}} | # {{level|Прямые методы решения СЛАУ}} | ||
## {{level|Linpack benchmark}} | ## {{level|Linpack benchmark}} | ||
Строка 128: | Строка 129: | ||
## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}} | ## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}} | ||
## {{level|Алгоритм_Качмажа}} | ## {{level|Алгоритм_Качмажа}} | ||
− | = | + | ==Решения спектральных задач== |
− | |||
− | =Решения спектральных задач= | ||
# {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | # {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ||
## {{level|QR-алгоритм}} | ## {{level|QR-алгоритм}} | ||
Строка 155: | Строка 154: | ||
### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}} | ### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}} | ||
## {{level|QR-алгоритм в приложении к сингулярному разложению}} | ## {{level|QR-алгоритм в приложении к сингулярному разложению}} | ||
− | = | + | ==Алгебра многочленов== |
− | # {{level| | + | # {{level|Схема Горнера, вещественная версия, последовательный вариант}} |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=Алгоритмы на графах= | =Алгоритмы на графах= | ||
# Обход графа | # Обход графа | ||
Строка 233: | Строка 222: | ||
=Криптографические алгоритмы= | =Криптографические алгоритмы= | ||
# {{level|Метод встречи посередине}} | # {{level|Метод встречи посередине}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=Алгоритмы машинного обучения= | =Алгоритмы машинного обучения= | ||
# {{level|Алгоритм k средних (k-means)}} | # {{level|Алгоритм k средних (k-means)}} | ||
Строка 250: | Строка 230: | ||
## {{level|Распознавание лиц}} | ## {{level|Распознавание лиц}} | ||
=Алгоритмы теории игр= | =Алгоритмы теории игр= | ||
− | =Алгоритмы моделирования квантовых систем= | + | =Исследование и моделирование компьютеров= |
+ | ==Тесты производительности компьютеров== | ||
+ | # {{level|High Performance Conjugate Gradient (HPCG) benchmark}} | ||
+ | # {{level|Linpack benchmark}} | ||
+ | ==Алгоритмы моделирования квантовых систем== | ||
# {{level|Алгоритмы моделирования квантовых вычислений}} | # {{level|Алгоритмы моделирования квантовых вычислений}} | ||
## {{level|Однокубитное преобразование вектора-состояния}} | ## {{level|Однокубитное преобразование вектора-состояния}} | ||
## {{level|Двухкубитное преобразование вектора-состояния}} | ## {{level|Двухкубитное преобразование вектора-состояния}} | ||
## {{level|Моделирование квантового преобразования Фурье}} | ## {{level|Моделирование квантового преобразования Фурье}} | ||
− | =Алгоритмы решения уравнений математической физики= | + | |
+ | = Прикладные задачи из разных областей = | ||
+ | ==Алгоритмы оптимизации== | ||
+ | # {{level|Линейное программирование}} | ||
+ | # {{level|Симплекс-метод}} | ||
+ | # {{level|Метод ветвей и границ}} | ||
+ | # {{level|Генетические алгоритмы}} | ||
+ | # {{level|Муравьиные алгоритмы}} | ||
+ | # {{level|Комбинированные алгоритмы}} | ||
+ | # {{level|Стохастическое двойственное динамическое программирование (SDDP)}} | ||
+ | ==Решение систем нелинейных уравнений== | ||
+ | # {{level|Метод Ньютона для систем нелинейных уравнений}} | ||
+ | |||
+ | ==Численные методы интегрирования== | ||
+ | # {{level|Квадратурные формулы}} | ||
+ | # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}} | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]] | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]] | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]] | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]] | ||
+ | ==Алгоритмы решения уравнений математической физики== | ||
# {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}} | # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}} | ||
=Другие алгоритмы= | =Другие алгоритмы= |
Версия 17:02, 3 февраля 2018
Содержание
- 1 Задачи алгебры
- 2 Алгоритмы на графах
- 3 Алгоритмы на списках и массивах
- 4 Вычислительная геометрия
- 5 Криптографические алгоритмы
- 6 Алгоритмы машинного обучения
- 7 Алгоритмы теории игр
- 8 Исследование и моделирование компьютеров
- 9 Прикладные задачи из разных областей
- 10 Другие алгоритмы
1 Задачи алгебры
1.1 Матричные и векторные операции
1.1.1 Векторные операции
- Суммирование сдваиванием
- Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
- Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
- Последовательно-параллельный метод суммирования
1.1.2 Умножения матриц на вектор
1.1.2.1 Умножения неособенных матриц на вектор
1.1.2.2 Умножения матриц специального вида на вектор
- Преобразование Фурье
1.1.3 Матричные операции
1.2 Разложения матриц
- Треугольные разложения
- Метод Гаусса (нахождение LU-разложения)
- Метод Холецкого (нахождение симметричного треугольного разложения)
- Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- Известные треугольные разложения для матриц специального вида
- Унитарно-треугольные разложения
- Подобные разложения
- Подобные разложения на унитарные и хессенберговы матрицы
- Симметричные разложения на унитарные и трёхдиагональные матрицы
- Спектральное разложение (нахождение собственных значений и векторов)
- Неподобные унитарные разложения
1.3 Решение систем линейных уравнений
- Прямые методы решения СЛАУ
- Linpack benchmark
- Методы решения СЛАУ с матрицами специального вида
- Методы решения СЛАУ с треугольными матрицами
- Методы решения СЛАУ с трёхдиагональными матрицами
- Методы решения СЛАУ с блочно-треугольными матрицами
- Блочная прямая подстановка (вещественный вариант)
- Блочная обратная подстановка (вещественный вариант)
- Методы решения СЛАУ с блочно-двухдиагональными матрицами
- Методы решения СЛАУ с блочно-трёхдиагональными матрицами
- Методы, основанные на стандартном LU-разложении матрицы
- Другие методы
- Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
- Итерационные методы решения СЛАУ
1.4 Решения спектральных задач
- Спектральное разложение (нахождение собственных значений и векторов)
- Частичная спектральная задача
- Сингулярное разложение (нахождение сингулярных значений и векторов)
1.5 Алгебра многочленов
2 Алгоритмы на графах
- Обход графа
- Поиск кратчайшего пути от одной вершины (SSSP)
- Поиск в ширину (BFS) (для невзвешенных графов)
- Алгоритм Дейкстры
- Алгоритм Беллмана-Форда
- Алгоритм Δ-шагания
- Поиск кратчайшего пути для всех пар вершин (APSP)
- Поиск транзитивного замыкания орграфа
- Определение диаметра графа
- Построение минимального остовного дерева (MST)
- Поиск изоморфных подграфов
- Связность в графах
- Алгоритм Шилоаха-Вишкина поиска компонент связности
- Система непересекающихся множеств
- Алгоритм Тарьяна поиска компонент сильной связности
- Алгоритм DCSC поиска компонент сильной связности
- Алгоритм Тарьяна поиска компонент двусвязности
- Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
- Алгоритм Тарьяна поиска «мостов» в графе
- Определение вершинной связности графа
- Алгоритм Габова определения рёберной связности графа
- Поиск максимального потока в транспортной сети
- Поиск потока минимальной стоимости в транспортной сети
- Задача о назначениях
- Вычисление betweenness centrality
3 Алгоритмы на списках и массивах
3.1 Алгоритмы поиска
- Линейный поиск - находит элемент в любом списке, [math]O(n)[/math]
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(\log(n))[/math]
3.2 Алгоритмы сортировки
- Сортировка с помощью двоичного дерева
- Сортировка пузырьком
- Сортировка слиянием (последовательный и параллельный варианты)
4 Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников
- Пересечение звёздных многоугольников
4.1 Компьютерная графика
- Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
- Алгоритм определения видимых частей трёхмерной сцены
- Трассировка лучей - рендеринг реалистичных изображений
- Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
5 Криптографические алгоритмы
6 Алгоритмы машинного обучения
6.1 Нейронные сети
7 Алгоритмы теории игр
8 Исследование и моделирование компьютеров
8.1 Тесты производительности компьютеров
8.2 Алгоритмы моделирования квантовых систем
9 Прикладные задачи из разных областей
9.1 Алгоритмы оптимизации
- Линейное программирование
- Симплекс-метод
- Метод ветвей и границ
- Генетические алгоритмы
- Муравьиные алгоритмы
- Комбинированные алгоритмы
- Стохастическое двойственное динамическое программирование (SDDP)
9.2 Решение систем нелинейных уравнений
9.3 Численные методы интегрирования
- Квадратурные формулы
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)