Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
| [выверенная версия] | [выверенная версия] |
Frolov (обсуждение | вклад) |
Dolganov (обсуждение | вклад) (Перенаправление на Служебная:Pma tree) |
||
| (не показано 106 промежуточных версий 10 участников) | |||
| Строка 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]] | [[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 Численные методы интегрирования
- Квадратурные формулы
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
