Классификация алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
[непроверенная версия] | [непроверенная версия] |
Dolganov (обсуждение | вклад) (Перенаправление на Служебная:Pma tree) |
Dolganov (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | |||
__TOC__ | __TOC__ | ||
= Задачи алгебры = | = Задачи алгебры = |
Версия 21:22, 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 Численные методы интегрирования
- Квадратурные формулы
- Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)