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

{{Координационный список}}
{{main|Алгоритм}}
Ниже приводится '''список алгоритмов''', группированный по категориям. Более детальные сведения приводятся в списке структур данных и [[Проект:Математика/Списки/Список основных разделов теории алгоритмов|списке основных разделов теории алгоритмов]]<ref>В тематическом проекте есть также [[Проект:Математика/Списки/Список терминов, относящихся к алгоритмам и структурам данных|список терминов, относящихся к алгоритмам и структурам данных]], составленный на основе словаря [[Американский национальный институт стандартов|Американского национального института стандартов]]. Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание. Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «{{Не переведено|Википедия:Алгоритмы в Википедии||en|Wikipedia:Algorithms on Wikipedia}}» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.</ref>

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

=== Общие [[комбинаторика|комбинаторные]] алгоритмы ===
* [[Задача нахождения цикла#Черепаха и заяц|Алгоритм Флойда для нахождения циклов]] находит цикл в итерациях
* [[Генератор псевдослучайных чисел|Генераторы псевдослучайных чисел]]:
** [[Алгоритм Блюм — Блюма — Шуба]]
** [[Вихрь Мерсенна]]
** [[Метод Фибоначчи с запаздываниями]]
** [[Линейный конгруэнтный метод]]
** [[Инверсный конгруэнтный метод]]
==== Генерация комбинаторных объектов ====
* [[Алгоритм Робинсона — Шенстеда]] — генерация перестановок из пар [[Диаграмма Юнга|таблиц Юнга]]
* [[Алгоритм Нарайаны]]
* [[Алгоритм Джонсона — Троттера]]

=== [[Теория графов|Алгоритмы на графах]] ===
* [[Алгоритм Беллмана — Форда]] — вычисляет [[проблема кратчайшего пути|кратчайший путь]] во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
* [[Алгоритм Борувки]] — находит минимальное остовное дерево в графе
* [[Алгоритм Брона — Кербоша]] — нахождение наибольших максимальных независимых по включению множеств вершин графа.
* [[Алгоритм Флойда — Уоршелла]] — вычисляет [[проблема всех кратчайших путей|все кратчайшие пути]] во взвешенном графе
* [[Алгоритм Дейкстры]] — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
* [[Алгоритм Левита]] — находит кратчайшее расстояние от одной из вершин графа до всех остальных
* [[Алгоритм Джонсона]] — вычисляет [[проблема всех кратчайших путей|все кратчайшие пути]] во взвешенном графе
* [[Алгоритм Краскала]] — находит [[остовный лес]] минимального веса в графе
* {{Не переведено|Алгоритм, основанный на источнике||en|Spring based algorithm}} — алгоритм для [[Визуализация графов|рисования графа]]
* [[Алгоритм Прима]] — находит [[остовное дерево]] минимального веса в связном графе
* [[Алгоритм Кристофидеса]] — эвристический приближенный алгоритм для решения [[МЗК|метрической задачи коммивояжера]] на графе.
* [[Алгоритм ближайшего соседа в задаче коммивояжёра|Метод ближайшего соседа]] —  «жадный» алгоритм, один из простейших эвристических методов решения [[задача коммивояжёра|задачи коммивояжёра]]
* [[Неблокирующий минимальный охватывающий переключатель]] например, для [[телефон|телефонной связи]]
* Построение транзитивного замыкания графа (установление факта достижимости вершин)

==== Алгоритмы нахождения [[максимальный поток|максимального потока]] ====
<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*]] — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
* [[BFPRT-Алгоритм|Алгоритм выбора]] — модификация алгоритма [[Линейный поиск|линейного поиска]]; находит <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-en|Best-first search}}) — проходит граф в порядке важности, используя [[очередь приоритетов]]
* [[Троичный поиск]] — находит максимум или минимум функции
* [[Хеш-таблица|Поиск в хеш-таблице]]
* [[Алгоритм Ли]] (волновой алгоритм) — поиск пути на карте.

=== [[Алгоритм на строках|Алгоритмы на строках]] ===

====[[Поиск подстроки|Алгоритмы поиска строки]]====
* [[Префикс-функция]]
* [[Z-функция|<math>Z</math>-функция]]
* [[Алгоритм Кнута — Морриса — Пратта]]
* [[Алгоритм Рабина — Карпа]] поиска строки
* [[Алгоритм Бойера — Мура]] поиска строки
** [[Алгоритм Бойера — Мура — Хорспула]]
** [[Первый алгоритм Бойера — Мура — Санди]]
** [[Второй алгоритм Бойера — Мура — Санди]]
** [[Алгоритм Бойера — Мура — Гелила]]
** [[Алгоритм Турбо-БМ]]
* [[Алгоритм Ахо — Корасик]]
* [[Двоичный алгоритм поиска подстроки|Алгоритм Битапа]] (также известен как shift-or, shift-and)
* [[Наибольшая общая подпоследовательность|Задача поиска наибольшей общей подпоследовательности]]
* [[Задача поиска наибольшей увеличивающейся подпоследовательности]]
* {{Не переведено|Задача поиска наикратчайшей общей надпоследовательности||en|Shortest common supersequence problem}}
* [[Наибольшая общая подстрока|Задача поиска наибольшей общей подстроки]]
* [[Количество подпалиндромов|Задача поиска количества подпалиндромов]]

==== [[Алгоритмы вычисления расстояния между строками]] ====
* [[Алгоритм Вагнера — Фишера]]
* [[Алгоритм Хешберга]]
* [[Алгоритм Ханта — Шиманского]]
* [[Алгоритм Укконена — Майерса]]

==== [[Алгоритмы приближенного сравнения строк с шаблоном]] ====
* [[Алгоритм Укконена]]
* [[Алгоритм Майерса]]
* [[Алгоритм Ву — Менбера]]

==== [[Характеристический паттерн|Вычисление характеристических паттернов]] ====
* [[Алгоритм Крочемора поиска всех кратных строк]]
* [[Алгоритм Мейна — Лоренца поиска всех кратных строк]]
* [[Алгоритм Мейна поиска крайних левых серий]]
* [[Алгоритм Колпакова — Кучерова поиска всех серий]]
* [[Алгоритм Ли — Смита поиска всех оболочек]]
* [[Алгоритм Франека — Смита — Танга поиска всех раппортов]]
* [[Алгоритм Шмидта поиска k-приближенных раппортов|Алгоритм Шмидта поиска <math>k</math>-приближенных раппортов]]
* [[Алгоритмы Сима — Илиопулоса — Парка — Смита поиска k-приближенных периодов|Алгоритмы Сима — Илиопулоса — Парка — Смита поиска <math>k</math>-приближенных периодов]]

==== [[Примерное соответствие]] ====
* [[Расстояние Левенштейна]]
* [[Расстояние Хэмминга]]
* [[Расстояние Дамерау — Левенштейна]]
* [[Алгоритм Нидлмана — Вунша]]
* {{Не переведено|Алгоритм Смита — Вотермана||en|Smith-Waterman algorithm}}
* [[Soundex]]
* [[Metaphone]]

====[[Индекс подстрок|Индексы подстрок]]====
*[[Суффиксный автомат]]
*[[Суффиксное дерево]]
* [[Алгоритм Мак-Крейта]]
* [[Алгоритм Укконена]]
* [[Алгоритм Вайнера]]
* [[Алгоритм Фрача]]
* [[Суффиксный массив]]

=== [[Алгоритм сортировки|Алгоритмы сортировки]] ===
* [[Bogosort]]
* [[Stooge sort]]
* [[Timsort]] —  гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием 
* [[Наивная сортировка]] — генерация всех <math>n!</math> возможных перестановок и проверка на отсортированность
* [[Блинная сортировка]]
* [[Блочная сортировка]] (также известен как ''корзинная сортировка''), ср. с поразрядной
* [[Быстрая сортировка]] — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
* [[Гномья сортировка]] — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — <math>O(n^2)</math>.
* [[Пирамидальная сортировка]] (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
* [[Плавная сортировка]]
* [[Поразрядная сортировка]] — сортирует строки буква за буквой.
* [[Сортировка Бентли — Седжвика]] ({{lang-en|BeSe sort}}) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
* [[Сортировка с помощью двоичного дерева]] ({{lang-en|Tree sort}})
* [[Сортировка методом вставок]] — определяем, где текущий элемент должен находиться в отсортированном списке, и вставляем его туда
* [[Сортировка методом выбора]] — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
* [[Сортировка перемешиванием]] (Сортировка коктейлем)
* [[Сортировка подсчётом]] — используется диапазон входных данных, подсчитывается число одинаковых элементов (3 варианта)
* [[Сортировка пузырьком]]
* [[Сортировка расчёской]]
* [[Сортировка слиянием]] — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
* [[Сортировка Шелла]] — попытка улучшить сортировку вставками
* [[Топологическая сортировка]]
* [[Хитрая сортировка]] — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
* [[Поразрядная сортировка|Цифровая сортировка]] — то же, что и [[Поразрядная сортировка]].

=== [[Алгоритм слияния|Алгоритмы слияния]] ===
* [[Простой алгоритм слияния]] ({{lang-en| Simple Merge algorithm }})
* [[k-мерный алгоритм слияния|<math>k</math>-мерный алгоритм слияния]] ({{lang-en| k-way Merge algorithm }})

=== Минимизация [[Булева функция|булевых функций]] ===
* [[Минимизация логических функций методом Куайна|Алгоритм Квайна]]
* [[Метод Куайна — Мак-Класки|Алгоритм Мак-Класки]]
* [[Карты Карно]]
* [[Алгоритм Свободы]]
* [[Алгоритм Хва]]
* [[Получение простых импликант на основе разбиения по кодам разности]]
* [[Метод поразрядного выращивания]]
* [[Метод Блейка]]

== [[Сжатие данных|Алгоритмы сжатия данных]] ==

=== [[:Категория:Алгоритмы сжатия без потерь|Алгоритмы сжатия без потерь]] ===
* [[Преобразование Барроуза — Уилера]] (также известен как {{lang-en|BWT}}) — предварительная обработка данных для улучшения сжатия без потерь
* [[Преобразование Шиндлера]] ({{lang-en| ST}}) — модификация преобразования Барроуза — Уилера
* Алгоритм [[DEFLATE]] — популярный свободный алгоритм сжатия (используется в библиотеке zlib)
* [[Дельта-кодирование]] — эффективно для сжатия данных с часто повторяющимися последовательностями
* [[Инкрементное кодирование]] — дельта-кодирование, применяемое к последовательности строк
* Семейство алгоритмов словарного сжатия Лемпеля — Зива:
** [[LZ77]] — родоначальник семейства LZ77-алгоритмов
*** [[LZ77-PM]]
*** [[LZFG]]
**** [[LZFG-PM]]
*** [[LZP]]
*** [[LZBW]]
*** [[LZSS]]
**** [[LZB]]
**** [[LZH]]
**** [[LZRW1]]
** [[LZ78]] — родоначальник семейства LZ78-алгоритмов
*** [[Алгоритм Лемпеля — Зива — Велча]] (также известен как {{lang-en|LZW}}) — сжатие без потерь
**** [[LZW-PM]]
*** [[LZMW]]
** [[LZMA]] — сокращение от {{lang-en|Lempel-Ziv-Markov chain-Algorithm}}
** [[LZO]] — алгоритм сжатия, ориентированный на скорость
* [[Алгоритм сжатия PPM]]
* [[Кодирование длин серий]] (Групповое кодирование, также известен как {{lang-en|RLE}}) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
* {{Не переведено|Алгоритм SEQUITUR||en|SEQUITUR algorithm}} — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
* {{Не переведено|Вейвлет-кодирование на основе вложенных нуль-деревьев||en|Embedded Zerotree Wavelet}} (EZW-кодирование)
* [[Энтропийное кодирование]] — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
** [[Алгоритм Шеннона — Фано]] — самый простой алгоритм кодирования
** [[Алгоритм Хаффмана]] — алгоритм построения кода при помощи кодовых деревьев
*** {{Не переведено|Адаптивное кодирование Хаффмана||en|Adaptive Huffman coding}} — техника адаптивного кодирования, основывающаяся на коде Хаффмана
** {{Не переведено|Усечённое двоичное кодирование||en|Truncated binary encoding}} — используется для однородного вероятностного распределения с конечным алфавитом
** [[Арифметическое кодирование]] — развитие энтропийного кодирования
*** [[Адаптивное арифметическое кодирование]] — техника адаптивного кодирования, основывающаяся на арифметическом кодировании
** {{Не переведено|Кодирование расстояний||en|Range encoding}} — метод сжатия данных, который близок по эффективности к арифметическому кодированию
* [[Энтропийное кодирование|Энтропийное кодирование с известными характеристиками]]
** [[Унарное кодирование]] — код, который представляет число <math>n</math> в виде <math>n</math> единиц с замыкающим нулём
** [[Дельта-код Элиаса|дельта]]|[[Гамма-код Элиаса|гамма]]|[[Омега-код Элиаса|омега]]-кодирование Элиаса ({{lang-en|Elias coding}}) — универсальный код, кодирующий положительные целые числа
** [[Кодирование Фибоначчи]] — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
** [[Кодирование Голомба]] — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
** [[Кодирование Райса]] — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

=== [[:Категория:Алгоритмы сжатия с потерями|Алгоритмы сжатия с потерями]] ===
* {{Не переведено|Линейное предсказывающее кодирование||en|Linear predictive coding}} — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
* [[А-закон|<math>A</math>-закон]] — стандартный алгоритм компандирования. Применяется в РФ.
* [[Мю-закон]] — стандартный алгоритм компандирования
* [[Фрактальное сжатие]] — метод, использующий фракталы для сжатия изображений
* {{Не переведено|Трансформирующее кодирование||en|Transform coding}} — тип сжатия данных для «естественных» данных, таких как аудиосигналы или фотографические изображения
* [[Векторное квантование]] — техника, часто используемая в сжатии данных с потерями
* [[Вейвлетное сжатие]] — тип компрессии данных, хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)

== [[Вычислительная геометрия]] ==
* [[Алгоритм Гилберта — Джонсона — Кёрти]] — определение наименьшего расстояния между двумя [[Выпуклое множество|выпуклыми множествами]]
* {{Не переведено|Поиск пары ближайших точек||en|Closest pair of points problem}} — трудоёмкость <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> — количество точек в выпуклой оболочке.
* {{Не переведено|Алгоритм Киркпатрика — Зайделя||en|Kirkpatrick–Seidel_algorithm}} — трудоёмкость <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(n^2)</math>.
* [[Алгоритмы построения триангуляции Делоне слиянием]] — трудоёмкость <math>O(n^2)</math> и <math>O(n\log n)</math>.
* [[Алгоритмы прямого построения триангуляции Делоне]] — трудоёмкость <math>O(n^2)</math>.
* [[Двухпроходные алгоритмы построения триангуляции Делоне]] — трудоёмкость <math>O(n^2)</math> и <math>O(n\log n)</math>.
* [[Триангуляция Делоне с ограничениями]] — трудоёмкость <math>O(n^2)</math>.

=== [[Квазитриангуляция]] ===
* [[Алгоритм построения квазитриангуляции]]

=== [[Диаграмма Вороного]] ===
* [[Простой алгоритм построения диаграммы Вороного]] — трудоёмкость <math>O(n^2\log n)</math>.
* [[Алгоритм построения диаграммы Вороного через заметающую прямую]] — трудоёмкость <math>O(n\log n)</math>.
* [[Рекурсивный алгоритм построения диаграммы Вороного]] — трудоёмкость <math>O(n\log n)</math>.

=== {{Не переведено|Локализация точки||en|Point location}} ===
* [[Локализация точки для выпуклого многоугольника]] — время запроса <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>.
* {{Не переведено|Определение наличия пересекающихся отрезков||en|Line segment intersection}} (алгоритм Шеймоса — Гоя) — трудоёмкость <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>.
* [[Алгоритм Лианга — Барски]]
* {{Не переведено|Быстрое отсечение||en|Fast-clipping}}
* [[Алгоритм Кируса — Бека]]
* {{Не переведено|Николла — Ли — Николла||en|Nicholl–Lee–Nicholl}}
* {{не переведено|Алгоритм Сазерленда — Ходжмана||en|Sutherland–Hodgman algorithm}}
* [[Алгоритм Уайлера — Атертона]]

=== {{Не переведено|Вращающиеся калиперы||en|Rotating calipers}} ===
* [[Поиск диаметра множества точек через вращающиеся калиперы]]
* {{Не переведено|Поиск минимального по площади описанного прямоугольника для множества точек||en|Minimum bounding box algorithms}}
* {{Не переведено|Поиск минимального по периметру описанного прямоугольника для множества точек||en|Minimum bounding box algorithms}}
* [[Определение ширины многоугольника]]
* [[Построение суммы Минковского двух выпуклых многоугольников]]
* [[Поиск максимального расстояния между двумя множествами точек]]
* [[Поиск минимального расстояния между двумя выпуклыми многоугольниками]]
* [[Построение мостов для двух выпуклых многоугольников]]
* [[Построение критических опорных прямых для выпуклых многоугольников]]

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

* {{Не переведено|Модель освещения||en|Shading}}
** [[Затенение по Фонгу]] — модель освещения и метод интерполяции в трёхмерной компьютерной графике
** [[Затенение по Гуро]] — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
** [[Модель освещения Блинна — Фонга]]
** [[Модель освещения Кука — Торренса]]

* {{Не переведено|Алгоритм сканирующей строки||en|Scanline rendering}} ({{lang-en|Scanline rendering}}) — конструирует образ с помощью перемещения воображаемой линии над образом
* [[Глобальное освещение]] — рассматривает прямое освещение и отражение от других объектов
* Алгоритмы [[Интерполяция|интерполяции]] — конструирование новых точек данных, таких как в [[Цифровой увеличитель|цифровом увеличителе]]
** {{Не переведено|Интерполяция сплайнами||en|Spline interpolation}} — уменьшение ошибки [[Феномен Рунге|феномена Рунге]]

== [[Компьютерное зрение]] ==
* {{Не переведено|Epitome||en|Epitome}} — представление образа или видео при помощи меньшего образа или видео

== [[Криптография|Криптографические]] алгоритмы ==
: ''См. также [[Разделы в криптографии]] для '''аналитического глоссария''' ''

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

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

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

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

* Алгоритмы [[разделение секрета|разделения секрета]]
** [[Рюкзак (криптография)|Рюкзак]] — на данный момент доказана нестойкость схемы
** [[Схема Шамира]]
** [[Схема Blakey]]

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

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

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

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

== [[Цифровая обработка сигналов]] ==
* [[CORDIC]] — быстрая техника вычисления [[Тригонометрическая функция|тригонометрических функций]].
* [[Медианный фильтр]] для одномерного массива
* {{Не переведено|Дождевой алгоритм||en|Rainflow-counting algorithm}} — уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе [[усталость (материал)|усталости]]
* [[Osem]] — алгоритм для обработки медицинских изображений
* [[Алгоритм Гёрцеля]] — может быть использован для декодирования цифр [[тональный сигнал|тональных сигналов]]
* {{Не переведено|Развеяние Ричардсона — Люси||en|Richardson-Lucy deconvolution}} — алгоритм увеличения резкости образа

== [[Разработка программного обеспечения]] ==
* {{Не переведено|Алгоритмы для восстановления и изоляции повреждённых семантик||en|Algorithms for Recovery and Isolation Exploiting Semantics}}
* {{Не переведено|Алгоритм сравнения Unicode||en|Unicode Collation Algorithm}}
* {{Не переведено|Алгоритм преобразования CHS||en|CHS conversion}} — Преобразование между системами адресации диска
* [[Циклический избыточный код|Алгоритм вычисления контрольной суммы]] (CRC или FCS) Циклическая избыточная сумма ({{lang-en|Cyclic Redunancy Check}}), или контрольная последовательность кадра ({{lang-en|Frame Check Sequence}}) — вычисление кода проверки.
* [[Чётность битов|Чётность]] — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
* [[Алгоритм соединения (СУБД)]] — реализация операции соединения реляционной алгебры.

=== [[Распределённые вычисления|Алгоритмы распределённых систем]] ===
* {{Не переведено|Упорядочение Лампорта||en|Lamport ordering}} — [[Частичное упорядочение]] событий в зависимости от ''того, что случилось раньше''
* {{Не переведено|Алгоритм мгновенного снимка||en|Snapshot algorithm}} — снимок процесса, записывающий глобальное состояние системы
* {{Не переведено|Векторное упорядочение||en|vector clocks}} — [[Полное упорядочение]] событий
* [[Алгоритм Марзулло]] — распределённая синхронизация часов
* {{Не переведено|Алгоритм пересечений||en|intersection algorithm}} — другой алгоритм синхронизации часов

=== Алгоритмы выделения и освобождения памяти ===
* {{Не переведено|Сборщик мусора Боема||en|Boehm garbage collector}} — «скромный» сборщик мусора
* {{Не переведено|Дружеское выделение памяти||en|Buddy memory allocation}} — алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
* [[Сборка мусора (программирование)|Сборщик мусора с поколениями]] — быстрые сборщики мусора, которые разделяют память по возрасту
* {{Не переведено|Пометить и вымести||en|Mark and sweep}} <!-- в en-wiki редирект на Garbage collection (computer science)#Mark and sweep -->
* [[Подсчёт ссылок]]

=== Алгоритмы в [[Операционная система|операционных системах]] ===
* {{Не переведено|Алгоритм банкира||en|Banker's algorithm}} — Алгоритм, использующийся для избежания [[Взаимная блокировка|взаимных блокировок]]
* {{Не переведено|Алгоритм замены страницы||en|Page replacement algorithms}} — выбор страницы-жертвы при условиях небольшого объёма памяти
* {{Не переведено|Адаптивный алгоритм замещения кэша||en|Adaptive replacement cache}}: скорость выполнения лучше, чем у LRU
* {{Не переведено|Часы с адаптивной заменой||en|Clock with Adaptive Replacement}} (CAR): алгоритм замены страниц со скоростью выполнения, сравнимой с [[Адаптивный алгоритм замещения кэша|адаптивным алгоритмом замещения кэша]]
* [[Алгоритм забияки]] — выбор нового лидера среди множества компьютеров
* [[rsync]] — алгоритм, использующийся для эффективной передачи файлов между двумя компьютерами

=== Дисковые алгоритмы-планировщики ===
* {{Не переведено|Алгоритм лифта||en|Elevator algorithm}} — дисковый алгоритм планирования, который работает как лифт
* {{Не переведено|Алгоритм кратчайшего перемещения||en|Shortest seek first}} — дисковый алгоритм планирования для уменьшения времени поиска

=== Сетевые алгоритмы ===
* [[Алгоритм Карна]]: получение точных оценок времени распространения пакетов сообщений при использовании TCP/IP
* {{Не переведено|Алгоритм Лулео||en|Luleå algorithm}}: техника эффективного сохранения и поиска в таблицах роутинга
* {{Не переведено|Нагрузка на сеть||en|Network congestion}}
** {{Не переведено|Экспоненциальная задержка||en|Exponential backoff}}
** {{Не переведено|Алгоритм Нагла||en|Nagle's algorithm}}: улучшение эффективности TCP/IP за счёт объединения пакетов
** {{Не переведено|Усечённая бинарная экспоненциальная задержка||en|Truncated binary exponential backoff}}
* [[Шейпинг (информатика)|Шейпинг]]
** [[Алгоритм текущего ведра]]
** {{Не переведено|Алгоритм ведра маркеров||en|Token bucket}}

=== Алгоритмы синхронизации процессов ===
* [[Алгоритм Петерсона]]
* [[Алгоритм пекарни Лампорта]]
* [[Алгоритм Деккера]]

=== [[Планирование|Алгоритмы планирования]] ===
* {{Не переведено|Планирование с постоянной скоростью||en|Rate-monotonic scheduling}}
* {{Не переведено|Первый заканчивает раньше (планирование)||en|Earliest deadline first scheduling}}
* {{Не переведено|Честное разделение (планирование)||en|Fair-share scheduling}}
* [[Round-robin (алгоритм)|Планирование Round-robin]]
* {{Не переведено|Многоуровневая отдача (планирование)||en|Multi level feedback queue}} ({{lang-en|Multi level feedback queue}})
* {{Не переведено|Кратчайшее оставшееся время (планирование)||en|Shortest remaining time}}
* {{Не переведено|Наименьшее время бездействия (планирование)||en|Least slack time scheduling}}
* {{Не переведено|Списковое планирование||en|List scheduling}} ({{lang-en|List scheduling}})
* {{Не переведено|Алгоритм высоких вершин||en|Top-nodes algorithm}}
* [[Кратчайшая работа следующей]]
* {{Не переведено|Кратчайшее оставшееся время||en|Shortest remaining time}}

== [[Генетические алгоритмы]] ==
* {{Не переведено|Выбор пропорционально пригодности||en|Fitness proportionate selection}} — также известен как '''выбор рулеточного колеса'''

== Медицинские алгоритмы ==
* [[Медицинский алгоритм]]
* {{Не переведено|Техасский проект медицинских алгоритмов||en|Texas Medication Algorithm Project}}

== [[Искусственная нейронная сеть|Нейронные сети]] ==
* [[Метод обратного распространения ошибки]]
* [[Самоорганизующееся отображение]] (Карты Кохонена, SOM)
* [[Метод коррекции ошибки]]
* [[Метод коррекции с обратной передачей сигнала ошибки]]

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

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

== [[Вычислительная алгебра]] ==
* {{Не переведено|Алгоритм Бухбергера||en|Buchberger's algorithm}} — находит [[базис Грёбнера]]
* [[Процесс Грама ― Шмидта]] — ортогонализация набора векторов
* {{Не переведено|Алгоритм пополнения Кнута — Бендикса||en|Knuth-Bendix completion algorithm}}
* {{Не переведено|Алгоритм мультивариационного деления||en|Multivariate division algorithm}} — для [[многочлен]]ов в некоторых неопределённостях
* Алгоритмы умножения матриц
** [[Алгоритм Штрассена]] — быстрое умножение матриц
** [[Алгоритм Копперсмита — Винограда]]
* {{Не переведено|Умножение цепных матриц||en|Chain matrix multiplication}} ({{lang-en|Chain matrix multiplication}})
* [[Алгоритм Катхилл — Макки]] — алгоритм уменьшения ширины ленты разреженных симметричных матриц
* Алгоритмы вычисления [[Дискретное преобразование Фурье|дискретного преобразования Фурье]]
** [[Быстрое преобразование Фурье]]
** [[Алгоритм Кули — Тьюки]]
** {{Не переведено|Алгоритм БПФ Рэдера||en|Rader's FFT algorithm}}
** [[Алгоритм Блуштайна]]
** {{Не переведено|Алгоритм БПФ Брууна||en|Bruun's FFT algorithm}}
** [[Алгоритм Гуда — Томаса]]
* {{Не переведено|Алгоритм нахождения собственного значения матрицы||en|Eigenvalue algorithm}}
* [[Преобразование Хаусхолдера|Преобразования Хаусхолдера]] ([[QR-разложение|<math>QR</math>-разложение]]) — вычисление обратной матрицы, собственных векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
* Решение систем линейных уравнений
** [[Метод Гаусса]] (Гауссово исключение) — стандартный метод решения систем линейных уравнений
** [[Структурированное гауссово исключение]] — применяется, когда матрица системы является разреженной
** [[Метод Жордана — Гаусса]] — модификация метода Гаусса для матричного представления
** [[Разложение Холецкого]] — метод, эффективный для ленточных и разреженных матриц
** [[Метод Пранис — Праневича]] — решение систем линейных уравнений с параллельными вычислениями по компонентам

== [[:Категория:Теоретико-числовые алгоритмы|Теоретико-числовые алгоритмы]] ==
* Целочисленная арифметика (алгоритмы для работы с большими числами)
** [[Умножение столбиком больших чисел]]
** «[[Быстрый столбик]]»
** [[Умножение Карацубы]] — алгоритм быстрого умножения чисел
** {{Не переведено|Алгоритм Тоома — Кука||en|Toom–Cook multiplication}} — обобщённый алгоритм умножения Карацубы (известен также как Toom-3)
** [[Метод умножения Шёнхаге — Штрассена]] — более быстрый алгоритм умножения
** [[Алгоритм Фюрера]] — на данный момент самый быстрый алгоритм умножения больших чисел
** [[Деление на одноразрядное число]] (DO)
** {{Не переведено|Деление больших чисел||en|Division algorithm}}
* [[Быстрое возведение в степень]] — вычисляет степени чисел при помощи возведения в квадрат
* Алгоритмы [[сравнение по модулю|модулярной]] арифметики
**[[Алгоритм Монтгомери]] — модулярное умножение и возведение в степень
** [[Алгоритм нахождения порядка элемента]]
** [[Алгоритм Тонелли — Шенкса]] — решение [[квадратичные сравнения|квадратичных сравнений]]
**[[Метод Берлекэмпа]] — вероятностный алгоритм для нахождения корней многочленов над конечным полем
**[[Алгоритм Берлекэмпа]] — факторизация многочленов над конечным полем
**[[Алгоритм Берлекэмпа — Мэсси]] — поиск линейного рекуррентного соотношения наименьшего порядка, которому удовлетворяет последовательность
** Решение [[системы линейных сравнений|систем линейных сравнений]]
*** С помощью [[китайская теорема об остатках|китайской теоремы об остатках]]
*** [[Алгоритм Гарнера]]
* Решение систем линейных уравнений над [[Поле (алгебра)|полем]]
** [[Алгоритм Ланцоша]] — эффективен над полем характеристики 2
** [[Алгоритм Видемана]]
* [[Дискретное логарифмирование]]:
** В простом конечном поле
*** [[Алгоритм Шенкса]] (алгоритм больших и маленьких шагов, {{lang-en| baby-step giant-step}})
*** [[Алгоритм Полига — Хеллмана]] — эффективен, если все делители <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>-метода
**** [[Алгоритм Ленстры (тест простоты)|Алгоритм Ленстры]] — использует [[сумма Якоби|суммы Якоби]] и некоторые тесты, обобщающие малую теорему Ферма
**** [[Тест Люка — Лемера]] для [[число Мерсенна|чисел Мерсенна]]
**** [[Тест Пепина]] для [[число Ферма|чисел Ферма]]
**** [[Тест Агравала — Каяла — Саксены]] — полиномиальный [[Детерминированный алгоритм|детерминированный]] тест простоты
*** Вероятностные тесты простоты:
**** [[Тест Соловея — Штрассена]] — опирается на [[малая теорема Ферма|малую теорему Ферма]] и свойства [[символ Лежандра|символа Лежандра]]
**** [[Тест Миллера — Рабина]] — эффективная модификация теста Соловея — Штрассена
** [[Факторизация]] — разложение числа на простые множители:
*** Алгоритмы с экспоненциальной сложностью:
**** [[Перебор делителей]]
**** [[Метод факторизации Ферма]]
**** [[(p-1)-алгоритм Полларда|<math>(p-1)</math>-алгоритм Полларда]]
**** [[ρ-алгоритм Полларда|ρ-метод Полларда]]
**** [[Метод Лемана]]
**** [[Алгоритм Ленстры (разложение на множители)|Алгоритм Ленстры]]
*** Алгоритмы с субэкспоненциальной сложностью:
**** [[Алгоритм Диксона]]
**** [[Метод квадратичного решета]] ({{lang-en|QS}})
**** [[Специальный метод решета числового поля]] ({{lang-en|SNFS}})
**** [[Общий метод решета числового поля]] ({{lang-en|GNFS}})
**** [[Факторизация с помощью эллиптических кривых]] — вероятностный алгоритм факторизации с помощью [[эллиптическая кривая|эллиптических кривых]]
* [[Дробь (математика)|Дроби]]
** [[Жадный алгоритм для египетских дробей]] — преобразует рациональные числа в египетские дроби
* Прочие
** [[Алгоритм Шуфа]] — вычисление порядка группы точек эллиптической кривой
** [[Алгоритм Ленстры — Ленстры — Ловаса]] (LLL-алгоритм, L³-алгоритм)

== Численные алгоритмы ==
{{main|Численный анализ}}
{{seealso|Список разделов численного анализа}}

* [[Алгоритм де Кастельжо]] — вычисление [[Кривая Безье|кривых Безье]]
* Методы интерполяции
** [[Линейное сглаживание по трём точкам]]
** [[Линейное сглаживание по пяти точкам]]
** [[Нелинейное сглаживание по семи точкам]]
* Приближенное вычисление решений
** {{Не переведено|Метод фальшпозиции||en|False position method}} (''False position method, regula falsi method'') — аппроксимирует корни функции
** [[Метод бисекции]] — нахождение нуля (корня) нелинейной функции
** [[Метод Ньютона]] (метод касательных) — нахождение нулей функций с помощью производной
** [[Метод секущих]] (метод хорд) — аппроксимирует корни функции
** Метод градиентов ([[градиентный спуск]]) — аппроксимирует решение системы уравнений
** [[Метод сопряжённого градиента]]
** [[Алгоритм Гаусса — Ньютона]] — алгоритм для решения нелинейных уравнений [[метод наименьших квадратов|методом наименьших квадратов]]
** [[Алгоритм Левенберга — Марквардта]] — алгоритм для решения нелинейных уравнений [[метод наименьших квадратов|методом наименьших квадратов]]
* {{Не переведено|Танцующие звенья||en|Dancing Links}} — нахождение всех решений задачи точного покрытия
* {{Не переведено|Алгоритм де Бора||en|De Boor algorithm}} — вычисление [[Сплайн (математика)|сплайнов]]
* {{Не переведено|Алгоритм Гаусса — Лежандра||en|Gauss-Legendre algorithm}} — вычисление цифр числа [[pi|пи]]
* [[Алгоритм Кэхэна]] — более аккуратный метод суммирования чисел с плавающей точкой
* {{Не переведено|Алгоритм MISER||en|MISER algorithm}} — моделирование [[метод Монте-Карло|методом Монте-Карло]], [[численное интегрирование]]
* {{Не переведено|Функции округления||en|Rounding functions}} — классические способы округления чисел
* {{Не переведено|Сдвигающий алгоритм корня n-ой степени||en|Shifting nth-root algorithm}} — извлечение корня цифра за цифрой
* Вычисление [[Квадратный корень|квадратного корня]]:
** [[Итерационная формула Герона|Алгоритм Герона]]
** [[Алгоритм вычисления квадратного корня|школьный (ручной) алгоритм]] — аппроксимирует квадратный корень числа
* [[Алгоритм нахождения корня n-ной степени|Вычисление корня <math>n</math>-ной степени]]

== [[Оптимизация (математика)|Алгоритмы оптимизации]] ==
* [[Линейное программирование]]
* [[Симплекс-метод]]
* «[[Венгерский метод]]» — решение задач целочисленного линейного программирования
* [[Метод Мака]] решения [[Задача о назначениях|задачи о назначениях]]
* [[Алгоритм имитации отжига]]
* [[Метод роя частиц]]
* [[Муравьиные алгоритмы]]
* [[Метод ветвей и границ]]
* [[Дифференциальная эволюция]]
* [[Эволюционная стратегия]]
* [[Метод Нелдера — Мида]] (downhill simplex method) — алгоритм [[нелинейная оптимизация|нелинейной оптимизации]]
* {{Не переведено|Всхождение со случайным перезапуском||en|Random-restart hill climbing}}
* {{Не переведено|Стохастическое туннелирование||en|Stochastic tunneling}}
* [[Задача о сумме подмножеств]]
* [[Метод перебора]]
* [[Метод Фибоначчи поиска экстремума]] — метод выбора точек для нахождения экстремума функции одной переменной
* [[Градиентный спуск]]
* [[Алгоритм Левенберга — Маркардта]] — комбинация метода Ньютона и наискорейшего спуска
* [[Метод Ньютона]] в оптимизации, основанный на [[Метод Ньютона|методе Ньютона]] поиска корня
* [[Квазиньютоновские методы]] — методы, основанные на замене матрицы Гессе её приближением.
** [[Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно]] — квазиньютоновский алгоритм [[нелинейная оптимизация|нелинейной оптимизации]]

== [[Грамматический разбор]] ==
* [[Рекурсивный нисходящий парсер]] — [[нисходящий парсер]], подходящий для <math>LL(k)</math>-грамматик
* [[LL-парсер]] — относительно простой алгоритм разбора за [[линейное время]] для ограниченного класса [[контекстно-свободная грамматика|контекстно-свободных грамматик]]
* {{Не переведено|LR-парсер||en|LR parser}} — более сложный алгоритм разбора за [[линейное время]] для большего класса [[контекстно-свободная грамматика|контекстно-свободных грамматик]]. Варианты:
** {{Не переведено|Парсер первенства операторов||en|Operator-precedence parser}}
** {{Не переведено|SLR-парсер||en|Simple LR parser}} ({{lang-en|Simple LR parser}})
** {{Не переведено|LALR-парсер||en|Look-ahead LR parser}} ({{lang-en|Look-ahead LR parser}})
** {{Не переведено|Канонический LR-парсер||en|Canonical LR parser}}
* {{Не переведено|Парсер старьёвщика||en|Packrat parser}} — алгоритм разбора за [[линейное время]], поддерживающий некоторые [[контекстно-свободная грамматика|контекстно-свободные грамматики]] и [[грамматика разбора выражений|грамматики разбора выражений]]
* [[Алгоритм Коука — Янгера — Касами]] (алгоритм CYK) — <math>O(n^3)</math>-алгоритм для разбора любой [[контекстно-свободная грамматика|контекстно-свободной грамматики]]
* [[Алгоритм Эрли]] — другой <math>O(n^3)</math>-алгоритм для разбора любой [[контекстно-свободная грамматика|контекстно-свободной грамматики]]
* [[GLR-парсер|<math>GLR</math>-парсер]] — алгоритм для разбора любой [[контекстно-свободная грамматика|контекстно-свободной грамматики]], он предназначен для определённых грамматик, на которых он действует практически за [[линейное время]] и <math>O(n^3)</math> в худшем случае.
* [[Метод рекурсивного спуска]] — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному [[контекстно-свободная грамматика|контекстно-свободной грамматикой]]
* [[Алгоритм Рутисхаузера]] — работает в предположении о полной скобочной структуре выражения
* [[Алгоритм сортировочной станции]]

== [[Квантовый алгоритм|Квантовые алгоритмы]] ==
''<small>Приложения [[Квантовые вычисления|квантовых вычислений]] к различным категориям проблем и алгоритмы</small>''

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

== Теория вычислений и автоматов ==
* {{Не переведено|Конструирование набора подмножеств||en|Powerset construction}} — алгоритм для преобразования недетерминированного автомата в детерминированный
* [[Алгоритм Тодда — Коксетера]] — процедура для создания сомножеств

== Другие ==
* [[Астрономический алгоритм|Астрономические алгоритмы]]
* Алгоритмы восстановления фазы волнового фронта (Гершберга-Сакстона, Фиенапа, Бейтса, Альморо и др.)
* [[Алгоритм Баума — Велша]]
* Алгоритмы манипуляции битами
** [[Алгоритм создания битовой маски]]
** [[Алгоритм обмена при помощи исключающего ИЛИ]] — обмен значений двух переменных без использования буфера
* [[Алгоритм Судного Дня|Алгоритм вычисления дня недели (Алгоритм Судного Дня)]]
* [[Алгоритм Витерби]]
* [[Алгоритм Луна]] — метод проверки правильности идентификационных чисел
* [[Стемминг|Алгоритм стемматизации (стемминга)]] — процесс нахождения [[Основа слова|основы слова]]
* [[Алгоритм Риша]] — нахождение [[первообразная|первообразных]]
* [[Алгоритм синтеза многосвязной сети]]
* [[Алгоритм распространения доверия]] (алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях
* [[Быстрый метод мультиполей]] — алгоритм вычисления сил взаимодействия <math>N</math> частиц<ref>{{статья
 |автор       = Barry A. Cipra
 |заглавие = The Best of the 20th Century: Editors Name Top 10 Algorithms
 |ссылка     = http://www.siam.org/news/news.php?id=637
 |язык         = en
 |издание   = SIAM News
 |год           = 2000
 |том           = 33
 |номер       = 4
 |archiveurl       = https://web.archive.org/web/20110615092015/http://www.siam.org/news/news.php?id=637
 |archivedate      = 2011-06-15
}}</ref>
* [[Алгоритм Зиккурат]] — алгоритм генерации неравномерно распределенных случайных чисел 

== См. также ==
* [[Список структур данных]]
* [[:Категория:Классы сложности|Список классов сложности]], [[Класс сложности]]
* [[Список основных разделов теории алгоритмов]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|подзаголовок
|заглавие=Структуры данных и алгоритмы
|оригинал=
|ссылка=
|автор=Ахо, Альфред, В., [[Хопкрофт, Джон]], Ульман, Джеффри, Д. 
|год=2000
|место=
|издательство=[[Вильямс (издательство)|Издательский дом «Вильямс»]]
|страниц =384
|isbn= 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.) 
}}
* {{книга
 |1                        = подзаголовок
 |заглавие         = Теоретико-числовые алгоритмы в криптографии
 |оригинал         = 
 |автор               = Василенко О.Н.
 |год                   = 2003
 |место               = Москва
 |издательство = [[МЦНМО]]
 |страниц           = 328
 |isbn                     = 5-94057-103-4
 |ссылка             = http://www.ict.edu.ru/ft/002416/book.pdf
}} {{Wayback|url=http://www.ict.edu.ru/ft/002416/book.pdf |date=20070127053816 }}
* {{книга
|автор = [[Дональд Кнут]]
|заглавие = Искусство программирования, том 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
}}
* {{книга
|заглавие = Алгоритмы: построение и анализ,  3-е издание 
|оригинал = Introduction to Algorithms, Third Edition 
|автор = Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн 
|страниц = 1328 
|isbn = 978-5-8459-1794-2 
|год = 2013 
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]] 
}}

* {{книга
|заглавие = Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск
|оригинал = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching
|автор = Роберт Седжвик
|страниц = 672
|год = 2003
|место =  СПб.
|издательство = ДиаСофтЮП
|isbn = 5-93772-081-4
}}
* {{книга
|заглавие = Фундаментальные алгоритмы на C. Алгоритмы на графах
|оригинал = Algorithms in C. Graph Algorithms
|автор = Роберт Седжвик
|страниц = 480
|год = 2003
|место =  СПб.
|издательство = ДиаСофтЮП
|isbn = 5-93772-082-2
}}
* {{книга
|подзаголовок
|заглавие=Algorithms
|оригинал=
|автор=Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani
|год=2006
|место=
|издательство=The McGraw-Hill Companies
|страниц=320
|isbn= 0-07-352340-2
|ссылка=http://www.cs.berkeley.edu/~vazirani/algorithms.html
}}
* {{книга
|заглавие=Жемчужины проектирования алгоритмов. Функциональный подход
|оригинал=Pearls of Functional Algorithm Design
|автор=Ричард Берд
|издательство=ДМК Пресс
|серия=Функциональное программирование
|isbn=978-5-94074-867-0
|год=2013
}}
* {{книга
|автор = Препарата Ф., Шеймос М.
|заглавие = Вычислительная геометрия: Введение
|оригинал = Computational Geometry An introduction
|издательство = Мир
|место = М.
|год = 1989
|страниц = 478
}}
* {{книга
|автор = Берг М., Чеонг О., Кревельд М., Овермарс М.
|заглавие = Вычислительная геометрия. Алгоритмы и приложения
|оригинал = Computational Geometry: Algorithms and Applications
|издательство = ДМК-Пресс
|место = М.
|год = 2016
|страниц = 438
|isbn = 978-5-97060-406-9
}}

== Ссылки ==
* [http://www.compression.ru/ Сайт по методам сжатия данных]
* [https://web.archive.org/web/20060704171110/http://rain.ifmo.ru/cat/view.php/ Дискретная математика: Алгоритмы] — библиотека алгоритмов и визуализаторов
* [http://algolist.manual.ru/ Алгоритмы, методы, исходники]
* [http://e-maxx.ru/algo/ Множество алгоритмов с примерами их реализации]
*«[https://algorithmica.org Алгоритмика]»

[[Категория:Проект:Математика:Списки]]