Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
[выверенная версия] | [выверенная версия] |
Daryin (обсуждение | вклад) (-> список алгоритмов на графах) |
Frolov (обсуждение | вклад) |
||
(не показано 14 промежуточных версий 2 участников) | |||
Строка 15: | Строка 15: | ||
#### Метод Гаусса без перестановок | #### Метод Гаусса без перестановок | ||
##### LU-разложение методом Гаусса | ##### LU-разложение методом Гаусса | ||
− | ##### Компактная схема метода Гаусса | + | ##### Компактная схема метода Гаусса и её модификации |
###### Компактная схема метода Гаусса для плотной матрицы | ###### Компактная схема метода Гаусса для плотной матрицы | ||
− | ###### Компактная схема метода Гаусса для трёхдиагональной матрицы | + | ###### [[Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации]] |
+ | ####### [[Компактная схема метода Гаусса для трёхдиагональной матрицы]] | ||
+ | ####### [[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы]] | ||
+ | ####### [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы]] | ||
#### Метод Гаусса с перестановками | #### Метод Гаусса с перестановками | ||
##### Метод Гаусса с выбором ведущего элемента по столбцу | ##### Метод Гаусса с выбором ведущего элемента по столбцу | ||
Строка 59: | Строка 62: | ||
### [[Алгоритм Беллмана-Форда]] | ### [[Алгоритм Беллмана-Форда]] | ||
### [[Алгоритм Δ-шагания]] | ### [[Алгоритм Δ-шагания]] | ||
− | |||
## [[Поиск кратчайшего пути для всех пар вершин (APSP)]] | ## [[Поиск кратчайшего пути для всех пар вершин (APSP)]] | ||
+ | ### [[Алгоритм Джонсона]] | ||
### [[Алгоритм Флойда-Уоршелла]] | ### [[Алгоритм Флойда-Уоршелла]] | ||
+ | ## [[Поиск транзитивного замыкания орграфа]] | ||
+ | ### [[Алгоритм Пурдома]] | ||
## [[Определение диаметра графа]] | ## [[Определение диаметра графа]] | ||
## [[Построение минимального остовного дерева (MST)]] | ## [[Построение минимального остовного дерева (MST)]] | ||
Строка 68: | Строка 73: | ||
### [[Алгоритм Прима]] | ### [[Алгоритм Прима]] | ||
### [[Алгоритм GHS]] | ### [[Алгоритм GHS]] | ||
− | ## [[Поиск изоморфных подграфов | + | ## [[Поиск изоморфных подграфов]] |
− | ## [[ | + | ### [[Алгоритм Ульмана]] |
+ | ### [[Алгоритм VF2]] | ||
## [[Связность в графах]] | ## [[Связность в графах]] | ||
− | ### [[ | + | ### [[Алгоритм Шилоаха-Вишкина поиска компонент связности]] |
− | ### [[Алгоритм Тарьяна поиска | + | ### [[Система непересекающихся множеств]] |
+ | ### [[Алгоритм Тарьяна поиска компонент сильной связности]] | ||
+ | ### [[Алгоритм DCSC поиска компонент сильной связности]] | ||
+ | ### [[Алгоритм Тарьяна поиска компонент двусвязности]] | ||
+ | ### [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности]] | ||
### [[Алгоритм Тарьяна поиска «мостов» в графе]] | ### [[Алгоритм Тарьяна поиска «мостов» в графе]] | ||
− | ### [[Определение | + | ### [[Определение вершинной связности графа]] |
− | ### [[ | + | ### [[Алгоритм Габова определения рёберной связности графа]] |
− | ## [[Поиск максимального потока в | + | ## [[Поиск максимального потока в транспортной сети]] |
### [[Алгоритм Форда-Фалкерсона]] | ### [[Алгоритм Форда-Фалкерсона]] | ||
### [[Алгоритм проталкивания предпотока]] | ### [[Алгоритм проталкивания предпотока]] | ||
− | ## [[Поиск потока минимальной стоимости в | + | ## [[Поиск потока минимальной стоимости в транспортной сети]] |
## [[Задача о назначениях]] | ## [[Задача о назначениях]] | ||
+ | ### [[Венгерский алгоритм]] | ||
### [[Алгоритм аукциона]] | ### [[Алгоритм аукциона]] | ||
### [[Алгоритм Гопкрофта-Карпа]] | ### [[Алгоритм Гопкрофта-Карпа]] | ||
− | + | ## [[Вычисление betweenness centrality|Вычисление центральности вершин]] | |
− | |||
− | |||
# <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div> | # <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div> | ||
## [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math> | ## [[Двоичный поиск - находит элемент в отсортированном списке]], <math>O(log(n))</math> |
Версия 19:58, 1 июля 2015
- Векторные операции
- Умножение матрицы на вектор
- Матричные операции
- Разложения матриц
- Треугольные разложения
- Метод Гаусса (накождение LU-разложения)
- Метод Гаусса без перестановок
- LU-разложение методом Гаусса
- Компактная схема метода Гаусса и её модификации
- Компактная схема метода Гаусса для плотной матрицы
- Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации
- Метод Гаусса с перестановками
- Метод Гаусса с выбором ведущего элемента по столбцу
- Метод Гаусса с выбором ведущего элемента по строке
- Метод Гаусса с выбором ведущего элемента по всей матрице
- Метод Гаусса без перестановок
- Метод Холецкого (нахождение симметричного треугольного разложения)
- Разложение Холецкого (метод квадратного корня) базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- Метод Гаусса (накождение LU-разложения)
- Унитарно-треугольные разложения
- Разложения на унитарные и хессенберговы матрицы
- Разложения на унитарные и диагональные матрицы
- Треугольные разложения
- Решение систем линейных уравнений
- Тесты производительности компьютеров
- Преобразование Фурье
- Алгебра многочленов
- Численные методы интегрирования
- Алгоритмы на графах
- Обход графа
- Поиск кратчайшего пути от одной вершины (SSSP)
- Поиск в ширину (BFS) (для невзвешенных графов)
- Алгоритм Дейкстры
- Алгоритм Беллмана-Форда
- Алгоритм Δ-шагания
- Поиск кратчайшего пути для всех пар вершин (APSP)
- Поиск транзитивного замыкания орграфа
- Определение диаметра графа
- Построение минимального остовного дерева (MST)
- Поиск изоморфных подграфов
- Связность в графах
- Алгоритм Шилоаха-Вишкина поиска компонент связности
- Система непересекающихся множеств
- Алгоритм Тарьяна поиска компонент сильной связности
- Алгоритм DCSC поиска компонент сильной связности
- Алгоритм Тарьяна поиска компонент двусвязности
- Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
- Алгоритм Тарьяна поиска «мостов» в графе
- Определение вершинной связности графа
- Алгоритм Габова определения рёберной связности графа
- Поиск максимального потока в транспортной сети
- Поиск потока минимальной стоимости в транспортной сети
- Задача о назначениях
- Вычисление центральности вершин
- Алгоритмы поиска
- Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
- Алгоритмы сортировки
- Вычислительная геометрия
- Поиск диаметра множества точек
- Построение выпуклой оболочки набора точек
- Триангуляция Делоне
- Диаграмма Вороного
- Принадлежность точки многоугольнику
- Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
- Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]
- Компьютерная графика
- Криптографические алгоритмы
- Нейронные сети
- Алгоритмы оптимизации
- Алгоритмы теории игр
- Алгоритмы моделирования квантовых систем
- Алгоритмы моделирования квантовых вычислений
- Алгоритмы решения уравнений математической физики
- Другие алгоритмы