Список алгоритмов

По сути, алгоритм — это набор правил или определенных процедур, которые обычно разрабатываются и используются для решения конкретной проблемы или широкого круга проблем.

В широком смысле алгоритмы определяют процесс(ы), наборы правил или методологии, которые должны соблюдаться при вычислениях, обработке данных, добыче данных, распознавании образов, автоматизированном рассуждении или других операциях по решению проблем. С ростом автоматизации услуг все больше решений принимаются алгоритмами. Вот некоторые общие примеры: оценка рисков, упреждающий контроль и технология распознавания образов. ^[1]

Ниже приведен список известных алгоритмов с краткими описаниями каждого из них.

Автоматизированное планирование

Комбинаторные алгоритмы

Общие комбинаторные алгоритмы

Алгоритм Брента : находит цикл в итерациях значения функции, используя только два итератора ^[2]
Алгоритм поиска цикла Флойда : находит цикл в итерациях значения функции ^[3]
Алгоритм Гейла-Шепли : решает проблему стабильного брака ^{[ необходима ссылка ]}
Генераторы псевдослучайных чисел (равномерно распределенные — см. также Список генераторов псевдослучайных чисел для других ГПСЧ с различной степенью сходимости и различным статистическим качеством): ^{[ необходима ссылка ]}

Графические алгоритмы

Алгоритм раскраски : Алгоритм раскраски графа.
Алгоритм Хопкрофта–Карпа : преобразование двудольного графа в паросочетание максимальной мощности
Венгерский алгоритм : алгоритм поиска идеального паросочетания
Кодирование Прюфера : преобразование между помеченным деревом и его последовательностью Прюфера
Оффлайновый алгоритм наименьших общих предков Тарьяна : вычисляет наименьших общих предков для пар узлов в дереве
Топологическая сортировка : находит линейный порядок узлов (например, заданий) на основе их зависимостей.

Графическое изображение

Алгоритмы, основанные на силе (также известные как алгоритмы, направленные силой, или пружинные алгоритмы)
Спектральная раскладка

Теория сетей

Сетевой анализ
- Анализ ссылок
  - Алгоритм Гирвана–Ньюмана : обнаружение сообществ в сложных системах
  - Анализ веб-ссылок
    - Поиск по темам, вызванный гиперссылками (HITS) (также известный как концентраторы и авторитетные источники )
    - PageRank
    - TrustRank
Сети потоков
- Алгоритм Динича : это сильно полиномиальный алгоритм для вычисления максимального потока в потоковой сети .
- Алгоритм Эдмондса–Карпа : реализация Форда–Фалкерсона
- Алгоритм Форда-Фалкерсона : вычисляет максимальный поток в графе
- Алгоритм Каргера : метод Монте-Карло для вычисления минимального разреза связного графа
- Алгоритм Push–Relabel : вычисляет максимальный поток в графе

Маршрутизация для графиков

Алгоритм Эдмондса (также известный как алгоритм Чу–Лю/Эдмондса): поиск максимального или минимального количества ветвлений
Евклидово минимальное остовное дерево : алгоритмы вычисления минимального остовного дерева набора точек на плоскости
Задача о самом длинном пути : найти простой путь максимальной длины в заданном графе.
Минимальное остовное дерево
Неблокируемый коммутатор с минимальным охватом , например, для телефонной станции
Задача о кратчайшем пути
- Алгоритм Беллмана–Форда : вычисляет кратчайшие пути во взвешенном графе (где некоторые веса ребер могут быть отрицательными)
- Алгоритм Дейкстры : вычисляет кратчайшие пути в графе с неотрицательными весами ребер.
- Алгоритм Флойда–Уоршелла : решает задачу поиска кратчайшего пути для всех пар вершин во взвешенном ориентированном графе.
- Алгоритм Джонсона : алгоритм кратчайшего пути для всех пар в разреженном взвешенном ориентированном графе
Задача транзитивного замыкания : найти транзитивное замыкание заданного бинарного отношения
Задача коммивояжера
- Алгоритм Кристофидеса
- Алгоритм ближайшего соседа
Правило Варнсдорфа : эвристический метод решения задачи о ходе коня

Поиск по графику

A* : особый случай поиска по первому наилучшему совпадению, использующий эвристику для повышения скорости
B* : алгоритм поиска по графу «лучший первый», который находит путь с наименьшей стоимостью от заданного начального узла до любого целевого узла (из одной или нескольких возможных целей)
Возврат : отказ от частичных решений, если они не удовлетворяют полному решению.
Поиск по лучу : это эвристический алгоритм поиска, который оптимизирует поиск по первому наилучшему совпадению, что снижает его требования к памяти.
Поиск стека лучей : объединяет возврат с поиском лучей
Поиск по принципу «лучшее-первое» : просматривает граф в порядке вероятной важности, используя приоритетную очередь.
Двунаправленный поиск : поиск кратчайшего пути от начальной вершины до целевой вершины в ориентированном графе.
Поиск в ширину : обходит граф уровень за уровнем.
Поиск методом перебора : исчерпывающий и надежный метод поиска, но вычислительно неэффективный во многих приложениях.
D* : алгоритм инкрементального эвристического поиска
Поиск в глубину : обходит граф ветвь за ветвью.
Алгоритм Дейкстры : особый случай A*, для которого не используется эвристическая функция.
Универсальный решатель проблем : основополагающий алгоритм доказательства теорем, предназначенный для работы в качестве универсальной машины для решения проблем.
Итеративное углубление поиска в глубину (IDDFS): стратегия поиска в пространстве состояний
Поиск точки перехода : оптимизация для A*, которая может сократить время вычислений на порядок с использованием дополнительных эвристик.
Лексикографический поиск в ширину (также известный как Lex-BFS): линейный по времени алгоритм для упорядочивания вершин графа.
Поиск с равномерной стоимостью : поиск по дереву , который находит маршрут с наименьшей стоимостью, где стоимость варьируется.
SSS* : поиск в пространстве состояний, проходящий по дереву игры в режиме «лучший-первый», аналогично алгоритму поиска A*

Подграфы

Клики
- Алгоритм Брона–Кербоша : метод поиска максимальных клик в неориентированном графе
- Алгоритм максимальной клики MaxCliqueDyn : поиск максимальной клики в неориентированном графе
Сильно связанные компоненты
Проблема изоморфизма подграфов

Последовательные алгоритмы

Приблизительное соответствие последовательностей

Алгоритм Bitap : нечеткий алгоритм, который определяет, являются ли строки приблизительно равными.
Фонетические алгоритмы
- Daitch–Mokotoff Soundex : уточнение Soundex , позволяющее сопоставлять славянские и германские фамилии
- Двойной Метафон : усовершенствованный Метафон
- Подход к оценке соответствия : фонетический алгоритм, разработанный Western Airlines
- Метафон : алгоритм индексации слов по их звучанию при произношении на английском языке.
- NYSIIS : фонетический алгоритм , улучшает Soundex
- Soundex : фонетический алгоритм для индексации имен по звучанию, как они произносятся на английском языке.
Метрики строк : вычисляют показатель сходства или различия (расстояние) между двумя парами текстовых строк.
- Расстояние Дамерау–Левенштейна : вычисляет меру расстояния между двумя строками, улучшает расстояние Левенштейна
- Коэффициент Дайса (также известный как коэффициент Дайса): мера сходства, связанная с индексом Жаккара.
- Расстояние Хэмминга : суммарное количество позиций, которые отличаются
- Расстояние Джаро–Винклера : мера сходства между двумя строками.
- Расстояние редактирования Левенштейна : вычисляет метрику для величины разницы между двумя последовательностями
Поиск триграмм : поиск текста, когда точный синтаксис или написание целевого объекта не известны.

Алгоритмы отбора

Поиск последовательности

Линейный поиск : находит элемент в несортированной последовательности.
Алгоритм выбора : находит k -й наибольший элемент в последовательности
Тернарный поиск : метод нахождения минимума или максимума функции, которая либо строго возрастает, а затем строго убывает или наоборот.
Сортированные списки
- Алгоритм двоичного поиска : находит элемент в отсортированной последовательности.
- Метод поиска Фибоначчи : поиск в отсортированной последовательности с использованием алгоритма «разделяй и властвуй», который сужает возможные местоположения с помощью чисел Фибоначчи.
- Поиск переходов (или блочный поиск): линейный поиск на меньшем подмножестве последовательности
- Предиктивный поиск : поиск типа бинарного, который учитывает величину поискового термина по сравнению с высокими и низкими значениями в поиске. Иногда называется поиском по словарю или интерполированным поиском.
- Равномерный бинарный поиск : оптимизация классического алгоритма бинарного поиска
- Двоичный поиск Эйтцингера : алгоритм бинарного поиска, удобный для кэширования ^[4]

Слияние последовательностей

Простой алгоритм слияния
алгоритм слияния k-way
Объединение (слияние, при этом элементы на выходе не повторяются)

Перестановки последовательностей

Перемешивание Фишера-Йетса (также известное как перетасовка Кнута): случайным образом перемешивает конечный набор
Алгоритм Шенстеда : создает пару таблиц Юнга из перестановки
Алгоритм Штейнхауза–Джонсона–Троттера (также известный как алгоритм Джонсона–Троттера): генерирует перестановки путем транспонирования элементов.
Алгоритм генерации перестановок Heap : перестановка элементов для генерации следующей перестановки

Последовательность комбинаций

Выравнивание последовательности

Динамическая временная деформация : измерение сходства между двумя последовательностями, которые могут различаться по времени или скорости.
Алгоритм Хиршберга : находит выравнивание последовательностей с наименьшей стоимостью между двумя последовательностями, измеряемое их расстоянием Левенштейна.
Алгоритм Нидлмана – Вунша : найти глобальное выравнивание между двумя последовательностями.
Алгоритм Смита-Уотермана : поиск локального выравнивания последовательностей

Сортировка последовательности

Сорта обмена
- Пузырьковая сортировка : для каждой пары индексов поменять местами элементы, если они не упорядочены
- Сортировка методом шейкера или двунаправленная пузырьковая сортировка, пузырьковая сортировка, проходящая список попеременно от начала к концу и от конца к началу.
- Сортировка гребнем
- сортировка гнома
- Сортировка по четным и нечетным
- Быстрая сортировка : разделите список на два, причем все элементы первого списка идут перед всеми элементами второго списка.; затем отсортируйте два списка. Часто метод выбора
Юмористический или неэффективный
Гибридный
- Флэшсорт
- Вводная сортировка : начните с быстрой сортировки и переключитесь на пирамидальную сортировку, когда глубина рекурсии превысит определенный уровень.
- Timsort : адаптивный алгоритм, полученный из сортировки слиянием и сортировки вставкой. Используется в Python 2.3 и выше, а также Java SE 7.
Сортировка вставкой
- Сортировка вставкой : определяет, где в списке отсортированных находится текущий элемент, и вставляет его туда.
- Библиотечная сортировка
- Терпение сортировка
- Сортировка Шелла : попытка улучшить сортировку вставкой
- Сортировка дерева (сортировка двоичного дерева): построение двоичного дерева, затем его обход для создания отсортированного списка.
- Циклическая сортировка : на месте с теоретически оптимальным количеством записей
Сортировка слиянием
- Сортировка слиянием : сортировка первой и второй половины списка по отдельности, затем объединение отсортированных списков.
- Медленная сортировка
- сортировка по прядям
Сортировки без сравнения
- сортировка бисера
- Сортировка по ведру
- Burstsort : создание компактного, эффективного по кэшированию пакетного дерева, а затем его обход для создания отсортированного вывода.
- Сортировка подсчетом
- сортировка по ячейкам
- Сортировка Почтальона : вариант сортировки Bucket, использующий преимущества иерархической структуры.
- Radix sort : сортирует строки по буквам
Сортировка по выбору
- Пирамидальная сортировка : преобразует список в кучу, удаляет из кучи наибольший элемент и добавляет его в конец списка.
- Сортировка выбором : выбрать наименьший из оставшихся элементов, добавить его в конец отсортированного списка.
- Smoothgamersort
Другой
Неизвестный класс
- ВыборкаСортировка

Подпоследовательности

Задача на самую длинную общую подпоследовательность : найти самую длинную подпоследовательность, общую для всех последовательностей в наборе последовательностей.
Задача на самую длинную возрастающую подпоследовательность : найти самую длинную возрастающую подпоследовательность заданной последовательности.
Алгоритм Руццо–Томпы : найти все неперекрывающиеся, смежные, максимально оцениваемые подпоследовательности в последовательности действительных чисел.
Задача на кратчайшую общую суперпоследовательность : найти кратчайшую суперпоследовательность, содержащую две или более последовательностей в качестве подпоследовательностей.

Подстроки

Алгоритм Кадане : находит непрерывный подмассив с наибольшей суммой в массиве чисел
Задача на самую длинную общую подстроку : найти самую длинную строку (или строки), которая является подстрокой (или являются подстроками) двух или более строк.
Поиск подстроки
- Алгоритм сопоставления строк Ахо–Корасика : алгоритм на основе префиксного дерева для поиска всех подстрок, соответствующих любому конечному набору строк
- Алгоритм поиска подстроки Бойера–Мура : амортизированный линейный ( в большинстве случаев сублинейный ) алгоритм поиска подстроки
- Алгоритм Бойера–Мура–Хорспула : упрощение алгоритма Бойера–Мура
- Алгоритм Кнута–Морриса–Пратта : поиск подстроки, который обходит повторную проверку совпавших символов
- Алгоритм поиска строк Рабина–Карпа : эффективно ищет несколько шаблонов
- Алгоритм сопоставления строк Чжу-Такаока : вариант алгоритма Бойера-Мура
Алгоритм Укконена : линейный по времени онлайн - алгоритм для построения суффиксных деревьев
Соответствие подстановочных знаков
- Wildmat Рича Сальца : широко используемый рекурсивный алгоритм с открытым исходным кодом
- Алгоритм Краусса с подстановочными знаками : нерекурсивный алгоритм с открытым исходным кодом

Вычислительная математика

Абстрактная алгебра

Поиск Чиена : рекурсивный алгоритм для определения корней многочленов, определенных над конечным полем
Алгоритм Шрайера–Симса : вычисление базового и сильного генераторного набора (BSGS) группы перестановок
Алгоритм Тодда–Коксетера : процедура генерации смежных классов .

Компьютерная алгебра

Алгоритм Бухбергера : находит базис Грёбнера
Алгоритм Кантора–Цассенхауза : факторизация многочленов над конечными полями
Алгоритм Фожера F4 : находит базис Грёбнера (также упоминается алгоритм F5)
Алгоритм Госпера : найти суммы гипергеометрических членов, которые сами являются гипергеометрическими членами
Алгоритм завершения Кнута-Бендикса : для переписывания систем правил
Алгоритм многомерного деления : для полиномов с несколькими неизвестными
Алгоритм кенгуру Полларда (также известный как лямбда-алгоритм Полларда): алгоритм решения задачи дискретного логарифмирования.
Полиномиальное деление в столбик : алгоритм деления полинома на другой полином той же или более низкой степени.
Алгоритм Риша : алгоритм для исчисления операции неопределенного интегрирования (т.е. нахождения первообразных )

Геометрия

Задача о самой близкой паре : найти пару точек (из набора точек) с наименьшим расстоянием между ними.
Алгоритмы обнаружения столкновений : проверка столкновения или пересечения двух заданных твердых тел
Алгоритм конуса : определение точек поверхности
Алгоритмы выпуклой оболочки : определение выпуклой оболочки набора точек
- сканирование Грэма
- Квикхалл
- Алгоритм упаковки подарков или марш Джарвиса
- Алгоритм Чана
- Алгоритм Киркпатрика–Зейделя
Преобразование евклидова расстояния : вычисляет расстояние между каждой точкой сетки и дискретным набором точек.
Геометрическое хеширование : метод эффективного нахождения двумерных объектов, представленных дискретными точками, которые подверглись аффинному преобразованию.
Алгоритм расстояния Гилберта–Джонсона–Кирти : определение наименьшего расстояния между двумя выпуклыми фигурами.
Алгоритм «Прыгай и ходи» : алгоритм определения местоположения точек в триангуляциях
Сглаживание Лапласа : алгоритм сглаживания полигональной сетки
Пересечение отрезков линий : определение того, пересекаются ли линии, обычно с помощью алгоритма скользящей линии
- Алгоритм Бентли–Оттмана
- Алгоритм Шамоса–Хоя
Алгоритмы минимального ограничивающего прямоугольника : поиск ориентированного минимального ограничивающего прямоугольника, охватывающего набор точек.
Поиск ближайшего соседа : поиск ближайшей точки или точек к точке запроса
Алгоритм вложения : максимально эффективное использование материала или пространства
Алгоритмы «точка в многоугольнике» : проверяют, лежит ли заданная точка внутри заданного многоугольника.
Алгоритмы регистрации наборов точек : находят преобразование между двумя наборами точек для их оптимального выравнивания.
Вращающиеся штангенциркули : определяют все антиподальные пары точек и вершин на выпуклом многоугольнике или выпуклой оболочке .
Алгоритм шнурка : определение площади многоугольника, вершины которого описываются упорядоченными парами на плоскости.
Триангуляция
- триангуляция Делоне
  - Алгоритм Рупперта (также известный как уточнение Делоне): создание качественных триангуляций Делоне
  - Второй алгоритм Чу : создание триангуляции Делоне с ограничениями по качеству
- Марширующие треугольники : реконструкция двумерной геометрии поверхности из неструктурированного облака точек
- Алгоритмы триангуляции полигонов : разложение полигона на набор треугольников
- Диаграммы Вороного , геометрически двойственные триангуляции Делоне
  - Алгоритм Бойера–Ватсона : создание диаграммы Вороного в любом количестве измерений
  - Алгоритм Форчуна : создание диаграммы Вороного
- Квазитриангуляция

Теоретико-числовые алгоритмы

Двоичный алгоритм НОД : эффективный способ вычисления НОД.
Алгоритм умножения Бута
Метод Чакравала : циклический алгоритм решения неопределенных квадратных уравнений, включая уравнение Пелля.
Дискретный логарифм :
Алгоритм Евклида : вычисляет наибольший общий делитель
Расширенный алгоритм Евклида : также решает уравнение ax + by = c
Факторизация целых чисел : разложение целого числа на простые множители
Алгоритмы умножения : быстрое умножение двух чисел
Модульный квадратный корень : вычисление квадратных корней по модулю простого числа
Алгоритм Одлыжко–Шёнхаге : вычисляет нетривиальные нули дзета -функции Римана
Алгоритм Ленстры–Ленстры–Ловаса (также известный как алгоритм LLL): нахождение короткого, почти ортогонального базиса решетки за полиномиальное время
Тесты на простоту : определение, является ли заданное число простым

Числовые алгоритмы

Решение дифференциальных уравнений

метод Эйлера
Обратный метод Эйлера
Правило трапеции (дифференциальные уравнения)
Линейные многошаговые методы
Методы Рунге–Кутты
- Интеграция Эйлера
Многосеточные методы (МГ-методы), группа алгоритмов решения дифференциальных уравнений с использованием иерархии дискретизаций
Уравнение с частными производными :
- Метод конечных разностей
- Метод Кранка–Николсона для уравнений диффузии
- Лакса–Вендроффа для волновых уравнений
Интеграция Верле ( французское произношение: [vɛʁˈlɛ] ): интегрировать уравнения движения Ньютона

Элементарные и специальные функции

Вычисление числа π :
- Алгоритм Борвейна : алгоритм для вычисления значения 1/π
- Алгоритм Гаусса–Лежандра : вычисляет цифры числа Пи
- Алгоритм Чудновского : быстрый метод вычисления цифр числа π
- Формула Бейли–Борвейна–Плуффа : (формула BBP) алгоритм Spigot для вычисления n-й двоичной цифры числа π
Алгоритмы деления : для вычисления частного и/или остатка двух чисел
- Деление в столбик
- Восстановление разделения
- Невосстанавливающее деление
- Подразделение SRT
- Деление Ньютона–Рафсона : использует метод Ньютона для нахождения обратной величины D и умножает эту обратную величину на N, чтобы найти окончательное частное Q.
- Подразделение Гольдшмидта
Гиперболические и тригонометрические функции:
- Алгоритм BKM : вычисляет элементарные функции с использованием таблицы логарифмов.
- CORDIC : вычисляет гиперболические и тригонометрические функции с использованием таблицы арктангенсов
Возведение в степень:
- Возведение в степень с помощью цепочки сложений : возведение в степень с использованием положительных целых степеней, требующее минимального количества умножений.
- Возведение в степень путем возведения в квадрат : алгоритм, используемый для быстрого вычисления больших целых степеней числа.
Редукция Монтгомери : алгоритм, позволяющий эффективно выполнять модульную арифметику , когда модуль большой.
Алгоритмы умножения : быстрое умножение двух чисел
- Алгоритм умножения Бута : алгоритм умножения, который умножает два двоичных числа со знаком в дополнительном коде.
- Алгоритм Фюрера : алгоритм целочисленного умножения очень больших чисел, обладающий очень низкой асимптотической сложностью.
- Алгоритм Карацубы : эффективная процедура умножения больших чисел
- Алгоритм Шёнхаге – Штрассена : асимптотически быстрый алгоритм умножения больших целых чисел.
- Умножение Тоома–Кука : (Toom3) алгоритм умножения больших целых чисел
Алгоритмы мультипликативной обратной величины : для вычисления мультипликативной обратной величины (обратного числа).
- Метод Ньютона
Функции округления : классические способы округления чисел
Алгоритм Spigot : способ вычисления значения математической константы без знания предыдущих цифр
Квадратный и N-й корень числа:
- Алгоритм альфа макс плюс бета мин : приближение квадратного корня из суммы двух квадратов
- Методы вычисления квадратных корней
- алгоритм n- го корня
Подведение итогов:
- Двоичное разбиение : метод «разделяй и властвуй» , который ускоряет численную оценку многих типов рядов с рациональными членами.
- Алгоритм суммирования Кахана : более точный метод суммирования чисел с плавающей точкой
Неограниченный алгоритм

Геометрический

Фильтрованная обратная проекция : эффективно вычисляет обратное двумерное преобразование Радона .
Метод набора уровней (LSM): численный метод отслеживания интерфейсов и форм.

Интерполяция и экстраполяция

Интерполяция Биркгофа : расширение полиномиальной интерполяции
Кубическая интерполяция
Интерполяция Эрмита
Интерполяция Лагранжа : интерполяция с использованием полиномов Лагранжа
Линейная интерполяция : метод аппроксимации кривой с использованием линейных полиномов.
Монотонная кубическая интерполяция : вариант кубической интерполяции, сохраняющий монотонность интерполируемого набора данных.
Многомерная интерполяция
- Бикубическая интерполяция : обобщение кубической интерполяции на два измерения.
- Билинейная интерполяция : расширение линейной интерполяции для интерполяции функций двух переменных на регулярной сетке.
- Повторная выборка Ланцоша («Lanzosh»): метод многомерной интерполяции, используемый для вычисления новых значений для любых цифровых выборочных данных.
- Интерполяция по методу ближайшего соседа
- Трикубическая интерполяция : обобщение кубической интерполяции на три измерения
Интерполяция Парето : метод оценки медианы и других свойств популяции, которая следует распределению Парето .
Полиномиальная интерполяция
- Алгоритм Невилла
Сплайн-интерполяция : уменьшает ошибку, связанную с явлением Рунге .
- Алгоритм Де Бура : B-сплайны
- Алгоритм де Кастельжо : кривые Безье
Тригонометрическая интерполяция

Линейная алгебра

Методы Крылова (для задач с большими разреженными матрицами; третий по важности класс численных методов 20-го века по рейтингу SISC; после быстрого Фурье и быстрого мультиполя)
Алгоритмы собственных значений
Процесс Грама–Шмидта : ортогонализирует набор векторов
Алгоритмы умножения матриц
- Алгоритм Кэннона : распределенный алгоритм умножения матриц , особенно подходящий для компьютеров, размещенных в сетке N × N.
- Алгоритм Копперсмита–Винограда : умножение квадратных матриц
- Алгоритм Фрейвальдса : рандомизированный алгоритм, используемый для проверки умножения матриц
- Алгоритм Штрассена : более быстрое умножение матриц

Решение систем линейных уравнений
- Метод бисопряженного градиента : решает системы линейных уравнений
- Сопряженный градиент : алгоритм численного решения частных систем линейных уравнений.
- Гауссово исключение
- Метод исключения Гаусса–Жордана : решает системы линейных уравнений
- Метод Гаусса–Зейделя : решает системы линейных уравнений итеративно
- Рекурсия Левинсона : решает уравнение, включающее матрицу Теплица
- Метод Стоуна : также известный как строго неявная процедура или SIP, представляет собой алгоритм решения разреженной линейной системы уравнений.
- Последовательная сверхрелаксация (SOR): метод, используемый для ускорения сходимости метода Гаусса–Зейделя.
- Алгоритм трехдиагональной матрицы (алгоритм Томаса): решает системы трехдиагональных уравнений
Алгоритмы разреженной матрицы
- Алгоритм Катхилла–Макки : уменьшение полосы пропускания симметричной разреженной матрицы
- Алгоритм минимальной степени : перестановка строк и столбцов симметричной разреженной матрицы перед применением разложения Холецкого
- Символическое разложение Холецкого : эффективный способ хранения разреженной матрицы

Монте-Карло

Выборка Гиббса : генерирует последовательность выборок из совместного распределения вероятностей двух или более случайных величин.
Гибридный Монте-Карло : генерирует последовательность выборок с использованием гамильтоновой взвешенной цепи Маркова Монте-Карло из распределения вероятностей, которое трудно выбрать напрямую.
Алгоритм Метрополиса-Гастингса : используется для генерации последовательности выборок из распределения вероятностей одной или нескольких переменных.
Алгоритм Вана и Ландау : расширение выборки алгоритма Метрополиса–Гастингса

Численное интегрирование

Алгоритм MISER : моделирование Монте-Карло, численное интегрирование

Поиск корня

Метод деления пополам
Метод ложного положения : и метод Иллинойса: 2-точечный, скобки
Метод Галлея : использует первую и вторую производные
Метод ITP : минимальная максимальная и сверхлинейная сходимость одновременно
Метод Мюллера : 3-точечная квадратичная интерполяция
Метод Ньютона : находит нули функций с помощью исчисления
Метод Риддера : 3-точечное, экспоненциальное масштабирование
Метод секущей : 2-точечный, 1-сторонний

Алгоритмы оптимизации

Гибридные алгоритмы

Альфа-бета-обрезка : поиск для уменьшения количества узлов в алгоритме минимакса
Ветви и границы
Алгоритм Брусса : см. алгоритм шансов
Цепное умножение матриц
Комбинаторная оптимизация : задачи оптимизации, в которых набор допустимых решений дискретен.
- Процедура жадного рандомизированного адаптивного поиска (GRASP): последовательное построение жадного рандомизированного решения и его последующие итеративные улучшения посредством локального поиска
- Венгерский метод : комбинаторный алгоритм оптимизации, который решает задачу назначения за полиномиальное время.
Удовлетворение ограничений
- Общие алгоритмы удовлетворения ограничений
- Алгоритм Чаффа : алгоритм для решения примеров задачи выполнимости булевых уравнений
- Алгоритм Дэвиса–Патнэма : проверка правильности логической формулы первого порядка
- Алгоритм Дэвиса–Патнэма–Логемана–Лавленда (DPLL): алгоритм для определения выполнимости пропозициональной логической формулы в конъюнктивной нормальной форме , т.е. для решения задачи CNF-SAT
- Проблема с точной обложкой
  - Алгоритм X : недетерминированный алгоритм
  - Dancing Links : эффективная реализация алгоритма X
Метод кросс-энтропии : общий подход Монте-Карло к комбинаторной и непрерывной многоэкстремальной оптимизации и выборке по важности
Дифференциальная эволюция
Динамическое программирование : задачи, демонстрирующие свойства перекрывающихся подзадач и оптимальной подструктуры
Метод эллипсоида : алгоритм решения задач выпуклой оптимизации.
Эволюционные вычисления : оптимизация, вдохновленная биологическими механизмами эволюции
- Стратегия эволюции
- Программирование экспрессии генов
- Генетические алгоритмы
  - Пропорциональный выбор по пригодности – также известный как выбор по принципу рулетки
  - Стохастическая универсальная выборка
  - Выбор усечения
  - Выбор турнира
- Меметический алгоритм
- Роевой интеллект
  - Оптимизация колонии муравьев
  - Алгоритм пчел : алгоритм поиска, который имитирует поведение роев медоносных пчел при поиске пищи.
  - Рой частиц
Алгоритм Франка-Вульфа : итеративный алгоритм оптимизации первого порядка для ограниченной выпуклой оптимизации
Поиск золотого сечения : алгоритм нахождения максимума действительной функции
Градиентный спуск
Поиск по сетке
Поиск гармонии (HS): метаэвристический алгоритм, имитирующий процесс импровизации музыкантов
Метод внутренней точки
Линейное программирование
- Алгоритм Бенсона : алгоритм решения задач линейной векторной оптимизации
- Разложение Данцига–Вульфа : алгоритм решения задач линейного программирования со специальной структурой
- Отложенная генерация столбцов
- Целочисленное линейное программирование : решение задач линейного программирования, в которых некоторые или все неизвестные ограничены целыми значениями.
  - Ветвь и разрез
  - Метод секущей плоскости
- Алгоритм Кармаркара : первый достаточно эффективный алгоритм, решающий задачу линейного программирования за полиномиальное время .
- Симплексный алгоритм : алгоритм решения задач линейного программирования.
Поиск строки
Локальный поиск : метаэвристика для решения вычислительно сложных задач оптимизации
- Случайный перезапуск восхождения на холм
- Поиск табу
Минимакс используется в программировании игр
Поиск ближайшего соседа (NNS): поиск ближайших точек в метрическом пространстве
- Best Bin First : найти приближенное решение задачи поиска ближайшего соседа в очень многомерных пространствах
Метод Ньютона в оптимизации
Нелинейная оптимизация
- Метод BFGS : нелинейный алгоритм оптимизации
- Алгоритм Гаусса–Ньютона : алгоритм решения нелинейных задач наименьших квадратов
- Алгоритм Левенберга–Марквардта : алгоритм решения нелинейных задач наименьших квадратов
- Метод Нелдера–Мида (метод симплекса вниз): нелинейный алгоритм оптимизации
Алгоритм шансов (алгоритм Брюсса): находит оптимальную стратегию для прогнозирования последнего конкретного события в случайной последовательности событий.
Случайный поиск
Имитация отжига
Стохастическое туннелирование
Алгоритм подмножества сумм
Гибридный алгоритм сопряженных градиентов HS-LS (см. https://doi.org/10.1016/j.cam.2023.115304)
Гибридный метод типа BFGS (подробнее см. https://doi.org/10.1016/j.cam.2024.115857)
Методы сопряженных градиентов (подробнее см. https://doi.org/10.1016/j.jksus.2022.101923)

Вычислительная наука

Астрономия

Алгоритм Судного дня : день недели
Сравнение Целлера — это алгоритм для вычисления дня недели для любой даты по юлианскому или григорианскому календарю.
Для расчета дня Пасхи используются различные пасхальные алгоритмы .

Биоинформатика

Базовый инструмент поиска локальных выравниваний, также известный как BLAST: алгоритм для сравнения первичной информации о биологических последовательностях
Алгоритм Кабша : вычисление оптимального выравнивания двух наборов точек для вычисления среднеквадратичного отклонения между двумя белковыми структурами.
Velvet : набор алгоритмов, манипулирующих графами де Брейна для сборки геномной последовательности
Сортировка по знаковым инверсиям: алгоритм для понимания геномной эволюции.
Максимальная экономия (филогенетика) : алгоритм нахождения простейшего филогенетического дерева для объяснения заданной матрицы признаков.
UPGMA : алгоритм построения филогенетического дерева на основе расстояния.
Фильтр Блума : вероятностная структура данных, используемая для проверки существования элемента в наборе. В основном используется в биоинформатике для проверки существования k-мера в последовательности или последовательностях.

Геонауки

Формулы Винсента : быстрый алгоритм для расчета расстояния между двумя точками широты/долготы на эллипсоиде
Geohash : общедоступный алгоритм, который кодирует десятичную пару широты/долготы в виде хэш-строки.

Лингвистика

Алгоритм Леска : разрешение неоднозначности смысла слова
Алгоритм стемминга : метод приведения слов к их основе, основанию или корневой форме.
Алгоритм Сухотина : статистический алгоритм классификации для классификации символов в тексте как гласных или согласных

Лекарство

Алгоритм ESC для диагностики сердечной недостаточности
Критерии Мэннинга для синдрома раздраженного кишечника
Алгоритмы диагностики тромбоэмболии легочной артерии
Техасский проект алгоритма лечения

Физика

Алгоритм ограничений : класс алгоритмов для удовлетворения ограничений для тел, которые подчиняются уравнениям движения Ньютона.
Алгоритм Демон : метод Монте-Карло для эффективной выборки членов микроканонического ансамбля с заданной энергией
Алгоритм Фезерстоуна : вычисляет эффекты сил, приложенных к структуре соединений и связей.
Приближение основного состояния
- Вариационный метод
  - метод Ритца
n- проблемы с телом
- Моделирование Барнса–Хата : решает задачу n тел приближенным способом, который имеет порядок $O(n log n)$ вместо $O(n 2),$ как при моделировании прямой суммы.
- Быстрый мультипольный метод (FMM): ускоряет расчет дальнодействующих сил
Алгоритм подсчета дождевого потока : сокращает сложную историю напряжений до количества элементарных перемен напряжений для использования в анализе усталости .
Sweep and prune : алгоритм широкой фазы, используемый при обнаружении столкновений для ограничения количества пар твердых тел, которые необходимо проверить на предмет столкновений.
Алгоритм VEGAS : метод уменьшения ошибок в моделировании Монте-Карло
Динамика Глаубера : метод моделирования модели Изинга на компьютере

Статистика

Алгоритмы расчета дисперсии : избежание нестабильности и численного переполнения
Приблизительный алгоритм подсчета : позволяет подсчитывать большое количество событий в небольшом регистре
Байесовская статистика
- Алгоритм вложенной выборки : вычислительный подход к проблеме сравнения моделей в байесовской статистике
Алгоритмы кластеризации
- Кластеризация со средней связью : простой агломеративный алгоритм кластеризации
- Алгоритм кластеризации Canopy : неконтролируемый алгоритм предварительной кластеризации, связанный с алгоритмом K-средних
- Кластеризация с полной связью : простой агломеративный алгоритм кластеризации
- DBSCAN : алгоритм кластеризации на основе плотности
- Алгоритм максимизации ожидания
- Нечеткая кластеризация : класс алгоритмов кластеризации, где каждая точка имеет степень принадлежности к кластерам.
  - Нечеткие c-средние
  - Кластеризация FLAME (нечеткая кластеризация с помощью локальной аппроксимации членства): определение кластеров в плотных частях набора данных и выполнение назначения кластеров исключительно на основе соседских отношений между объектами.
- Алгоритм кластеризации KHOPCA : локальный алгоритм кластеризации, который создает иерархические многосетевые кластеры в статических и мобильных средах.
- Кластеризация k-средних : кластеризация объектов на основе атрибутов в разделы
- k-means++ : вариация этого метода, использующая модифицированные случайные семена
- k-medoids : аналогично k-means, но выбирает точки данных или медоиды в качестве центров
- Алгоритм Линде–Бузо–Грея : алгоритм векторного квантования для получения хорошей кодовой книги
- Алгоритм Ллойда (итерация или релаксация Вороного): группирует точки данных в заданное количество категорий, популярный алгоритм для кластеризации методом k-средних.
- ОПТИКА : алгоритм кластеризации на основе плотности с методом визуальной оценки
- Кластеризация с одной связью : простой агломеративный алгоритм кластеризации
- SUBCLU : алгоритм кластеризации подпространства
- Метод Уорда : агломеративный алгоритм кластеризации, расширенный до более общих алгоритмов Ланса–Вильямса
- Алгоритм кластеризации WACA : локальный алгоритм кластеризации с потенциально многоскачковыми структурами; для динамических сетей
Теория Оценки
- Алгоритм максимизации ожидания. Класс связанных алгоритмов для нахождения оценок максимального правдоподобия параметров в вероятностных моделях.
  - Максимизация ожидания упорядоченного подмножества (OSEM): используется в медицинской визуализации для позитронно-эмиссионной томографии , однофотонной эмиссионной компьютерной томографии и рентгеновской компьютерной томографии.
- Алгоритм шансов (алгоритм Брюсса) Оптимальный онлайн-поиск различающегося значения в последовательном случайном вводе
- Фильтр Калмана : оценка состояния линейной динамической системы по серии зашумленных измерений
Алгоритм ложного ближайшего соседа (FNN) оценивает фрактальную размерность
Скрытая марковская модель
- Алгоритм Баума-Велча : вычисляет оценки максимального правдоподобия и оценки апостериорной моды для параметров скрытой марковской модели.
- Алгоритм «вперед-назад» : алгоритм динамического программирования для вычисления вероятности определенной последовательности наблюдений.
- Алгоритм Витерби : найти наиболее вероятную последовательность скрытых состояний в скрытой марковской модели
Частичная регрессия наименьших квадратов : находит линейную модель, описывающую некоторые прогнозируемые переменные в терминах других наблюдаемых переменных.
Теория массового обслуживания
- Алгоритм Бузена : алгоритм вычисления нормировочной константы G(K) в теореме Гордона–Ньюэлла
RANSAC (аббревиатура от «RANdom SAmple Consensus»): итеративный метод оценки параметров математической модели из набора наблюдаемых данных, содержащих выбросы.
Алгоритм подсчета очков : это форма метода Ньютона, используемая для численного решения уравнений максимального правдоподобия .
Метод Ямартино : вычислить приближение к стандартному отклонению σθ направления ветра θ за один проход по входящим данным
Алгоритм Зиккурата : генерирует случайные числа из неравномерного распределения.

Информатика

Архитектура компьютера

Алгоритм Томасуло : позволяет последовательным инструкциям, которые обычно останавливаются из-за определенных зависимостей, выполняться непоследовательно.

Компьютерная графика

Вырезка
- Обрезка линии
- Отсечение полигона
Контурные линии и изоповерхности
- Марширующие кубы : извлечение полигональной сетки изоповерхности из трехмерного скалярного поля (иногда называемого вокселями)
- Марширующие квадраты : генерируют контурные линии для двумерного скалярного поля.
- Марширующие тетраэдры : альтернатива марширующим кубам
Дискретная теорема Грина: это алгоритм для вычисления двойного интеграла по обобщенной прямоугольной области за постоянное время. Это естественное расширение алгоритма таблицы суммированной площади
Заливка : заполняет связанную область многомерного массива указанным символом.
Алгоритмы глобального освещения : учитывают прямое освещение и отражение от других объектов.
Удаление скрытой поверхности или визуальное определение поверхности
- Алгоритм Ньюэлла : устранение полигональных циклов при сортировке по глубине, необходимой при удалении скрытых поверхностей
- Алгоритм художника : обнаруживает видимые части трехмерного пейзажа.
- Рендеринг сканлайна : создает изображение путем перемещения воображаемой линии по изображению.
- Алгоритм Уорнока
Рисование линии : графический алгоритм аппроксимации отрезка линии на дискретных графических носителях.
- Алгоритм Брезенхэма : строит график точек двумерного массива, образуя прямую линию между двумя указанными точками (использует переменные решения)
- Алгоритм линии DDA : строит график точек двумерного массива, образуя прямую линию между двумя указанными точками (использует математику с плавающей точкой)
- Алгоритм линий Сяолиня У : алгоритм сглаживания линий.
Алгоритм средней точки окружности : алгоритм, используемый для определения точек, необходимых для рисования окружности.
Алгоритм Рамера–Дугласа–Пейкера : для заданной «кривой», состоящей из отрезков прямых, найти кривую, не слишком отличающуюся от нее, но имеющую меньше точек.
Затенение
- Затенение по Гуро : алгоритм для моделирования различных эффектов света и цвета на поверхности объекта в трехмерной компьютерной графике.
- Затенение по Фонгу : алгоритм интерполяции векторов нормалей поверхности для затенения поверхности в трехмерной компьютерной графике.
Slerp (сферическая линейная интерполяция): кватернионная интерполяция для анимации трехмерного вращения.
Таблица суммированной площади (также известная как интегральное изображение): алгоритм вычисления суммы значений в прямоугольном подмножестве сетки за постоянное время.
Двоичное разбиение пространства

Криптография

Асимметричное (с открытым ключом) шифрование :
Цифровые подписи (асимметричная аутентификация):
- DSA и его варианты:
  - ECDSA и детерминированный ECDSA
  - EdDSA (Ed25519)
- ЮАР
Криптографические хэш-функции (см. также раздел о кодах аутентификации сообщений):
- БЛЕЙК
- MD5 – Обратите внимание, что теперь есть метод генерации коллизий для MD5.
- RIPEMD-160
- SHA-1 – Обратите внимание, что теперь есть метод генерации коллизий для SHA-1.
- ША-2 (ША-224, ША-256, ША-384, ША-512)
- SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
- Tiger (TTH), обычно используется в хэшах Tiger tree
- ВОДОПРОВОД
Криптографически безопасные генераторы псевдослучайных чисел
- Блюм Блюм Шуб – на основе сложности факторизации
- Fortuna , задуманная как улучшение алгоритма Ярроу
- Регистр сдвига с линейной обратной связью (примечание: многие алгоритмы на основе LFSR слабы или были взломаны)
- Алгоритм Ярроу
Обмен ключами
- Обмен ключами Диффи-Хеллмана
- Эллиптическая кривая Диффи-Хеллмана (ECDH)
Функции вывода ключей , часто используемые для хеширования паролей и растяжения ключей.
Коды аутентификации сообщений (симметричные алгоритмы аутентификации, которые принимают ключ в качестве параметра):
- HMAC : аутентификация сообщений с использованием хэш-ключа
- Поли1305
- SipHash
Разделение секрета , Разделение секрета, Разделение ключа, Алгоритмы M из N
- Схема Блейки
- Схема Шамира
Симметричное (с секретным ключом) шифрование :
- Расширенный стандарт шифрования (AES), победитель конкурса NIST , также известный как Rijndael
- Рыба-иглу
- Дверыбы
- Трирыбы
- Стандарт шифрования данных (DES), иногда алгоритм DE, победитель конкурса NBS, заменен на AES для большинства целей
- ИДЕЯ
- RC4 (шифр)
- Крошечный алгоритм шифрования (TEA)
- Salsa20 и его обновленный вариант ChaCha20
Постквантовая криптография
Алгоритмы доказательства работы

Цифровая логика

Булева минимизация
- Алгоритм Куайна–Маккласки : также называемый алгоритмом QM, программируемый метод упрощения булевых уравнений.
- Метод Петрика : еще один алгоритм для упрощения булевых выражений
- Минимизатор эвристической логики Espresso : быстрый алгоритм минимизации булевой функции

Машинное обучение и статистическая классификация

Рекуррентное обратное распространение ошибки Алмейды–Пинеды : настройка матрицы синаптических весов для генерации желаемых выходных данных с учетом ее входных данных.
ALOPEX : алгоритм машинного обучения на основе корреляции
Изучение правил ассоциации : обнаружение интересных связей между переменными, используемых в интеллектуальном анализе данных.
Повышение эффективности (мета-алгоритм) : использование множества слабых учеников для повышения эффективности.
- AdaBoost : адаптивное усиление
- BrownBoost : алгоритм повышения производительности, который может быть устойчив к зашумленным наборам данных.
- LogitBoost : усиление логистической регрессии
- LPBoost : линейное программирование
Бутстреп-агрегирование (бэггинг): метод повышения стабильности и точности классификации
Компьютерное зрение
- Grabcut на основе разрезов Graph
Деревья решений
- Алгоритм C4.5 : расширение ID3
- Алгоритм ID3 (итеративный дихотомизатор 3): использование эвристики для генерации небольших деревьев решений
Кластеризация : класс алгоритмов неконтролируемого обучения для группировки и объединения связанных входных векторов.
- k-ближайших соседей (k-NN): метод классификации объектов на основе ближайших обучающих примеров в пространстве признаков.
Алгоритм Линде–Бузо–Грея : алгоритм векторного квантования, используемый для получения хорошей кодовой книги.
Хеширование с учетом локальности (LSH): метод вероятностного уменьшения размерности многомерных данных.
Нейронная сеть
- Обратное распространение : контролируемый метод обучения , требующий учителя, который знает или может рассчитать желаемый результат для любого заданного входа.
- Сеть Хопфилда : рекуррентная нейронная сеть , в которой все соединения симметричны.
- Персептрон : простейший вид нейронной сети прямого распространения: линейный классификатор .
- Импульсно-связанные нейронные сети (PCNN): нейронные модели, предложенные путем моделирования зрительной коры кошки и разработанные для высокопроизводительной биомиметической обработки изображений.
- Сеть радиальных базисных функций : искусственная нейронная сеть, которая использует радиальные базисные функции в качестве функций активации.
- Самоорганизующаяся карта : неконтролируемая сеть, которая создает низкоразмерное представление входного пространства обучающих выборок.
Случайный лес : классификация с использованием множества деревьев решений
Обучение с подкреплением :
- Q-обучение : изучает функцию «действие-ценность», которая дает ожидаемую полезность выполнения данного действия в данном состоянии и последующего следования фиксированной политике.
- Состояние–Действие–Вознаграждение–Состояние–Действие (SARSA): изучите политику процесса принятия решений Маркова
- Временная разница в обучении
Машина релевантных векторов (RVM): похожа на SVM, но обеспечивает вероятностную классификацию
Контролируемое обучение : обучение на примерах (маркированный набор данных разделен на обучающий и тестовый наборы)
Машина опорных векторов (SVM): набор методов, которые разделяют многомерные данные путем нахождения разделяющей гиперплоскости с максимальным запасом между двумя наборами.
- Структурированный SVM : позволяет обучать классификатор для общих структурированных выходных меток.
Алгоритм Winnow : похож на персептрон, но использует схему мультипликативного обновления веса.

Теория языка программирования

C3 линеаризация : алгоритм, используемый в основном для получения последовательной линеаризации иерархии множественного наследования в объектно-ориентированном программировании.
Алгоритм Чайтина : восходящий алгоритм распределения регистров раскраски графа, который использует стоимость/степень в качестве метрики утечки
Алгоритм вывода типа Хиндли-Милнера
Алгоритм Rete : эффективный алгоритм сопоставления с образцом для реализации систем правил производства
Алгоритм Сети-Ульмана : генерирует оптимальный код для арифметических выражений

Разбор

Алгоритм CYK : алгоритм O(n ³ ) для анализа контекстно-свободных грамматик в нормальной форме Хомского
Анализатор Early : еще один алгоритм O(n ^{3 ) для анализа любой}контекстно-свободной грамматики
GLR parser : алгоритм для разбора любой контекстно-свободной грамматики Масару Томиты . Он настроен на детерминированные грамматики, на которых он выполняет почти линейное время и O(n ³ ) в худшем случае.
Алгоритм «изнутри-снаружи» : алгоритм O(n ³ ) для переоценки вероятностей продукции в вероятностных контекстно-свободных грамматиках
LL-парсер : относительно простой алгоритм линейного времени синтаксического анализа для ограниченного класса контекстно-свободных грамматик.
LR parser : более сложный алгоритм линейного времени анализа для большего класса контекстно-свободных грамматик . Варианты:
Анализатор Packrat : алгоритм линейного анализа времени, поддерживающий некоторые контекстно-свободные грамматики и грамматики выражений анализа
Анализатор рекурсивного спуска : анализатор сверху вниз, подходящий для грамматик LL( k )
Алгоритм сортировочной станции : преобразует математическое выражение в инфиксной записи в постфиксную.
Парсер Пратта
Лексический анализ

Квантовые алгоритмы

Алгоритм Дойча–Йожи : критерий баланса для булевой функции
Алгоритм Гровера : обеспечивает квадратичное ускорение для многих задач поиска.
Алгоритм Шора : обеспечивает экспоненциальное ускорение (по сравнению с известными в настоящее время неквантовыми алгоритмами) для факторизации числа.
Алгоритм Саймона : обеспечивает доказуемо экспоненциальное ускорение (относительно любого неквантового алгоритма) для задачи черного ящика.

Теория вычислений и автоматов

Алгоритм Хопкрофта , алгоритм Мура и алгоритм Бжозовского : алгоритмы минимизации числа состояний в детерминированном конечном автомате
Построение Powerset : алгоритм преобразования недетерминированного автомата в детерминированный автомат .
Алгоритм Тарского–Куратовского : недетерминированный алгоритм , который обеспечивает верхнюю границу сложности формул в арифметической иерархии и аналитической иерархии.

Теория информации и обработка сигналов

Теория кодирования

Обнаружение и исправление ошибок

Коды BCH
Алгоритм BCJR : декодирование кодов с исправлением ошибок, определенных на решетках (в основном сверточных кодов)
Прямое исправление ошибок
Код Грея
Коды Хэмминга
- Хэмминг(7,4) : код Хэмминга , который кодирует 4 бита данных в 7 бит путем добавления 3 бит четности.
- Расстояние Хэмминга : суммарное количество позиций, которые отличаются
- Вес Хэмминга (количество популяций): найти количество единичных битов в двоичном слове
Проверка избыточности
- Адлер-32
- Циклическая проверка избыточности
- Алгоритм Дамма
- Контрольная сумма Флетчера
- Контроль продольной избыточности (LRC)
- Алгоритм Луна : метод проверки идентификационных номеров
- Алгоритм Луна mod N : расширение алгоритма Луна на нечисловые символы
- Четность : простая/быстрая техника обнаружения ошибок
- Алгоритм Верхоффа

Алгоритмы сжатия без потерь

Преобразование Барроуза-Уиллера : предварительная обработка полезна для улучшения сжатия без потерь
Вес контекстного дерева
Дельта-кодирование : помощь в сжатии данных, в которых последовательные данные встречаются часто.
Динамическое марковское сжатие : сжатие с использованием предиктивного арифметического кодирования
Кодировщики словарей
- Кодирование пар байтов (BPE)
- Сдувать
- Лемпель–Зив
  - ЛЗ77 и ЛЗ78
  - Лемпель – Зив Джефф Бонвик (LZJB)
  - Алгоритм цепей Лемпеля–Зива–Маркова (LZMA)
  - Лемпель – Зив – Оберхумер (LZO): ориентирован на скорость.
  - Лемпель–Зив–Стац (LZS)
  - Лемпель – Зив – Сторер – Шимански (ЛЗСС)
  - Лемпель-Зив-Уэлч (LZW)
  - LZWL : вариант на основе слога
  - ЛЗХ
  - Лемпель – Зив Росс Уильямс (LZRW)
Энтропийное кодирование : схема кодирования, которая присваивает коды символам таким образом, чтобы длины кодов соответствовали вероятностям символов.
- Арифметическое кодирование : расширенное энтропийное кодирование
  - Кодирование диапазона : то же самое, что и арифметическое кодирование , но рассматривается немного по-другому.
- Кодирование Хаффмана : простое сжатие без потерь, использующее относительные частоты символов
  - Адаптивное кодирование Хаффмана : метод адаптивного кодирования, основанный на кодировании Хаффмана.
  - Алгоритм слияния пакетов : оптимизирует кодирование Хаффмана с учетом ограничений на длину строк кода.
- Кодирование Шеннона-Фано
- Кодирование Шеннона–Фано–Элиаса : предшественник арифметического кодирования ^[5]
Энтропийное кодирование с известными характеристиками энтропии
- Кодирование Голомба : форма энтропийного кодирования, которая оптимальна для алфавитов, следующих геометрическому распределению.
- Кодирование Райса : форма энтропийного кодирования, которая оптимальна для алфавитов, следующих геометрическому распределению.
- Усеченное двоичное кодирование
- Унарное кодирование : код, представляющий число n с n единицами, за которыми следует ноль.
- Универсальные коды : кодируют положительные целые числа в двоичные кодовые слова.
  - Дельта- , гамма- и омега -кодирование Элиаса
  - Экспоненциально-голомбовское кодирование
  - Кодирование Фибоначчи
  - Кодирование Левенштейна
Быстрая, эффективная и безпотерьная система сжатия изображений (FELICS): алгоритм сжатия изображений без потерь
Инкрементное кодирование : дельта-кодирование, применяемое к последовательностям строк
Прогнозирование путем частичного сопоставления (PPM): адаптивный статистический метод сжатия данных, основанный на моделировании контекста и прогнозировании.
Кодирование длин серий : сжатие данных без потерь с использованием строк повторяющихся символов.
Алгоритм SEQUITUR : сжатие без потерь путем инкрементального вывода грамматики в строке

Алгоритмы сжатия с потерями

3Dc : алгоритм сжатия данных с потерями для нормальных карт
Сжатие звука и речи
- Алгоритм A-law : стандартный алгоритм компандирования
- Линейное предсказание с кодовым возбуждением (CELP): сжатие речи с низкой скоростью передачи данных
- Линейное предсказательное кодирование (LPC): сжатие с потерями путем представления спектральной огибающей цифрового сигнала речи в сжатой форме.
- Алгоритм Mu-law : стандартный алгоритм сжатия аналогового сигнала или компандирования
- Искривленное линейное предсказательное кодирование (WLPC)
Сжатие изображения
- Кодирование с блочным усечением (BTC): тип метода сжатия изображений с потерями для изображений в оттенках серого.
- Встроенный вейвлет Zerotree (EZW)
- Алгоритмы быстрого косинусного преобразования (алгоритмы FCT): эффективно вычисляют дискретное косинусное преобразование (DCT)
- Фрактальное сжатие : метод, используемый для сжатия изображений с использованием фракталов.
- Разделение наборов в иерархических деревьях (SPIHT)
- Сжатие волн : форма сжатия данных, хорошо подходящая для сжатия изображений (иногда также для сжатия видео и аудио).
Кодирование с преобразованием : тип сжатия данных для «естественных» данных, таких как аудиосигналы или фотографические изображения.
Сжатие видео
Векторная квантизация : метод, часто используемый при сжатии данных с потерями.

Цифровая обработка сигнала

Адаптивно-аддитивный алгоритм (алгоритм АА): нахождение фазы пространственной частоты наблюдаемого источника волны
Дискретное преобразование Фурье : определяет частоты, содержащиеся в (сегменте) сигнала.
Алгоритм быстрого сворачивания : эффективный алгоритм для обнаружения приблизительно периодических событий в данных временных рядов.
Алгоритм Герхберга–Сакстона : алгоритм восстановления фазы для оптических плоскостей
Алгоритм Герцеля : определение конкретного частотного компонента в сигнале. Может использоваться для декодирования цифр DTMF .
Синтез струнных инструментов Karplus-Strong : синтез физического моделирования для имитации звука ударной или щипковой струны или некоторых типов ударных инструментов.

Обработка изображений

Усиление контрастности
- Выравнивание гистограммы : использование гистограммы для улучшения контрастности изображения.
- Адаптивное выравнивание гистограммы : выравнивание гистограммы, которое адаптируется к локальным изменениям контрастности
Маркировка связанных компонентов : поиск и маркировка непересекающихся областей
Дизеринг и полутонирование
Алгоритм разностной карты Элзера : алгоритм поиска для общих проблем удовлетворения ограничений. Первоначально использовался для рентгеновской дифракционной микроскопии
Обнаружение особенностей
- Детектор краев Canny : обнаруживает широкий диапазон краев на изображениях
- Обобщенное преобразование Хафа
- преобразование Хафа
- Алгоритм Марра–Хилдрета : алгоритм раннего обнаружения границ
- SIFT (масштабно-инвариантное преобразование признаков): алгоритм для обнаружения и описания локальных особенностей на изображениях.
- SURF ( Speed Up Robust Features ) : надежный локальный детектор признаков, впервые представленный Гербертом Бэем и др. в 2006 году, который может использоваться в задачах компьютерного зрения, таких как распознавание объектов или 3D-реконструкция. Он частично вдохновлен дескриптором SIFT. Стандартная версия SURF в несколько раз быстрее SIFT и, по утверждениям ее авторов, более устойчива к различным преобразованиям изображений, чем SIFT.^[6]^[7]
Деконволюция Ричардсона–Люси : алгоритм устранения размытости изображения
Слепая деконволюция : алгоритм устранения размытости изображения, когда функция рассеяния точки неизвестна.
Медианная фильтрация
Вырезание швов : алгоритм изменения размера изображения с учетом содержимого
Сегментация : разделение цифрового изображения на две или более областей.
- Алгоритм GrowCut : интерактивный алгоритм сегментации
- Алгоритм случайного блуждания
- Регион растущий
- Преобразование водораздела : класс алгоритмов, основанных на аналогии водораздела

Разработка программного обеспечения

Алгоритмы кэширования
Преобразование CHS : преобразование между системами адресации дисков
Double dabble : преобразование двоичных чисел в BCD
Функция хэширования : преобразует большой объем данных, возможно, переменного размера, в небольшой элемент данных, обычно одно целое число, которое может служить индексом в массиве.
- Функция хэширования Фаулера–Нолла–Во : быстрая с низкой частотой коллизий
- Хеширование Пирсона : вычисляет только 8-битное значение, оптимизировано для 8-битных компьютеров.
- Хеширование Зобриста : используется при реализации таблиц транспозиции
Алгоритм сопоставления Unicode
Алгоритм обмена Xor : меняет местами значения двух переменных без использования буфера.

Алгоритмы базы данных

Алгоритмы распределенных систем

Синхронизация часов
Консенсус (компьютерная наука) : достижение согласия относительно единого значения или истории среди ненадежных процессоров.
Обнаружение завершения процесса
- Алгоритм Дейкстры-Шолтена
- Алгоритм Хуанга
Упорядочение Лампорта : частичное упорядочение событий, основанное на отношении «произошло раньше» .
Выборы лидера : метод динамического выбора координатора
- Алгоритм хулигана
Взаимное исключение
Алгоритм моментального снимка : запись согласованного глобального состояния для асинхронной системы
- Алгоритм Чанди–Лэмпорта
Векторные часы : генерируют частичный порядок событий в распределенной системе и обнаруживают нарушения причинно-следственной связи .

Алгоритмы выделения и освобождения памяти

Распределение памяти Buddy : алгоритм распределения памяти с меньшей фрагментацией
Сборщики мусора
- Алгоритм Чейни : усовершенствование полупространственного коллектора
- Сборщик мусора поколений : быстрые сборщики мусора, которые разделяют память по возрасту
- Алгоритм Mark-compact : комбинация алгоритма Mark-Sweep и алгоритма копирования Чейни.
- Отметить и подмести
- Полукосмический коллекционер: ранний коллекционер-копировщик
Подсчет ссылок

Нетворкинг

Алгоритм Карна : решает проблему получения точных оценок времени передачи сообщений в обоих направлениях при использовании TCP.
Алгоритм Лулео : метод эффективного хранения и поиска таблиц маршрутизации в Интернете.
Перегрузка сети
- Экспоненциальный откат
- Алгоритм Нейгла : повышение эффективности сетей TCP/IP путем объединения пакетов
- Усеченный двоичный экспоненциальный откат

Алгоритмы операционных систем

Алгоритм банкира : алгоритм, используемый для избежания тупиковых ситуаций
Алгоритмы замены страниц : для выбора страницы-жертвы в условиях нехватки памяти
- Адаптивный замещающий кэш : более высокая производительность, чем LRU
- Часы с адаптивной заменой (CAR): алгоритм замены страниц с производительностью, сопоставимой с кэшем адаптивной замены

Синхронизация процессов

Планирование

Планирование ввода-вывода

Планирование диска

Алгоритм лифта : алгоритм планирования работы диска, работающий как лифт.
Сначала кратчайший поиск : алгоритм планирования диска для сокращения времени поиска .

Смотрите также

Ссылки

^ "алгоритм". LII / Институт правовой информации . Получено 2023-10-26 .
^ Гегенфуртнер, Карл Р. (1992-12-01). «PRAXIS: алгоритм Брента для минимизации функций». Методы исследования поведения, приборы и компьютеры . 24 (4): 560–564. doi : 10.3758/BF03203605 . ISSN 1532-5970.
^ "richardshin.com | Алгоритм обнаружения цикла Флойда". 2013-09-30 . Получено 2023-10-26 .
^ "Двоичный поиск Эйтцингера - Algorithmica" . Получено 2023-04-09 .
^ "Кодирование Шеннона-Фано-Элиаса" (PDF) . my.ece.msstate.edu . Архивировано из оригинала (PDF) 2021-02-28 . Получено 2023-10-11 .
^ "Архивная копия" (PDF) . www.vision.ee.ethz.ch . Архивировано из оригинала (PDF) 21 февраля 2007 г. . Получено 13 января 2022 г. .{{cite web}}: CS1 maint: archived copy as title (link)
^ "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2013-10-06 . Получено 2013-10-05 .{{cite web}}: CS1 maint: archived copy as title (link)