Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 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|Схема Горнера, вещественная версия, последовательный вариант}} |
− | + | ||
− | = | + | = Алгоритмы на списках и массивах = |
− | # {{level| | + | ==Алгоритмы поиска== |
− | = | + | # {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, <math>O(n)</math> |
− | # {{level| | + | # {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, <math>O(\log(n))</math> |
− | # {{level| | + | ==Алгоритмы сортировки== |
− | # | + | # {{level|Сортировка с помощью двоичного дерева}} |
− | + | # {{level|Сортировка пузырьком}} | |
− | + | # {{level|Сортировка слиянием (последовательный и параллельный варианты)}} | |
− | + | ==Алгоритмы на графах== | |
− | =Алгоритмы на графах= | ||
# Обход графа | # Обход графа | ||
## {{level|Поиск в ширину (BFS)}} | ## {{level|Поиск в ширину (BFS)}} | ||
Строка 210: | Строка 208: | ||
## {{level|Алгоритм Гопкрофта-Карпа}} | ## {{level|Алгоритм Гопкрофта-Карпа}} | ||
# {{level|Вычисление betweenness centrality|Вычисление центральности вершин}} | # {{level|Вычисление betweenness centrality|Вычисление центральности вершин}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=Вычислительная геометрия= | =Вычислительная геометрия= | ||
# {{level|Поиск диаметра множества точек}} | # {{level|Поиск диаметра множества точек}} | ||
Строка 225: | Строка 216: | ||
# {{level|Пересечения выпуклых многоугольников}} | # {{level|Пересечения выпуклых многоугольников}} | ||
# {{level|Пересечение звёздных многоугольников}} | # {{level|Пересечение звёздных многоугольников}} | ||
− | + | ==Компьютерная графика== | |
− | =Компьютерная графика= | ||
# {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}} | # {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}} | ||
# {{level|Алгоритм определения видимых частей трёхмерной сцены}} | # {{level|Алгоритм определения видимых частей трёхмерной сцены}} | ||
# {{level|Трассировка лучей - рендеринг реалистичных изображений}} | # {{level|Трассировка лучей - рендеринг реалистичных изображений}} | ||
# {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}} | # {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}} | ||
− | = | + | |
− | # {{level| | + | =Исследование и моделирование компьютеров= |
− | =Нейронные сети= | + | ==Тесты производительности компьютеров== |
+ | # {{level|High Performance Conjugate Gradient (HPCG) benchmark}} | ||
+ | # {{level|Linpack benchmark}} | ||
+ | ==Алгоритмы моделирования квантовых систем== | ||
+ | # {{level|Алгоритмы моделирования квантовых вычислений}} | ||
+ | ## {{level|Однокубитное преобразование вектора-состояния}} | ||
+ | ## {{level|Двухкубитное преобразование вектора-состояния}} | ||
+ | ## {{level|Моделирование квантового преобразования Фурье}} | ||
+ | ==Алгоритмы машинного обучения== | ||
+ | # {{level|Алгоритм k средних (k-means)}} | ||
+ | ===Нейронные сети=== | ||
# {{level|Распознавание образов}} | # {{level|Распознавание образов}} | ||
## {{level|Распознавание текста}} | ## {{level|Распознавание текста}} | ||
## {{level|Распознавание речи}} | ## {{level|Распознавание речи}} | ||
## {{level|Распознавание лиц}} | ## {{level|Распознавание лиц}} | ||
+ | ===Алгоритмы теории игр=== | ||
− | =Алгоритмы оптимизации= | + | = Прикладные задачи из разных областей = |
+ | ==Алгоритмы оптимизации== | ||
# {{level|Линейное программирование}} | # {{level|Линейное программирование}} | ||
# {{level|Симплекс-метод}} | # {{level|Симплекс-метод}} | ||
Строка 247: | Строка 249: | ||
# {{level|Комбинированные алгоритмы}} | # {{level|Комбинированные алгоритмы}} | ||
# {{level|Стохастическое двойственное динамическое программирование (SDDP)}} | # {{level|Стохастическое двойственное динамическое программирование (SDDP)}} | ||
− | = | + | ==Решение систем нелинейных уравнений== |
− | # {{level| | + | # {{level|Метод Ньютона для систем нелинейных уравнений}} |
− | = | + | ==Численные методы интегрирования== |
− | = | + | # {{level|Квадратурные формулы}} |
− | # {{level| | + | # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}} |
− | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]] | |
− | ## | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]] |
− | ## | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]] |
− | =Алгоритмы решения уравнений математической физики= | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]] |
+ | ==Алгоритмы решения уравнений математической физики== | ||
# {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}} | # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}} | ||
+ | =Криптографические алгоритмы= | ||
+ | # {{level|Метод встречи посередине}} | ||
=Другие алгоритмы= | =Другие алгоритмы= | ||
Версия 14:16, 5 февраля 2018
Содержание
- 1 Задачи алгебры
- 2 Алгоритмы на списках и массивах
- 3 Вычислительная геометрия
- 4 Исследование и моделирование компьютеров
- 5 Прикладные задачи из разных областей
- 6 Криптографические алгоритмы
- 7 Другие алгоритмы
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 Алгоритмы на списках и массивах
2.1 Алгоритмы поиска
- Линейный поиск - находит элемент в любом списке, [math]O(n)[/math]
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(\log(n))[/math]
2.2 Алгоритмы сортировки
- Сортировка с помощью двоичного дерева
- Сортировка пузырьком
- Сортировка слиянием (последовательный и параллельный варианты)
2.3 Алгоритмы на графах
- Обход графа
- Поиск кратчайшего пути от одной вершины (SSSP)
- Поиск в ширину (BFS) (для невзвешенных графов)
- Алгоритм Дейкстры
- Алгоритм Беллмана-Форда
- Алгоритм Δ-шагания
- Поиск кратчайшего пути для всех пар вершин (APSP)
- Поиск транзитивного замыкания орграфа
- Определение диаметра графа
- Построение минимального остовного дерева (MST)
- Поиск изоморфных подграфов
- Связность в графах
- Алгоритм Шилоаха-Вишкина поиска компонент связности
- Система непересекающихся множеств
- Алгоритм Тарьяна поиска компонент сильной связности
- Алгоритм DCSC поиска компонент сильной связности
- Алгоритм Тарьяна поиска компонент двусвязности
- Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
- Алгоритм Тарьяна поиска «мостов» в графе
- Определение вершинной связности графа
- Алгоритм Габова определения рёберной связности графа
- Поиск максимального потока в транспортной сети
- Поиск потока минимальной стоимости в транспортной сети
- Задача о назначениях
- Вычисление betweenness centrality
3 Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников
- Пересечение звёздных многоугольников
3.1 Компьютерная графика
- Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
- Алгоритм определения видимых частей трёхмерной сцены
- Трассировка лучей - рендеринг реалистичных изображений
- Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
4 Исследование и моделирование компьютеров
4.1 Тесты производительности компьютеров
4.2 Алгоритмы моделирования квантовых систем
4.3 Алгоритмы машинного обучения
4.3.1 Нейронные сети
4.3.2 Алгоритмы теории игр
5 Прикладные задачи из разных областей
5.1 Алгоритмы оптимизации
- Линейное программирование
- Симплекс-метод
- Метод ветвей и границ
- Генетические алгоритмы
- Муравьиные алгоритмы
- Комбинированные алгоритмы
- Стохастическое двойственное динамическое программирование (SDDP)
5.2 Решение систем нелинейных уравнений
5.3 Численные методы интегрирования
- Квадратурные формулы
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)