https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/api.php?action=feedcontributions&feedformat=atom&user=Dolganov Алговики - Вклад [ru] 2026-10-22T16:05:06Z Вклад MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&diff=26860 Классификация алгоритмов 2018-12-25T19:20:25Z <p>Dolganov: Перенаправление на Служебная:Pma tree</p> <hr /> <div>#redirect [[Special:Pma_tree]]<br /> __TOC__<br /> = Задачи алгебры =<br /> ==Матричные и векторные операции==<br /> ===Векторные операции===<br /> # {{level|Суммирование сдваиванием}}<br /> ## {{level|Нахождение суммы элементов массива сдваиванием}}<br /> ## {{level|Нахождение частных сумм элементов массива сдваиванием}}<br /> # {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}}<br /> # {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}}<br /> # {{level|Последовательно-параллельный метод суммирования}}<br /> === Умножения матриц на вектор ===<br /> ==== Умножения неособенных матриц на вектор ====<br /> # {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}}<br /> ==== Умножения матриц специального вида на вектор ====<br /> # {{level|Преобразование Фурье}}<br /> ## {{level|Быстрое преобразование Фурье для составной размерности}}<br /> ### {{level|Быстрое преобразование Фурье для степеней двойки}}<br /> #### {{level|Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки}}<br /> #### {{level|Быстрое преобразование Фурье для чётных степеней двойки}}<br /> ### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}}<br /> ## {{level|Быстрое преобразование Фурье для простой размерности}}<br /> ===Матричные операции===<br /> # {{level|Умножение плотных матриц}}<br /> ## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}}<br /> ## {{level|Метод Штрассена}}<br /> ==Разложения матриц==<br /> {{level|Задача разложения матриц}}<br /> # {{level|Треугольные разложения}}<br /> ## {{level|Метод Гаусса (нахождение LU-разложения)}}<br /> ### {{level|LU-разложение методом Гаусса без перестановок}}<br /> #### {{level|LU-разложение методом Гаусса}}<br /> #### {{level|Компактная схема метода Гаусса и её модификации}}<br /> ##### {{level|Компактная схема метода Гаусса для плотной матрицы}}<br /> ##### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации}}<br /> ###### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант}}<br /> ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}<br /> ###### {{level|Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы}}<br /> ### {{level|LU-разложение методом Гаусса с перестановками}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по столбцу}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по строке}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по главной диагонали}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по всей матрице}}<br /> ## {{level|Метод Холецкого (нахождение симметричного треугольного разложения)}}<br /> ### {{level|Разложение Холецкого (метод квадратного корня)}} базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы<br /> # {{level|Известные треугольные разложения для матриц специального вида}}<br /> # {{level|Унитарно-треугольные разложения}}<br /> ## {{level|QR-разложения плотных неособенных матриц}}<br /> ### {{level|Метод Гивенса (вращений) QR-разложения матрицы}}<br /> #### {{level|Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)}}<br /> ### {{level|Метод Хаусхолдера (отражений) QR-разложения матрицы}}<br /> #### {{level|Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант}}<br /> ### {{level|Метод ортогонализации}}<br /> #### {{level|Классический метод ортогонализации}}<br /> #### {{level|Метод ортогонализации с переортогонализацией}}<br /> ### {{level|Метод треугольного разложения матрицы Грама}}<br /> ## {{level|Методы QR-разложения плотных хессенберговых матриц}}<br /> ### {{level|Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)}}<br /> ### {{level|Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)}}<br /> # {{level|Разложения, содержащие матрицу, подобную исходной}}<br /> ## {{level|Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> ## {{level|Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}}<br /> ## {{level|Спектральное разложение (нахождение собственных значений и векторов)}}<br /> # {{level|Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной}}<br /> ## {{level|Разложения на две унитарные и одну двухдиагональную матрицы}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}}<br /> ## {{level|Разложения на две унитарные и одну диагональную матрицы}}<br /> ### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}<br /> #### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}}<br /> ##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}}<br /> ###### {{level|Итерация алгоритма dqds}}<br /> <br /> ==Решение систем линейных уравнений==<br /> # {{level|Прямые методы решения СЛАУ}}<br /> ## {{level|Linpack benchmark}}<br /> ## {{level|Методы решения СЛАУ с матрицами специального вида}}<br /> ### {{level|Методы решения СЛАУ с треугольными матрицами}}<br /> #### {{level|Прямая подстановка (вещественный вариант)}}<br /> #### {{level|Обратная подстановка (вещественный вариант)}}<br /> #### {{level|Методы решения СЛАУ с двудиагональными матрицами}}<br /> ##### {{level|Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей}}<br /> ##### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}<br /> ##### {{level|Последовательно-параллельный вариант обратной подстановки}}<br /> ### {{level|Методы решения СЛАУ с трёхдиагональными матрицами}}<br /> #### {{level|Методы, основанные на стандартном LU-разложении матрицы}}<br /> ##### {{level|Прогонка}}<br /> ###### {{level|Прогонка, точечный вариант}}<br /> ###### {{level|Классическая монотонная прогонка, повторный вариант}}<br /> ##### {{level|Метод сдваивания Стоуна}}<br /> ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}<br /> ###### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}<br /> ##### {{level|Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками}}<br /> #### Другие методы<br /> ##### {{level|Метод редукции}}<br /> ###### {{level|Полный метод редукции}}<br /> ###### {{level|Повторный метод редукции для новой правой части}}<br /> ##### {{level|Встречная прогонка}}<br /> ###### {{level|Встречная прогонка, точечный вариант}}<br /> ###### {{level|Повторная встречная прогонка, точечный вариант}}<br /> ##### {{level|Метод циклической редукции}}<br /> ###### {{level|Полный метод циклической редукции}}<br /> ###### {{level|Повторный метод циклической редукции для новой правой части}}<br /> ##### {{level|Метод окаймления}}<br /> ### Методы решения СЛАУ с блочно-треугольными матрицами<br /> #### {{level|Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка}}<br /> #### {{level|Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка}}<br /> #### Методы решения СЛАУ с блочно-двухдиагональными матрицами<br /> ##### {{level|Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей}}<br /> ##### {{level|Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ}}<br /> ##### {{level|Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ}}<br /> ### {{level|Методы решения СЛАУ с блочно-трёхдиагональными матрицами}}<br /> #### Методы, основанные на стандартном LU-разложении матрицы<br /> ##### {{level|Блочная прогонка}}<br /> ##### {{level|Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}}<br /> #### Другие методы<br /> ##### {{level|Встречная прогонка, блочный вариант}}<br /> ##### {{level|Блочный метод циклической редукции}}<br /> ##### {{level|Блочный метод окаймления}}<br /> ## {{level|Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы}}<br /> # Итерационные методы решения СЛАУ<br /> ## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}<br /> ## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}}<br /> ## {{level|Алгоритм_Качмажа}}<br /> <br /> ==Решения спектральных задач==<br /> # {{level|Спектральное разложение (нахождение собственных значений и векторов)}}<br /> ## {{level|QR-алгоритм}}<br /> ### {{level|QR-алгоритм, используемый в SCALAPACK}}<br /> #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK}}<br /> ### {{level|QR-алгоритм для симметричных матриц, используемый в SCALAPACK}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}<br /> #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}<br /> ### {{level|QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}<br /> #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}<br /> ## {{level|Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц}}<br /> ### {{level|Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице}}<br /> ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением}}<br /> ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами}}<br /> ## {{level|Метод Ланцоша}}<br /> ### {{level|Алгоритм Ланцоша для точной арифметики (без переортогонализации)}}<br /> # {{level|Частичная спектральная задача}}<br /> ## {{level|Метод бисекций}}<br /> # {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}<br /> ## {{level|Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц}}<br /> ### {{level|Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором}}<br /> ### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}}<br /> ## {{level|QR-алгоритм в приложении к сингулярному разложению}}<br /> ==Алгебра многочленов==<br /> # {{level|Схема Горнера, вещественная версия, последовательный вариант}}<br /> <br /> = Алгоритмы на списках и массивах =<br /> ==Алгоритмы поиска==<br /> # {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, &lt;math&gt;O(n)&lt;/math&gt;<br /> # {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, &lt;math&gt;O(\log(n))&lt;/math&gt;<br /> ==Алгоритмы сортировки==<br /> # {{level|Сортировка с помощью двоичного дерева}}<br /> # {{level|Сортировка пузырьком}}<br /> # {{level|Сортировка слиянием (последовательный и параллельный варианты)}}<br /> ==Алгоритмы на графах==<br /> # Обход графа<br /> ## {{level|Поиск в ширину (BFS)}}<br /> ## {{level|Поиск в глубину (DFS)}}<br /> # {{level|Поиск кратчайшего пути от одной вершины (SSSP)}} <br /> ## {{level|Поиск в ширину (BFS)}} (для невзвешенных графов)<br /> ## {{level|Алгоритм Дейкстры}} <br /> ## {{level|Алгоритм Беллмана-Форда}} <br /> ## {{level|Алгоритм Δ-шагания}} <br /> # {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}} <br /> ## {{level|Алгоритм Джонсона}}<br /> ## {{level|Алгоритм Флойда-Уоршелла}}<br /> # {{level|Поиск транзитивного замыкания орграфа}}<br /> ## {{level|Алгоритм Пурдома}}<br /> # {{level|Определение диаметра графа}}<br /> # {{level|Построение минимального остовного дерева (MST)}}<br /> ## {{level|Алгоритм Борувки}}<br /> ## {{level|Алгоритм Крускала}}<br /> ## {{level|Алгоритм Прима}}<br /> ## {{level|Алгоритм GHS}}<br /> # {{level|Поиск изоморфных подграфов}}<br /> ## {{level|Алгоритм Ульмана}}<br /> ## {{level|Алгоритм VF2}}<br /> # {{level|Связность в графах}}<br /> ## {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}}<br /> ## {{level|Система непересекающихся множеств}}<br /> ## {{level|Алгоритм Тарьяна поиска компонент сильной связности}}<br /> ## {{level|Алгоритм DCSC поиска компонент сильной связности}}<br /> ## {{level|Алгоритм Тарьяна поиска компонент двусвязности}}<br /> ## {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}}<br /> ## {{level|Алгоритм Тарьяна поиска «мостов» в графе}}<br /> ## {{level|Определение вершинной связности графа}}<br /> ## {{level|Алгоритм Габова определения рёберной связности графа}}<br /> # {{level|Поиск максимального потока в транспортной сети}}<br /> ## {{level|Алгоритм Форда-Фалкерсона}}<br /> ## {{level|Алгоритм проталкивания предпотока}}<br /> # {{level|Поиск потока минимальной стоимости в транспортной сети}}<br /> # {{level|Задача о назначениях}}<br /> ## {{level|Венгерский алгоритм}}<br /> ## {{level|Алгоритм аукциона}}<br /> ## {{level|Алгоритм Гопкрофта-Карпа}}<br /> # {{level|Вычисление betweenness centrality|Вычисление центральности вершин}}<br /> =Вычислительная геометрия=<br /> # {{level|Поиск диаметра множества точек}}<br /> # {{level|Построение выпуклой оболочки набора точек}}<br /> # {{level|Триангуляция Делоне}}<br /> # {{level|Диаграмма Вороного}}<br /> # {{level|Принадлежность точки многоугольнику}}<br /> # {{level|Пересечения выпуклых многоугольников}} <br /> # {{level|Пересечение звёздных многоугольников}}<br /> ==Компьютерная графика==<br /> # {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}}<br /> # {{level|Алгоритм определения видимых частей трёхмерной сцены}}<br /> # {{level|Трассировка лучей - рендеринг реалистичных изображений}}<br /> # {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}}<br /> <br /> =Исследование и моделирование компьютеров=<br /> ==Тесты производительности компьютеров==<br /> # {{level|High Performance Conjugate Gradient (HPCG) benchmark}}<br /> # {{level|Linpack benchmark}}<br /> ==Алгоритмы моделирования квантовых систем==<br /> # {{level|Алгоритмы моделирования квантовых вычислений}}<br /> ## {{level|Однокубитное преобразование вектора-состояния}}<br /> ## {{level|Двухкубитное преобразование вектора-состояния}}<br /> ## {{level|Моделирование квантового преобразования Фурье}}<br /> ==Алгоритмы машинного обучения==<br /> # {{level|Алгоритм k средних (k-means)}}<br /> ===Нейронные сети===<br /> # {{level|Распознавание образов}}<br /> ## {{level|Распознавание текста}}<br /> ## {{level|Распознавание речи}}<br /> ## {{level|Распознавание лиц}}<br /> ===Алгоритмы теории игр===<br /> <br /> = Прикладные задачи из разных областей =<br /> ==Алгоритмы оптимизации==<br /> # {{level|Линейное программирование}}<br /> # {{level|Симплекс-метод}}<br /> # {{level|Метод ветвей и границ}}<br /> # {{level|Генетические алгоритмы}}<br /> # {{level|Муравьиные алгоритмы}}<br /> # {{level|Комбинированные алгоритмы}}<br /> # {{level|Стохастическое двойственное динамическое программирование (SDDP)}}<br /> ==Решение систем нелинейных уравнений==<br /> # {{level|Метод Ньютона для систем нелинейных уравнений}}<br /> ==Численные методы интегрирования==<br /> # {{level|Квадратурные формулы}}<br /> # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}}<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]]<br /> ==Алгоритмы решения уравнений математической физики==<br /> # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}}<br /> =Криптографические алгоритмы=<br /> # {{level|Метод встречи посередине}}<br /> =Другие алгоритмы=<br /> <br /> [[en:Algorithm classification]]<br /> <br /> [[Категория:Алгоритмы|*]]</div> Dolganov https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&diff=26859 Классификация алгоритмов 2018-12-25T18:22:37Z <p>Dolganov: Отмена правки 26858, сделанной участником Dolganov (обс.)</p> <hr /> <div>__TOC__<br /> = Задачи алгебры =<br /> ==Матричные и векторные операции==<br /> ===Векторные операции===<br /> # {{level|Суммирование сдваиванием}}<br /> ## {{level|Нахождение суммы элементов массива сдваиванием}}<br /> ## {{level|Нахождение частных сумм элементов массива сдваиванием}}<br /> # {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}}<br /> # {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}}<br /> # {{level|Последовательно-параллельный метод суммирования}}<br /> === Умножения матриц на вектор ===<br /> ==== Умножения неособенных матриц на вектор ====<br /> # {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}}<br /> ==== Умножения матриц специального вида на вектор ====<br /> # {{level|Преобразование Фурье}}<br /> ## {{level|Быстрое преобразование Фурье для составной размерности}}<br /> ### {{level|Быстрое преобразование Фурье для степеней двойки}}<br /> #### {{level|Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки}}<br /> #### {{level|Быстрое преобразование Фурье для чётных степеней двойки}}<br /> ### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}}<br /> ## {{level|Быстрое преобразование Фурье для простой размерности}}<br /> ===Матричные операции===<br /> # {{level|Умножение плотных матриц}}<br /> ## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}}<br /> ## {{level|Метод Штрассена}}<br /> ==Разложения матриц==<br /> {{level|Задача разложения матриц}}<br /> # {{level|Треугольные разложения}}<br /> ## {{level|Метод Гаусса (нахождение LU-разложения)}}<br /> ### {{level|LU-разложение методом Гаусса без перестановок}}<br /> #### {{level|LU-разложение методом Гаусса}}<br /> #### {{level|Компактная схема метода Гаусса и её модификации}}<br /> ##### {{level|Компактная схема метода Гаусса для плотной матрицы}}<br /> ##### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации}}<br /> ###### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант}}<br /> ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}<br /> ###### {{level|Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы}}<br /> ### {{level|LU-разложение методом Гаусса с перестановками}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по столбцу}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по строке}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по главной диагонали}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по всей матрице}}<br /> ## {{level|Метод Холецкого (нахождение симметричного треугольного разложения)}}<br /> ### {{level|Разложение Холецкого (метод квадратного корня)}} базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы<br /> # {{level|Известные треугольные разложения для матриц специального вида}}<br /> # {{level|Унитарно-треугольные разложения}}<br /> ## {{level|QR-разложения плотных неособенных матриц}}<br /> ### {{level|Метод Гивенса (вращений) QR-разложения матрицы}}<br /> #### {{level|Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)}}<br /> ### {{level|Метод Хаусхолдера (отражений) QR-разложения матрицы}}<br /> #### {{level|Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант}}<br /> ### {{level|Метод ортогонализации}}<br /> #### {{level|Классический метод ортогонализации}}<br /> #### {{level|Метод ортогонализации с переортогонализацией}}<br /> ### {{level|Метод треугольного разложения матрицы Грама}}<br /> ## {{level|Методы QR-разложения плотных хессенберговых матриц}}<br /> ### {{level|Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)}}<br /> ### {{level|Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)}}<br /> # {{level|Разложения, содержащие матрицу, подобную исходной}}<br /> ## {{level|Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> ## {{level|Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}}<br /> ## {{level|Спектральное разложение (нахождение собственных значений и векторов)}}<br /> # {{level|Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной}}<br /> ## {{level|Разложения на две унитарные и одну двухдиагональную матрицы}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}}<br /> ## {{level|Разложения на две унитарные и одну диагональную матрицы}}<br /> ### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}<br /> #### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}}<br /> ##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}}<br /> ###### {{level|Итерация алгоритма dqds}}<br /> <br /> ==Решение систем линейных уравнений==<br /> # {{level|Прямые методы решения СЛАУ}}<br /> ## {{level|Linpack benchmark}}<br /> ## {{level|Методы решения СЛАУ с матрицами специального вида}}<br /> ### {{level|Методы решения СЛАУ с треугольными матрицами}}<br /> #### {{level|Прямая подстановка (вещественный вариант)}}<br /> #### {{level|Обратная подстановка (вещественный вариант)}}<br /> #### {{level|Методы решения СЛАУ с двудиагональными матрицами}}<br /> ##### {{level|Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей}}<br /> ##### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}<br /> ##### {{level|Последовательно-параллельный вариант обратной подстановки}}<br /> ### {{level|Методы решения СЛАУ с трёхдиагональными матрицами}}<br /> #### {{level|Методы, основанные на стандартном LU-разложении матрицы}}<br /> ##### {{level|Прогонка}}<br /> ###### {{level|Прогонка, точечный вариант}}<br /> ###### {{level|Классическая монотонная прогонка, повторный вариант}}<br /> ##### {{level|Метод сдваивания Стоуна}}<br /> ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}<br /> ###### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}<br /> ##### {{level|Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками}}<br /> #### Другие методы<br /> ##### {{level|Метод редукции}}<br /> ###### {{level|Полный метод редукции}}<br /> ###### {{level|Повторный метод редукции для новой правой части}}<br /> ##### {{level|Встречная прогонка}}<br /> ###### {{level|Встречная прогонка, точечный вариант}}<br /> ###### {{level|Повторная встречная прогонка, точечный вариант}}<br /> ##### {{level|Метод циклической редукции}}<br /> ###### {{level|Полный метод циклической редукции}}<br /> ###### {{level|Повторный метод циклической редукции для новой правой части}}<br /> ##### {{level|Метод окаймления}}<br /> ### Методы решения СЛАУ с блочно-треугольными матрицами<br /> #### {{level|Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка}}<br /> #### {{level|Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка}}<br /> #### Методы решения СЛАУ с блочно-двухдиагональными матрицами<br /> ##### {{level|Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей}}<br /> ##### {{level|Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ}}<br /> ##### {{level|Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ}}<br /> ### {{level|Методы решения СЛАУ с блочно-трёхдиагональными матрицами}}<br /> #### Методы, основанные на стандартном LU-разложении матрицы<br /> ##### {{level|Блочная прогонка}}<br /> ##### {{level|Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}}<br /> #### Другие методы<br /> ##### {{level|Встречная прогонка, блочный вариант}}<br /> ##### {{level|Блочный метод циклической редукции}}<br /> ##### {{level|Блочный метод окаймления}}<br /> ## {{level|Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы}}<br /> # Итерационные методы решения СЛАУ<br /> ## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}<br /> ## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}}<br /> ## {{level|Алгоритм_Качмажа}}<br /> <br /> ==Решения спектральных задач==<br /> # {{level|Спектральное разложение (нахождение собственных значений и векторов)}}<br /> ## {{level|QR-алгоритм}}<br /> ### {{level|QR-алгоритм, используемый в SCALAPACK}}<br /> #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK}}<br /> ### {{level|QR-алгоритм для симметричных матриц, используемый в SCALAPACK}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}<br /> #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}<br /> ### {{level|QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}<br /> #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}<br /> ## {{level|Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц}}<br /> ### {{level|Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице}}<br /> ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением}}<br /> ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами}}<br /> ## {{level|Метод Ланцоша}}<br /> ### {{level|Алгоритм Ланцоша для точной арифметики (без переортогонализации)}}<br /> # {{level|Частичная спектральная задача}}<br /> ## {{level|Метод бисекций}}<br /> # {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}<br /> ## {{level|Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц}}<br /> ### {{level|Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором}}<br /> ### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}}<br /> ## {{level|QR-алгоритм в приложении к сингулярному разложению}}<br /> ==Алгебра многочленов==<br /> # {{level|Схема Горнера, вещественная версия, последовательный вариант}}<br /> <br /> = Алгоритмы на списках и массивах =<br /> ==Алгоритмы поиска==<br /> # {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, &lt;math&gt;O(n)&lt;/math&gt;<br /> # {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, &lt;math&gt;O(\log(n))&lt;/math&gt;<br /> ==Алгоритмы сортировки==<br /> # {{level|Сортировка с помощью двоичного дерева}}<br /> # {{level|Сортировка пузырьком}}<br /> # {{level|Сортировка слиянием (последовательный и параллельный варианты)}}<br /> ==Алгоритмы на графах==<br /> # Обход графа<br /> ## {{level|Поиск в ширину (BFS)}}<br /> ## {{level|Поиск в глубину (DFS)}}<br /> # {{level|Поиск кратчайшего пути от одной вершины (SSSP)}} <br /> ## {{level|Поиск в ширину (BFS)}} (для невзвешенных графов)<br /> ## {{level|Алгоритм Дейкстры}} <br /> ## {{level|Алгоритм Беллмана-Форда}} <br /> ## {{level|Алгоритм Δ-шагания}} <br /> # {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}} <br /> ## {{level|Алгоритм Джонсона}}<br /> ## {{level|Алгоритм Флойда-Уоршелла}}<br /> # {{level|Поиск транзитивного замыкания орграфа}}<br /> ## {{level|Алгоритм Пурдома}}<br /> # {{level|Определение диаметра графа}}<br /> # {{level|Построение минимального остовного дерева (MST)}}<br /> ## {{level|Алгоритм Борувки}}<br /> ## {{level|Алгоритм Крускала}}<br /> ## {{level|Алгоритм Прима}}<br /> ## {{level|Алгоритм GHS}}<br /> # {{level|Поиск изоморфных подграфов}}<br /> ## {{level|Алгоритм Ульмана}}<br /> ## {{level|Алгоритм VF2}}<br /> # {{level|Связность в графах}}<br /> ## {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}}<br /> ## {{level|Система непересекающихся множеств}}<br /> ## {{level|Алгоритм Тарьяна поиска компонент сильной связности}}<br /> ## {{level|Алгоритм DCSC поиска компонент сильной связности}}<br /> ## {{level|Алгоритм Тарьяна поиска компонент двусвязности}}<br /> ## {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}}<br /> ## {{level|Алгоритм Тарьяна поиска «мостов» в графе}}<br /> ## {{level|Определение вершинной связности графа}}<br /> ## {{level|Алгоритм Габова определения рёберной связности графа}}<br /> # {{level|Поиск максимального потока в транспортной сети}}<br /> ## {{level|Алгоритм Форда-Фалкерсона}}<br /> ## {{level|Алгоритм проталкивания предпотока}}<br /> # {{level|Поиск потока минимальной стоимости в транспортной сети}}<br /> # {{level|Задача о назначениях}}<br /> ## {{level|Венгерский алгоритм}}<br /> ## {{level|Алгоритм аукциона}}<br /> ## {{level|Алгоритм Гопкрофта-Карпа}}<br /> # {{level|Вычисление betweenness centrality|Вычисление центральности вершин}}<br /> =Вычислительная геометрия=<br /> # {{level|Поиск диаметра множества точек}}<br /> # {{level|Построение выпуклой оболочки набора точек}}<br /> # {{level|Триангуляция Делоне}}<br /> # {{level|Диаграмма Вороного}}<br /> # {{level|Принадлежность точки многоугольнику}}<br /> # {{level|Пересечения выпуклых многоугольников}} <br /> # {{level|Пересечение звёздных многоугольников}}<br /> ==Компьютерная графика==<br /> # {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}}<br /> # {{level|Алгоритм определения видимых частей трёхмерной сцены}}<br /> # {{level|Трассировка лучей - рендеринг реалистичных изображений}}<br /> # {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}}<br /> <br /> =Исследование и моделирование компьютеров=<br /> ==Тесты производительности компьютеров==<br /> # {{level|High Performance Conjugate Gradient (HPCG) benchmark}}<br /> # {{level|Linpack benchmark}}<br /> ==Алгоритмы моделирования квантовых систем==<br /> # {{level|Алгоритмы моделирования квантовых вычислений}}<br /> ## {{level|Однокубитное преобразование вектора-состояния}}<br /> ## {{level|Двухкубитное преобразование вектора-состояния}}<br /> ## {{level|Моделирование квантового преобразования Фурье}}<br /> ==Алгоритмы машинного обучения==<br /> # {{level|Алгоритм k средних (k-means)}}<br /> ===Нейронные сети===<br /> # {{level|Распознавание образов}}<br /> ## {{level|Распознавание текста}}<br /> ## {{level|Распознавание речи}}<br /> ## {{level|Распознавание лиц}}<br /> ===Алгоритмы теории игр===<br /> <br /> = Прикладные задачи из разных областей =<br /> ==Алгоритмы оптимизации==<br /> # {{level|Линейное программирование}}<br /> # {{level|Симплекс-метод}}<br /> # {{level|Метод ветвей и границ}}<br /> # {{level|Генетические алгоритмы}}<br /> # {{level|Муравьиные алгоритмы}}<br /> # {{level|Комбинированные алгоритмы}}<br /> # {{level|Стохастическое двойственное динамическое программирование (SDDP)}}<br /> ==Решение систем нелинейных уравнений==<br /> # {{level|Метод Ньютона для систем нелинейных уравнений}}<br /> ==Численные методы интегрирования==<br /> # {{level|Квадратурные формулы}}<br /> # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}}<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]]<br /> ==Алгоритмы решения уравнений математической физики==<br /> # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}}<br /> =Криптографические алгоритмы=<br /> # {{level|Метод встречи посередине}}<br /> =Другие алгоритмы=<br /> <br /> [[en:Algorithm classification]]<br /> <br /> [[Категория:Алгоритмы|*]]</div> Dolganov https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&diff=26858 Классификация алгоритмов 2018-12-25T18:19:12Z <p>Dolganov: Перенаправление на Служебная:Pma tree</p> <hr /> <div>#redirect [[Special:Pma_tree]]<br /> __TOC__<br /> = Задачи алгебры =<br /> ==Матричные и векторные операции==<br /> ===Векторные операции===<br /> # {{level|Суммирование сдваиванием}}<br /> ## {{level|Нахождение суммы элементов массива сдваиванием}}<br /> ## {{level|Нахождение частных сумм элементов массива сдваиванием}}<br /> # {{level|Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант}}<br /> # {{level|Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант}}<br /> # {{level|Последовательно-параллельный метод суммирования}}<br /> === Умножения матриц на вектор ===<br /> ==== Умножения неособенных матриц на вектор ====<br /> # {{level|Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)}}<br /> ==== Умножения матриц специального вида на вектор ====<br /> # {{level|Преобразование Фурье}}<br /> ## {{level|Быстрое преобразование Фурье для составной размерности}}<br /> ### {{level|Быстрое преобразование Фурье для степеней двойки}}<br /> #### {{level|Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки}}<br /> #### {{level|Быстрое преобразование Фурье для чётных степеней двойки}}<br /> ### {{level|Быстрое преобразование Фурье для составной размерности с небольшими простыми делителями (2,3,5,7)}}<br /> ## {{level|Быстрое преобразование Фурье для простой размерности}}<br /> ===Матричные операции===<br /> # {{level|Умножение плотных матриц}}<br /> ## {{level|Перемножение плотных неособенных матриц (последовательный вещественный вариант)}}<br /> ## {{level|Метод Штрассена}}<br /> ==Разложения матриц==<br /> {{level|Задача разложения матриц}}<br /> # {{level|Треугольные разложения}}<br /> ## {{level|Метод Гаусса (нахождение LU-разложения)}}<br /> ### {{level|LU-разложение методом Гаусса без перестановок}}<br /> #### {{level|LU-разложение методом Гаусса}}<br /> #### {{level|Компактная схема метода Гаусса и её модификации}}<br /> ##### {{level|Компактная схема метода Гаусса для плотной матрицы}}<br /> ##### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации}}<br /> ###### {{level|Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант}}<br /> ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}<br /> ###### {{level|Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы}}<br /> ### {{level|LU-разложение методом Гаусса с перестановками}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по столбцу}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по строке}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по главной диагонали}}<br /> #### {{level|LU-разложение методом Гаусса с выбором ведущего элемента по всей матрице}}<br /> ## {{level|Метод Холецкого (нахождение симметричного треугольного разложения)}}<br /> ### {{level|Разложение Холецкого (метод квадратного корня)}} базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы<br /> # {{level|Известные треугольные разложения для матриц специального вида}}<br /> # {{level|Унитарно-треугольные разложения}}<br /> ## {{level|QR-разложения плотных неособенных матриц}}<br /> ### {{level|Метод Гивенса (вращений) QR-разложения матрицы}}<br /> #### {{level|Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант)}}<br /> ### {{level|Метод Хаусхолдера (отражений) QR-разложения матрицы}}<br /> #### {{level|Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант}}<br /> ### {{level|Метод ортогонализации}}<br /> #### {{level|Классический метод ортогонализации}}<br /> #### {{level|Метод ортогонализации с переортогонализацией}}<br /> ### {{level|Метод треугольного разложения матрицы Грама}}<br /> ## {{level|Методы QR-разложения плотных хессенберговых матриц}}<br /> ### {{level|Метод Гивенса (вращений) QR-разложения хессенберговой матрицы (вещественный вариант)}}<br /> ### {{level|Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)}}<br /> # {{level|Разложения, содержащие матрицу, подобную исходной}}<br /> ## {{level|Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|Классический точечный метод Гивенса (вращений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> ## {{level|Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения к трёхдиагональному виду}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}}<br /> ## {{level|Спектральное разложение (нахождение собственных значений и векторов)}}<br /> # {{level|Разложения с использованием унитарных преобразований, не содержащие матриц, подобной исходной}}<br /> ## {{level|Разложения на две унитарные и одну двухдиагональную матрицы}}<br /> ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}}<br /> ### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}}<br /> ## {{level|Разложения на две унитарные и одну диагональную матрицы}}<br /> ### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}<br /> #### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}}<br /> ##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}}<br /> ###### {{level|Итерация алгоритма dqds}}<br /> <br /> ==Решение систем линейных уравнений==<br /> # {{level|Прямые методы решения СЛАУ}}<br /> ## {{level|Linpack benchmark}}<br /> ## {{level|Методы решения СЛАУ с матрицами специального вида}}<br /> ### {{level|Методы решения СЛАУ с треугольными матрицами}}<br /> #### {{level|Прямая подстановка (вещественный вариант)}}<br /> #### {{level|Обратная подстановка (вещественный вариант)}}<br /> #### {{level|Методы решения СЛАУ с двудиагональными матрицами}}<br /> ##### {{level|Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей}}<br /> ##### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}<br /> ##### {{level|Последовательно-параллельный вариант обратной подстановки}}<br /> ### {{level|Методы решения СЛАУ с трёхдиагональными матрицами}}<br /> #### {{level|Методы, основанные на стандартном LU-разложении матрицы}}<br /> ##### {{level|Прогонка}}<br /> ###### {{level|Прогонка, точечный вариант}}<br /> ###### {{level|Классическая монотонная прогонка, повторный вариант}}<br /> ##### {{level|Метод сдваивания Стоуна}}<br /> ###### {{level|Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы}}<br /> ###### {{level|Метод сдваивания Стоуна для решения двудиагональных СЛАУ}}<br /> ##### {{level|Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками}}<br /> #### Другие методы<br /> ##### {{level|Метод редукции}}<br /> ###### {{level|Полный метод редукции}}<br /> ###### {{level|Повторный метод редукции для новой правой части}}<br /> ##### {{level|Встречная прогонка}}<br /> ###### {{level|Встречная прогонка, точечный вариант}}<br /> ###### {{level|Повторная встречная прогонка, точечный вариант}}<br /> ##### {{level|Метод циклической редукции}}<br /> ###### {{level|Полный метод циклической редукции}}<br /> ###### {{level|Повторный метод циклической редукции для новой правой части}}<br /> ##### {{level|Метод окаймления}}<br /> ### Методы решения СЛАУ с блочно-треугольными матрицами<br /> #### {{level|Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка}}<br /> #### {{level|Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка}}<br /> #### Методы решения СЛАУ с блочно-двухдиагональными матрицами<br /> ##### {{level|Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей}}<br /> ##### {{level|Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ}}<br /> ##### {{level|Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ}}<br /> ### {{level|Методы решения СЛАУ с блочно-трёхдиагональными матрицами}}<br /> #### Методы, основанные на стандартном LU-разложении матрицы<br /> ##### {{level|Блочная прогонка}}<br /> ##### {{level|Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}}<br /> #### Другие методы<br /> ##### {{level|Встречная прогонка, блочный вариант}}<br /> ##### {{level|Блочный метод циклической редукции}}<br /> ##### {{level|Блочный метод окаймления}}<br /> ## {{level|Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы}}<br /> # Итерационные методы решения СЛАУ<br /> ## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}<br /> ## {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}}<br /> ## {{level|Алгоритм_Качмажа}}<br /> <br /> ==Решения спектральных задач==<br /> # {{level|Спектральное разложение (нахождение собственных значений и векторов)}}<br /> ## {{level|QR-алгоритм}}<br /> ### {{level|QR-алгоритм, используемый в SCALAPACK}}<br /> #### {{level|Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме}}<br /> #### {{level|QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK}}<br /> ### {{level|QR-алгоритм для симметричных матриц, используемый в SCALAPACK}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду}}<br /> #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}<br /> ### {{level|QR-алгоритм для комплексных эрмитовых матриц, используемый в SCALAPACK}}<br /> #### {{level|Метод Хаусхолдера (отражений) для приведения комплексных эрмитовых матриц к трёхдиагональному симметричному виду}}<br /> #### {{level|QR-алгоритм для симметричных трёхдиагональных матриц, используемый в SCALAPACK}}<br /> ## {{level|Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц}}<br /> ### {{level|Классический метод Якоби (вращений) для симметричных матриц с выбором по всей матрице}}<br /> ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением}}<br /> ### {{level|Метод Якоби (вращений) для симметричных матриц с циклическим исключением и барьерами}}<br /> ## {{level|Метод Ланцоша}}<br /> ### {{level|Алгоритм Ланцоша для точной арифметики (без переортогонализации)}}<br /> # {{level|Частичная спектральная задача}}<br /> ## {{level|Метод бисекций}}<br /> # {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}<br /> ## {{level|Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц}}<br /> ### {{level|Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором}}<br /> ### {{level|Метод Якоби для нахождения сингулярных значений со специальным подбором вращений}}<br /> ## {{level|QR-алгоритм в приложении к сингулярному разложению}}<br /> ==Алгебра многочленов==<br /> # {{level|Схема Горнера, вещественная версия, последовательный вариант}}<br /> <br /> = Алгоритмы на списках и массивах =<br /> ==Алгоритмы поиска==<br /> # {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, &lt;math&gt;O(n)&lt;/math&gt;<br /> # {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, &lt;math&gt;O(\log(n))&lt;/math&gt;<br /> ==Алгоритмы сортировки==<br /> # {{level|Сортировка с помощью двоичного дерева}}<br /> # {{level|Сортировка пузырьком}}<br /> # {{level|Сортировка слиянием (последовательный и параллельный варианты)}}<br /> ==Алгоритмы на графах==<br /> # Обход графа<br /> ## {{level|Поиск в ширину (BFS)}}<br /> ## {{level|Поиск в глубину (DFS)}}<br /> # {{level|Поиск кратчайшего пути от одной вершины (SSSP)}} <br /> ## {{level|Поиск в ширину (BFS)}} (для невзвешенных графов)<br /> ## {{level|Алгоритм Дейкстры}} <br /> ## {{level|Алгоритм Беллмана-Форда}} <br /> ## {{level|Алгоритм Δ-шагания}} <br /> # {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}} <br /> ## {{level|Алгоритм Джонсона}}<br /> ## {{level|Алгоритм Флойда-Уоршелла}}<br /> # {{level|Поиск транзитивного замыкания орграфа}}<br /> ## {{level|Алгоритм Пурдома}}<br /> # {{level|Определение диаметра графа}}<br /> # {{level|Построение минимального остовного дерева (MST)}}<br /> ## {{level|Алгоритм Борувки}}<br /> ## {{level|Алгоритм Крускала}}<br /> ## {{level|Алгоритм Прима}}<br /> ## {{level|Алгоритм GHS}}<br /> # {{level|Поиск изоморфных подграфов}}<br /> ## {{level|Алгоритм Ульмана}}<br /> ## {{level|Алгоритм VF2}}<br /> # {{level|Связность в графах}}<br /> ## {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}}<br /> ## {{level|Система непересекающихся множеств}}<br /> ## {{level|Алгоритм Тарьяна поиска компонент сильной связности}}<br /> ## {{level|Алгоритм DCSC поиска компонент сильной связности}}<br /> ## {{level|Алгоритм Тарьяна поиска компонент двусвязности}}<br /> ## {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}}<br /> ## {{level|Алгоритм Тарьяна поиска «мостов» в графе}}<br /> ## {{level|Определение вершинной связности графа}}<br /> ## {{level|Алгоритм Габова определения рёберной связности графа}}<br /> # {{level|Поиск максимального потока в транспортной сети}}<br /> ## {{level|Алгоритм Форда-Фалкерсона}}<br /> ## {{level|Алгоритм проталкивания предпотока}}<br /> # {{level|Поиск потока минимальной стоимости в транспортной сети}}<br /> # {{level|Задача о назначениях}}<br /> ## {{level|Венгерский алгоритм}}<br /> ## {{level|Алгоритм аукциона}}<br /> ## {{level|Алгоритм Гопкрофта-Карпа}}<br /> # {{level|Вычисление betweenness centrality|Вычисление центральности вершин}}<br /> =Вычислительная геометрия=<br /> # {{level|Поиск диаметра множества точек}}<br /> # {{level|Построение выпуклой оболочки набора точек}}<br /> # {{level|Триангуляция Делоне}}<br /> # {{level|Диаграмма Вороного}}<br /> # {{level|Принадлежность точки многоугольнику}}<br /> # {{level|Пересечения выпуклых многоугольников}} <br /> # {{level|Пересечение звёздных многоугольников}}<br /> ==Компьютерная графика==<br /> # {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}}<br /> # {{level|Алгоритм определения видимых частей трёхмерной сцены}}<br /> # {{level|Трассировка лучей - рендеринг реалистичных изображений}}<br /> # {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}}<br /> <br /> =Исследование и моделирование компьютеров=<br /> ==Тесты производительности компьютеров==<br /> # {{level|High Performance Conjugate Gradient (HPCG) benchmark}}<br /> # {{level|Linpack benchmark}}<br /> ==Алгоритмы моделирования квантовых систем==<br /> # {{level|Алгоритмы моделирования квантовых вычислений}}<br /> ## {{level|Однокубитное преобразование вектора-состояния}}<br /> ## {{level|Двухкубитное преобразование вектора-состояния}}<br /> ## {{level|Моделирование квантового преобразования Фурье}}<br /> ==Алгоритмы машинного обучения==<br /> # {{level|Алгоритм k средних (k-means)}}<br /> ===Нейронные сети===<br /> # {{level|Распознавание образов}}<br /> ## {{level|Распознавание текста}}<br /> ## {{level|Распознавание речи}}<br /> ## {{level|Распознавание лиц}}<br /> ===Алгоритмы теории игр===<br /> <br /> = Прикладные задачи из разных областей =<br /> ==Алгоритмы оптимизации==<br /> # {{level|Линейное программирование}}<br /> # {{level|Симплекс-метод}}<br /> # {{level|Метод ветвей и границ}}<br /> # {{level|Генетические алгоритмы}}<br /> # {{level|Муравьиные алгоритмы}}<br /> # {{level|Комбинированные алгоритмы}}<br /> # {{level|Стохастическое двойственное динамическое программирование (SDDP)}}<br /> ==Решение систем нелинейных уравнений==<br /> # {{level|Метод Ньютона для систем нелинейных уравнений}}<br /> ==Численные методы интегрирования==<br /> # {{level|Квадратурные формулы}}<br /> # {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}}<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод прямоугольников|Метод прямоугольников]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод трапеций|Метод трапеций]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод парабол (метод Симпсона)|Метод парабол (метод Симпсона)]]<br /> ## [[Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Метод Гаусса|Метод Гаусса]]<br /> ==Алгоритмы решения уравнений математической физики==<br /> # {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}}<br /> =Криптографические алгоритмы=<br /> # {{level|Метод встречи посередине}}<br /> =Другие алгоритмы=<br /> <br /> [[en:Algorithm classification]]<br /> <br /> [[Категория:Алгоритмы|*]]</div> Dolganov