Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
[досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) м |
Frolov (обсуждение | вклад) м |
||
Строка 57: | Строка 57: | ||
#### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}} | #### {{level|Метод Гивенса (вращений) приведения матрицы к трёхдиагональной форме}} | ||
### {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ### {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ||
− | ## {{level|Неподобные разложения на унитарные и двухдиагональные матрицы}} | + | ## {{level|Неподобные унитарные разложения}} |
− | ### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}} | + | ### {{level|Неподобные разложения на унитарные и двухдиагональные матрицы}} |
− | ### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}} | + | #### {{level|Метод Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме}} |
− | ## {{level|Разложения на унитарные и диагональные матрицы}} | + | #### {{level|Метод Гивенса (вращений) приведения матрицы к двухдиагональной форме}} |
− | ### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}} | + | ### {{level|Разложения на унитарные и диагональные матрицы}} |
− | #### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}} | + | #### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}} |
− | ##### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}} | + | ##### {{level|Методы нахождения сингулярных чисел двухдиагональных матриц}} |
− | ###### {{level|Итерация алгоритма dqds}} | + | ###### {{level|Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы}} |
+ | ####### {{level|Итерация алгоритма dqds}} | ||
# {{level|Решение систем линейных уравнений}} | # {{level|Решение систем линейных уравнений}} | ||
## {{level|Прямые методы решения СЛАУ}} | ## {{level|Прямые методы решения СЛАУ}} |
Версия 18:10, 20 ноября 2017
- Векторные операции
- Матрично-векторные операции
- Матричные операции
Разложения матриц
Треугольные разложения
Метод Гаусса (нахождение LU-разложения)
Метод Холецкого (нахождение симметричного треугольного разложения)
Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- Известные треугольные разложения для матриц специального вида
Унитарно-треугольные разложения
- Подобные разложения
- Подобные разложения на унитарные и хессенберговы матрицы
- Симметричные разложения на унитарные и трёхдиагональные матрицы
Спектральное разложение (нахождение собственных значений и векторов)
- Неподобные унитарные разложения
- Решение систем линейных уравнений
- Прямые методы решения СЛАУ
Linpack benchmark
- Методы решения СЛАУ с матрицами специального вида
- Методы решения СЛАУ с треугольными матрицами
Методы решения СЛАУ с трёхдиагональными матрицами
- Методы решения СЛАУ с блочно-треугольными матрицами
- Блочная прямая подстановка (вещественный вариант)
- Блочная обратная подстановка (вещественный вариант)
- Методы решения СЛАУ с блочно-двухдиагональными матрицами
- Методы решения СЛАУ с блочно-трёхдиагональными матрицами
- Методы, основанные на стандартном LU-разложении матрицы
- Другие методы
- Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
- Итерационные методы решения СЛАУ
- Прямые методы решения СЛАУ
- Решения спектральных задач
Спектральное разложение (нахождение собственных значений и векторов)
- Частичная спектральная задача
Сингулярное разложение (нахождение сингулярных значений и векторов)
- Тесты производительности компьютеров
- Преобразование Фурье
- Алгебра многочленов
- Численные методы интегрирования
- Алгоритмы на графах
- Обход графа
Поиск кратчайшего пути от одной вершины (SSSP)
Поиск в ширину (BFS) (для невзвешенных графов)
Алгоритм Дейкстры
Алгоритм Беллмана-Форда
Алгоритм Δ-шагания
Поиск кратчайшего пути для всех пар вершин (APSP)
Поиск транзитивного замыкания орграфа
Определение диаметра графа
Построение минимального остовного дерева (MST)
Поиск изоморфных подграфов
Связность в графах
Алгоритм Шилоаха-Вишкина поиска компонент связности
Система непересекающихся множеств
Алгоритм Тарьяна поиска компонент сильной связности
Алгоритм DCSC поиска компонент сильной связности
Алгоритм Тарьяна поиска компонент двусвязности
Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
Алгоритм Тарьяна поиска «мостов» в графе
Определение вершинной связности графа
Алгоритм Габова определения рёберной связности графа
Поиск максимального потока в транспортной сети
Поиск потока минимальной стоимости в транспортной сети
Задача о назначениях
- Вычисление betweenness centrality
- Алгоритмы поиска
- Линейный поиск - находит элемент в любом списке, [math]O(n)[/math]
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
- Алгоритмы сортировки
- Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
- Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]
- Компьютерная графика
- Криптографические алгоритмы
- Нейронные сети
- Алгоритмы оптимизации
- Алгоритмы теории игр
- Алгоритмы моделирования квантовых систем
- Алгоритмы моделирования квантовых вычислений
- Алгоритмы решения уравнений математической физики
- Другие алгоритмы