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

Список статей для координации работ по развитию темы.

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

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

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

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

См. Список комбинаторных алгоритмов

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

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

• Преобразование Барроуза-Уилера (также известен как англ. 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-кодирование)
• Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
  • Кодирование Шеннона-Фано — самый простой алгоритм кодирования
  • Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
    •  — техника адаптивного кодирования, основывающая на коде Хаффмана
  •  — используется для однородного вероятностного распределения с конечным алфавитом
  • Арифметическое кодирование — развитие энтропийного кодирования
  •  — метод сжатия данных, который близок по эффективности к арифметическому кодированию
• Энтропийное кодирование с известными характеристиками
  • Унарное кодирование — код, который представляет число n в виде n единиц с замыкающим нулём
  • дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
  • — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
  • Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
  • — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Криптографические функции дайджестов сообщений:
  • MD5 — существует метод генерации коллизий
  • SHA-1
  • HMAC — аутентификация сообщение с помощью хеш-ключа
  • (TTH) — обычно используется в Тигровых деревьях хэшей
• Криптографически надёжные генераторы псевдослучайных чисел
  • Алгоритм Блюма, Блюма и Шуба — базируется на сложности факторизации
  • ГПСЧ Фортуна— якобы улучшение алгоритма Ярроу

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

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

Разработка ПО

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

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

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

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

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

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

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

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

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

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

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

• (англ. Multi level feedback queue)
• (англ. List scheduling)

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

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

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

• Самоорганизующееся отображение (Карты Кохонена, SOM)

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

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

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

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

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

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

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

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

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

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

• Рекурсивный нисходящий парсер — Нисходящий парсер, подходящий для LL(k) грамматик
• — Относительно простой алгоритм разбора за линейное время для ограниченного класса контекстно-свободных грамматик
•  — Более сложный алгоритм разбора за линейное время для большего класса контекстно-свободных грамматик.Варианты:
  • (англ. Simple LR parser)
  • (англ. Look-ahead LR parser)
•  — Алгоритм разбора за линейное время поддерживающий некоторые контекстно-свободные грамматики и грамматики разбора выражений
•  — O(n³)-алгоритм для разбора любой контекстно-свободной грамматики
•  — Другой O(n³)-алгоритм для разбора любой контекстно-свободной грамматики
•  — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и O(n³) в худшем случае.
• Метод рекурсивного спуска — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной грамматикой
• Алгоритм Рутисхаузера — работает в предположении о полной скобочной структуре выражения

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

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

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

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

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

Другие

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

Литература

• Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. — Издательский дом "Вильямс", 2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.).
• Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦМНО, 2003. — С. 328. — ISBN 5-94057-103-4.

• Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4.
• Дональд Кнут. Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2.
• Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
• Дональд Кнут . Искусство программирования, том 4, выпуск 3. Генерация всех сочетаний и разбиений = The Art of Computer Programming, Volume 4, Fascicle 3 : Generating All Combinations and Partitions. — М.: «Вильямс», 2007. — С. 208. — ISBN 0-201-85394-9.
• Дональд Кнут . Искусство программирования, том 4, выпуск 4. Генерация всех деревьев. История комбинаторной генерации = The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees -- History of Combinatorial Generation. — М.: «Вильямс», 2007. — С. 160. — ISBN 0-321-33570-8.
• Порублев Илья Николаевич, Ставровский Андрей Борисович. Алгоритмы и программы. Решение олимпиадных задач. — М.: «Вильямс», 2007. — С. 480. — ISBN 978-5-8459-1244-2.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Robert Sedgewick. Algorithms in C (Part 1–4). — Addison-Wesley. — ISBN 0-201-31452-5.

• Robert Sedgewick. Algorithms in C (Part 5). — Addison-Wesley. — ISBN 0-201-31663-3.

• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Introduction to Algorithms. — McGraw-Hill Companies, The, 2006. — С. 320. — ISBN 0-073-52340-2.

Ссылки

• Алгоритмы, методы, исходники