Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
| [досмотренная версия] | [досмотренная версия] |
Konshin (обсуждение | вклад) |
Konshin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | __TOC__ | |
| − | + | =Векторные операции= | |
| − | + | # {{level|Суммирование сдваиванием}} | |
| − | + | ## {{level|Нахождение суммы элементов массива сдваиванием}} | |
| − | + | ## {{level|Нахождение частных сумм элементов массива сдваиванием}} | |
| − | + | # {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}} | |
| − | + | # {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}} | |
| − | + | # {{level|Последовательно-параллельный метод суммирования}} | |
| − | + | =Матрично-векторные операции | |
| − | + | # {{level|Умножение плотной матрицы на вектор}} | |
| − | + | ## {{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|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}} | ||
| − | + | ##### {{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|High Performance Conjugate Gradient (HPCG) benchmark}} | ||
| − | ## {{level| | + | ## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}} |
| − | # {{level| | + | ## {{level|Алгоритм_Качмажа}} |
| − | + | =Решение систем нелинейных уравнений= | |
| − | + | # {{level|Метод Ньютона для систем нелинейных уравнений}} | |
| − | + | =Решения спектральных задач= | |
| − | ## {{level| | + | # {{level|Спектральное разложение (нахождение собственных значений и векторов)}} |
| − | # | + | ## {{level|QR-алгоритм}} |
| − | ## {{level| | + | ### {{level|QR-алгоритм, используемый в SCALAPACK}} |
| − | ## {{level| | + | #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}} |
| − | ### | + | #### {{level|QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK}} |
| − | ### | + | ### {{level|QR-алгоритм для симметричных матриц, используемый в SCALAPACK}} |
| − | ### | + | #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}} |
| − | ### | + | #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}} |
| − | # | + | ### {{level|QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK}} |
| − | ## | + | #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}} |
| − | ### {{level| | + | #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}} |
| − | ### {{level| | + | ## {{level|Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц}} |
| − | ## {{level| | + | ### {{level|Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице}} |
| − | ### {{level| | + | ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением}} |
| − | ### {{level| | + | ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами}} |
| − | ### {{level| | + | ## {{level|Метод Ланцоша}} |
| − | + | ### {{level|Алгоритм Ланцоша для точной арифметики (без переортогонализации)}} | |
| − | ## {{level| | + | # {{level|Частичная спектральная задача}} |
| − | + | ## {{level|Метод бисекций}} | |
| − | + | # {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}} | |
| − | + | ## {{level|Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц}} | |
| − | + | ### {{level|Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором}} | |
| − | ## {{level| | + | ### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}} |
| − | ## {{level| | + | ## {{level|QR-алгоритм в приложении к сингулярному разложению}} |
| − | + | =Тесты производительности компьютеров= | |
| − | + | # {{level|High Performance Conjugate Gradient (HPCG) benchmark}} | |
| − | + | # {{level|Linpack benchmark}} | |
| − | + | =Преобразование Фурье= | |
| − | ## {{level| | + | # {{level|Быстрое преобразование Фурье}} |
| − | + | ## {{level|Быстрое преобразование Фурье для степеней двойки}} | |
| − | + | =Алгебра многочленов= | |
| − | + | # {{level|Схема Горнера, вещественная версия, последовательный вариант}} | |
| − | ### | + | =Численные методы интегрирования= |
| − | ### | + | # {{level|Квадратурные формулы}} |
| − | ## | + | # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}} |
| − | ### | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]] |
| − | ### {{level| | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]] |
| − | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]] | |
| − | + | ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]] | |
| − | + | =Алгоритмы на графах= | |
| − | + | # Обход графа | |
| − | + | ## {{level|Поиск в ширину (BFS)}} | |
| − | + | ## {{level|Поиск в глубину (DFS)}} | |
| − | + | # {{level|Поиск кратчайшего пути от одной вершины (SSSP)}} | |
| − | + | ## {{level|Поиск в ширину (BFS)}} (для невзвешенных графов) | |
| − | ## {{level| | + | ## {{level|Алгоритм Дейкстры}} |
| − | + | ## {{level|Алгоритм Беллмана-Форда}} | |
| − | + | ## {{level|Алгоритм Δ-шагания}} | |
| − | + | # {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}} | |
| − | + | ## {{level|Алгоритм Джонсона}} | |
| − | # | + | ## {{level|Алгоритм Флойда-Уоршелла}} |
| − | ## {{level| | + | # {{level|Поиск транзитивного замыкания орграфа}} |
| − | ## {{level| | + | ## {{level|Алгоритм Пурдома}} |
| − | # | + | # {{level|Определение диаметра графа}} |
| − | ## {{level| | + | # {{level|Построение минимального остовного дерева (MST)}} |
| − | + | ## {{level|Алгоритм Борувки}} | |
| − | ## {{level| | + | ## {{level|Алгоритм Крускала}} |
| − | + | ## {{level|Алгоритм Прима}} | |
| − | ## {{level| | + | ## {{level|Алгоритм GHS}} |
| − | ## {{level| | + | # {{level|Поиск изоморфных подграфов}} |
| − | ## {{level| | + | ## {{level|Алгоритм Ульмана}} |
| − | ## {{level| | + | ## {{level|Алгоритм VF2}} |
| − | ## {{level| | + | # {{level|Связность в графах}} |
| − | ## {{level| | + | ## {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}} |
| − | ## {{level| | + | ## {{level|Система непересекающихся множеств}} |
| − | # | + | ## {{level|Алгоритм Тарьяна поиска компонент сильной связности}} |
| − | ## {{level| | + | ## {{level|Алгоритм DCSC поиска компонент сильной связности}} |
| − | ## {{level|Алгоритм | + | ## {{level|Алгоритм Тарьяна поиска компонент двусвязности}} |
| − | + | ## {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}} | |
| − | ## {{level| | + | ## {{level|Алгоритм Тарьяна поиска «мостов» в графе}} |
| − | # | + | ## {{level|Определение вершинной связности графа}} |
| − | ## {{level| | + | ## {{level|Алгоритм Габова определения рёберной связности графа}} |
| − | # | + | # {{level|Поиск максимального потока в транспортной сети}} |
| − | + | ## {{level|Алгоритм Форда-Фалкерсона}} | |
| − | + | ## {{level|Алгоритм проталкивания предпотока}} | |
| − | + | # {{level|Поиск потока минимальной стоимости в транспортной сети}} | |
| − | + | # {{level|Задача о назначениях}} | |
| − | # | + | ## {{level|Венгерский алгоритм}} |
| − | + | ## {{level|Алгоритм аукциона}} | |
| − | + | ## {{level|Алгоритм Гопкрофта-Карпа}} | |
| − | + | # {{level|Вычисление betweenness centrality|Вычисление центральности вершин}} | |
| − | + | =Алгоритмы поиска= | |
| − | + | # {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, <math>O(n)</math> | |
| − | + | # {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, <math>O(\log(n))</math> | |
| − | + | =Алгоритмы сортировки= | |
| − | # | + | # {{level|Сортировка с помощью двоичного дерева}} |
| − | + | # {{level|Сортировка пузырьком}} | |
| − | + | # {{level|Сортировка слиянием (последовательный и параллельный варианты)}} | |
| − | + | =Вычислительная геометрия= | |
| − | + | # {{level|Поиск диаметра множества точек}} | |
| − | + | # {{level|Построение выпуклой оболочки набора точек}} | |
| − | + | # {{level|Триангуляция Делоне}} | |
| − | + | # {{level|Диаграмма Вороного}} | |
| − | + | # {{level|Принадлежность точки многоугольнику}} | |
| − | + | # {{level|Пересечения выпуклых многоугольников}} - трудоёмкость <math>O(n_1 + n_2)</math> | |
| − | + | # {{level|Пересечение звёздных многоугольников}} - трудоёмкость <math>O(n_1 \cdot n_2)</math> | |
| + | =Компьютерная графика= | ||
| + | # {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}} | ||
| + | # {{level|Алгоритм определения видимых частей трёхмерной сцены}} | ||
| + | # {{level|Трассировка лучей - рендеринг реалистичных изображений}} | ||
| + | # {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}} | ||
| + | =Криптографические алгоритмы= | ||
| + | # {{level|Метод встречи посередине}} | ||
| + | =Нейронные сети= | ||
| + | # {{level|Распознование образов}} | ||
| + | ## {{level|Распознование текста}} | ||
| + | ## {{level|Распознование речи}} | ||
| + | ## {{level|Распознование лиц}} | ||
| + | =Алгоритмы оптимизации= | ||
| + | # {{level|Линейное программирование}} | ||
| + | # {{level|Симплекс-метод}} | ||
| + | # {{level|Метод ветвей и границ}} | ||
| + | # {{level|Генетические алгоритмы}} | ||
| + | # {{level|Муравьиные алгоритмы}} | ||
| + | # {{level|Комбинированные алгоритмы}} | ||
| + | # {{level|Стохастическое двойственное динамическое программирование (SDDP)}} | ||
| + | =Алгоритмы машинного обучения= | ||
| + | # {{level|Алгоритм k средних (k-means)}} | ||
| + | =Алгоритмы теории игр= | ||
| + | =Алгоритмы моделирования квантовых систем= | ||
| + | # {{level|Алгоритмы моделирования квантовых вычислений}} | ||
| + | ## {{level|Однокубитное преобразование вектора-состояния}} | ||
| + | ## {{level|Двухкубитное преобразование вектора-состояния}} | ||
| + | ## {{level|Моделирование квантового преобразования Фурье}} | ||
| + | =Алгоритмы решения уравнений математической физики= | ||
| + | # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}} | ||
| + | =Другие алгоритмы= | ||
[[en:Algorithm classification]] | [[en:Algorithm classification]] | ||
[[Категория:Алгоритмы|*]] | [[Категория:Алгоритмы|*]] | ||
Версия 11:51, 18 января 2018
Содержание
- 1 Векторные операции
- 2 Матричные операции
- 3 Разложения матриц
- 4 Решение систем линейных уравнений
- 5 Решение систем нелинейных уравнений
- 6 Решения спектральных задач
- 7 Тесты производительности компьютеров
- 8 Преобразование Фурье
- 9 Алгебра многочленов
- 10 Численные методы интегрирования
- 11 Алгоритмы на графах
- 12 Алгоритмы поиска
- 13 Алгоритмы сортировки
- 14 Вычислительная геометрия
- 15 Компьютерная графика
- 16 Криптографические алгоритмы
- 17 Нейронные сети
- 18 Алгоритмы оптимизации
- 19 Алгоритмы машинного обучения
- 20 Алгоритмы теории игр
- 21 Алгоритмы моделирования квантовых систем
- 22 Алгоритмы решения уравнений математической физики
- 23 Другие алгоритмы
1 Векторные операции
Суммирование сдваиванием
Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант- Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
- Последовательно-параллельный метод суммирования
=Матрично-векторные операции
2 Матричные операции
3 Разложения матриц
Треугольные разложения
- Метод Гаусса (нахождение LU-разложения)
- Метод Холецкого (нахождение симметричного треугольного разложения)
- Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- Известные треугольные разложения для матриц специального вида
- Унитарно-треугольные разложения
- Подобные разложения
- Подобные разложения на унитарные и хессенберговы матрицы
- Симметричные разложения на унитарные и трёхдиагональные матрицы
- Спектральное разложение (нахождение собственных значений и векторов)
- Неподобные унитарные разложения
4 Решение систем линейных уравнений
- Прямые методы решения СЛАУ
- Linpack benchmark
- Методы решения СЛАУ с матрицами специального вида
- Методы решения СЛАУ с треугольными матрицами
- Методы решения СЛАУ с трёхдиагональными матрицами
- Методы решения СЛАУ с блочно-треугольными матрицами
- Блочная прямая подстановка (вещественный вариант)
- Блочная обратная подстановка (вещественный вариант)
- Методы решения СЛАУ с блочно-двухдиагональными матрицами
- Методы решения СЛАУ с блочно-трёхдиагональными матрицами
- Методы, основанные на стандартном LU-разложении матрицы
- Другие методы
- Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
- Итерационные методы решения СЛАУ
5 Решение систем нелинейных уравнений
6 Решения спектральных задач
- Спектральное разложение (нахождение собственных значений и векторов)
- Частичная спектральная задача
- Сингулярное разложение (нахождение сингулярных значений и векторов)
7 Тесты производительности компьютеров
8 Преобразование Фурье
9 Алгебра многочленов
10 Численные методы интегрирования
- Квадратурные формулы
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
11 Алгоритмы на графах
- Обход графа
- Поиск кратчайшего пути от одной вершины (SSSP)
- Поиск в ширину (BFS) (для невзвешенных графов)
- Алгоритм Дейкстры
- Алгоритм Беллмана-Форда
- Алгоритм Δ-шагания
- Поиск кратчайшего пути для всех пар вершин (APSP)
- Поиск транзитивного замыкания орграфа
- Определение диаметра графа
- Построение минимального остовного дерева (MST)
- Поиск изоморфных подграфов
- Связность в графах
- Алгоритм Шилоаха-Вишкина поиска компонент связности
- Система непересекающихся множеств
- Алгоритм Тарьяна поиска компонент сильной связности
- Алгоритм DCSC поиска компонент сильной связности
- Алгоритм Тарьяна поиска компонент двусвязности
- Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
- Алгоритм Тарьяна поиска «мостов» в графе
- Определение вершинной связности графа
- Алгоритм Габова определения рёберной связности графа
- Поиск максимального потока в транспортной сети
- Поиск потока минимальной стоимости в транспортной сети
- Задача о назначениях
- Вычисление betweenness centrality
12 Алгоритмы поиска
- Линейный поиск - находит элемент в любом списке, [math]O(n)[/math]
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(\log(n))[/math]
13 Алгоритмы сортировки
- Сортировка с помощью двоичного дерева
- Сортировка пузырьком
- Сортировка слиянием (последовательный и параллельный варианты)
14 Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
- Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 \cdot n_2)[/math]
15 Компьютерная графика
- Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
- Алгоритм определения видимых частей трёхмерной сцены
- Трассировка лучей - рендеринг реалистичных изображений
- Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
16 Криптографические алгоритмы
17 Нейронные сети
18 Алгоритмы оптимизации
- Линейное программирование
- Симплекс-метод
- Метод ветвей и границ
- Генетические алгоритмы
- Муравьиные алгоритмы
- Комбинированные алгоритмы
- Стохастическое двойственное динамическое программирование (SDDP)
