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

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

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

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

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

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

Комбинаторные алгоритмы [ править ]

Общие комбинаторные алгоритмы [ править ]

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

Алгоритмы графов [ править ]

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

Рисование графика [ править ]

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

Теория сетей [ править ]

Сетевой анализ
- Анализ ссылок
  - Алгоритм Гирвана – Ньюмана : обнаружение сообществ в сложных системах
  - Анализ веб-ссылок
    - Тематический поиск по гиперссылкам (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-й самый большой элемент в последовательности.
Тернарный поиск : метод поиска минимума или максимума функции, которая либо строго возрастает, а затем строго убывает, или наоборот.
Сортированные списки
- Алгоритм двоичного поиска : находит элемент в отсортированной последовательности.
- Техника поиска Фибоначчи : поиск отсортированной последовательности с использованием алгоритма «разделяй и властвуй», который сужает возможные местоположения с помощью чисел Фибоначчи.
- Поиск с переходом (или поиск блока): линейный поиск на меньшем подмножестве последовательности.
- Прогнозирующий поиск : бинарный поиск, в котором величина поискового запроса зависит от высоких и низких значений в поиске. Иногда его называют поиском по словарю или интерполированным поиском.
- Унифицированный двоичный поиск : оптимизация классического алгоритма двоичного поиска.
- Бинарный поиск Эйцингера : алгоритм двоичного поиска, дружественный к кэшу ^[6]

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

Простой алгоритм слияния
алгоритм слияния 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-й корневой алгоритм
- Алгоритм сдвига корня n-й степени : поразрядное извлечение корня
Суммирование:
- Двоичное расщепление : метод «разделяй и властвуй» , который ускоряет численную оценку многих типов рядов с помощью рациональных членов.
- Алгоритм суммирования Кахана : более точный метод суммирования чисел с плавающей запятой
Неограниченный алгоритм

Геометрический [ править ]

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

Интерполяция и экстраполяция [ править ]

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

Линейная алгебра [ править ]

Алгоритмы собственных значений
Процесс Грама – Шмидта : ортогонализует набор векторов.
Алгоритмы умножения матриц
- Алгоритм Кэннона : распределенный алгоритм умножения матриц , особенно подходящий для компьютеров, разбитых на сетку 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
  - ЭдDSA (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)
  - Lempel–Ziv–Markov chain algorithm (LZMA)
  - Лемпель – Зив – Оберхумер (LZO): ориентирован на скорость.
  - Лемпель – Зив – Стац (ЛЗС)
  - Лемпель – Зив – Сторер – Шимански (ЛЗСС)
  - Лемпель – Зив – Велч (LZW)
  - LZWL : слоговой вариант
  - ЛЗХ
  - Лемпель – Зив Росс Уильямс (LZRW)
Энтропийное кодирование : схема кодирования, которая присваивает символам коды таким образом, чтобы длина кода соответствовала вероятностям символов.
- Арифметическое кодирование : расширенное энтропийное кодирование
  - Кодирование диапазона : то же, что и арифметическое кодирование , но рассматривается немного по-другому.
- Кодирование Хаффмана : простое сжатие без потерь с использованием относительных частот символов.
  - Адаптивное кодирование Хаффмана : метод адаптивного кодирования, основанный на кодировании Хаффмана.
  - Алгоритм слияния пакетов : оптимизирует кодирование Хаффмана с учетом ограничения длины строк кода.
- Кодирование Шеннона – Фано
- Кодирование Шеннона-Фано-Элиаса : предшественник арифметического кодирования ^[7]
Энтропийное кодирование с известными энтропийными характеристиками
- Кодирование Голомба : форма энтропийного кодирования, оптимальная для алфавитов, следующих геометрическим распределениям.
- Кодирование Райса : форма энтропийного кодирования, оптимальная для алфавитов, следующих геометрическим распределениям.
- Усеченное двоичное кодирование
- Унарное кодирование : код, представляющий число 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. ^[8]^[9]
Деконволюция Ричардсона – Люси : алгоритм устранения размытия изображения
Слепая деконволюция : алгоритм устранения размытия изображения, когда функция распространения точки неизвестна.
Медианная фильтрация
Резьба по шву : алгоритм изменения размера изображения с учетом содержимого
Сегментация : разделение цифрового изображения на две или более области.
- Алгоритм 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 г.
^ Осипенко, Александр (12 сентября 2021 г.). «Алгоритм Гейла – Шепли просто объяснен» . Середина . Проверено 27 октября 2023 г.
^ Бертольди, Дэвид (11 ноября 2019 г.). «Создание генератора псевдослучайных чисел» . Середина . Проверено 27 октября 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] Осипенко, Александр (12 сентября 2021 г.). «Алгоритм Гейла – Шепли просто объяснен» . Середина . Проверено 27 октября 2023 г.

[5] Бертольди, Дэвид (11 ноября 2019 г.). «Создание генератора псевдослучайных чисел» . Середина . Проверено 27 октября 2023 г.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

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