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

Нижеследующее — это список алгоритмов. Также смотрите список структур данных, список основных разделов теории алгоритмов и список терминов, относящихся к алгоритмам и структурам данных.

Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание.

Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.

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

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

Алгоритм Флойда для нахождения циклов — находит цикл в итерациях
Генераторы псевдослучайных чисел:
— генерация перестановок из пар таблиц Юнга

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

Алгоритм Беллмана — Форда — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
Алгоритм Борувки — находит минимальное остовное дерево в графе

Алгоритм Брона — Кербоша — нахождение наибольших максимальных независимых по включению множеств вершин графа.

Алгоритм Флойда — Уоршелла — вычисляет все кратчайшие пути во взвешенном графе
Алгоритм Дейкстры — вычисляет кратчайший путь в графе с неотрицательными весами рёбер

Алгоритм Джонсона — вычисляет все кратчайшие пути во взвешенном графе
Алгоритм Краскала — находит остовный лес минимального веса в графе
— алгоритм для рисования графа
Алгоритм Прима — находит остовное дерево минимального веса в связном графе

Алгоритм Кристофидеса — эвристический приближенный алгоритм для решения метрической задачи коммивояжера на графе.
Метод ближайшего соседа

Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
Построение транзитивного замыкания графа (установление факта достижимости вершин)

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

Алгоритм Форда — Фалкерсона
Алгоритм Эдмондса — Карпа, локально-максимального увеличения
Алгоритм Диница
Алгоритм Карзанова
Алгоритм Малхотри — Кумара — Махешвари
Алгоритм Галила — Наамада
Алгоритм Слейтора — Тарьяна
Алгоритм Голдберга — Тарьяна
Алгоритм CHM
Алгоритм Кинга
Алгоритм Голдберга — Рао

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

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

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

Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма

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

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

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

Алгоритм Кнута — Морриса — Пратта
Алгоритм Рабина — Карпа поиска строки
Алгоритм Бойера — Мура поиска строки
Алгоритм Ахо — Корасик
(также известен как shift-or, shift-and или алгоритм Баеса-Ятеса — Гоннета)
Задача поиска наибольшей общей подпоследовательности
Задача поиска наибольшей увеличивающейся подпоследовательности
Задача поиска наибольшей общей подстроки
Задача поиска количества подпалиндромов

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

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

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

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

Наивная сортировка — генерация всех (....) возможных перестановок и проверка на отсортированность
Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной

Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Глупая сортировка, найти отличия от Bogosort

Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Поразрядная сортировка — сортирует строки буква за буквой (ср. с блочной)

Сортировка Бентли — Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
Сортировка бинарным деревом

Сортировка методом вставок — определяем, где текущий элемент должен находится в отсортированном списке, и вставляем его туда

Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
Сортировка методом Шелла — попытка улучшить сортировку вставками
Сортировка перемешиванием (Сортировка коктейлем)

Сортировка подсчётом — используется диапазон входных данных, подсчитывается число одинаковых элементов (3 варианта)
Сортировка пузырьком

Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
Топологическая сортировка

Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
Цифровая сортировка (Сортировка по отделениям)

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

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

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

Преобразование Барроуза — Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза — Уилера

Дельта-кодирование — эффективно для сжатия данных, в которых последовательности часто повторяются
Инкрементное кодирование — дельта-кодирование применяемое к последовательности строк
Семейство алгоритмов словарного сжатия Лемпеля — Зива:
- 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) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений

— сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
(EZW-кодирование)

Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
- Алгоритм Шеннона — Фано — самый простой алгоритм кодирования
- Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
  - — техника адаптивного кодирования, основывающаяся на коде Хаффмана
- — используется для однородного вероятностного распределения с конечным алфавитом
- Арифметическое кодирование — развитие энтропийного кодирования

Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании

— метод сжатия данных, который близок по эффективности к арифметическому кодированию

Энтропийное кодирование с известными характеристиками

Унарное кодирование — код, который представляет число (....) в виде (....) единиц с замыкающим нулём

дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа

Кодирование Фибоначчи — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова

Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

— форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

— сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
А-закон — стандартный алгоритм компандирования. Применяется в РФ.
Мю-закон — стандартный алгоритм компандирования
Фрактальное сжатие — метод, использующий фракталы для сжатия изображений

— тип сжатия данных для «естественных» данных, таких как аудио-сигналы или фотографические изображения
— техника, часто используемая в сжатии данных с потерями

Вейвлетное сжатие — тип компрессии данных хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)

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

— определение наименьшего расстояния между двумя выпуклыми фигурами
— трудоёмкость (....).
Поиск диаметра множества точек
Алгоритм Цируса — Бека — отсечение линий.
Алгоритм Сазерленда — Ходжмана — отсечение многоугольника.
Построения контура прямоугольников (стороны параллельны осям координат).
Нахождение ядра многоугольника
Регуляризация многоугольника — декомпозиция многоугольника на монотонные части.

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

Построение ВП через треугольники — трудоёмкость (....).
Построение ВП перебором рёбер на принадлежность — трудоёмкость (....).
Алгоритм сканирования Грэхема — трудоёмкость (....).
Алгоритм Экла — Туссена — трудоёмкость (....). Улучшение алгоритма Грэхема.
Алгоритм Эндрю — трудоёмкость (....). Улучшение алгоритма Грэхема.
Алгоритм быстрой оболочки — трудоёмкость (....), в среднем — (....).

Алгоритм Киркпатрика — построение выпуклой оболочки набора точек на плоскости методом «разделяй и властвуй» через мосты. Трудоёмкость (....).

Построение методом «разделяй и властвуй» через построение касательных — трудоёмкость (....).

Алгоритм заворачивания подарков (Джарвиса) — трудоёмкость (....), (....) — количество точек в выпуклой оболочке.
— трудоёмкость (....), (....) — количество точек в выпуклой оболочке.
Алгоритм Чана — трудоёмкость (....), (....) — количество точек в выпуклой оболочке.

Инкрементальный алгоритм (fast online hull) — через построение касательных (....), с помощью сбалансированного дерева — (....).

Приближённая выпуклая оболочка снизу (lower approximate hull) — методом полос. Трудоёмкость (....), где (....) — количество полос.

Приближённая выпуклая оболочка сверху (upper approximate hull) — методом полос. Трудоёмкость (....), где (....) — количество полос.

Алгоритм Ли (выпуклые оболочки) — построение выпуклой оболочки простого многоугольника через отрезание карманов. Трудоёмкость (....).

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

Триангуляция через поиск диагоналей — ищется диагональ, многоугольник делится на два и далее рекурсивно. Трудоёмкость (....).

Триангуляция через отрезание ушей — ищется образующая треугольник диагональ, соседние с треугольником вершины — следующие претенденты на отрезание. Трудоёмкость (....).
Триангуляция монотонного простого многоугольника — трудоёмкость (....).
Жадная триангуляция — трудоёмкость (....).

Оптимальная триангуляция — NP-полная задача. Суммарная длина всех рёбер минимальна среди всех триангуляций данного множества.

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

Итеративные алгоритмы построения триангуляции Делоне — трудоёмкость (....).
Алгоритмы построения триангуляциии Делоне слиянием — трудоёмкость (....) и (....).
Алгоритмы прямого построения триангуляциии Делоне — трудоёмкость (....).

Двухпроходные алгоритмы построения триангуляциии Делоне — трудоёмкость (....) и (....).
Триангуляциии Делоне с ограничениями — трудоёмкость (....).

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

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

Локализация точки для выпуклого многоугольника — время запроса (....).
Локализация точки в звездном многоугольнике — время запроса (....).

Алгоритм точки в многоугольнике — проверка принадлежности данной точки простому многоугольнику (....).

Метод луча — принадлежность точки простому многоугольнику (....).
Метод углов — принадлежность точки выпуклому многоугольнику. Трудоёмкость (....).
Метод полос — простой многоугольник. Время запроса (....), память (....).

Метод детализации триангуляции Киркпатрика — простой многоугольник. Время запроса (....), память (....).

Трапецоидальная карта — простой многоугольник. Рандомизированный алгоритм, время запроса (....), память (....).
Метод цепей — простой многоугольник. Время запроса (....), память (....).

Пересечения

Пересечение отрезков (алгоритм Бентли — Оттманна) — поиск всех точек пересечения отрезков на плоскости (....), (....) — количество точек пересечения.
Алгоритм Чазелла — Эдельсбруннера — пересечение отрезков за (....).
(алгоритм Шеймоса — Гоя) — трудоёмкость (....).
Алгоритм Сазерленда — Коэна — для выпуклых многоугольников. Трудоёмкость (....).
Пересечения выпуклых многоугольников — трудоёмкость (....).
Алгоритм Шеймоса — Хоуи — для выпуклых многоугольников методом полос. Трудоёмкость (....).
Пересечения выпуклых многоугольников с заметающей прямой — трудоёмкость (....).
Пересечение звёздных многоугольников — трудоёмкость (....).
Пересечение полуплоскостей — трудоёмкость (....).

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

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

Алгоритм Брезенхэма — растеризует отрезок линии с заданными координатами начала и конца
— алгоритм для аппроксимации отрезка на дискретной графической поверхности

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

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

(англ. Scanline rendering) — конструирует образ с помощью перемещения воображаемой линии над образом
— рассматривает прямое освещение и отражение от других объектов

Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
- — уменьшение ошибки с помощью

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

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

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

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

Шифрование с симметричным (скрытым) ключом:
- ГОСТ 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 — аутентификация сообщение с помощью хеш-ключа
Тигр — обычно используется в Тигровых деревьях хэшей

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

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

CORDIC — быстрая техника вычисления тригонометрических функций.
Медианный фильтр для одномерного массива

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

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

— Преобразование между системами адресации диска

Алгоритм вычисления контрольной суммы (CRC или FCS) Циклическая избыточная сумма (Ciclic Redunancy Check), или контрольная последовательность кадра (Frame Check Sequence) — вычисление кода проверки.

Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Петерсона

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

Планирование Round-robin
(англ. Multi level feedback queue)
Кратчайшая работа следующей (планирование)
(англ. List scheduling)

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

— также известен как выбор рулеточного колеса

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

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

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

— находит базис Грёбнера
— ортогонализация набора векторов
— для многочленов в некоторых неопределённостях
Алгоритмы умножения матриц
- Алгоритм Штрассена — быстрое умножение матриц
- Алгоритм Копперсмита — Винограда
(англ. Chain matrix multiplication)
Алгоритмы вычисления дискретного преобразования Фурье

Преобразования Хаусхолдера (QR-разложение) — вычисление обратной матрицы, собственный векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
Решение систем линейных уравнений
- Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений

Структурированное гауссово исключение — применяется, когда матрица системы является разреженной
Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления
Преобразования Холеского — метод, эффективный для ленточных и разреженных матриц

Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам

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

Целочисленная арифметика (алгоритмы для работы с большими числами)
- Умножение столбиком больших чисел
- «Быстрый столбик»
- Умножение Карацубы — алгоритм быстрого умножения чисел
- Деление на одноразрядное число (DO)
- Деление больших чисел
Быстрое возведение в степень — вычисляет степени чисел при помощи возведения в квадрат
Алгоритмы модулярной арифметики
- Алгоритм Монтгомери — модулярное умножение и возведение в степень
- Алгоритм нахождения порядка элемента
- Алгоритм Тонелли — Шенкса — решение квадратичных сравнений
- Решение систем линейных сравнений
  - С помощью китайской теоремы об остатках
  - Алгоритм Гарнера
Решение систем линейных уравнений над полем
- Алгоритм Ланцоша — эффективен над полем характеристики 2
- Алгоритм Видемана
Дискретное логарифмирование:
- В простом конечном поле
  - (алгоритм больших и маленьких шагов, англ. baby-step giant-step)
  - Алгоритм Полига — Хеллмана — эффективен, если все делители (....) — небольшие
  - ρ-метод Полларда дискретного логарифмирования
  - Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования

Алгоритм COS (алгоритм Копперсмита — Одлыжко — Шреппеля) — достаточно эффективный субэкспоненциальный алгоритм

Решето числового поля — наиболее эффективный на данный момент алгоритм дискретного логарифмирования

В произвольном конечном поле

(алгоритм index-calculus) — сведение дискретного логарифмирования в произвольном конечном поле к аналогичной задаче в простом поле

Алгоритм Копперсмита — эффективный алгоритм дискретного логарифмирования в конечном поле характеристики 2

Алгоритмы нахождения наибольшего общего делителя (НОД) двух чисел
- Алгоритм Евклида

Расширенный алгоритм Евклида — также решает уравнение (....), где (....)НОД(....), НОД(....)НОД(....)
Бинарный алгоритм нахождения НОД — эффективный способ вычисления НОД

Расширенный бинарный алгоритм — модификация бинарного алгоритма нахождения НОД, аналогичная расширенному алгоритму Евклида

Тесты простоты — проверка, является ли данное число простым
- Детерминированные тесты простоты
  - Перебор делителей
  - Решето Эратосфена
  - Решето Аткина — оптимизированная версия решета Эратосфена
  - Тест на основе малой теоремы Ферма

Тест Миллера — модификация теста на основе малой теоремы Ферма; опирается на расширенную гипотезу Римана

(N-1)–метод проверки простоты — тест на простоту при известном разложении на множители числа (....); также используется для построения больших простых чисел

(N+1)–метод проверки простоты — тест на простоту при известном разложении на множители числа (....)
Алгоритм Конягина — Померанса — модификация (....)-метода

Алгоритм Ленстры — использует суммы Якоби и некоторые тесты, обобщающие малую теорему Ферма
Тест Люка — Лемера для чисел Мерсенна
Тест Пепина для чисел Ферма
(тест Агравала, Кайала, Саксены) — полиномиальный детерминированный тест на простоту

Вероятностные тесты простоты

Тест Соловея — Штрассена — опирается на малую теорему Ферма и свойства символа Лежандра
Тест Миллера — Рабина — эффективная модификация теста Соловея — Штрассена

Факторизация — разложение числа на множители
- Алгоритмы с экспоненциальной сложностью
  - Перебор делителей
  - ρ-метод Полларда
  - Алгоритм Шермана — Лемана
  - Алгоритм Ленстры
- Алгоритмы с субэкспоненциальной сложностью
  - (англ. SNFS)
  - (англ. GNFS)
  - — вероятностный алгоритм факторизации с помощью эллиптических кривых
Алгоритм Шуфа — вычисление порядка группы точек эллиптической кривой
(LLL-алгоритм, L³-алгоритм)

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

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

— вычисление кривых Безье
Методы интерполяции
Приближенное вычисление решений
- (False position method, regula falsi method) — аппроксимирует корни функции
- Метод Ньютона (метод касательных) — нахождение нулей функций с помощью производной
- Метод секущих (метод хорд) — аппроксимирует корни функции
- Метод градиентов (градиентный спуск) — аппроксимирует решение системы уравнений

Алгоритм Гаусса — Ньютона — алгоритм для решения нелинейных уравнений методом наименьших квадратов

Алгоритм Левенберга — Марквардта — алгоритм для решения нелинейных уравнений методом наименьших квадратов

— нахождение всех решений задачи точного покрытия
— вычисление сплайнов
— вычисление цифр числа пи
— более аккуратный метод суммирования чисел с плавающей точкой

— моделирование методом Монте-Карло, численное интегрирование
— классические способы округления чисел
— извлечение корня цифра за цифрой
Вычисление квадратного корня:
- Алгоритм Герона

школьный (ручной) алгоритм — аппроксимирует квадратный корень числа

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

Линейное программирование
Симплекс-метод
«Венгерский метод» — решение задач целочисленного линейного программирования
Метод Мака решения задачи о назначениях
Алгоритм имитации отжига
Муравьиные алгоритмы
Метод ветвей и границ

Метод Нелдера — Мида (downhill simplex method) — алгоритм нелинейной оптимизации
Метод перебора

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

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

Рекурсивный нисходящий парсер — Нисходящий парсер, подходящий для (....)-грамматик

LL-парсер — Относительно простой алгоритм разбора за линейное время для ограниченного класса контекстно-свободных грамматик

— Более сложный алгоритм разбора за линейное время для большего класса контекстно-свободных грамматик. Варианты:
- (англ. Simple LR parser)
- (англ. Look-ahead LR parser)

— Алгоритм разбора за линейное время поддерживающий некоторые контекстно-свободные грамматики и грамматики разбора выражений

— (....)-алгоритм для разбора любой контекстно-свободной грамматики

— Другой (....)-алгоритм для разбора любой контекстно-свободной грамматики

— алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и (....) в худшем случае.

Метод рекурсивного спуска — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной грамматикой
Алгоритм Рутисхаузера — работает в предположении о полной скобочной структуре выражения

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

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

Алгоритм Гровера — позволяет выполнять поиск среди (....) вариантов за (....) проверок
Алгоритм Шора — полиномиальный алгоритм факторизации числа
Алгоритм Дойча — Джоза — критерий баланса для булевой функции
Задача Фейнмана

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

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

Другие

Астрономические алгоритмы
Алгоритм Баума — Велша
Алгоритмы манипуляции битами
- Алгоритм создания битовой маски

Алгоритм обмена при помощи исключающего ИЛИ — обмен значений двух переменных без использования буфера

Алгоритм вычисления дня недели
Алгоритм Витерби
Алгоритм Луна — метод проверки правильности идентификационных чисел
Алгоритм стемминга — процесс нахождения основы слова

Примечания

Литература

Ссылки

[http://www.compression.ru/ Сайт по методам сжатия данных]

[http://rain.ifmo.ru/cat/view.php/ Дискретная математика: Алгоритмы] — библиотека алгоритмов и визуализаторов
[http://algolist.manual.ru/ Алгоритмы, методы, исходники]

Ссылки на внешние ресурсы:

- Читать статью в википедии
wiki-ассоциации

- Список наиболее близких по теме статей

- Упоминания этой статьи в других статьях

Просмотр Карты Памяти (MindMap) статьи

Перейти на главную страницу

По теме:

Категории:

Списки