Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
[непроверенная версия] | [выверенная версия] |
Frolov (обсуждение | вклад) |
Dolganov (обсуждение | вклад) (Перенаправление на Служебная:Pma tree) |
||
(не показано 146 промежуточных версий 12 участников) | |||
Строка 1: | Строка 1: | ||
− | == Векторные операции == | + | #redirect [[Special:Pma_tree]] |
+ | __TOC__ | ||
+ | = Задачи алгебры = | ||
+ | ==Матричные и векторные операции== | ||
+ | ===Векторные операции=== | ||
+ | # {{level|Суммирование сдваиванием}} | ||
+ | ## {{level|Нахождение суммы элементов массива сдваиванием}} | ||
+ | ## {{level|Нахождение частных сумм элементов массива сдваиванием}} | ||
+ | # {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}} | ||
+ | # {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}} | ||
+ | # {{level|Последовательно-параллельный метод суммирования}} | ||
+ | === Умножения матриц на вектор === | ||
+ | ==== Умножения неособенных матриц на вектор ==== | ||
+ | # {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}} | ||
+ | ==== Умножения матриц специального вида на вектор ==== | ||
+ | # {{level|Преобразование Фурье}} | ||
+ | ## {{level|Быстрое преобразование Фурье для составной размерности}} | ||
+ | ### {{level|Быстрое преобразование Фурье для степеней двойки}} | ||
+ | #### {{level|Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки}} | ||
+ | #### {{level|Быстрое преобразование Фурье для чётных степеней двойки}} | ||
+ | ### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}} | ||
+ | ## {{level|Быстрое преобразование Фурье для простой размерности}} | ||
+ | ===Матричные операции=== | ||
+ | # {{level|Умножение плотных матриц}} | ||
+ | ## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}} | ||
+ | ## {{level|Метод Штрассена}} | ||
+ | ==Разложения матриц== | ||
+ | {{level|Задача разложения матриц}} | ||
+ | # {{level|Треугольные разложения}} | ||
+ | ## {{level|Метод Гаусса (нахождение LU-разложения)}} | ||
+ | ### {{level|LU-разложение методом Гаусса без перестановок}} | ||
+ | #### {{level|LU-разложение методом Гаусса}} | ||
+ | #### {{level|Компактная схема метода Гаусса и её модификации}} | ||
+ | ##### {{level|Компактная схема метода Гаусса для плотной матрицы}} | ||
+ | ##### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации}} | ||
+ | ###### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант}} | ||
+ | ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}} | ||
+ | ###### {{level|Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы}} | ||
+ | ### {{level|LU-разложение методом Гаусса с перестановками}} | ||
+ | #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по столбцу}} | ||
+ | #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по строке}} | ||
+ | #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по главной диагонали}} | ||
+ | #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по всей матрице}} | ||
+ | ## {{level|Метод Холецкого (нахождение симметричного треугольного разложения)}} | ||
+ | ### {{level|Разложение Холецкого (метод квадратного корня)}} базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы | ||
+ | # {{level|Известные треугольные разложения для матриц специального вида}} | ||
+ | # {{level|Унитарно-треугольные разложения}} | ||
+ | ## {{level|QR-разложения плотных неособенных матриц}} | ||
+ | ### {{level|Метод Гивенса (вращений) QR-разложения матрицы}} | ||
+ | #### {{level|Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)}} | ||
+ | ### {{level|Метод Хаусхолдера (отражений) QR-разложения матрицы}} | ||
+ | #### {{level|Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант}} | ||
+ | ### {{level|Метод ортогонализации}} | ||
+ | #### {{level|Классический метод ортогонализации}} | ||
+ | #### {{level|Метод ортогонализации с переортогонализацией}} | ||
+ | ### {{level|Метод треугольного разложения матрицы Грама}} | ||
+ | ## {{level|Методы QR-разложения плотных хессенберговых матриц}} | ||
+ | ### {{level|Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)}} | ||
+ | ### {{level|Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)}} | ||
+ | # {{level|Разложения, содержащие матрицу, подобную исходной}} | ||
+ | ## {{level|Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной}} | ||
+ | ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}} | ||
+ | #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}} | ||
+ | ### {{level|Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}} | ||
+ | #### {{level|Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}} | ||
+ | ## {{level|Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной}} | ||
+ | ### {{level|Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду}} | ||
+ | #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}} | ||
+ | #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}} | ||
+ | ### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}} | ||
+ | ## {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ||
+ | # {{level|Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной}} | ||
+ | ## {{level|Разложения на две унитарные и одну двухдиагональную матрицы}} | ||
+ | ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}} | ||
+ | ### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}} | ||
+ | ## {{level|Разложения на две унитарные и одну диагональную матрицы}} | ||
+ | ### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}} | ||
+ | #### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}} | ||
+ | ##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}} | ||
+ | ###### {{level|Итерация алгоритма dqds}} | ||
− | # | + | ==Решение систем линейных уравнений== |
− | # | + | # {{level|Прямые методы решения СЛАУ}} |
− | # | + | ## {{level|Linpack benchmark}} |
− | # | + | ## {{level|Методы решения СЛАУ с матрицами специального вида}} |
+ | ### {{level|Методы решения СЛАУ с треугольными матрицами}} | ||
+ | #### {{level|Прямая подстановка (вещественный вариант)}} | ||
+ | #### {{level|Обратная подстановка (вещественный вариант)}} | ||
+ | #### {{level|Методы решения СЛАУ с двудиагональными матрицами}} | ||
+ | ##### {{level|Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей}} | ||
+ | ##### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}} | ||
+ | ##### {{level|Последовательно-параллельный вариант обратной подстановки}} | ||
+ | ### {{level|Методы решения СЛАУ с трёхдиагональными матрицами}} | ||
+ | #### {{level|Методы, основанные на стандартном LU-разложении матрицы}} | ||
+ | ##### {{level|Прогонка}} | ||
+ | ###### {{level|Прогонка, точечный вариант}} | ||
+ | ###### {{level|Классическая монотонная прогонка, повторный вариант}} | ||
+ | ##### {{level|Метод сдваивания Стоуна}} | ||
+ | ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}} | ||
+ | ###### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}} | ||
+ | ##### {{level|Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками}} | ||
+ | #### Другие методы | ||
+ | ##### {{level|Метод редукции}} | ||
+ | ###### {{level|Полный метод редукции}} | ||
+ | ###### {{level|Повторный метод редукции для новой правой части}} | ||
+ | ##### {{level|Встречная прогонка}} | ||
+ | ###### {{level|Встречная прогонка, точечный вариант}} | ||
+ | ###### {{level|Повторная встречная прогонка, точечный вариант}} | ||
+ | ##### {{level|Метод циклической редукции}} | ||
+ | ###### {{level|Полный метод циклической редукции}} | ||
+ | ###### {{level|Повторный метод циклической редукции для новой правой части}} | ||
+ | ##### {{level|Метод окаймления}} | ||
+ | ### Методы решения СЛАУ с блочно-треугольными матрицами | ||
+ | #### {{level|Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка}} | ||
+ | #### {{level|Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка}} | ||
+ | #### Методы решения СЛАУ с блочно-двухдиагональными матрицами | ||
+ | ##### {{level|Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей}} | ||
+ | ##### {{level|Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ}} | ||
+ | ##### {{level|Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ}} | ||
+ | ### {{level|Методы решения СЛАУ с блочно-трёхдиагональными матрицами}} | ||
+ | #### Методы, основанные на стандартном LU-разложении матрицы | ||
+ | ##### {{level|Блочная прогонка}} | ||
+ | ##### {{level|Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}} | ||
+ | #### Другие методы | ||
+ | ##### {{level|Встречная прогонка, блочный вариант}} | ||
+ | ##### {{level|Блочный метод циклической редукции}} | ||
+ | ##### {{level|Блочный метод окаймления}} | ||
+ | ## {{level|Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы}} | ||
+ | # Итерационные методы решения СЛАУ | ||
+ | ## {{level|High Performance Conjugate Gradient (HPCG) benchmark}} | ||
+ | ## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}} | ||
+ | ## {{level|Алгоритм_Качмажа}} | ||
− | == | + | ==Решения спектральных задач== |
+ | # {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ||
+ | ## {{level|QR-алгоритм}} | ||
+ | ### {{level|QR-алгоритм, используемый в SCALAPACK}} | ||
+ | #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}} | ||
+ | #### {{level|QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK}} | ||
+ | ### {{level|QR-алгоритм для симметричных матриц, используемый в SCALAPACK}} | ||
+ | #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}} | ||
+ | #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}} | ||
+ | ### {{level|QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK}} | ||
+ | #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}} | ||
+ | #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}} | ||
+ | ## {{level|Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц}} | ||
+ | ### {{level|Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице}} | ||
+ | ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением}} | ||
+ | ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами}} | ||
+ | ## {{level|Метод Ланцоша}} | ||
+ | ### {{level|Алгоритм Ланцоша для точной арифметики (без переортогонализации)}} | ||
+ | # {{level|Частичная спектральная задача}} | ||
+ | ## {{level|Метод бисекций}} | ||
+ | # {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}} | ||
+ | ## {{level|Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц}} | ||
+ | ### {{level|Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором}} | ||
+ | ### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}} | ||
+ | ## {{level|QR-алгоритм в приложении к сингулярному разложению}} | ||
+ | ==Алгебра многочленов== | ||
+ | # {{level|Схема Горнера, вещественная версия, последовательный вариант}} | ||
− | # | + | = Алгоритмы на списках и массивах = |
+ | ==Алгоритмы поиска== | ||
+ | # {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, <math>O(n)</math> | ||
+ | # {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, <math>O(\log(n))</math> | ||
+ | ==Алгоритмы сортировки== | ||
+ | # {{level|Сортировка с помощью двоичного дерева}} | ||
+ | # {{level|Сортировка пузырьком}} | ||
+ | # {{level|Сортировка слиянием (последовательный и параллельный варианты)}} | ||
+ | ==Алгоритмы на графах== | ||
+ | # Обход графа | ||
+ | ## {{level|Поиск в ширину (BFS)}} | ||
+ | ## {{level|Поиск в глубину (DFS)}} | ||
+ | # {{level|Поиск кратчайшего пути от одной вершины (SSSP)}} | ||
+ | ## {{level|Поиск в ширину (BFS)}} (для невзвешенных графов) | ||
+ | ## {{level|Алгоритм Дейкстры}} | ||
+ | ## {{level|Алгоритм Беллмана-Форда}} | ||
+ | ## {{level|Алгоритм Δ-шагания}} | ||
+ | # {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}} | ||
+ | ## {{level|Алгоритм Джонсона}} | ||
+ | ## {{level|Алгоритм Флойда-Уоршелла}} | ||
+ | # {{level|Поиск транзитивного замыкания орграфа}} | ||
+ | ## {{level|Алгоритм Пурдома}} | ||
+ | # {{level|Определение диаметра графа}} | ||
+ | # {{level|Построение минимального остовного дерева (MST)}} | ||
+ | ## {{level|Алгоритм Борувки}} | ||
+ | ## {{level|Алгоритм Крускала}} | ||
+ | ## {{level|Алгоритм Прима}} | ||
+ | ## {{level|Алгоритм GHS}} | ||
+ | # {{level|Поиск изоморфных подграфов}} | ||
+ | ## {{level|Алгоритм Ульмана}} | ||
+ | ## {{level|Алгоритм VF2}} | ||
+ | # {{level|Связность в графах}} | ||
+ | ## {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}} | ||
+ | ## {{level|Система непересекающихся множеств}} | ||
+ | ## {{level|Алгоритм Тарьяна поиска компонент сильной связности}} | ||
+ | ## {{level|Алгоритм DCSC поиска компонент сильной связности}} | ||
+ | ## {{level|Алгоритм Тарьяна поиска компонент двусвязности}} | ||
+ | ## {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}} | ||
+ | ## {{level|Алгоритм Тарьяна поиска «мостов» в графе}} | ||
+ | ## {{level|Определение вершинной связности графа}} | ||
+ | ## {{level|Алгоритм Габова определения рёберной связности графа}} | ||
+ | # {{level|Поиск максимального потока в транспортной сети}} | ||
+ | ## {{level|Алгоритм Форда-Фалкерсона}} | ||
+ | ## {{level|Алгоритм проталкивания предпотока}} | ||
+ | # {{level|Поиск потока минимальной стоимости в транспортной сети}} | ||
+ | # {{level|Задача о назначениях}} | ||
+ | ## {{level|Венгерский алгоритм}} | ||
+ | ## {{level|Алгоритм аукциона}} | ||
+ | ## {{level|Алгоритм Гопкрофта-Карпа}} | ||
+ | # {{level|Вычисление betweenness centrality|Вычисление центральности вершин}} | ||
+ | =Вычислительная геометрия= | ||
+ | # {{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|Стохастическое двойственное динамическое программирование (SDDP)}} | ||
+ | ==Решение систем нелинейных уравнений== | ||
+ | # {{level|Метод Ньютона для систем нелинейных уравнений}} | ||
+ | ==Численные методы интегрирования== | ||
+ | # {{level|Квадратурные формулы}} | ||
+ | # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}} | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]] | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]] | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]] | ||
+ | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]] | ||
+ | ==Алгоритмы решения уравнений математической физики== | ||
+ | # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}} | ||
+ | =Криптографические алгоритмы= | ||
+ | # {{level|Метод встречи посередине}} | ||
+ | =Другие алгоритмы= | ||
− | + | [[en:Algorithm classification]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | [[Категория:Алгоритмы|*]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Текущая версия на 22:20, 25 декабря 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 Численные методы интегрирования
- Квадратурные формулы
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)