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

Эта страница — информационный список.

Основная статья: Алгоритм

Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и списке основных разделов теории алгоритмов^[1]

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

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

• Алгоритм Флойда для нахождения циклов (англ.) — находит цикл в итерациях
• Генераторы псевдослучайных чисел:
  • Алгоритм Блюма — Блюма — Шуба
  • Вихрь Мерсенна
  • Метод Фибоначчи с запаздываниями
  • Линейный конгруэнтный метод
• Алгоритм Робинсона — Шенстеда — генерация перестановок из пар таблиц Юнга

Алгоритмы на графах

• Алгоритм Беллмана — Форда — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
• Алгоритм Борувки — находит минимальное остовное дерево в графе
• Алгоритм Брона — Кербоша — нахождение наибольших максимальных независимых по включению множеств вершин графа.
• Алгоритм Флойда — Уоршелла — вычисляет все кратчайшие пути во взвешенном графе
• Алгоритм Дейкстры — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
• Алгоритм Джонсона — вычисляет все кратчайшие пути во взвешенном графе
• Алгоритм Краскала — находит остовный лес минимального веса в графе
• Алгоритм основанный на источнике (англ.) — алгоритм для рисования графа
• Алгоритм Прима — находит остовное дерево минимального веса в связном графе
• Алгоритм Кристофидеса — эвристический приближенный алгоритм для решения метрической задачи коммивояжера на графе.
• Метод ближайшего соседа — «жадных» алгоритм, один из простейших эвристических методов решения задачи коммивояжёра
• Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
• Построение транзитивного замыкания графа (установление факта достижимости вершин)

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

n — число вершин, m — число рёбер, U — наибольшая величина максимальной пропускной способности сети.

• Алгоритм Форда — Фалкерсона (1956) — $O(nmU)$.
• Алгоритм Эдмондса — Карпа, кратчайших увеличивающихся цепей (1969) — $O(nm^2)$.
• Алгоритм Диница (1970) — $O(n^2m)$.
• Алгоритм Эдмондса — Карпа, локально-максимального увеличения (1972) — $O(m^2 \log U)$.
• Алгоритм Диница 2 (1973) — $O(nm \log U)$.
• Алгоритм Карзанова (1974) — $O(n^3)$.
• Алгоритм Черкаского (1977) — $O(n^2 \sqrt m)$.
• Алгоритм Малхотры — Кумара — Махешвари (1977) — $O(n^3)$.
• Алгоритм Галила (1980) — $O(n^{5/3}m^{2/3})$.
• Алгоритм Галила — Наамада (1980) — $O(nm\log^2{n})$.
• Алгоритм Слейтора — Тарьяна (1983) — $O(nm\log n)$.
• Алгоритм Габоу (1985) — $O(nm\log U)$.
• Алгоритм Голдберга — Тарьяна (1988) — $O(nm\log{(n^2/m)})$.
• Алгоритм Ахьюа — Орлина (1989) — $O(nm + n^2\log U)$.
• Алгоритм Ахьюа — Орлина — Тарьяна (1989) — $O(nm \log {(n\sqrt U / {(m + 2)})})$.
• Алгоритм Кинга — Рао — Тарьяна 1 (1992) — $O(nm + n^{2 + \epsilon})$.
• Алгоритм Кинга — Рао — Тарьяна 2 (1994) — $O(nm \log _{m/n \log n}n)$.
• Алгоритм Черияна — Хейджрапа — Мехлхорна (1996) — $O(n^3 / \log n)$.
• Алгоритм Голдберга — Рао (1998) — $O(\min\{n^{2/3}, m^{1/2}\} m \log(n^2 / m) \log U)$.
• Алгоритм Орлина 1 (2012) — $O(nm)$.
• Алгоритм Орлина 2 (2012) — $O(n^2 / \log n)$, если $m = O(n)$.

Алгоритмы нахождения максимального паросочетания

• Алгоритм Хопкрофта — Карпа
• Алгоритм Форда — Фалкерсона
• Алгоритм Куна
• Алгоритм Габоу

Алгоритмы поиска

• Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
• Алгоритм выбора (англ.) — модификация алгоритма линейного поиска; находит $k$-тый по величине элемент в списке;
• Двоичное дерево поиска O(log(n)) — использует бинарное дерево для хранения элементов;
• Двоичный поиск O(log(n)) — находит элемент в отсортированном списке
• Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю)
• Линейный поиск O(n) — находит элемент в неотсортированном списке
• Локальный поиск (оптимизация)
• Метод штрафов
• Поиск в глубину — проходит граф ветка за веткой
• Поиск в ширину — проходит граф уровень за уровнем
• Поиск по первому наилучшему совпадению (англ. Best-first search) — проходит граф в порядке важности, используя очередь приоритетов
• Троичный поиск — находит максимум или минимум функции
• Поиск в хеш-таблице
• Алгоритм Ли (волновой алгоритм) — поиск пути на карте.

Алгоритмы на строках

Алгоритмы поиска строки

• Z-функция
• Алгоритм Кнута — Морриса — Пратта
• Алгоритм Рабина — Карпа поиска строки
• Алгоритм Бойера — Мура поиска строки
  • Алгоритм Бойера — Мура — Хорспула
  • Первый алгоритм Бойера — Мура — Санди
  • Второй алгоритм Бойера — Мура — Санди
  • Алгоритм Бойера — Мура — Гелила
  • Алгоритм Турбо-БМ
• Алгоритм Демелки — Баеса-Ятеса — Гоннета (также известен как Двоичный алгоритм поиска подстроки)
• Алгоритм Ахо — Корасик
• Алгоритм Битапа (англ.) (также известен как shift-or, shift-and, Двоичный алгоритм поиска подстроки, ^[2]или алгоритм Баеса-Ятеса^[3] — Гоннета)
• Задача поиска наибольшей общей подпоследовательности
• Задача поиска наибольшей увеличивающейся подпоследовательности
• Задача поиска наикратчайшей общей надпоследовательности (англ.)
• Задача поиска наибольшей общей подстроки
• Задача поиска количества подпалиндромов

Алгоритмы вычисления расстояния между строками

• Алгоритм Вагнера — Фишера
• Алгоритм Хешберга
• Алгоритм Ханта — Шиманского
• Алгоритм Укконена — Майерса

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

• Алгоритм Укконена
• Алгоритм Майерса
• Алгоритм Ву — Менбера

Вычисление характеристических паттернов

• Алгоритм Крочемора поиска всех кратных строк
• Алгоритм Мейна — Лоренца поиска всех кратных строк
• Алгоритм Мейна поиска крайних левых серий
• Алгоритм Колпакова — Кучерова поиска всех серий
• Алгоритм Ли — Смита поиска всех оболочек
• Алгоритм Франека — Смита — Танга поиска всех раппортов
• Алгоритм Шмидта поиска k-приближенных раппортов
• Алгоритмы Сима — Илиопулоса — Парка — Смита поиска k-приближенных периодов

Примерное соответствие

• Расстояние Левенштейна
• Расстояние Хэмминга
• Расстояние Дамерау — Левенштейна
• Алгоритм Нидлмана — Вунша
• Алгоритм Смита — Вотермана (англ.)
• Soundex
• Metaphone

Деревья для строковых последовательностей

• Суффиксное дерево
• Алгоритм Мак-Крейта
• Алгоритм Укконена
• Алгоритм Вайнера
• Алгоритм Фрача
• Суффиксный массив

Алгоритмы сортировки

• Bogosort
• Stooge sort
• Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием
• Наивная сортировка — генерация всех $n!$ возможных перестановок и проверка на отсортированность
• Блинная сортировка
• Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной
• Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
• Глупая сортировка
• Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — $O(n^2)$.
• Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
• Плавная сортировка (англ.)
• Поразрядная сортировка — сортирует строки буква за буквой.
• Сортировка Бентли — Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
• Сортировка с помощью двоичного дерева (англ. Tree sort)
• Сортировка методом вставок — определяем, где текущий элемент должен находиться в отсортированном списке, и вставляем его туда
• Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
• Сортировка перемешиванием (Сортировка коктейлем)
• Сортировка подсчётом — используется диапазон входных данных, подсчитывается число одинаковых элементов (3 варианта)
• Сортировка пузырьком
• Сортировка расчёской
• Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
• Сортировка Шелла — попытка улучшить сортировку вставками
• Топологическая сортировка
• Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
• Цифровая сортировка — то же, что и Поразрядная сортировка.

Алгоритмы слияния

• Простой алгоритм слияния (англ.  Simple Merge algorithm )
• -мерный алгоритм слияния (англ.  k-way Merge algorithm )

Минимизация булевых функций

• Алгоритм Куайна
• Алгоритм Мак-Класки
• Карты Карно
• Алгоритм Свободы
• Алгоритм Хва
• Получение простых импликант на основе разбиения по кодам разности
• Метод поразрядного выращивания

Алгоритмы сжатия данных

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

• Преобразование Барроуза — Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
• Преобразование Шиндлера (англ.  ST) — модификация преобразования Барроуза — Уилера
• Алгоритм DEFLATE — популярный свободный алгоритм сжатия (используется в библиотеке zlib)
• Дельта-кодирование — эффективно для сжатия данных, в которых последовательности часто повторяются
• Инкрементное кодирование — дельта-кодирование применяемое к последовательности строк
• Семейство алгоритмов словарного сжатия Лемпеля — Зива:
  • LZ77 — родоначальник семейства LZ77-алгоритмов
    • LZ77-PM
    • LZFG
      • LZFG-PM
    • LZP
    • LZBW
    • LZSS
      • LZB
      • LZH
      • LZRW1
  • LZ78 — родоначальник семейства LZ78 алгоритмов
    • Алгоритм Лемпеля — Зива — Велча (также известен как англ. LZW) — сжатие без потерь
      • LZW-PM
    • LZMW
  • LZMA — сокращение от англ. Lempel-Ziv-Markov chain-Algorithm
  • LZO — алгоритм компрессии данных ориентированный на скорость
• Алгоритм сжатия PPM
• Кодирование длин серий (Групповое кодирование, также известен как англ. RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
• Алгоритм SEQUITUR (англ.) — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
• Вейвлет-кодирование на основе вложенных нуль-деревьев (англ.) (EZW-кодирование)
• Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
  • Алгоритм Шеннона — Фано — самый простой алгоритм кодирования
  • Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
    • Адаптивное кодирование Хаффмана (англ.) — техника адаптивного кодирования, основывающаяся на коде Хаффмана
  • Усечённое двоичное кодирование (англ.) — используется для однородного вероятностного распределения с конечным алфавитом
  • Арифметическое кодирование — развитие энтропийного кодирования
    • Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании
  • Кодирование расстояний (англ.) — метод сжатия данных, который близок по эффективности к арифметическому кодированию
• Энтропийное кодирование с известными характеристиками
  • Унарное кодирование — код, который представляет число $n$ в виде $n$ единиц с замыкающим нулём
  • дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
  • Кодирование Фибоначчи — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
  • Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
  • Кодирование Райса (англ.) — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

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

• Линейное предсказывающее кодирование (англ.) — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
• А-закон — стандартный алгоритм компандирования. Применяется в РФ.
• Мю-закон — стандартный алгоритм компандирования
• Фрактальное сжатие — метод, использующий фракталы для сжатия изображений
• Трансформирующее кодирование (англ.) — тип сжатия данных для «естественных» данных, таких как аудиосигналы или фотографические изображения
• Векторное квантование — техника, часто используемая в сжатии данных с потерями
• Вейвлетное сжатие — тип компрессии данных хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)

Вычислительная геометрия

• Алгоритм Гилберта — Джонсона — Кёрти — определение наименьшего расстояния между двумя выпуклыми множествами
• Поиск пары ближайших точек (англ.) — трудоёмкость $O(n\log n)$.
• Поиск диаметра множества точек
• Алгоритм Цируса — Бека — отсечение линий.
• Алгоритм Сазерленда — Ходжмана — отсечение многоугольника.
• Построения контура прямоугольников (стороны параллельны осям координат).
• Нахождение ядра многоугольника
• Регуляризация многоугольника — декомпозиция многоугольника на монотонные части.

Построение выпуклой оболочки набора точек

• Построение ВП через треугольники — трудоёмкость $O(n^4)$.
• Построение ВП перебором рёбер на принадлежность — трудоёмкость $O(n^3)$.
• Алгоритм сканирования Грэхема — трудоёмкость $O(n\log n)$.
• Алгоритм Экла — Туссена — трудоёмкость $O(n\log n)$. Улучшение алгоритма Грэхема.
• Алгоритм Эндрю — трудоёмкость $O(n\log n)$. Улучшение алгоритма Грэхема.
• Алгоритм быстрой оболочки — трудоёмкость $O(n^2)$, в среднем — $O(n\log n)$.
• Алгоритм Киркпатрика — построение выпуклой оболочки набора точек на плоскости методом «разделяй и властвуй» через мосты. Трудоёмкость $O(n\log n)$.
• Построение методом «разделяй и властвуй» через построение касательных — трудоёмкость $O(n\log n)$.
• Алгоритм заворачивания подарков (Джарвиса) — трудоёмкость $O(nh)$, $h$ — количество точек в выпуклой оболочке.
• Алгоритм Киркпатрика — Зейделя (англ.) — трудоёмкость $O(n\log h)$, $h$ — количество точек в выпуклой оболочке.
• Алгоритм Чана — трудоёмкость $O(n\log h)$, $h$ — количество точек в выпуклой оболочке.
• Инкрементальный алгоритм (fast online hull) — через построение касательных $O(n^2)$, с помощью сбалансированного дерева — $O(n\log n)$.
• Приближённая выпуклая оболочка снизу (lower approximate hull) — методом полос. Трудоёмкость $O(nk)$, где $k$ — количество полос.
• Приближённая выпуклая оболочка сверху (upper approximate hull) — методом полос. Трудоёмкость $O(nk)$, где $k$ — количество полос.
• Алгоритм Ли (выпуклые оболочки) — построение выпуклой оболочки простого многоугольника через отрезание карманов. Трудоёмкость $O(n)$.

Триангуляция

• Триангуляция через поиск диагоналей — ищется диагональ, многоугольник делится на два и далее рекурсивно. Трудоёмкость $O(n^4)$.
• Триангуляция через отрезание ушей — ищется образующая треугольник диагональ, соседние с треугольником вершины — следующие претенденты на отрезание. Трудоёмкость $O(n^2)$.
• Триангуляция монотонного простого многоугольника — трудоёмкость $O(n)$.
• Жадная триангуляция — трудоёмкость $O(n^2\log n)$.
• Оптимальная триангуляция — NP-полная задача. Суммарная длина всех рёбер минимальна среди всех триангуляций данного множества.

Триангуляция Делоне

• Итеративные алгоритмы построения триангуляции Делоне — трудоёмкость $O(n^2)$.
• Алгоритмы построения триангуляции Делоне слиянием — трудоёмкость $O(n^2)$ и $O(n\log n)$.
• Алгоритмы прямого построения триангуляции Делоне — трудоёмкость $O(n^2)$.
• Двухпроходные алгоритмы построения триангуляции Делоне — трудоёмкость $O(n^2)$ и $O(n\log n)$.
• Триангуляции Делоне с ограничениями — трудоёмкость $O(n^2)$.

Квазитриангуляция

• Алгоритм построения квазитриангуляции

Диаграмма Вороного

• Простой алгоритм построения диаграммы Вороного — трудоёмкость $O(n^2\log n)$.
• Алгоритм построения диаграммы Вороного через заметающую прямую — трудоёмкость $O(n\log n)$.
• Рекурсивный алгоритм построения диаграммы Вороного — трудоёмкость $O(n\log n)$.

Локализация точки (англ.)

• Локализация точки для выпуклого многоугольника — время запроса $O(\log n)$.
• Локализация точки в звездном многоугольнике — время запроса $O(\log n)$.
• Алгоритм точки в многоугольнике — проверка принадлежности данной точки простому многоугольнику $O(n)$.
• Метод луча — принадлежность точки простому многоугольнику $O(n)$.
• Метод углов — принадлежность точки выпуклому многоугольнику. Трудоёмкость $O(n)$.
• Метод полос — простой многоугольник. Время запроса $O(\log n)$, память $O(n^2)$.
• Метод детализации триангуляции Киркпатрика — простой многоугольник. Время запроса $O(\log n)$, память $O(n)$.
• Трапецоидальная карта — простой многоугольник. Рандомизированный алгоритм, время запроса $O(\log n)$, память $O(n)$.
• Метод цепей — простой многоугольник. Время запроса $O(\log^2 n)$, память $O(n)$.

Пересечения

• Алгоритм Бентли — Оттмана — поиск всех точек пересечения отрезков на плоскости $O((n+k)\log n)$, $k$ — количество точек пересечения.
• Алгоритм Чазелла — Эдельсбруннера — пересечение отрезков за $O(k+n\log n)$.
• Определение наличия пересекающихся отрезков (англ.) (алгоритм Шеймоса — Гоя) — трудоёмкость $O(n\log n)$.
• Алгоритм Сазерленда — Коэна — для выпуклых многоугольников. Трудоёмкость $O(n_1 n_2)$.
• Пересечения выпуклых многоугольников — трудоёмкость $O(n_1+n_2)$.
• Алгоритм Шеймоса — Хоуи — для выпуклых многоугольников методом полос. Трудоёмкость $O(n_1+n_2)$.
• Пересечения выпуклых многоугольников с заметающей прямой — трудоёмкость $O(n_1+n_2)$.
• Пересечение звёздных многоугольников — трудоёмкость $O(n_1 n_2)$.
• Пересечение полуплоскостей — трудоёмкость $O(n\log n)$.
• Алгоритм Лианга — Барски (англ.)
• Быстрое отсечение (англ.)
• Алгоритм Сайреса — Бека (англ.)
• Николла — Ли — Николла (англ.)
• Алгоритм Сазерленда — Ходгмана
• Алгоритм Уайлера — Атертона

Вращающиеся калиперы (англ.)

• Поиск диаметра множества точек через вращающиеся калиперы
• Поиск минимального по площади описанного прямоугольника для множества точек (англ.)
• Поиск минимального по периметру описанного прямоугольника для множества точек (англ.)
• Определение ширины многоугольника
• Построение суммы Минковского двух выпуклых многоугольников
• Поиск максимального расстояния между двумя множествами точек
• Поиск минимального расстояния между двумя выпуклыми многоугольниками
• Построение мостов для двух выпуклых многоугольников
• Построение критических опорных прямых для выпуклых многоугольников

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

• Алгоритм Брезенхэма — растеризует отрезок линии с заданными координатами начала и конца
• Алгоритм рисования прямой (англ.) — алгоритм для аппроксимации отрезка на дискретной графической поверхности
• Алгоритм DDA-линии — чертит точки двухмерного массива в форме прямой линии между двумя заданными точками (использует вычисления с плавающей точкой)
• Алгоритм заливки области (англ.) — заполняет соединённый регион многомерного массива указанным значением
• Алгоритм Ву — алгоритм для сглаживания прямой
• Алгоритм художника (англ.) — определяет видимые части трёхмерной сцены
• Алгоритм лучевой трассировки (англ.) — рендеринг реалистичных изображений
• Затенение по Фонгу — модель освещения и метод интерполяции в трёхмерной компьютерной графике
• Затенение по Гуро — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
• Изображение сканирующей линией (англ.) (англ. Scanline rendering) — конструирует образ с помощью перемещения воображаемой линии над образом
• Алгоритмы глобального освещения (англ.) — рассматривает прямое освещение и отражение от других объектов
• Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
  • Интерполяция сплайнами (англ.) — уменьшение ошибки феномена Рунге

Компьютерное зрение

• Epitome (англ.) — представление образа или видео при помощи меньшего образа или видео

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

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

• Шифрование с симметричным (скрытым) ключом:
  • ГОСТ 28147-89
  • AES (англ. Advanced Encryption Standard) — победитель соревнования NIST, также известен как Rijndael
  • Blowfish
  • DES (англ. Data Encryption Standard) — иногда, алгоритм DEA (англ. Data Encryption Algorithm), победитель соревнования NBS, заменён на AES для большинства применений
  • RC2
  • IDEA (англ. International Data Encryption Algorithm)
  • RC4

• Асимметричное шифрование (с публичным ключом)
  • Алгоритм Эль-Гамаля
  • RSA
  • NTRUEncrypt

• Алгоритмы выработки общего ключа
  • Алгоритм Диффи — Хеллмана

• Алгоритмы цифровой подписи:
  • ГОСТ Р 34.10-94 — устаревший российский стандарт цифровой подписи, модификация схемы Эль-Гамаля
  • ГОСТ Р 34.10-2001 — российский стандарт цифровой подписи, основанный на эллиптических кривых
  • DSA (англ. Digital Signature Algorithm) — базируется на схеме Эль-Гамаля
  • ECDSA (англ. Elliptic Curve Digital Signature Algorithm) — перенос DSA на эллиптические кривые

• Алгоритмы разделения секрета
  • Рюкзак — на данный момент доказана нестойкость схемы
  • Схема Шамира
  • Схема Blakey

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

• Доказательство с нулевым разглашением

• Криптографические функции дайджестов сообщений:
  • ГОСТ Р 34.11-94
  • MD5 Резюме сообщения 5 (Message Digest 5) Разработан Рональдом Ривестом (RFC 1321) — существует метод генерации коллизий
  • RIPEMD-160
  • SHA-1
  • HMAC — аутентификация сообщение с помощью хеш-ключа
  • Тигр — обычно используется в Тигровых деревьях хэшей
• Криптостойкие генераторы псевдослучайных чисел
  • Алгоритм Блюма — Блюма — Шуба — базируется на сложности факторизации
  • Алгоритм Ярроу
  • ГПСЧ Фортуна (англ.) — якобы улучшение алгоритма Ярроу
  • Генерация случайных простых чисел
  • Алгоритм аутентификации сообщений Message authentication algorithm

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

• CORDIC — быстрая техника вычисления тригонометрических функций.
• Медианный фильтр для одномерного массива
• Дождевой алгоритм (англ.) — Уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
• Osem — алгоритм для обработки медицинских изображений
• Алгоритм Гёрцеля — Может быть использован для декодирования цифр тональных сигналов
• Развеяние Ричардсона — Люси (англ.) — алгоритм увеличения резкости образа

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

• Алгоритмы для восстановления и изоляции повреждённых семантик (англ.)
• Алгоритм сравнения Unicode (англ.)
• Алгоритм преобразования CHS (англ.) — Преобразование между системами адресации диска
• Алгоритм вычисления контрольной суммы (CRC или FCS) Циклическая избыточная сумма (Ciclic Redunancy Check), или контрольная последовательность кадра (Frame Check Sequence) — вычисление кода проверки.
• Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
• Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.

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

• Упорядочение Лампорта (англ.) — Частичное упорядочение событий в зависимости от того, что случилось раньше
• Алгоритм мгновенного снимка (англ.) — снимок процесса записывающий глобальное состояние системы
• Векторное упорядочение (англ.) — Полное упорядочение событий
• Алгоритм Марцулло (англ.) — распределённая синхронизация часов
• Алгоритм пересечений (англ.) — другой алгоритм синхронизации часов

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

• Сборщик мусора Боема (англ.) — «скромный» сборщик мусора
• Дружеское выделение памяти (англ.) — алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
• Сборщик мусора с поколениями — быстрые сборщики мусора, которые разделяют память по возрасту
• Пометить и вымести (англ.)
• Подсчёт ссылок

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

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

Дисковые алгоритмы-планировщики

• Алгоритм лифта (англ.) — дисковый алгоритм планирования, который работает как лифт
• Алгоритм кратчайшего перемещения (англ.) — дисковый алгоритм планирования для уменьшения времени поиска

Сетевые алгоритмы

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

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

• Алгоритм Петерсона
• Алгоритм пекарни Лампорта (англ.)
• Алгоритм Деккера

Алгоритмы планирования

• Планирование с постоянной скоростью (англ.)
• Первый заканчивает раньше (планирование) (англ.)
• Честное разделение (планирование) (англ.)
• Планирование Round-robin
• Многоуровневая отдача (планирование) (англ.) (англ. Multi level feedback queue)
• Кратчайшее оставшееся время (планирование) (англ.)
• Наименьшее время бездействия (планирование) (англ.)
• Списковое планирование (англ.) (англ. List scheduling)
• Алгоритм высоких вершин (англ.)
• Кратчайшая работа следующей
• Кратчайшее оставшееся время (англ.)

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

• Выбор пропорционально пригодности (англ.) — также известен как выбор рулеточного колеса

Медицинские алгоритмы

• Медицинский алгоритм (англ.)
• Техасский проект медицинских алгоритмов (англ.)

Нейронные сети

• Метод обратного распространения ошибки
• Самоорганизующееся отображение (Карты Кохонена, SOM)
• Метод коррекции ошибки
• Метод коррекции с обратной передачей сигнала ошибки

Вычислительная алгебра

• Алгоритм Бухбергера (англ.) — находит базис Грёбнера
• Процесс Грама ― Шмидта — ортогонализация набора векторов
• Алгоритм пополнения Кнута — Бендикса (англ.)
• Алгоритм мультивариационного деления (англ.) — для многочленов в некоторых неопределённостях
• Алгоритмы умножения матриц
  • Алгоритм Штрассена — быстрое умножение матриц
  • Алгоритм Копперсмита — Винограда
• Умножение цепных матриц (англ.) (англ. Chain matrix multiplication)
• Алгоритм Катхилла — Макки — алгоритм уменьшения ширины ленты разреженных симметричных матриц
• Алгоритмы вычисления дискретного преобразования Фурье
  • Быстрое преобразование Фурье
  • Алгоритм БПФ Кули — Туки (англ.)
  • Алгоритм БПФ Рэдера (англ.)
  • Алгоритм БПФ Блюштейна (англ.)
  • Алгоритм БПФ Брууна (англ.)
  • Алгоритм БПФ при помощи простых сомножителей (англ.)
• Алгоритм нахождения собственного значения матрицы (англ.)
• Преобразования Хаусхолдера (QR-разложение) — вычисление обратной матрицы, собственных векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
• Решение систем линейных уравнений
  • Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений
  • Структурированное гауссово исключение — применяется, когда матрица системы является разреженной
  • Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления
  • Разложение Холецкого — метод, эффективный для ленточных и разреженных матриц
  • Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам

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

• Целочисленная арифметика (алгоритмы для работы с большими числами)
  • Умножение столбиком больших чисел
  • «Быстрый столбик»
  • Умножение Карацубы — алгоритм быстрого умножения чисел
  • Алгоритм Тоома — Кука (англ.) — обобщённый алгоритм умножения Карацубы (известен также как Toom-3)
  • Метод умножения Шёнхаге — Штрассена — более быстрый алгоритм умножения
  • Алгоритм Фюрера — на данный момент самый быстрый алгоритм умножения больших чисел
  • Деление на одноразрядное число (DO)
  • Деление больших чисел
• Быстрое возведение в степень — вычисляет степени чисел при помощи возведения в квадрат
• Алгоритмы модулярной арифметики
  • Алгоритм Монтгомери — модулярное умножение и возведение в степень
  • Алгоритм нахождения порядка элемента
  • Алгоритм Тонелли — Шенкса — решение квадратичных сравнений
  • Решение систем линейных сравнений
    • С помощью китайской теоремы об остатках
    • Алгоритм Гарнера
• Решение систем линейных уравнений над полем
  • Алгоритм Ланцоша — эффективен над полем характеристики 2
  • Алгоритм Видемана
• Дискретное логарифмирование:
  • В простом конечном поле
    • Алгоритм Шенкса (алгоритм больших и маленьких шагов, англ.  baby-step giant-step)
    • Алгоритм Полига — Хеллмана — эффективен, если все делители $p-1$ — небольшие
    • ρ-метод Полларда дискретного логарифмирования
    • Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования
    • Алгоритм COS (алгоритм Копперсмита — Одлыжко — Шреппеля) — достаточно эффективный субэкспоненциальный алгоритм
    • Решето числового поля — наиболее эффективный на данный момент алгоритм дискретного логарифмирования
  • В произвольном конечном поле
    • Алгоритм исчисления индексов (англ.) (алгоритм index-calculus) — сведение дискретного логарифмирования в произвольном конечном поле к аналогичной задаче в простом поле
    • Алгоритм Копперсмита — эффективный алгоритм дискретного логарифмирования в конечном поле характеристики 2
• Алгоритмы нахождения наибольшего общего делителя (НОД) двух чисел
  • Алгоритм Евклида
  • Расширенный алгоритм Евклида — также решает уравнение $ax+by=c$, где $c=$НОД$(a,\;b)$, НОД$(a,\;y)=$НОД$(b,\;x)=1$
  • Бинарный алгоритм вычисления НОД — эффективный способ вычисления НОД
  • Расширенный бинарный алгоритм — модификация бинарного алгоритма нахождения НОД, аналогичная расширенному алгоритму Евклида
• Простые числа:
  • Нахождение простых чисел:
    • Перебор делителей
    • Решето Эратосфена
    • Решето Аткина — оптимизированная версия решета Эратосфена
    • Решето Сундарама
  • Тесты простоты — проверка, является ли данное число простым:
    • Детерминированные тесты простоты:
      • Тест на основе малой теоремы Ферма
      • Тест Миллера — модификация теста на основе малой теоремы Ферма; опирается на расширенную гипотезу Римана
      • (N-1)–метод проверки простоты — тест на простоту при известном разложении на множители числа $N-1$; также используется для построения больших простых чисел
      • (N+1)–метод проверки простоты — тест на простоту при известном разложении на множители числа $N+1$
      • Алгоритм Конягина — Померанса — модификация $(N-1)$-метода
      • Алгоритм Ленстры — использует суммы Якоби и некоторые тесты, обобщающие малую теорему Ферма
      • Тест Люка — Лемера для чисел Мерсенна
      • Тест Пепина для чисел Ферма
      • Тест Агравала — Каяла — Саксены — полиномиальный детерминированный тест простоты
    • Вероятностные тесты простоты:
      • Тест Соловея — Штрассена — опирается на малую теорему Ферма и свойства символа Лежандра
      • Тест Миллера — Рабина — эффективная модификация теста Соловея — Штрассена
  • Факторизация — разложение числа на простые множители:
    • Алгоритмы с экспоненциальной сложностью:
      • Перебор делителей
      • Метод факторизации Ферма
      • (p-1)-алгоритм Полларда
      • ρ-метод Полларда
      • Метод Лемана
      • Алгоритм Ленстры
    • Алгоритмы с субэкспоненциальной сложностью:
      • Алгоритм Диксона
      • Метод квадратичного решета
      • Специальное решето числового поля (англ.) (англ. SNFS)
      • Общее решето числового поля (англ.) (англ. GNFS)
      • Факторизация с помощью эллиптических кривых — вероятностный алгоритм факторизации с помощью эллиптических кривых
• Алгоритм Шуфа — вычисление порядка группы точек эллиптической кривой
• Алгоритм Ленстры — Ленстры — Ловаса (англ.) (LLL-алгоритм, L³-алгоритм)

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

Основная статья: Численный анализ

Смотри также Список разделов численного анализа

• Алгоритм де Кастельжо — вычисление кривых Безье
• Методы интерполяции
  • Линейное сглаживание по трём точкам
  • Линейное сглаживание по пяти точкам
  • Нелинейное сглаживание по семи точкам
• Приближенное вычисление решений
  • Метод фальшпозиции (англ.) (False position method, regula falsi method) — аппроксимирует корни функции
  • Метод бисекции - нахождение нуля (корня) нелинейной функции
  • Метод Ньютона (метод касательных) — нахождение нулей функций с помощью производной
  • Метод секущих (метод хорд) — аппроксимирует корни функции
  • Метод градиентов (градиентный спуск) — аппроксимирует решение системы уравнений
  • Метод сопряжённого градиента
  • Алгоритм Гаусса — Ньютона — алгоритм для решения нелинейных уравнений методом наименьших квадратов
  • Алгоритм Левенберга — Марквардта — алгоритм для решения нелинейных уравнений методом наименьших квадратов
• Танцующие звенья (англ.) — нахождение всех решений задачи точного покрытия
• Алгоритм де Бора (англ.) — вычисление сплайнов
• Алгоритм Гаусса — Лежандра (англ.) — вычисление цифр числа пи
• Алгоритм суммирования Кахана (англ.) — более аккуратный метод суммирования чисел с плавающей точкой
• Алгоритм MISER (англ.) — моделирование методом Монте-Карло, численное интегрирование
• Функции округления (англ.) — классические способы округления чисел
• Сдвигающий алгоритм корня n-ой степени (англ.) — извлечение корня цифра за цифрой
• Вычисление квадратного корня:
  • Алгоритм Герона
  • школьный (ручной) алгоритм — аппроксимирует квадратный корень числа
• Вычисление корня n-ной степени

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

• Линейное программирование
• Симплекс-метод
• «Венгерский метод» — решение задач целочисленного линейного программирования
• Метод Мака решения задачи о назначениях
• Алгоритм имитации отжига
• Метод роя частиц
• Муравьиные алгоритмы
• Метод ветвей и границ
• Дифференциальная эволюция
• Эволюционная стратегия
• Метод Нелдера — Мида (downhill simplex method) — алгоритм нелинейной оптимизации
• Всхождение со случайным перезапуском (англ.)
• Стохастическое туннелирование (англ.)
• Алгоритм суммирования подмножеств (англ.)
• Метод перебора
• Метод Фибоначчи поиска экстремума — метод выбора точек для нахождения экстремума функции одной переменной
• Градиентный спуск
• Алгоритм Левенберга — Маркардта — комбинация метода Ньютона и наискорейшего спуска
• Метод Ньютона в оптимизации, основанный на методе Ньютона поиска корня
• Квазиньютоновские методы — методы, основанные на замене матрицы Гессе её приближением.
  • Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (англ.) — квазиньютоновский алгоритм нелинейной оптимизации

Грамматический разбор

• Рекурсивный нисходящий парсер — Нисходящий парсер, подходящий для $LL(k)$-грамматик
• LL-парсер — относительно простой алгоритм разбора за линейное время для ограниченного класса контекстно-свободных грамматик
• LR-парсер (англ.) — более сложный алгоритм разбора за линейное время для большего класса контекстно-свободных грамматик. Варианты:
  • Парсер первенства операторов (англ.)
  • SLR-парсер (англ.) (англ. Simple LR parser)
  • LALR-парсер (англ.) (англ. Look-ahead LR parser)
  • Канонический LR-парсер (англ.)
• Парсер старьёвщика (англ.) — алгоритм разбора за линейное время, поддерживающий некоторые контекстно-свободные грамматики и грамматики разбора выражений
• Алгоритм Коука — Янгера — Касами (алгоритм CYK) — $O(n^3)$-алгоритм для разбора любой контекстно-свободной грамматики
• Алгоритм Эрли — другой $O(n^3)$-алгоритм для разбора любой контекстно-свободной грамматики
• GLR-парсер — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и $O(n^3)$ в худшем случае.
• Метод рекурсивного спуска — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной грамматикой
• Алгоритм Рутисхаузера — работает в предположении о полной скобочной структуре выражения

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

Приложения квантовых вычислений к различным категориям проблем и алгоритмы

• Алгоритм Гровера — позволяет выполнять поиск среди $N$ вариантов за $O(\sqrt{N})$ проверок
• Алгоритм Шора — полиномиальный алгоритм факторизации числа
• Алгоритм Дойча — Джоза — критерий баланса для булевой функции
• Задача Фейнмана

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

• Конструирование набора подмножеств (англ.) — алгоритм для преобразования недетерминированного автомата в детерминированный
• Алгоритм Тодда — Коксетера — процедура для создания сомножеств

Другие

• Астрономические алгоритмы
• Алгоритмы восстановления фазы волнового фронта (Гершберга-Сакстона, Фиенапа, Бейтса, Альморо и др.)
• Алгоритм Баума — Велша
• Алгоритмы манипуляции битами
  • Алгоритм создания битовой маски
  • Алгоритм обмена при помощи исключающего ИЛИ — обмен значений двух переменных без использования буфера
• Алгоритм вычисления дня недели (Алгоритм Судного Дня)
• Алгоритм Шрейера — Симса (англ.)
• Алгоритм Витерби
• Алгоритм Луна — метод проверки правильности идентификационных чисел
• Алгоритм стемматизации (стемминга) — процесс нахождения основы слова
• Алгоритм Риша (англ.) — нахождение первообразных
• Алгоритм синтеза многосвязной сети
• Алгоритм распространения доверия (алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях
• Быстрый метод мультиполей — алгоритм вычисления сил взаимодействия N частиц^[4]

Примечания

1. ↑ В тематическом проекте есть также список терминов, относящихся к алгоритмам и структурам данных, составленный на основе словаря Американского национального института стандартов. Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание. Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «Википедия:Алгоритмы в Википедии (англ.)» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.
2. ↑ Ошибка в сносках^?: Неверный тег <ref>; для сносок autogenerated1 не указан текст
3. ↑ Вице-президент Yahoo приедет в «Яндекс» — PCNEWS.RU
4. ↑ Barry A. Cipra The Best of the 20th Century: Editors Name Top 10 Algorithms (англ.) // SIAM News. — 2000. — Т. 33. — № 4.

Литература

• Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. — Издательский дом «Вильямс», 2000. — 384 с. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)
• Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
• Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, Volume 1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — 720 с. — ISBN 5-8459-0080-8
• Дональд Кнут Искусство программирования, том 1, выпуск 1. MMIX — RISC-компьютеры нового тысячелетия = The Art of Computer Programming, Volume 1, Fascicle 1: MMIX — A RISC Computer for the New Millennium. — М.: «Вильямс», 2007. — 160 с. — ISBN 978-5-8459-1163-6
• Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, Volume 2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — 832 с. — ISBN 5-8459-0081-6
• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, Volume 3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4
• Дональд Кнут Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. — М.: «Вильямс», 2013. — 960 с. — ISBN 978-5-8459-1744-7
• Д-р Сидни Фейт TCP/IP: Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) = TCP/IP: Arhitecture, Protocols, and Implementation with IPv6 and IP Security. — 2nd. ed. Dr. Sidnie Feit Copyright 1997, 1993 by The McGraw-Hill Companies, Inc. (включая IP версии 6 и IP Security). — 2-е изд. — М.: Издательство «Лори», 2003. — 424 с. — ISBN 5-85582-072-6 (рус.) / ISBN 0-07-021389-5 (англ.)
• Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. — М.: «Вильямс», 2007. — 480 с. — ISBN 978-5-8459-1244-2
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. — ISBN 5-8459-0857-4
• Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — 672 с. — ISBN 5-93772-081-4
• Роберт Седжвик Фундаментальные алгоритмы на C. Алгоритмы на графах = Algorithms in C. Graph Algorithms. — СПб.: ДиаСофтЮП, 2003. — 480 с. — ISBN 5-93772-082-2
• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Algorithms. — The McGraw-Hill Companies, 2006. — 320 с. — ISBN 0-07-352340-2

Ссылки

• Сайт по методам сжатия данных
• Дискретная математика: Алгоритмы — библиотека алгоритмов и визуализаторов
• Алгоритмы, методы, исходники
• Множество алгоритмов с примерами их реализации