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

Широкое определение термина «алгоритм».

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

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

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

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

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

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

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

Графовые алгоритмы

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

Рисование графика

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

Теория сетей

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

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

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

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

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

Подграфы

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

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

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

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

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

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

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

Объединение последовательностей

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

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

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

Комбинации последовательностей

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

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

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

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

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

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

Подстроки

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

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

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

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

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

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

Геометрия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Монте-Карло

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

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

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

Нахождение корня

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

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

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

Альфа-бета-обрезка : поиск для уменьшения количества узлов в минимаксном алгоритме
Ветвь и граница
Алгоритм Брусса : см. алгоритм шансов
Цепное матричное умножение
Комбинаторная оптимизация : задачи оптимизации, в которых набор возможных решений дискретен.
- Жадная рандомизированная процедура адаптивного поиска (GRASP): последовательное построение жадного рандомизированного решения и последующие итеративные его улучшения посредством локального поиска.
- Венгерский метод : алгоритм комбинаторной оптимизации, который решает задачу назначения за полиномиальное время.
Удовлетворение ограничений
- Общие алгоритмы удовлетворения ограничений
- Алгоритм Чаффа : алгоритм для решения случаев булевой проблемы выполнимости.
- Алгоритм Дэвиса – Патнэма : проверьте правильность логической формулы первого порядка.
- Алгоритм Дэвиса-Патнэма-Логемана-Лавленда (DPLL): алгоритм для определения выполнимости формулы пропозициональной логики в конъюнктивной нормальной форме , т.е. для решения CNF-SAT. проблемы
- Точная проблема с обложкой
  - Алгоритм X : недетерминированный алгоритм
  - Танцующие ссылки : эффективная реализация алгоритма 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 : общедоступный алгоритм, который кодирует десятичную пару широты и долготы в виде хеш-строки.

Лингвистика

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

Лекарство

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

Физика

Алгоритм ограничений : класс алгоритмов для удовлетворения ограничений для тел, подчиняющихся уравнениям движения Ньютона.
Алгоритм демона : метод Монте-Карло для эффективной выборки членов микроканонического ансамбля с заданной энергией.
Алгоритм Физерстоуна : вычисляет воздействие сил, приложенных к конструкции суставов и связей.
основного состояния Приближение
- Вариационный метод
  - метод Ритца
проблемы с телом
- Моделирование Барнса – Хата : решает задачу n тел приближенным способом, который имеет порядок $O(n log n)$ вместо $O(n 2),$ как при моделировании прямой суммы.
- Метод быстрых мультиполей (FMM): ускоряет расчет дальнодействующих сил.
Алгоритм подсчета дождевых потоков : сводит сложную историю напряжений к подсчету элементарных обращений напряжений для использования в усталости . анализе
Развертка и обрезка : алгоритм широкой фазы, используемый при обнаружении столкновений для ограничения количества пар твердых тел, которые необходимо проверить на предмет столкновений.
Алгоритм 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 : отображает точки двумерного массива для формирования прямой линии между двумя указанными точками (использует математические вычисления с плавающей запятой).
- Алгоритм линии Сяолиня Ву : алгоритм сглаживания линий.
Алгоритм средней точки круга : алгоритм, используемый для определения точек, необходимых для рисования круга.
Алгоритм Рамера – Дугласа – Пейкера : дана «кривая», состоящая из отрезков линий, чтобы найти кривую, не слишком отличающуюся, но имеющую меньше точек.
Затенение
- Затенение Гуро : алгоритм для моделирования различных эффектов света и цвета на поверхности объекта в 3D-компьютерной графике.
- Затенение Фонга : алгоритм интерполяции векторов нормалей поверхности для затенения поверхности в 3D компьютерной графике.
Slerp (сферическая линейная интерполяция): кватернионная интерполяция с целью анимации трехмерного вращения.
Таблица суммированных площадей (также известная как интегральное изображение): алгоритм вычисления суммы значений в прямоугольном подмножестве сетки за постоянное время.
Разделение двоичного пространства

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

Асимметричное шифрование (с открытым ключом) :
Цифровые подписи (асимметричная аутентификация):
- DSA и его варианты:
  - ECDSA и детерминированный ECDSA
  - ЭдДСА (Ed25519)
- ЮАР
Криптографические хэш-функции (см. также раздел о кодах аутентификации сообщений):
- БЛЕЙК
- MD5 – Обратите внимание, что теперь существует метод генерации коллизий для MD5.
- РИПЕМД-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.
- ВИРЛПУЛ
Криптографически безопасные генераторы псевдослучайных чисел
- Блюм Блюм Шуб - на основе жесткости факторизации
- Fortuna , задуманная как улучшение алгоритма Ярроу.
- Регистр сдвига с линейной обратной связью (примечание: многие алгоритмы на основе LFSR слабы или сломаны)
- Алгоритм тысячелистника
Обмен ключами
- Обмен ключами Диффи-Хеллмана
- Эллиптическая кривая Диффи – Хеллмана (ECDH)
Функции получения ключей , часто используемые для хеширования паролей и растяжения ключей.
Коды аутентификации сообщений (алгоритмы симметричной аутентификации, принимающие ключ в качестве параметра):
- HMAC : аутентификация сообщения с использованием хэш-ключа.
- Поли1305
- СипХэш
Совместное использование секретов , разделение секретов, разделение ключей, алгоритмы M of N
- Схема Блейки
- Схема Шамира
Симметричное (секретный ключ) шифрование :
- Advanced Encryption Standard (AES), победитель конкурса NIST , также известный как Rijndael.
- Иглобрюхая рыба
- Две рыбы
- Тройка
- Стандарт шифрования данных (DES), иногда алгоритм DE, победитель отборочного конкурса NBS, в большинстве случаев заменен на AES.
- ИДЕЯ
- RC4 (шифр)
- Крошечный алгоритм шифрования (TEA)
- Salsa20 и его обновленный вариант ChaCha20.
Постквантовая криптография
Алгоритмы доказательства работы

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

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

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

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

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

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

Разбор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программная инженерия

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

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

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

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

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

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

сеть

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

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

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

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

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

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

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

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

См. также

Ссылки

^ «алгоритм» . ЛИИ/Институт правовой информации . Проверено 26 октября 2023 г.
^ Гегенфуртнер, Карл Р. (1 декабря 1992 г.). «ПРАКСИС: Алгоритм Брента для минимизации функций» . Методы, инструменты и компьютеры исследования поведения . 24 (4): 560–564. дои : 10.3758/BF03203605 . ISSN 1532-5970 .
^ «richardshin.com | Алгоритм обнаружения цикла Флойда» . 30 сентября 2013 г. Проверено 26 октября 2023 г.
^ «Двоичный поиск Эйцингера — Алгоритмика» . Проверено 9 апреля 2023 г.
^ «Кодирование Шеннона-Фано-Элиаса» (PDF) . my.ece.msstate.edu . Архивировано из оригинала (PDF) 28 февраля 2021 г. Проверено 11 октября 2023 г.
^ «Архивная копия» (PDF) . www.vision.ee.ethz.ch . Архивировано из оригинала (PDF) 21 февраля 2007 года . Проверено 13 января 2022 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 6 октября 2013 г. Проверено 5 октября 2013 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[1] «алгоритм» . ЛИИ/Институт правовой информации . Проверено 26 октября 2023 г.

[2] Гегенфуртнер, Карл Р. (1 декабря 1992 г.). «ПРАКСИС: Алгоритм Брента для минимизации функций» . Методы, инструменты и компьютеры исследования поведения . 24 (4): 560–564. дои : 10.3758/BF03203605 . ISSN 1532-5970 .

[3] «richardshin.com | Алгоритм обнаружения цикла Флойда» . 30 сентября 2013 г. Проверено 26 октября 2023 г.

[4] «Двоичный поиск Эйцингера — Алгоритмика» . Проверено 9 апреля 2023 г.

[5] «Кодирование Шеннона-Фано-Элиаса» (PDF) . my.ece.msstate.edu . Архивировано из оригинала (PDF) 28 февраля 2021 г. Проверено 11 октября 2023 г.

[6] «Архивная копия» (PDF) . www.vision.ee.ethz.ch . Архивировано из оригинала (PDF) 21 февраля 2007 года . Проверено 13 января 2022 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[7] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 6 октября 2013 г. Проверено 5 октября 2013 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

v т и Структуры данных и алгоритмы
Структуры данных	Множество Ассоциативный массив Бинарное дерево поиска Дерево Фенвика График Хэш-таблица Куча Связанный список Очередь Дерево сегментов Куча Нить Дерево Три
Алгоритмы	Возврат Бинарный поиск Поиск в ширину Поиск методом перебора Поиск в глубину Разделяй и властвуй Динамическое программирование Обход графа Складывать Жадный Хэш-функция Минимакс Онлайн Рандомизированный Рекурсия Поиск корней Сортировка Потоковое вещание Развертка линии Поиск строк Топологическая сортировка
Список структур данных Список алгоритмов