Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
[досмотренная версия] | [досмотренная версия] |
Konshin (обсуждение | вклад) |
Konshin (обсуждение | вклад) |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 115: | Строка 115: | ||
## Итерационные методы решения СЛАУ | ## Итерационные методы решения СЛАУ | ||
### {{level|High Performance Conjugate Gradient (HPCG) benchmark}} | ### {{level|High Performance Conjugate Gradient (HPCG) benchmark}} | ||
+ | ### {{level|Стабилизированный метод бисопряженных градиентов (BiCGStab)}} | ||
### {{level|Алгоритм_Качмажа}} | ### {{level|Алгоритм_Качмажа}} | ||
+ | # {{level|Решение систем нелинейных уравнений}} | ||
+ | ## {{level|Метод Ньютона для систем нелинейных уравнений}} | ||
# <div id="Решения спектральных задач">'''Решения спектральных задач'''</div> | # <div id="Решения спектральных задач">'''Решения спектральных задач'''</div> | ||
## {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ## {{level|Спектральное разложение (нахождение собственных значений и векторов)}} | ||
Строка 200: | Строка 203: | ||
# <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div> | # <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div> | ||
## {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, <math>O(n)</math> | ## {{level|Линейный поиск - находит элемент в любом списке|Линейный поиск}}, <math>O(n)</math> | ||
− | ## {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, <math>O(log(n))</math> | + | ## {{level|Двоичный поиск - находит элемент в отсортированном списке|Двоичный поиск}}, <math>O(\log(n))</math> |
# <div id="Алгоритмы сортировки">'''Алгоритмы сортировки'''</div> | # <div id="Алгоритмы сортировки">'''Алгоритмы сортировки'''</div> | ||
## {{level|Сортировка с помощью двоичного дерева}} | ## {{level|Сортировка с помощью двоичного дерева}} | ||
Строка 212: | Строка 215: | ||
## {{level|Принадлежность точки многоугольнику}} | ## {{level|Принадлежность точки многоугольнику}} | ||
## {{level|Пересечения выпуклых многоугольников}} - трудоёмкость <math>O(n_1 + n_2)</math> | ## {{level|Пересечения выпуклых многоугольников}} - трудоёмкость <math>O(n_1 + n_2)</math> | ||
− | ## {{level|Пересечение звёздных многоугольников}} - трудоёмкость <math>O(n_1 | + | ## {{level|Пересечение звёздных многоугольников}} - трудоёмкость <math>O(n_1 \cdot n_2)</math> |
# <div id="Компьютерная графика">'''Компьютерная графика'''</div> | # <div id="Компьютерная графика">'''Компьютерная графика'''</div> | ||
## {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}} | ## {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}} | ||
Строка 221: | Строка 224: | ||
## {{level|Метод встречи посередине}} | ## {{level|Метод встречи посередине}} | ||
# <div id="Нейронные сети">'''Нейронные сети'''</div> | # <div id="Нейронные сети">'''Нейронные сети'''</div> | ||
+ | ## {{level|Распознование образов}} | ||
+ | ### {{level|Распознование текста}} | ||
+ | ### {{level|Распознование речи}} | ||
+ | ### {{level|Распознование лиц}} | ||
# <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div> | # <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div> | ||
## {{level|Линейное программирование}} | ## {{level|Линейное программирование}} | ||
## {{level|Симплекс-метод}} | ## {{level|Симплекс-метод}} | ||
− | ## {{level|Метод ветвей и границ | + | ## {{level|Метод ветвей и границ}} |
## {{level|Генетические алгоритмы}} | ## {{level|Генетические алгоритмы}} | ||
## {{level|Муравьиные алгоритмы}} | ## {{level|Муравьиные алгоритмы}} | ||
## {{level|Комбинированные алгоритмы}} | ## {{level|Комбинированные алгоритмы}} | ||
− | ## {{level| | + | ## {{level|Стохастическое двойственное динамическое программирование (SDDP)}} |
+ | # <div id="Алгоритмы машинного обучения">'''Алгоритмы машинного обучения'''</div> | ||
+ | ## {{level|Алгоритм k средних (k-means)}} | ||
# <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div> | # <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div> | ||
# <div id="Алгоритмы моделирования квантовых систем">'''Алгоритмы моделирования квантовых систем'''</div> | # <div id="Алгоритмы моделирования квантовых систем">'''Алгоритмы моделирования квантовых систем'''</div> |
Версия 21:10, 16 января 2018
- Векторные операции
- Матрично-векторные операции
- Матричные операции
- Разложения матриц
- Треугольные разложения
- Метод Гаусса (нахождение 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 \cdot n_2)[/math]
- Компьютерная графика
- Криптографические алгоритмы
- Нейронные сети
- Алгоритмы оптимизации
- Алгоритмы машинного обучения
- Алгоритмы теории игр
- Алгоритмы моделирования квантовых систем
- Алгоритмы моделирования квантовых вычислений
- Алгоритмы решения уравнений математической физики
- Другие алгоритмы