Список алгоритмов - List of algorithms
Ниже приводится список алгоритмов с однострочными описаниями каждого из них.
Автоматизированное планирование
Комбинаторные алгоритмы
Общие комбинаторные алгоритмы
- Алгоритм Брента : находит цикл в итерациях значений функции, используя только два итератора
- Алгоритм поиска цикла Флойда : находит цикл в итерациях значений функции
- Алгоритм Гейла – Шепли : решает проблему стабильного брака
- Генераторы псевдослучайных чисел (равномерно распределенные - см. Также Список генераторов псевдослучайных чисел для других ГПСЧ с различной степенью сходимости и различным статистическим качеством):
Алгоритмы графа
- Алгоритм раскраски: Алгоритм раскраски графиков.
- Алгоритм Хопкрофта – Карпа : преобразование двудольного графа в соответствие максимальной мощности
- Венгерский алгоритм : алгоритм поиска идеального соответствия
- Кодирование Прюфера : преобразование между помеченным деревом и его последовательностью Прюфера
- Автономный алгоритм наименьших общих предков Тарьяна : вычисляет наименьших общих предков для пар узлов в дереве.
- Топологическая сортировка : находит линейный порядок узлов (например, заданий) на основе их зависимостей.
Рисование графика
- Алгоритмы, основанные на силе (также известные как алгоритмы, основанные на силе или пружинный алгоритм)
- Спектральный план
Теория сети
- Сетевой анализ
- Анализ ссылок
- Алгоритм Гирвана – Ньюмана : обнаружение сообществ в сложных системах
- Анализ веб-ссылок
- Поиск тем, вызванный гиперссылками (HITS) (также известный как концентраторы и авторитетные источники )
- PageRank
- TrustRank
- Анализ ссылок
-
Поточные сети
- Алгоритм Динича : это сильно полиномиальный алгоритм для вычисления максимального потока в потоковой сети .
- Алгоритм Эдмондса – Карпа : реализация Форда – Фулкерсона
- Алгоритм Форда – Фулкерсона : вычисляет максимальный поток на графике
- Алгоритм Каргера : метод Монте-Карло для вычисления минимального разреза связного графа
- Алгоритм push – relabel : вычисляет максимальный поток на графике.
Маршрутизация для графиков
- Алгоритм Эдмондса (также известный как алгоритм Чу – Лю / Эдмондса): найти максимальное или минимальное ветвление
- Евклидово минимальное остовное дерево : алгоритмы вычисления минимального остовного дерева набора точек на плоскости
- Задача евклидова кратчайшего пути : найти кратчайший путь между двумя точками, который не пересекает никаких препятствий
- Проблема самого длинного пути : найти простой путь максимальной длины в заданном графе
- Минимальное остовное дерево
- Неблокирующий коммутатор с минимальным охватом, скажем, для телефонной станции
-
Задача кратчайшего пути
- Алгоритм Беллмана – Форда : вычисляет кратчайшие пути во взвешенном графе (где некоторые веса ребер могут быть отрицательными).
- Алгоритм Дейкстры : вычисляет кратчайшие пути в графе с неотрицательными весами ребер
- Алгоритм Флойда – Уоршалла : решает задачу поиска кратчайшего пути для всех пар во взвешенном ориентированном графе.
- Алгоритм Джонсона: алгоритм кратчайшего пути для всех пар в разреженном взвешенном ориентированном графе
- Проблема транзитивного замыкания : найти транзитивное замыкание заданного бинарного отношения
- Проблема коммивояжера
- Правило Варнсдорфа : эвристический метод решения задачи рыцарского тура .
Поиск граф
- A * : частный случай поиска по первому лучшему, который использует эвристику для повышения скорости
- B * : алгоритм поиска по графу «лучший первый», который находит путь с наименьшей стоимостью от заданного начального узла к любому целевому узлу (из одной или нескольких возможных целей)
- Поиск с возвратом : отказывается от частичных решений, когда обнаруживается, что они не удовлетворяют полному решению.
- Поиск по лучу : это эвристический алгоритм поиска, который является оптимизацией поиска по первому лучшему, что снижает требования к памяти.
- Поиск по стеку лучей : интегрирует обратное отслеживание с поиском луча
- Поиск лучшего первого : просматривает график в порядке вероятной важности с использованием очереди приоритетов.
- Двунаправленный поиск : найти кратчайший путь от начальной вершины до целевой вершины в ориентированном графе
- Поиск в ширину: пересекает график уровень за уровнем
- Поиск методом грубой силы : исчерпывающий и надежный метод поиска, но неэффективный с точки зрения вычислений во многих приложениях.
- D * : алгоритм инкрементального эвристического поиска
- Поиск в глубину : пересекает ветвь графа за веткой
- Алгоритм Дейкстры : частный случай A *, для которого не используется эвристическая функция
- General Problem Solver : оригинальный алгоритм доказательства теорем, предназначенный для работы в качестве универсальной машины для решения проблем.
- Итеративный поиск в глубину (IDDFS): стратегия поиска в пространстве состояний
- Поиск точки перехода : оптимизация до A *, которая может на порядок сократить время вычислений с использованием дополнительных эвристик.
- Лексикографический поиск в ширину (также известный как Lex-BFS): алгоритм с линейным временем для упорядочивания вершин графа
- Поиск с единообразной стоимостью : поиск по дереву, который находит самый дешевый маршрут с разной стоимостью.
- SSS * : поиск в пространстве состояний, проходящий по дереву игры по принципу best-first, аналогично алгоритму поиска A *
- F * : специальный алгоритм для объединения двух массивов
Подграфы
-
Клики
- Алгоритм Брона – Кербоша : метод нахождения максимальных клик в неориентированном графе
- Алгоритм максимальной клики MaxCliqueDyn : найти максимальную клику в неориентированном графе
- Сильносвязные компоненты
- Проблема изоморфизма подграфов
Алгоритмы последовательности
Приблизительное соответствие последовательности
- Битовый алгоритм : нечеткий алгоритм, который определяет, примерно равны ли строки.
-
Фонетические алгоритмы
- Daitch – Mokotoff Soundex : уточнение Soundex, позволяющее сопоставить славянские и германские фамилии.
- Двойной метафон : улучшение метафона
- Подход с рейтингом соответствия : фонетический алгоритм, разработанный Western Airlines
- Метафон : алгоритм индексации слов по их звучанию при произношении на английском языке
- NYSIIS : фонетический алгоритм , улучшенный по сравнению с Soundex
- Soundex : фонетический алгоритм индексации имен по звуку, как произносится на английском языке.
-
Строковые показатели : вычисляет оценку сходства или несходства (расстояния) между двумя парами текстовых строк.
- Расстояние Дамерау – Левенштейна : вычисляет меру расстояния между двумя строками, улучшает расстояние Левенштейна
- Коэффициент Дайса (также известный как коэффициент Дайса): мера сходства, связанная с индексом Жаккара.
- Расстояние Хэмминга : сумма различающихся позиций
- Расстояние Яро – Винклера : мера сходства двух струн.
- Расстояние редактирования Левенштейна : вычисляет метрику количества разницы между двумя последовательностями.
- Поиск по триграмме : поиск текста, когда точный синтаксис или написание целевого объекта точно не известны
Алгоритмы выбора
Последовательный поиск
- Линейный поиск : находит элемент в несортированной последовательности
- Алгоритм выбора : находит k- й по величине элемент в последовательности
- Тернарный поиск : метод нахождения минимума или максимума функции, которая либо строго возрастает, а затем строго убывает, либо наоборот.
-
Сортированные списки
- Алгоритм двоичного поиска : находит элемент в отсортированной последовательности
- Техника поиска Фибоначчи : поиск отсортированной последовательности с использованием алгоритма «разделяй и властвуй», который сужает возможные местоположения с помощью чисел Фибоначчи.
- Поиск с переходом (или поиск блока): линейный поиск на меньшем подмножестве последовательности
- Прогностический поиск : бинарный поиск, который учитывает величину поискового запроса по сравнению с высокими и низкими значениями в поиске. Иногда называется поиском по словарю или интерполированным поиском.
- Единый двоичный поиск : оптимизация классического алгоритма двоичного поиска
Слияние последовательностей
- Простой алгоритм слияния
- k-way алгоритм слияния
- Объединение (слияние, при этом элементы на выходе не повторяются)
Последовательность перестановок
- Перемешивание Фишера – Йетса (также известное как перемешивание Кнута): случайное перемешивание конечного набора
- Алгоритм Шенстеда : строит пару таблиц Юнга из перестановки
- Алгоритм Штейнхауса – Джонсона – Троттера (также известный как алгоритм Джонсона – Троттера): генерирует перестановки путем транспонирования элементов
- Алгоритм генерации перестановки кучи : элементы обмена для генерации следующей перестановки
Комбинации последовательностей
Выравнивание последовательности
- Динамическое искажение времени : измерьте сходство между двумя последовательностями, которые могут различаться по времени или скорости.
- Алгоритм Хиршберга : находит выравнивание последовательностей между двумя последовательностями с наименьшими затратами на основании их расстояния Левенштейна.
- Алгоритм Нидлмана – Вунша : найти глобальное выравнивание между двумя последовательностями
- Алгоритм Смита – Уотермана : найти локальное выравнивание последовательностей
Сортировка последовательности
- Обменные сорта
- Пузырьковая сортировка : для каждой пары индексов меняйте местами элементы, если они вышли из строя
- Сортировка коктейльных шейкеров или двунаправленная пузырьковая сортировка, пузырьковая сортировка, перемещающаяся по списку поочередно спереди назад и сзади вперед
- Сортировка гребней
- Сортировка гномов
- Сортировка по четным и нечетным
- Быстрая сортировка : разделите список на два, причем все элементы в первом списке идут перед всеми элементами во втором списке .; затем отсортируйте два списка. Часто метод выбора
- Юмористический или неэффективный
- Гибридный
- Сорта вставки
- Сортировка вставкой: определите, где текущий элемент находится в списке отсортированных, и вставьте его туда
- Сортировка библиотеки
- Сортировка терпения
- Сортировка оболочки : попытка улучшить сортировку вставками
- Сортировка дерева ( сортировка двоичного дерева): построить двоичное дерево, затем пройти по нему, чтобы создать отсортированный список
- Циклическая сортировка : на месте с теоретически оптимальным количеством записей
- Сортировка слияния
- Сортировка слиянием : отсортируйте первую и вторую половину списка отдельно, затем объедините отсортированные списки
- Slowsort
- Сортировка прядей
- Несравнительные виды
- Сортировка бисера
- Ковшовая сортировка
- Burstsort : построить компактный, кэш эффективного Trie взрыва , а затем пройти через него , чтобы создать упорядоченный выход
- Счетная сортировка
- Сорт голубятни
- Сортировка почтальона : вариант сортировки по ведру, использующий иерархическую структуру
- Radix sort : сортирует строки по буквам
- Выборочные сорта
- Heapsort : преобразовать список в кучу, продолжать удалять самый большой элемент из кучи и добавлять его в конец списка
- Сортировка по выбору : выберите наименьший из оставшихся элементов, добавьте его в конец отсортированного списка
- Гладкая сортировка
- Другой
- Неизвестный класс
Подпоследовательности
- Алгоритм Кадане : находит максимальный подмассив любого размера
- Задача самой длинной общей подпоследовательности : найти самую длинную подпоследовательность, общую для всех последовательностей в наборе последовательностей.
- Задача самой длинной возрастающей подпоследовательности: найти самую длинную возрастающую подпоследовательность заданной последовательности
- Кратчайшая общая проблема суперпоследовательности : найдите самую короткую суперпоследовательность, которая содержит две или более последовательностей в качестве подпоследовательностей.
Подстроки
- Самая длинная общая проблема с подстрокой : найдите самую длинную строку (или строки), которая является подстрокой (или являются подстроками) из двух или более строк
-
Поиск подстроки
- Алгоритм сопоставления строк Ахо – Корасика : алгоритм на основе trie для поиска всех совпадений подстроки с любой из конечного набора строк
- Алгоритм поиска строки Бойера – Мура : амортизированный линейный ( в большинстве случаев сублинейный ) алгоритм поиска подстроки
- Алгоритм Бойера – Мура – Хорспула : упрощение алгоритма Бойера – Мура
- Алгоритм Кнута – Морриса – Пратта : поиск подстроки без повторной проверки совпадающих символов
- Алгоритм поиска строки Рабина – Карпа : эффективный поиск нескольких шаблонов
- Алгоритм сопоставления строк Чжу – Такаока : вариант Бойера – Мура
- Алгоритм Укконена : а линейное время , онлайн алгоритм для построения деревьев суффиксов
-
Подстановочные знаки соответствия
- Богатые Salz ' wildmat : широко используется с открытым исходным кодом рекурсивный алгоритм
- Алгоритм сопоставления подстановочных знаков Краусса : нерекурсивный алгоритм с открытым исходным кодом
Вычислительная математика
Абстрактная алгебра
- Поиск Чьен : рекурсивный алгоритм для определения корней многочленов, определенных над конечным полем
- Алгоритм Шрайера – Симса : вычисление базового и сильного порождающего набора (BSGS) группы перестановок
- Алгоритм Тодда – Кокстера : процедура генерации смежных классов .
Компьютерная алгебра
- Алгоритм Бухбергера : находит базис Грёбнера
- Алгоритм Кантора – Цассенхауза : фактор-полиномы над конечными полями
- Алгоритм Faugère F4 : находит базис Грёбнера (также упоминает алгоритм F5)
- Алгоритм Госпера : найдите суммы гипергеометрических терминов, которые сами являются гипергеометрическими терминами
- Алгоритм завершения Кнута – Бендикса : для переписывания систем правил
- Алгоритм многомерного деления : для многочленов от нескольких неопределенностей
- Алгоритм кенгуру Полларда (также известный как лямбда-алгоритм Полларда): алгоритм для решения задачи дискретного логарифмирования
- Полиномиальное деление в столбик : алгоритм деления многочлена на другой многочлен той же или более низкой степени
- Алгоритм Риша : алгоритм для операции вычисления неопределенного интегрирования (то есть поиска первообразных )
Геометрия
- Задача ближайшей пары : найти пару точек (из набора точек) с наименьшим расстоянием между ними
- Алгоритмы обнаружения столкновений : проверка столкновения или пересечения двух заданных тел.
- Алгоритм конуса : определение точек поверхности
- Алгоритмы корпусных Выпуклые : определение выпуклой оболочки в виде множества точек
- Преобразование евклидова расстояния : вычисляет расстояние между каждой точкой в сетке и дискретным набором точек.
- Геометрическое хеширование : метод эффективного поиска двумерных объектов, представленных дискретными точками, подвергшимися аффинному преобразованию.
- Алгоритм расстояния Гилберта – Джонсона – Кирти : определение наименьшего расстояния между двумя выпуклыми формами.
- Алгоритм Jump-and-Walk : алгоритм определения местоположения точки в триангуляции
- Лапласовское сглаживание : алгоритм сглаживания полигональной сетки
- Пересечение отрезка линии : определение того, пересекаются ли линии, обычно с помощью алгоритма развертки линии
- Алгоритмы минимального ограничивающего прямоугольника : найти ориентированный минимальный ограничивающий прямоугольник, охватывающий набор точек
- Поиск ближайшего соседа : найти ближайшую точку или указывает на точку запроса
- Алгоритмы точки в многоугольнике : проверяет, находится ли данная точка в пределах данного многоугольника.
- Алгоритмы регистрации набора точек : находит преобразование между двумя наборами точек для их оптимального выравнивания.
- Вращающиеся штангенциркули : определить все противоположные пары точек и вершин на выпуклом многоугольнике или выпуклой оболочке .
- Алгоритм шнурка : определение площади многоугольника, вершины которого описываются упорядоченными парами на плоскости
-
Триангуляция
-
Триангуляция Делоне
- Алгоритм Рупперта (также известный как уточнение Делоне): создание качественных триангуляций Делоне
- Второй алгоритм Чу : создание триангуляции Делоне с ограничением качества
- Марширующие треугольники : реконструируйте двумерную геометрию поверхности из неструктурированного облака точек.
- Алгоритмы триангуляции многоугольника : разложите многоугольник на набор треугольников
-
Вороного , геометрический двойной из триангуляции Делоне
- Алгоритм Бойера – Ватсона : создание диаграммы Вороного в любом количестве измерений
- Алгоритм Фортуны : построение диаграммы Вороного
- Квазитриангуляция
-
Триангуляция Делоне
Теоретико-числовые алгоритмы
- Алгоритм двоичного НОД : эффективный способ вычисления НОД.
- Алгоритм умножения Бута
- Метод Чакравалы : циклический алгоритм для решения неопределенных квадратных уравнений, включая уравнение Пелла
- Дискретный логарифм :
- Алгоритм Евклида : вычисляет наибольший общий делитель
- Расширенный алгоритм Евклида : также решает уравнение ax + by = c .
- Целочисленная факторизация : разбиение целого числа на простые множители
- Алгоритмы умножения : быстрое умножение двух чисел
- Модульный квадратный корень : вычисление квадратных корней по модулю простого числа
- Алгоритм Одлыжко – Шёнхаге : вычисляет нетривиальные нули дзета-функции Римана
- Алгоритм Ленстры – Ленстры – Ловаса (также известный как алгоритм LLL): найти короткий, почти ортогональный базис решетки за полиномиальное время
- Тесты на простоту : определение того, является ли данное число простым
Численные алгоритмы
Решение дифференциального уравнения
- Метод Эйлера
- Обратный метод Эйлера
- Правило трапеции (дифференциальные уравнения)
- Линейные многоступенчатые методы
- Методы Рунге – Кутты
- Многосеточные методы ( методы MG), группа алгоритмов решения дифференциальных уравнений с использованием иерархии дискретизаций.
-
Уравнение в частных производных :
- Метод конечных разностей
- Метод Кранка – Николсона для уравнений диффузии.
- Лакса – Вендрофа для волновых уравнений
- Интегрирование Верле ( французское произношение: [vɛʁlɛ] ): интегрировать уравнение движения Ньютона
Элементарные и специальные функции
-
Вычисление π :
- Алгоритм Борвейна : алгоритм для вычисления значения 1 / π
- Алгоритм Гаусса – Лежандра : вычисляет цифры числа пи
- Алгоритм Чудновского : быстрый метод вычисления цифр числа π
- Формула Бейли – Борвейна – Плуффа : (формула BBP) втулочный алгоритм для вычисления n-й двоичной цифры числа π
-
Алгоритмы деления : для вычисления частного и / или остатка двух чисел
- Длинное деление
- Восстановление деления
- Невосстанавливающееся подразделение
- Отделение СТО
- Деление Ньютона-Рафсона : использует метод Ньютона для нахождения обратной величины D и умножает эту обратную величину на N, чтобы найти конечное частное Q.
- Подразделение Гольдшмидта
- Гиперболические и тригонометрические функции:
- Алгоритм BKM : вычисляет элементарные функции с использованием таблицы логарифмов
- CORDIC : вычисляет гиперболические и тригонометрические функции с использованием таблицы арктангенсов.
- Возведение в степень:
- Возведение в степень цепочки сложения : возведение в степень положительными целыми степенями, которое требует минимального числа умножений
- Возведение в степень возведения в квадрат : алгоритм, используемый для быстрого вычисления больших целых степеней числа
- Редукция Монтгомери : алгоритм, который позволяет эффективно выполнять модульную арифметику при большом модуле
-
Алгоритмы умножения : быстрое умножение двух чисел
- Алгоритм умножения Бута: алгоритм умножения, который умножает два двоичных числа со знаком в системе дополнения до двух.
- Алгоритм Фюрера: алгоритм целочисленного умножения для очень больших чисел, обладающий очень низкой асимптотической сложностью
- Алгоритм Карацубы : эффективная процедура умножения больших чисел
- Алгоритм Шёнхаге – Штрассена : асимптотически быстрый алгоритм умножения для больших целых чисел
- Умножение Тоома – Кука : (Тоом3) алгоритм умножения для больших целых чисел.
- Мультипликативные обратные алгоритмы : для вычисления мультипликативного обратного числа (обратного).
- Функции округления : классические способы округления чисел
- Алгоритм втулки : способ вычислить значение математической константы, не зная предшествующих цифр.
- Квадрат и корень N-й степени числа:
- Алгоритм альфа макс плюс бета мин : приближение квадратного корня из суммы двух квадратов
- Методы вычисления квадратных корней
- n- й корневой алгоритм
- Алгоритм смещения корня n-й степени : извлечение корня по цифре
- Суммирование:
- Двоичное разбиение : метод « разделяй и властвуй» , который ускоряет численное вычисление многих типов рядов с помощью рациональных членов.
- Алгоритм суммирования Кахана : более точный метод суммирования чисел с плавающей запятой
- Неограниченный алгоритм
Геометрический
- Отфильтрованная обратная проекция : эффективно вычисляет обратное двумерное преобразование Радона .
- Метод установки уровня (LSM): численный метод отслеживания границ раздела фаз и форм.
Интерполяция и экстраполяция
- Интерполяция Биркгофа : расширение полиномиальной интерполяции
- Кубическая интерполяция
- Эрмита интерполяция
- Интерполяция Лагранжа : интерполяция с использованием полиномов Лагранжа
- Линейная интерполяция : метод аппроксимации кривой с использованием линейных полиномов
- Монотонная кубическая интерполяция : вариант кубической интерполяции, сохраняющий монотонность интерполируемого набора данных.
-
Многомерная интерполяция
- Бикубическая интерполяция , обобщение кубической интерполяции до двух измерений
- Билинейная интерполяция : расширение линейной интерполяции для интерполяции функций двух переменных на регулярной сетке
- Фильтр ланцош ( «Lanzosh»): многомерный метод интерполяции используется для вычисления новых значений для любых данных в цифровой выборке
- Интерполяция ближайшего соседа
- Трикубическая интерполяция , обобщение кубической интерполяции до трех измерений
- Интерполяция Парето : метод оценки медианы и других свойств населения, который следует распределению Парето .
- Полиномиальная интерполяция
- Сплайн-интерполяция : уменьшает ошибку с помощью феномена Рунге .
- Тригонометрическая интерполяция
Линейная алгебра
- Алгоритмы собственных значений
- Процесс Грама – Шмидта : ортогонализирует набор векторов
-
Алгоритмы умножения матриц
- Алгоритм Кэннона : распределенный алгоритм для умножения матриц, особенно подходящий для компьютеров, размещенных в сетке N × N
- Алгоритм Копперсмита – Винограда : умножение квадратных матриц
- Алгоритм Фрейвальдса : рандомизированный алгоритм, используемый для проверки умножения матриц.
- Алгоритм Штрассена : более быстрое умножение матриц
- Решение систем линейных уравнений
- Метод двусопряженных градиентов : решает системы линейных уравнений
- Сопряженный градиент : алгоритм численного решения частных систем линейных уравнений
- Гауссово исключение
- Метод исключения Гаусса – Жордана : решает системы линейных уравнений.
- Метод Гаусса – Зейделя : итеративное решение систем линейных уравнений.
- Рекурсия Левинсона : решает уравнение, содержащее матрицу Теплица
- Метод Стоуна : также известный как строго неявная процедура или SIP, представляет собой алгоритм для решения разреженной линейной системы уравнений.
- Последовательная избыточная релаксация (SOR): метод, используемый для ускорения сходимости метода Гаусса – Зейделя.
- Алгоритм трехдиагональной матрицы ( алгоритм Томаса): решает системы трехдиагональных уравнений
-
Алгоритмы
разреженных матриц
- Алгоритм Cuthill-Макки : уменьшить полосу пропускания в виде симметричной разреженной матрицы
- Алгоритм минимальной степени : переставьте строки и столбцы симметричной разреженной матрицы перед применением разложения Холецкого
- Символьное разложение Холецкого : эффективный способ хранения разреженной матрицы
Монте-Карло
- Выборка Гиббса : генерирует последовательность выборок из совместного распределения вероятностей двух или более случайных величин.
- Гибридный Монте-Карло : генерирует последовательность выборок с использованием гамильтоновой взвешенной цепи Маркова Монте-Карло из распределения вероятностей, из которого трудно выполнить выборку напрямую.
- Алгоритм Метрополиса – Гастингса : используется для создания последовательности выборок из распределения вероятностей одной или нескольких переменных.
- Алгоритм Ванга и Ландау : расширение выборки алгоритма Метрополиса – Гастингса
Численное интегрирование
- Алгоритм MISER : моделирование Монте-Карло, численное интегрирование
Поиск корня
- Метод деления пополам
- Метод ложного положения : аппроксимирует корни функции
- Метод ИТП : оптимальная minmax и суперлинейная сходимость одновременно
- Метод Ньютона : находит нули функций с помощью исчисления
- Метод Галлея : использует первую и вторую производные
- Метод секущей : 2-х точечный, односторонний
- Метод ложного положения и метод Иллинойса: 2 точки, брекетинг
- Метод Риддера : 3-точечное экспоненциальное масштабирование
- Метод Мюллера : трехточечная квадратичная интерполяция
Алгоритмы оптимизации
- Отсечение альфа – бета : поиск по уменьшению количества узлов в алгоритме минимакс.
- Ветвь и переплет
- Алгоритм Брюсса : см. Алгоритм шансов
- Цепное умножение матриц
-
Комбинаторная оптимизация : задачи оптимизации, в которых множество допустимых решений дискретно
- Жадная рандомизированная процедура адаптивного поиска (GRASP): последовательное построение жадного рандомизированного решения и последующие итерационные улучшения его посредством локального поиска
- Венгерский метод : комбинаторный алгоритм оптимизации, который решает задачу о назначении за полиномиальное время
-
Удовлетворение ограничений
- Общие алгоритмы выполнения ограничений
- Алгоритм Чаффа : алгоритм для решения экземпляров проблемы логической выполнимости
- Алгоритм Дэвиса – Патнэма : проверка правильности логической формулы первого порядка
- Дэвис-Putnam-Logemann-Ловеланд алгоритм (DPLL): алгоритм принятия решения выполнимости пропозициональной логики формулы в КНФЕ , то есть для решения CNF-SAT проблем
-
Проблема с
точным покрытием
- Алгоритм X : недетерминированный алгоритм
- Танцующие ссылки : эффективная реализация алгоритма X
- Метод кросс-энтропии : общий подход Монте-Карло к комбинаторной и непрерывной многоэкстремальной оптимизации и выборке важности
- Дифференциальная эволюция
- Динамическое программирование : задачи, демонстрирующие свойства перекрывающихся подзадач и оптимальной подструктуры
- Метод эллипсоидов : алгоритм решения задач выпуклой оптимизации.
-
Эволюционные вычисления : оптимизация, вдохновленная биологическими механизмами эволюции
- Стратегия эволюции
- Программирование экспрессии генов
-
Генетические алгоритмы
- Пропорциональный выбор фитнеса - также известный как выбор колеса рулетки
- Стохастическая универсальная выборка
- Выбор усечения
- Выбор турнира
- Меметический алгоритм
-
Рой интеллект
- Оптимизация колонии муравьев
- Алгоритм пчел : алгоритм поиска, который имитирует поведение роя медоносных пчел в поисках пищи.
- Рой частиц
- Алгоритм Франка-Вульфа : итерационный алгоритм оптимизации первого порядка для выпуклой оптимизации с ограничениями
- Поиск по золотому сечению : алгоритм поиска максимума реальной функции
- Градиентный спуск
- Поиск по сетке
- Поиск гармонии (HS): метаэвристический алгоритм, имитирующий процесс импровизации музыкантов.
- Метод внутренней точки
-
Линейное программирование
- Алгоритм Бенсона : алгоритм для решения линейных векторной оптимизации задач
- Разложение Данцига – Вульфа : алгоритм решения задач линейного программирования специальной структуры
- Отложенная генерация столбца
- Целочисленное линейное программирование : решение задач линейного программирования, в которых некоторые или все неизвестные ограничены целыми значениями.
- Алгоритм Кармаркара : первый достаточно эффективный алгоритм, решающий задачу линейного программирования за полиномиальное время .
- Simplex алгоритм : алгоритм для решения задачи линейного программирования задач
- Линейный поиск
- Локальный поиск : метаэвристика для решения вычислительно трудных задач оптимизации
- Минимакс, используемый в программировании игр
-
Поиск ближайшего соседа (NNS): поиск ближайших точек в метрическом пространстве
- Best Bin First : найти приближенное решение проблемы поиска ближайшего соседа в очень многомерных пространствах
- Метод Ньютона в оптимизации
-
Нелинейная оптимизация
- Метод BFGS : алгоритм нелинейной оптимизации
- Алгоритм Гаусса – Ньютона : алгоритм для решения нелинейных задач наименьших квадратов .
- Алгоритм Левенберга – Марквардта : алгоритм для решения нелинейных задач наименьших квадратов .
- Метод Нелдера – Мида (симплексный метод спуска): алгоритм нелинейной оптимизации.
- Алгоритм Odds ( алгоритм Брюсса): находит оптимальную стратегию для прогнозирования последнего конкретного события в случайной последовательности событий.
- Случайный поиск
- Имитация отжига
- Стохастическое туннелирование
- Алгоритм суммы подмножества
Вычислительная наука
Астрономия
- Алгоритм судного дня : день недели
- Сравнение Целлера - это алгоритм для вычисления дня недели для любой даты в юлианском или григорианском календаре.
- различные пасхальные алгоритмы используются для расчета дня Пасхи
Биоинформатика
- Инструмент поиска базового локального выравнивания, также известный как BLAST: алгоритм для сравнения информации о первичной биологической последовательности.
- Алгоритм Кабша : вычислить оптимальное выравнивание двух наборов точек, чтобы вычислить среднеквадратичное отклонение между двумя белковыми структурами.
- Velvet : набор алгоритмов, управляющих графами де Брейна для сборки геномных последовательностей
- Сортировка по разворотам со знаком : алгоритм понимания геномной эволюции.
- Максимальная экономия (филогенетика) : алгоритм поиска простейшего филогенетического дерева для объяснения заданной матрицы символов.
- UPGMA : дистанционный алгоритм построения филогенетического дерева.
Геонауки
- Формулы Винсенти : быстрый алгоритм для вычисления расстояния между двумя точками широты / долготы на эллипсоиде
- Geohash : алгоритм, являющийся общественным достоянием, который кодирует десятичную пару широты / долготы в виде хэш-строки.
Лингвистика
- Алгоритм Леска : устранение неоднозначности слов
- Алгоритм выделения слов: метод сокращения слов до их основы, основы или корневой формы.
- Алгоритм Сухотина: алгоритм статистической классификации для классификации символов в тексте как гласных или согласных
Медицина
- Алгоритм ESC для диагностики сердечной недостаточности
- Критерии Мэннинга для синдрома раздраженного кишечника
- Алгоритмы диагностики тромбоэмболии легочной артерии
- Техасский проект по разработке алгоритмов лечения
Физика
- Алгоритм ограничения : класс алгоритмов для удовлетворения ограничений для тел, которые подчиняются уравнениям движения Ньютона.
- Алгоритм Демона : метод Монте-Карло для эффективной выборки членов микроканонического ансамбля с заданной энергией
- Алгоритм Фезерстоуна : вычисляет эффекты сил, приложенных к конструкции суставов и звеньев.
- Приближение основного состояния
-
п -Боди проблемы
- Моделирование Барнса – Хата : приближенно решает задачу n тел, которая имеет порядок O ( n log n ) вместо O ( n 2 ), как при моделировании с прямой суммой.
- Быстрый многополюсный метод (FMM): ускоряет расчет дальнодействующих сил.
- Алгоритм подсчета дождевого потока: сводит сложную историю напряжений к количеству элементарных реверсивных напряжений для использования в анализе усталости.
- Sweep and prune : алгоритм широкой фазы, используемый во время обнаружения столкновений, чтобы ограничить количество пар твердых тел, которые необходимо проверить на столкновение.
- Алгоритм VEGAS : метод уменьшения ошибок моделирования Монте-Карло
- Глауберова динамика : метод моделирования модели Изинга на компьютере
Статистика
- Алгоритмы вычисления дисперсии : предотвращение нестабильности и числового переполнения
- Приблизительный алгоритм подсчета : позволяет подсчитывать большое количество событий в небольшом регистре
-
Байесовская статистика
- Алгоритм вложенной выборки : вычислительный подход к проблеме сравнения моделей в байесовской статистике
-
Алгоритмы кластеризации
- Кластеризация с усредненными связями : простой алгоритм агломеративной кластеризации
- Алгоритм кластеризации Canopy : неконтролируемый алгоритм предварительной кластеризации, связанный с алгоритмом K-средних
- Кластеризация с полной связью : простой алгоритм агломеративной кластеризации
- DBSCAN : алгоритм кластеризации на основе плотности
- Алгоритм ожидания-максимизации
-
Нечеткая кластеризация : класс алгоритмов кластеризации, где каждая точка имеет степень принадлежности к кластерам.
- Нечеткие c-средства
- Кластеризация FLAME (нечеткая кластеризация с помощью локальной аппроксимации MEmbership): определение кластеров в плотных частях набора данных и выполнение назначения кластеров исключительно на основе отношений соседства между объектами
- Алгоритм кластеризации KHOPCA : алгоритм локальной кластеризации, который создает иерархические многоскачковые кластеры в статической и мобильной среде.
- k-означает кластеризацию : кластерные объекты на основе атрибутов в разделы
- k-means ++ : вариант этого с использованием модифицированных случайных начальных чисел
- k-medoids : похож на k-means, но выбирает точки данных или medoids в качестве центров
- Алгоритм Линде – Бузо – Грея : алгоритм векторного квантования для получения хорошей кодовой книги
- Алгоритм Ллойда (итерация или релаксация Вороного): группировка точек данных в заданное количество категорий, популярный алгоритм для кластеризации k-средних
- ОПТИКА : алгоритм кластеризации на основе плотности с методом визуальной оценки
- Односвязная кластеризация : простой алгоритм агломеративной кластеризации
- SUBCLU : алгоритм кластеризации подпространств
- Метод Уорда : алгоритм агломеративной кластеризации, расширенный до более общих алгоритмов Ланса – Вильямса.
- Алгоритм кластеризации WACA : алгоритм локальной кластеризации с потенциально многозвенными структурами; для динамических сетей
-
Теория оценок
-
Алгоритм максимизации ожидания Класс связанных алгоритмов для поиска оценок максимального правдоподобия параметров в вероятностных моделях
- Максимизация упорядоченного подмножества ожиданий (OSEM): используется в медицинской визуализации для позитронно-эмиссионной томографии , однофотонной эмиссионной компьютерной томографии и рентгеновской компьютерной томографии.
- Алгоритм шансов ( алгоритм Брюсса) Оптимальный онлайн-поиск выделенного значения в последовательном случайном вводе
- Фильтр Калмана : оцените состояние линейной динамической системы на основе серии зашумленных измерений
-
Алгоритм максимизации ожидания Класс связанных алгоритмов для поиска оценок максимального правдоподобия параметров в вероятностных моделях
- Алгоритм ложного ближайшего соседа (FNN) оценивает фрактальную размерность
-
Скрытая марковская модель
- Алгоритм Баума – Велча : вычисляет оценки максимального правдоподобия и оценки апостериорного режима для параметров скрытой марковской модели.
- Вперед-назад алгоритм : алгоритм динамического программирования для вычисления вероятности конкретной последовательности наблюдений.
- Алгоритм Витерби : найти наиболее вероятную последовательность скрытых состояний в скрытой марковской модели
- Частичная регрессия наименьших квадратов : находит линейную модель, описывающую некоторые предсказанные переменные в терминах других наблюдаемых переменных.
-
Теория массового обслуживания
- Алгоритм Бузена : алгоритм вычисления нормировочной константы G (K) в теореме Гордона – Ньюэлла
- RANSAC (аббревиатура от RANdom SAmple Consensus): итерационный метод оценки параметров математической модели на основе набора наблюдаемых данных, который содержит выбросы.
- Алгоритм подсчета очков : это форма метода Ньютона, используемая для численного решения уравнений максимального правдоподобия.
- Метод Ямартино : вычислить приближение к стандартному отклонению σθ направления ветра θ за один проход через входящие данные.
- Алгоритм Зикгурата : генерирует случайные числа из неравномерного распределения
Информатика
Компьютерная архитектура
- Алгоритм Томасуло : позволяет последовательным инструкциям, которые обычно останавливаются из-за определенных зависимостей, выполняться непоследовательно
Компьютерная графика
- Вырезка
-
Контурные линии и изоповерхности
- Марширующие кубы : извлеките полигональную сетку изоповерхности из трехмерного скалярного поля (иногда называемого вокселями).
- Марширующие квадраты : генерирует контурные линии для двумерного скалярного поля.
- Марширующие тетраэдры : альтернатива маршевым кубам
- Дискретная теорема Грина : алгоритм вычисления двойного интеграла по обобщенной прямоугольной области за постоянное время. Это естественное расширение алгоритма таблицы суммированных площадей.
- Заливка : заполняет связанную область многомерного массива указанным символом.
- Алгоритмы глобального освещения : учитывает прямое освещение и отражение от других объектов.
-
Удаление скрытой поверхности или визуальное определение поверхности
- Алгоритм Ньюэлла : устранение циклов полигонов в сортировке по глубине, необходимой при удалении скрытых поверхностей
- Алгоритм художника : обнаруживает видимые части трехмерного пейзажа.
- Рендеринг строки развертки : создает изображение, перемещая воображаемую линию по изображению.
- Алгоритм Варнока
-
Рисование линии : графический алгоритм аппроксимации отрезка линии на дискретном графическом носителе.
- Линейный алгоритм Брезенхема : отображает точки двумерного массива, чтобы сформировать прямую линию между двумя указанными точками (использует переменные решения)
- Алгоритм линии DDA : отображает точки двумерного массива для формирования прямой линии между 2 указанными точками (использует математику с плавающей запятой)
- Линейный алгоритм Сяолинь Ву : алгоритм линейного сглаживания.
- Алгоритм средней точки круга : алгоритм, используемый для определения точек, необходимых для рисования круга.
- Алгоритм Рамера – Дугласа – Пекера : для «кривой», состоящей из отрезков линии, найти кривую, не слишком отличающуюся, но имеющую меньшее количество точек.
-
Затенение
- Затенение по Гуро : алгоритм для имитации различных эффектов света и цвета на поверхности объекта в трехмерной компьютерной графике.
- Затенение Фонга : алгоритм интерполяции векторов нормали к поверхности для затенения поверхности в трехмерной компьютерной графике
- Slerp (сферическая линейная интерполяция): кватернионная интерполяция с целью анимации трехмерного вращения.
- Таблица суммированных площадей (также известная как целостное изображение): алгоритм для вычисления суммы значений в прямоугольном подмножестве сетки за постоянное время.
Криптография
- Асимметричное (с открытым ключом) шифрование :
-
Цифровые подписи (асимметричная аутентификация):
-
DSA и его варианты:
- ECDSA и детерминированный ECDSA
- EdDSA (Ed25519)
- ЮАР
-
DSA и его варианты:
-
Криптографические хеш-функции (см. Также раздел о кодах аутентификации сообщений):
- БЛЕЙК
- MD5 - Обратите внимание, что теперь есть метод генерации коллизий для MD5.
- РИПЭМД-160
- SHA-1 - обратите внимание, что теперь есть метод генерации коллизий для SHA-1
- SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
- SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
- Тигр (TTH), обычно используется в хэшах дерева Тигра
- БАССЕЙН
-
Криптографически безопасные генераторы псевдослучайных чисел
- Блюм Блюм Шуб - по жесткости факторизации
- Фортуна , задуманная как улучшение алгоритма Ярроу
- Регистр сдвига с линейной обратной связью (примечание: многие алгоритмы на основе LFSR слабые или были сломаны)
- Алгоритм тысячелистника
- Обмен ключами
- Функции вывода ключей , часто используемые для хеширования паролей и растягивания ключей
- Коды аутентификации сообщений (симметричные алгоритмы аутентификации, которые принимают ключ в качестве параметра):
-
Совместное использование секрета, разделение секрета, разделение ключа, M из N алгоритмов
- Схема Блейки
- Схема Шамира
-
Симметричное (секретный ключ) шифрование :
- Advanced Encryption Standard (AES), победитель конкурса NIST , также известный как Rijndael
- Blowfish
- Twofish
- Три рыбы
- Стандарт шифрования данных (DES), иногда алгоритм DE, победитель отборочного конкурса NBS, заменен на AES для большинства целей
- ИДЕЯ
- RC4 (шифр)
- Крошечный алгоритм шифрования (TEA)
- Salsa20 и его обновленный вариант ChaCha20
- Постквантовая криптография
- Алгоритмы доказательства работы
Цифровая логика
- Логическая минимизация
- Алгоритм Куайна – Маккласки : также называется алгоритмом QM, программируемым методом упрощения булевых уравнений.
- Метод Петрика : еще один алгоритм логического упрощения.
- Минимизатор эвристической логики эспрессо : быстрый алгоритм минимизации логических функций.
Машинное обучение и статистическая классификация
- ALOPEX : алгоритм машинного обучения на основе корреляции
- Изучение правил ассоциации : обнаруживайте интересные отношения между переменными, используемые в интеллектуальном анализе данных.
-
Повышение (метаалгоритм) : используйте много слабых учеников, чтобы повысить эффективность
- AdaBoost : адаптивное ускорение
- BrownBoost : алгоритм повышения, который может быть устойчивым к зашумленным наборам данных
- LogitBoost : ускорение логистической регрессии
- LPBoost : ускорение линейного программирования
- Агрегирование бутстрапа (упаковка): метод повышения стабильности и точности классификации
-
Компьютерное зрение
- Grabcut на основе разрезов графика
-
Деревья решений
- Алгоритм C4.5 : расширение ID3
- Алгоритм ID3 (Iterative Dichotomiser 3): используйте эвристику для генерации небольших деревьев решений
-
Кластеризация : класс алгоритмов неконтролируемого обучения для группировки и сортировки связанных входных векторов.
- k-ближайшие соседи (k-NN): метод классификации объектов на основе ближайших обучающих примеров в пространстве признаков
- Алгоритм Линде – Бузо – Грея : алгоритм векторного квантования, используемый для получения хорошей кодовой книги
- Хеширование с учетом местоположения (LSH): метод выполнения вероятностного уменьшения размерности данных большой размерности.
-
Нейронная сеть
- Обратное распространение : метод обучения с учителем, который требует от учителя, который знает или может вычислить желаемый результат для любого заданного ввода.
- Сеть Хопфилда : рекуррентная нейронная сеть, в которой все связи симметричны
- Персептрон : простейший вид нейронной сети прямого распространения: линейный классификатор .
- Импульсно-связанные нейронные сети (PCNN): нейронные модели, предложенные путем моделирования зрительной коры головного мозга кошки и разработанные для высокопроизводительной биомиметической обработки изображений.
- Сеть радиальных базисных функций : искусственная нейронная сеть, которая использует радиальные базисные функции в качестве функций активации.
- Самоорганизующаяся карта : неконтролируемая сеть, которая создает низкоразмерное представление входного пространства обучающих выборок.
- Случайный лес : классификация с использованием множества деревьев решений
-
Обучение с подкреплением :
- Q-обучение : изучает функцию значения действия, которая дает ожидаемую полезность выполнения заданного действия в заданном состоянии и последующего следования фиксированной политике.
- Состояние – Действие – Вознаграждение – Состояние – Действие (SARSA): изучите политику процесса принятия решений Маркова.
- Обучение временной разнице
- Машина вектора релевантности (RVM): аналогична SVM, но обеспечивает вероятностную классификацию
- Обучение с учителем : обучение на примерах (помеченный набор данных, разделенный на обучающий набор и тестовый набор)
-
Машина опорных векторов (SVM): набор методов, которые делят многомерные данные путем нахождения разделяющей гиперплоскости с максимальным запасом между двумя наборами.
- Структурированная SVM : позволяет обучить классификатор для общих структурированных выходных меток.
- Алгоритм Винноу : связан с перцептроном, но использует схему обновления мультипликативного веса.
Теория языка программирования
- C3 линеаризация : алгоритм, используемый в первую очередь для получения последовательной линеаризации иерархии множественного наследования в объектно-ориентированном программировании.
- Алгоритм Чейтина : восходящий алгоритм распределения регистров раскраски графа, который использует стоимость / степень в качестве метрики распространения
- Алгоритм вывода типа Хиндли-Милнера
- Алгоритм Rete : эффективный алгоритм сопоставления с образцом для реализации систем производственных правил
- Алгоритм Сетхи-Уллмана : генерирует оптимальный код для арифметических выражений
Парсинг
- Алгоритм CYK : алгоритм O (n 3 ) для разбора контекстно-свободных грамматик в нормальной форме Хомского
- Парсер Эрли : еще один алгоритм O (n 3 ) для разбора любой контекстно-свободной грамматики
- РВО анализатор : алгоритм для разбора любой контекстно-свободной грамматики по Масару Томита . Он настроен для детерминированных грамматик, на которых он выполняет почти линейное время и O (n 3 ) в худшем случае.
- Внутренний-внешний алгоритм : алгоритм O (n 3 ) для переоценки производственных вероятностей в вероятностных контекстно-свободных грамматиках
- LL-синтаксический анализатор : относительно простой алгоритм синтаксического анализа с линейным временем для ограниченного класса контекстно-свободных грамматик.
- Парсер LR : более сложный алгоритм синтаксического анализа с линейным временем для более широкого класса контекстно-свободных грамматик . Варианты:
- Парсер Packrat : алгоритм синтаксического анализа с линейным временем , поддерживающий некоторые контекстно-свободные грамматики и грамматики синтаксического анализа выражений.
- Парсер с рекурсивным спуском : нисходящий синтаксический анализатор, подходящий для грамматик LL ( k )
- Алгоритм маневрового двора : преобразование математического выражения с инфиксной нотацией в постфиксное
- Парсер Пратта
- Лексический анализ
Квантовые алгоритмы
- Алгоритм Дойча – Йожи : критерий баланса для булевой функции
- Алгоритм Гровера : обеспечивает квадратичное ускорение для многих задач поиска.
- Алгоритм Шора : обеспечивает экспоненциальное ускорение (по сравнению с известными в настоящее время неквантовыми алгоритмами) для факторизации числа.
- Алгоритм Саймона : обеспечивает доказуемо экспоненциальное ускорение (по сравнению с любым неквантовым алгоритмом) для проблемы черного ящика.
Теория вычислений и автоматов
- Алгоритм Hopcroft в , алгоритм Мура и алгоритм Brzozowski в : алгоритмы минимизации числа состояний детерминированного конечного автомата
- Конструкция Powerset : алгоритм преобразования недетерминированного автомата в детерминированный автомат .
- Алгоритм Тарского – Куратовского : недетерминированный алгоритм, который обеспечивает верхнюю границу сложности формул в арифметической иерархии и аналитической иерархии.
Теория информации и обработка сигналов
Теория кодирования
Обнаружение и исправление ошибок
- Коды BCH
- Алгоритм BCJR : декодирование кодов с исправлением ошибок, определенных на решетках (в основном сверточных кодов)
- Прямое исправление ошибок
- Код Грея
-
Коды Хэмминга
- Хэмминга (7,4) : код Хэмминга, который кодирует 4 бита данных в 7 бит, добавляя 3 бита четности.
- Расстояние Хэмминга : сумма различающихся позиций
- Вес Хэмминга (подсчет населения): найти количество 1 бит в двоичном слове
-
Проверки избыточности
- Адлер-32
- Циклическая проверка избыточности
- Алгоритм дамма
- Контрольная сумма Флетчера
- Продольный контроль избыточности (LRC)
- Алгоритм Луна : метод проверки идентификационных номеров
- Алгоритм Luhn mod N : расширение Luhn на нечисловые символы
- Четность : простой / быстрый метод обнаружения ошибок
- Алгоритм Верхоффа
Алгоритмы сжатия без потерь
- Преобразование Барроуза – Уиллера : предварительная обработка полезна для улучшения сжатия без потерь
- Взвешивание дерева контекста
- Дельта-кодирование : помощь в сжатии данных, в которых часто встречаются последовательные данные
- Динамическое марковское сжатие : сжатие с использованием прогнозирующего арифметического кодирования
-
Словарные кодеры
- Кодирование пар байтов (BPE)
- Сдувать
-
Лемпель-Зив
- LZ77 и LZ78
- Лемпель – Зив Джефф Бонвик (LZJB)
- Цепной алгоритм Лемпеля – Зива – Маркова (LZMA)
- Лемпель – Зив – Оберхумер (LZO): ориентированный на скорость
- Лемпель – Зив – Стац (LZS)
- Лемпель – Зив – Сторер – Шиманский (ЛЗСС)
- Лемпель – Зив – Велч (LZW)
- LZWL : слоговый вариант
- LZX
- Лемпель – Зив Росс Уильямс (LZRW)
-
Энтропийное кодирование : схема кодирования, которая присваивает коды символам, чтобы согласовать длину кода с вероятностями символов.
-
Арифметическое кодирование : расширенное энтропийное кодирование
- Кодирование диапазона : то же, что и арифметическое кодирование , но немного по-другому.
-
Кодирование Хаффмана : простое сжатие без потерь с использованием относительных частот символов
- Адаптивное кодирование Хаффмана : метод адаптивного кодирования на основе кодирования Хаффмана
- Алгоритм слияния пакетов : оптимизирует кодирование Хаффмана с учетом ограничения длины кодовых строк.
- Кодирование Шеннона – Фано
- Кодирование Шеннона – Фано – Элиаса : предшественник арифметического кодирования
-
Арифметическое кодирование : расширенное энтропийное кодирование
-
Энтропийное кодирование с известными энтропийными характеристиками
- Кодирование Голомба : форма энтропийного кодирования, оптимальная для алфавитов, следующих геометрическим распределениям
- Кодирование риса : форма энтропийного кодирования, оптимальная для алфавитов, следующих геометрическим распределениям.
- Усеченное двоичное кодирование
- Унарное кодирование : код, представляющий число n с n единицами, за которыми следует ноль
-
Универсальные коды : кодирует положительные целые числа в двоичные кодовые слова.
- Элиас дельта , гамма , и омега - кодирование
- Экспоненциально-голомбское кодирование
- Кодирование Фибоначчи
- Кодирование Левенштейна
- Быстрая эффективная система сжатия изображений без потерь (FELICS): алгоритм сжатия изображений без потерь
- Инкрементное кодирование : дельта-кодирование, применяемое к последовательностям строк
- Прогнозирование путем частичного сопоставления (PPM): метод адаптивного статистического сжатия данных, основанный на контекстном моделировании и прогнозировании.
- Кодирование длин серий : сжатие данных без потерь с использованием строк повторяющихся символов
- Алгоритм SEQUITUR : сжатие без потерь с помощью инкрементального грамматического вывода в строке
Алгоритмы сжатия с потерями
- 3Dc : алгоритм сжатия данных с потерями для карт нормалей
-
Сжатие
звука и речи
- Алгоритм A-law : стандартный алгоритм компандирования
- Линейное предсказание с кодовым возбуждением (CELP): сжатие речи с низкой скоростью передачи данных
- Кодирование с линейным предсказанием (LPC): сжатие с потерями путем представления спектральной огибающей цифрового сигнала речи в сжатой форме
- Алгоритм мю-закона : стандартный
- Искаженное линейное прогнозирующее кодирование (WLPC)
- Block Truncation Coding (BTC): метод сжатия изображений с потерями для изображений в оттенках серого.
- Встроенный вейвлет нулевого дерева (EZW)
- Алгоритмы быстрого косинусного преобразования ( алгоритмы FCT): эффективное вычисление дискретного косинусного преобразования (DCT)
- Фрактальное сжатие : метод сжатия изображений с помощью фракталов.
- Установить секционирование в иерархических деревьях (SPIHT)
- Вейвлет-сжатие : форма сжатия данных, хорошо подходящая для сжатия изображений (иногда также сжатие видео и аудио)
Цифровая обработка сигналов
- Адаптивно-аддитивный алгоритм ( алгоритм AA): найти фазу пространственной частоты наблюдаемого источника волны
- Дискретное преобразование Фурье : определяет частоты, содержащиеся в (сегменте) сигнала
- Алгоритм быстрого сворачивания : эффективный алгоритм для обнаружения приблизительно периодических событий в данных временных рядов
- Алгоритм Гершберга – Сакстона : алгоритм восстановления фазы для оптических плоскостей
- Алгоритм Герцеля : определите конкретную частотную составляющую в сигнале. Может использоваться для декодирования цифр DTMF .
- Синтез струн Karplus-Strong : синтез физического моделирования для имитации звука ударной или щипковой струны или некоторых типов перкуссии.
Обработка изображений
- Повышение контрастности
- Выравнивание гистограммы: используйте гистограмму для улучшения контрастности изображения
- Адаптивное выравнивание гистограммы : выравнивание гистограммы, которое адаптируется к локальным изменениям контрастности
- Маркировка связанных компонентов : поиск и маркировка непересекающихся областей
- Дизеринг и полутонирование
- Алгоритм карты различий Эльзера : алгоритм поиска общих проблем удовлетворения ограничений. Первоначально использовался для рентгеновской дифракционной микроскопии.
-
Обнаружение функции
- Детектор Canny Edge : обнаруживает широкий диапазон краев на изображениях
- Обобщенное преобразование Хафа
- Преобразование Хафа
- Марр-Хилдрет алгоритм : раннее обнаружение края алгоритм
- SIFT (масштабно-инвариантное преобразование признаков): это алгоритм для обнаружения и описания локальных особенностей на изображениях.
- SURF ( Ускоренные надежные функции ) : это надежный детектор локальных особенностей, впервые представленный Гербертом Бей и др. в 2006 году это может быть использовано в задачах компьютерного зрения, таких как распознавание объектов или трехмерная реконструкция. Частично он основан на дескрипторе SIFT. Стандартная версия SURF в несколько раз быстрее, чем SIFT, и, по утверждениям ее авторов, более устойчива к различным преобразованиям изображений, чем SIFT.
- Деконволюция Ричардсона – Люси : алгоритм устранения размытия изображения
- Слепая деконволюция : алгоритм устранения размытости изображения, когда функция рассеяния точки неизвестна.
- Медианная фильтрация
- Резьба по шву : алгоритм изменения размера изображения с учетом содержимого
-
Сегментация : разделите цифровое изображение на две или более областей.
- Алгоритм GrowCut : интерактивный алгоритм сегментации
- Алгоритм случайного блуждания
- Регион растет
- Трансформация водораздела : класс алгоритмов, основанный на аналогии водораздела
Программная инженерия
- Алгоритмы кеширования
- Преобразование CHS : преобразование между системами адресации дисков
- Double dabble : преобразование двоичных чисел в BCD
-
Хеш-функция : преобразование большого объема данных, возможно, переменного размера, в небольшой элемент данных, обычно одно целое число, которое может служить индексом в массиве.
- Хеш-функция Фаулера – Нолла – Во : быстрая с низкой частотой конфликтов
- Хеширование Пирсона : вычисляет только 8-битное значение, оптимизировано для 8-битных компьютеров.
- Зобристское хеширование : используется при реализации таблиц транспонирования
- Алгоритм сортировки Unicode
- Алгоритм обмена Xor : меняет местами значения двух переменных без использования буфера
Алгоритмы базы данных
- Алгоритмы восстановления и изоляции, использующие семантику (ARIES): восстановление транзакций
- Алгоритмы соединения
Алгоритмы распределенных систем
- Синхронизация часов
- Консенсус (информатика) : согласование одного значения или истории среди ненадежных процессоров
- Обнаружение завершения процесса
- Упорядочение Лампорта : а частичное упорядочение событий на основе произошли, до связи
- Выборы лидера : метод динамического выбора координатора
- Взаимное исключение
- Алгоритм моментального снимка : запись согласованного глобального состояния асинхронной системы
- Векторные часы : создание частичного упорядочивания событий в распределенной системе и обнаружение нарушений причинно-следственной связи.
Алгоритмы выделения и освобождения памяти
- Распределение памяти приятеля : алгоритм распределения памяти таким образом, чтобы фрагментация была меньше.
-
Сборщики мусора
- Алгоритм Чейни : улучшение полупространственного коллектора
- Сборщик мусора поколений : быстрые сборщики мусора, которые разделяют память по возрасту.
- Алгоритм Mark-compact : комбинация алгоритма mark-sweep и алгоритма копирования Чейни
- Отметить и развернуть
- Коллекционер полупространства : коллекционер раннего копирования.
- Подсчет ссылок
Сети
- Алгоритм Карна : решает проблему получения точных оценок времени приема-передачи сообщений при использовании TCP.
- Алгоритм Лулео : метод эффективного хранения и поиска таблиц интернет-маршрутизации
-
Перегрузка сети
- Экспоненциальная отсрочка
- Алгоритм Нагла : повышение эффективности сетей TCP / IP за счет объединения пакетов
- Усеченная двоичная экспоненциальная отсрочка
Алгоритмы операционных систем
- Алгоритм Банкира : алгоритм, используемый для предотвращения тупиковых ситуаций.
-
Алгоритмы замены страниц : выбор страницы-жертвы в условиях нехватки памяти.
- Адаптивный кеш замещения : производительность лучше, чем у LRU
- Часы с адаптивной заменой (CAR): это алгоритм замены страниц, который имеет производительность, сопоставимую с адаптивным кешем замены.
Синхронизация процессов
Планирование
- Первое планирование на самый ранний срок
- Планирование справедливого распределения
- Планирование минимального перерыва в работе
- Планирование списка
- Многоуровневая очередь обратной связи
- Скоростно-монотонное планирование
- Планирование с циклическим перебором
- Самая короткая работа следующая
- Наименьшее оставшееся время
- Алгоритм верхних узлов : управление календарем ресурсов
Планирование ввода / вывода
Планирование диска
- Алгоритм лифта : алгоритм планирования диска, который работает как лифт.
- Кратчайший поиск в первую очередь : алгоритм планирования диска для сокращения времени поиска .
Смотрите также
- Список структур данных
- Список алгоритмов машинного обучения
- Список алгоритмов поиска пути
- Список общих тем алгоритмов
- Список терминов, относящихся к алгоритмам и структурам данных
- Эвристический