Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание.
Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.
Комбинаторные алгоритмы
- Алгоритм Кристофидеса — эвристический приближенный алгоритм для решения метрической задачи коммивояжера на графе.
- Метод ближайшего соседа
- Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
- Построение транзитивного замыкания графа (установление факта достижимости вершин)
Алгоритмы нахождения максимального потока
- Алгоритм Форда — Фалкерсона
- Алгоритм Эдмондса — Карпа, локально-максимального увеличения
- Алгоритм Диница
- Алгоритм Карзанова
- Алгоритм Малхотри — Кумара — Махешвари
- Алгоритм Галила — Наамада
- Алгоритм Слейтора — Тарьяна
- Алгоритм Голдберга — Тарьяна
- Алгоритм CHM
- Алгоритм Кинга
- Алгоритм Голдберга — Рао
Алгоритмы нахождения максимального паросочетания
Алгоритмы поиска
- Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
Алгоритмы на строках
Алгоритмы поиска строки
Примерное соответствие
Деревья для строковых последовательностей
- Наивная сортировка — генерация всех (....) возможных перестановок и проверка на отсортированность
- Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной
- Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
- Глупая сортировка, найти отличия от Bogosort
- Сортировка Бентли — Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
- Сортировка бинарным деревом
- Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
- Цифровая сортировка (Сортировка по отделениям)
Алгоритмы слияния
- Простой алгоритм слияния (англ. Simple Merge algorithm )
- (....)-мерный алгоритм слияния (англ. k-way Merge algorithm )
- Преобразование Барроуза — Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
- Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза — Уилера
- Дельта-кодирование — эффективно для сжатия данных, в которых последовательности часто повторяются
- Инкрементное кодирование — дельта-кодирование применяемое к последовательности строк
- Семейство алгоритмов словарного сжатия Лемпеля — Зива:
- LZ77 — родоначальник семейства LZ77-алгоритмов
- LZ77-PM
- LZFG
- LZP
- LZBW
- LZSS
- LZ78 — родоначальник семейства LZ78 алгоритмов
- 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) — конструирует образ с помощью перемещения воображаемой линии над образом
- — рассматривает прямое освещение и отражение от других объектов
- Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
- — уменьшение ошибки с помощью
- — представление образа или видео при помощи меньшего образа или видео
- См. также Разделы в криптографии для аналитического глоссария
- AES (англ. Advanced Encryption Standard) — победитель соревнования NIST, также известен как Rijndael
- Blowfish
- DES (англ. Data Encryption Standard) — иногда, алгоритм DEA (англ. Data Encryption Algorithm), победитель соревнования NBS, заменён на AES для большинства применений
- RC2
- IDEA (англ. International Data Encryption Algorithm)
- RC4
- Алгоритмы выработки общего ключа
- Алгоритмы разделения секрета
- Рюкзак — на данный момент доказана нестойкость схемы
- Схема Шамира
- Схема Blakey
- Алгоритмы подбрасывания монеты по телефону
- MD5 Резюме сообщения 5 (Message Digest 5) Разработан Рональдом Ривестом (RFC 1321) — существует метод генерации коллизий
- RIPEMD-160
- SHA-1
- HMAC — аутентификация сообщение с помощью хеш-ключа
- Тигр — обычно используется в Тигровых деревьях хэшей
- — Уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
- Osem — алгоритм для обработки медицинских изображений
- — Может быть использован для декодирования цифр тональных сигналов
- — алгоритм увеличения резкости образа
- — Преобразование между системами адресации диска
- Алгоритм вычисления контрольной суммы (CRC или FCS) Циклическая избыточная сумма (Ciclic Redunancy Check), или контрольная последовательность кадра (Frame Check Sequence) — вычисление кода проверки.
- Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
- Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.
Алгоритмы распределённых систем
- — Частичное упорядочение событий в зависимости от того, что случилось раньше
- — снимок процесса записывающий глобальное состояние системы
- — Полное упорядочение событий
- — распределённая синхронизация часов
- — другой алгоритм синхронизации часов
Алгоритмы выделения и освобождения памяти
- — «скромный» сборщик мусора
- — алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
- — Быстрые сборщики мусора, которые разделяют память по возрасту
- Подсчёт ссылок
- — Алгоритм, использующийся для избежания взаимных блокировок
- — выбор страницы-жертвы при условиях небольшого объёма памяти
- : скорость выполнения лучше, чем у LRU
- (CAR): алгоритм замены страниц со скоростью выполнения, сравнимой с адаптивным алгоритмом замещения кэша
- — выбор нового лидера среди множества компьютеров
- rsync — алгоритм, использующийся для эффективной передачи файлов между двумя компьютерами
Дисковые алгоритмы-планировщики
- — дисковый алгоритм планирования, который работает как лифт
- — дисковый алгоритм планирования для уменьшения времени поиска
Сетевые алгоритмы
- : получение точных оценок времени распространения пакетов сообщений при использовании TCP/IP
- : техника эффективного сохранения и поиска в таблицах роутинга
- : улучшение эффективности TCP/IP за счёт объединения пакетов
- Шейпинг
Алгоритмы синхронизации процессов
- — также известен как выбор рулеточного колеса
Медицинские алгоритмы
Вычислительная алгебра
- Преобразования Хаусхолдера (QR-разложение) — вычисление обратной матрицы, собственный векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
- Решение систем линейных уравнений
- Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений
- Структурированное гауссово исключение — применяется, когда матрица системы является разреженной
- Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления
- Преобразования Холеского — метод, эффективный для ленточных и разреженных матриц
- Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам
- Целочисленная арифметика (алгоритмы для работы с большими числами)
- Умножение столбиком больших чисел
- «Быстрый столбик»
- Умножение Карацубы — алгоритм быстрого умножения чисел
- Деление на одноразрядное число (DO)
- Деление больших чисел
- Быстрое возведение в степень — вычисляет степени чисел при помощи возведения в квадрат
- Алгоритмы модулярной арифметики
- Алгоритм Монтгомери — модулярное умножение и возведение в степень
- Алгоритм нахождения порядка элемента
- Алгоритм Тонелли — Шенкса — решение квадратичных сравнений
- Решение систем линейных сравнений
- Решение систем линейных уравнений над полем
- Алгоритм Ланцоша — эффективен над полем характеристики 2
- Алгоритм Видемана
- Дискретное логарифмирование:
- Алгоритм COS (алгоритм Копперсмита — Одлыжко — Шреппеля) — достаточно эффективный субэкспоненциальный алгоритм
- Решето числового поля — наиболее эффективный на данный момент алгоритм дискретного логарифмирования
- В произвольном конечном поле
- (алгоритм index-calculus) — сведение дискретного логарифмирования в произвольном конечном поле к аналогичной задаче в простом поле
- Алгоритм Копперсмита — эффективный алгоритм дискретного логарифмирования в конечном поле характеристики 2
- Алгоритмы нахождения наибольшего общего делителя (НОД) двух чисел
- Расширенный бинарный алгоритм — модификация бинарного алгоритма нахождения НОД, аналогичная расширенному алгоритму Евклида
- Тест Миллера — модификация теста на основе малой теоремы Ферма; опирается на расширенную гипотезу Римана
- (N-1)–метод проверки простоты — тест на простоту при известном разложении на множители числа (....); также используется для построения больших простых чисел
- (N+1)–метод проверки простоты — тест на простоту при известном разложении на множители числа (....)
- Алгоритм Конягина — Померанса — модификация (....)-метода
- Вероятностные тесты простоты
- Факторизация — разложение числа на множители
- Алгоритмы с экспоненциальной сложностью
- Алгоритмы с субэкспоненциальной сложностью
- Алгоритм Шуфа — вычисление порядка группы точек эллиптической кривой
- (LLL-алгоритм, L³-алгоритм)
Численные алгоритмы
Смотри также Список разделов численного анализа
- — вычисление кривых Безье
- Методы интерполяции
- Приближенное вычисление решений
- (False position method, regula falsi method) — аппроксимирует корни функции
- Метод Ньютона (метод касательных) — нахождение нулей функций с помощью производной
- Метод секущих (метод хорд) — аппроксимирует корни функции
- Метод градиентов (градиентный спуск) — аппроксимирует решение системы уравнений
- — нахождение всех решений задачи точного покрытия
- — вычисление сплайнов
- — вычисление цифр числа пи
- — более аккуратный метод суммирования чисел с плавающей точкой
- школьный (ручной) алгоритм — аппроксимирует квадратный корень числа
- — Более сложный алгоритм разбора за линейное время для большего класса контекстно-свободных грамматик. Варианты:
- (англ. Simple LR parser)
- (англ. Look-ahead LR parser)
- — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и (....) в худшем случае.
Теория вычислений и автоматов
- — алгоритм для преобразования недетерминированного автомата в детерминированный
- Алгоритм Тодда — Коксетера — процедура для создания сомножеств
Другие
Примечания
Литература
Ссылки
- [http://www.compression.ru/ Сайт по методам сжатия данных]
- [http://rain.ifmo.ru/cat/view.php/ Дискретная математика: Алгоритмы] — библиотека алгоритмов и визуализаторов
- [http://algolist.manual.ru/ Алгоритмы, методы, исходники]