Проект:Математика/Списки/Список алгоритмов

Шаблон:Координационный список Шаблон:Main Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и списке основных разделов теории алгоритмов<ref>В тематическом проекте есть также список терминов, относящихся к алгоритмам и структурам данных, составленный на основе словаря Американского национального института стандартов. Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание. Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «Шаблон:Не переведено» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.</ref>

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

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

Генерация комбинаторных объектов

Алгоритм Робинсона — Шенстеда — генерация перестановок из пар таблиц Юнга
Алгоритм Нарайаны
Алгоритм Джонсона — Троттера

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

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

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

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

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

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

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

Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
Алгоритм выбора — модификация алгоритма линейного поиска; находит <math>k</math>-й по величине элемент в списке;
Двоичное дерево поиска <math>O(\log n)</math>, <math>O(n)</math> в худшем случае — использует бинарное дерево для хранения элементов;
- Красно-чёрное дерево <math>O(\log n)</math> — использует дополнительный атрибут узла дерева — «цвет»
- АВЛ-дерево <math>O(\log n)</math> — в каждом узле хранит разницу высот (целое число от −1 до +1)
- Расширяющееся дерево <math>O(\log n)</math> — вместо дополнительных полей в узлах дерева «расширяющие операции» выполняются при каждом обращении к дереву.
Двоичный поиск <math>O(\log n)</math> — находит элемент в отсортированном списке
Интерполяционный поиск (Предсказывающий поиск, Поиск по словарю)
Линейный поиск <math>O(n)</math> — находит элемент в неотсортированном списке
Локальный поиск (оптимизация)
Метод штрафов
Поиск в глубину — проходит граф ветка за веткой
Поиск в ширину — проходит граф уровень за уровнем
Поиск по первому наилучшему совпадению (англ. Шаблон:Lang-en2) — проходит граф в порядке важности, используя очередь приоритетов
Троичный поиск — находит максимум или минимум функции
Поиск в хеш-таблице
Алгоритм Ли (волновой алгоритм) — поиск пути на карте.

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

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

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

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

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

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

Индексы подстрок

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

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

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

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

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

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

Преобразование Барроуза — Уилера (также известен как англ. Шаблон:Lang-en2) — предварительная обработка данных для улучшения сжатия без потерь
Преобразование Шиндлера (англ. Шаблон:Lang-en2) — модификация преобразования Барроуза — Уилера
Алгоритм DEFLATE — популярный свободный алгоритм сжатия (используется в библиотеке zlib)
Дельта-кодирование — эффективно для сжатия данных с часто повторяющимися последовательностями
Инкрементное кодирование — дельта-кодирование, применяемое к последовательности строк
Семейство алгоритмов словарного сжатия Лемпеля — Зива:
- LZ77 — родоначальник семейства LZ77-алгоритмов
  - LZ77-PM
  - LZFG
    - LZFG-PM
  - LZP
  - LZBW
  - LZSS
    - LZB
    - LZH
    - LZRW1
- LZ78 — родоначальник семейства LZ78-алгоритмов
  - Алгоритм Лемпеля — Зива — Велча (также известен как англ. Шаблон:Lang-en2) — сжатие без потерь
    - LZW-PM
  - LZMW
- LZMA — сокращение от англ. Шаблон:Lang-en2
- LZO — алгоритм сжатия, ориентированный на скорость
Алгоритм сжатия PPM
Кодирование длин серий (Групповое кодирование, также известен как англ. Шаблон:Lang-en2) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
Шаблон:Не переведено — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
Шаблон:Не переведено (EZW-кодирование)
Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
- Алгоритм Шеннона — Фано — самый простой алгоритм кодирования
- Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
  - Адаптивное кодирование Хаффмана — техника адаптивного кодирования, основывающаяся на коде Хаффмана
- Шаблон:Не переведено — используется для однородного вероятностного распределения с конечным алфавитом
- Арифметическое кодирование — развитие энтропийного кодирования
  - Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании
- Шаблон:Не переведено — метод сжатия данных, который близок по эффективности к арифметическому кодированию
Энтропийное кодирование с известными характеристиками
- Унарное кодирование — код, который представляет число <math>n</math> в виде <math>n</math> единиц с замыкающим нулём
- дельта|гамма|омега-кодирование Элиаса (англ. Шаблон:Lang-en2) — универсальный код, кодирующий положительные целые числа
- Кодирование Фибоначчи — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
- Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
- Кодирование Райса — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

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

Шаблон:Не переведено — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
<math>A</math>-закон — стандартный алгоритм компандирования. Применяется в РФ.
Мю-закон — стандартный алгоритм компандирования
Фрактальное сжатие — метод, использующий фракталы для сжатия изображений
Шаблон:Не переведено — тип сжатия данных для «естественных» данных, таких как аудиосигналы или фотографические изображения
Векторное квантование — техника, часто используемая в сжатии данных с потерями
Вейвлетное сжатие — тип компрессии данных, хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)

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

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

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

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

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

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

Шаблон:Не переведено

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

Пересечения

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

Шаблон:Не переведено

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

Алгоритмы построения отрезка — алгоритмы для аппроксимации отрезка на дискретной графической поверхности
- Алгоритм Брезенхэма — растеризует отрезок линии с заданными координатами начала и конца
- Алгоритм DDA-линии — чертит точки двухмерного массива в форме прямой линии между двумя заданными точками (использует вычисления с плавающей точкой)
- Алгоритм Ву — алгоритм растеризации отрезка со сглаживанием
Алгоритм закраски с затравкой — заполняет соединённый регион многомерного массива указанным значением
Алгоритм художника — определяет видимые части трёхмерной сцены
Трассировка лучей — рендеринг реалистичных изображений

Модель освещения
- Затенение по Фонгу — модель освещения и метод интерполяции в трёхмерной компьютерной графике
- Затенение по Гуро — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
- Модель освещения Блинна — Фонга
- Модель освещения Кука — Торренса

Шаблон:Не переведено (англ. Шаблон:Lang-en2) — конструирует образ с помощью перемещения воображаемой линии над образом
Глобальное освещение — рассматривает прямое освещение и отражение от других объектов
Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
- Интерполяция сплайнами — уменьшение ошибки феномена Рунге

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

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

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

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

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

Асимметричное шифрование (с публичным ключом)

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

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

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

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

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

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

Криптостойкие генераторы псевдослучайных чисел
- Алгоритм Блюма — Блюма — Шуба — базируется на сложности факторизации
- Алгоритм Ярроу
- Алгоритм Fortuna — улучшение алгоритма Ярроу
- Генерация случайных простых чисел
- Алгоритм аутентификации сообщений Message authentication algorithm

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

CORDIC — быстрая техника вычисления тригонометрических функций.
Медианный фильтр для одномерного массива
Шаблон:Не переведено — уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
Osem — алгоритм для обработки медицинских изображений
Алгоритм Гёрцеля — может быть использован для декодирования цифр тональных сигналов
Шаблон:Не переведено — алгоритм увеличения резкости образа

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

Шаблон:Не переведено
Шаблон:Не переведено
Шаблон:Не переведено — Преобразование между системами адресации диска
Алгоритм вычисления контрольной суммы (CRC или FCS) Циклическая избыточная сумма (англ. Шаблон:Lang-en2), или контрольная последовательность кадра (англ. Шаблон:Lang-en2) — вычисление кода проверки.
Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.

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

Шаблон:Не переведено — Частичное упорядочение событий в зависимости от того, что случилось раньше
Шаблон:Не переведено — снимок процесса, записывающий глобальное состояние системы
Шаблон:Не переведено — Полное упорядочение событий
Алгоритм Марзулло — распределённая синхронизация часов
Шаблон:Не переведено — другой алгоритм синхронизации часов

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

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

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

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

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

Шаблон:Не переведено — дисковый алгоритм планирования, который работает как лифт
Шаблон:Не переведено — дисковый алгоритм планирования для уменьшения времени поиска

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

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

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

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

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

Шаблон:Не переведено — также известен как выбор рулеточного колеса

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

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

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

Алгоритм Тодда — Коксетера — перечисление смежных классов подгруппы
Алгоритм Шрайера — Симса — эффективное представление конечно-порождённой подгруппы

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

Шаблон:Не переведено — находит базис Грёбнера
Процесс Грама ― Шмидта — ортогонализация набора векторов
Шаблон:Не переведено
Шаблон:Не переведено — для многочленов в некоторых неопределённостях
Алгоритмы умножения матриц
- Алгоритм Штрассена — быстрое умножение матриц
- Алгоритм Копперсмита — Винограда
Шаблон:Не переведено (англ. Шаблон:Lang-en2)
Алгоритм Катхилл — Макки — алгоритм уменьшения ширины ленты разреженных симметричных матриц
Алгоритмы вычисления дискретного преобразования Фурье
Алгоритм нахождения собственного значения матрицы
Преобразования Хаусхолдера (<math>QR</math>-разложение) — вычисление обратной матрицы, собственных векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
Решение систем линейных уравнений
- Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений
- Структурированное гауссово исключение — применяется, когда матрица системы является разреженной
- Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления
- Разложение Холецкого — метод, эффективный для ленточных и разреженных матриц
- Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам

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

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

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

Шаблон:Main Шаблон:Seealso

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

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

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

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

Рекурсивный нисходящий парсер — нисходящий парсер, подходящий для <math>LL(k)</math>-грамматик
LL-парсер — относительно простой алгоритм разбора за линейное время для ограниченного класса контекстно-свободных грамматик
LR-парсер — более сложный алгоритм разбора за линейное время для большего класса контекстно-свободных грамматик. Варианты:
Шаблон:Не переведено — алгоритм разбора за линейное время, поддерживающий некоторые контекстно-свободные грамматики и грамматики разбора выражений
Алгоритм Коука — Янгера — Касами (алгоритм CYK) — <math>O(n^3)</math>-алгоритм для разбора любой контекстно-свободной грамматики
Алгоритм Эрли — другой <math>O(n^3)</math>-алгоритм для разбора любой контекстно-свободной грамматики
<math>GLR</math>-парсер — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и <math>O(n^3)</math> в худшем случае.
Метод рекурсивного спуска — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной грамматикой
Алгоритм Рутисхаузера — работает в предположении о полной скобочной структуре выражения
Алгоритм сортировочной станции

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

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

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

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

Шаблон:Не переведено — алгоритм для преобразования недетерминированного автомата в детерминированный
Алгоритм Тодда — Коксетера — процедура для создания сомножеств

Другие

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

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