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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Список алгоритмов»  -  новости  · газеты  · книги  · ученый  · JSTOR ( июль 2017 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

Автоматизированное планирование [ править ]

Комбинаторные алгоритмы [ править ]

Общие комбинаторные алгоритмы [ править ]

• Алгоритм Брента : находит цикл в итерациях значений функции, используя только два итератора
• Алгоритм поиска цикла Флойда : находит цикл в итерациях значений функции
• Алгоритм Гейла – Шепли : решает проблему стабильного брака
• Генераторы псевдослучайных чисел (равномерно распределенные - см. Также Список генераторов псевдослучайных чисел для других ГПСЧ с различной степенью сходимости и различным статистическим качеством):
  • Генератор желудя
  • Блюм Блюм Шуб
  • Генератор Фибоначчи с запаздыванием
  • Линейный конгруэнтный генератор
  • Мерсенн Твистер

Графические алгоритмы [ править ]

• Алгоритм раскраски: Алгоритм раскраски графиков.
• Алгоритм Хопкрофта – Карпа : преобразование двудольного графа в соответствие максимальной мощности
• Венгерский алгоритм : алгоритм поиска идеального соответствия
• Кодирование Прюфера : преобразование между помеченным деревом и его последовательностью Прюфера
• Автономный алгоритм наименьших общих предков Тарьяна : вычисление наименьших общих предков для пар узлов в дереве
• Топологическая сортировка : находит линейный порядок узлов (например, заданий) на основе их зависимостей.

Рисование графика [ править ]

• Алгоритмы, основанные на силе (также известные как алгоритмы, основанные на силе или пружинный алгоритм)
• Спектральный план

Теория сети [ править ]

• Сетевой анализ
  • Анализ ссылок
    • Алгоритм Гирвана – Ньюмана : обнаружение сообществ в сложных системах
    • Анализ веб-ссылок
      • Поиск тем, вызванный гиперссылками (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 алгоритм слияния
• Объединение (слияние, при этом элементы на выходе не повторяются)

Перестановки последовательностей [ править ]

• Перемешивание Фишера – Йетса (также известное как перемешивание Кнута): случайное перемешивание конечного набора
• Алгоритм Шенстеда : строит пару таблиц Юнга из перестановки
• Алгоритм Штейнхауса – Джонсона – Троттера (также известный как алгоритм Джонсона – Троттера): генерировать перестановки путем транспонирования элементов
• Алгоритм генерации перестановки кучи : элементы обмена для генерации следующей перестановки

Комбинации последовательностей [ править ]

Выравнивание последовательности [ править ]

• Динамическое искажение времени : измерьте сходство между двумя последовательностями, которые могут различаться по времени или скорости.
• Алгоритм Хиршберга : находит выравнивание последовательностей между двумя последовательностями с наименьшими затратами на основании их расстояния Левенштейна.
• Алгоритм Нидлмана – Вунша : найти глобальное выравнивание между двумя последовательностями
• Алгоритм Смита – Уотермана : найти локальное выравнивание последовательностей

Сортировка последовательности [ править ]

Эта статья противоречит статье Sorting_algorithm # Comparison_of_algorithms . См. Обсуждение на связанной странице обсуждения . ( Март 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

• Обменные сорта
  • Пузырьковая сортировка : для каждой пары индексов меняйте местами элементы, если они вышли из строя
  • Сортировка коктейльных шейкеров или двунаправленная пузырьковая сортировка, пузырьковая сортировка, перемещающаяся по списку поочередно спереди назад и сзади вперед
  • Расческа сортировка
  • Сортировка гномов
  • Сортировка по четным и нечетным
  • Быстрая сортировка : разделите список на два, причем все элементы в первом списке идут перед всеми элементами во втором списке .; затем отсортируйте два списка. Часто метод выбора
• Юмористический или неэффективный
  • Богосорт
  • Stooge sort
• Гибридный
  • Flashsort
  • Introsort : начните с быстрой сортировки и переключитесь на heapsort, когда глубина рекурсии превышает определенный уровень.
  • Timsort : адаптивный алгоритм, полученный на основе сортировки слиянием и сортировки вставкой. Используется в Python 2.3 и выше, а также в Java SE 7.
• Вставки
  • Сортировка вставкой: определите, где текущий элемент находится в списке отсортированных, и вставьте его туда
  • Сортировка библиотеки
  • Сортировка терпения
  • Сортировка оболочки : попытка улучшить сортировку вставками
  • Сортировка дерева ( сортировка двоичного дерева): построить двоичное дерево, затем пройти по нему, чтобы создать отсортированный список
  • Циклическая сортировка : на месте с теоретически оптимальным количеством записей
• Сортировка слияния
  • Сортировка слиянием : отсортируйте первую и вторую половину списка отдельно, затем объедините отсортированные списки
  • Slowsort
  • Сортировка прядей
• Несравнительные сорта
  • Бусина сортировка
  • Ковшовая сортировка
  • Burstsort : построить компактный, кэш эффективного Trie взрыва , а затем пройти через него , чтобы создать упорядоченный выход
  • Счетная сортировка
  • Сорт голубятни
  • Сортировка почтальона : вариант сортировки по ведру, использующий иерархическую структуру
  • Radix sort : сортирует строки по буквам
• Выборочные сорта
  • Heapsort : преобразовать список в кучу, продолжать удалять самый большой элемент из кучи и добавлять его в конец списка
  • Сортировка по выбору : выберите наименьший из оставшихся элементов, добавьте его в конец отсортированного списка
  • Гладкая сортировка
• Другой
  • Bitonic сортировщик
  • Сортировка блинов
  • Сортировка спагетти
  • Топологическая сортировка
• Неизвестный класс
  • Samplesort

Подпоследовательности [ править ]

• Алгоритм Кадане : находит максимальный подмассив любого размера
• Задача самой длинной общей подпоследовательности : найти самую длинную подпоследовательность, общую для всех последовательностей в наборе последовательностей.
• Задача самой длинной возрастающей подпоследовательности: найти самую длинную возрастающую подпоследовательность заданной последовательности
• Кратчайшая общая проблема суперпоследовательности : найдите самую короткую суперпоследовательность, которая содержит две или более последовательностей в качестве подпоследовательностей.

Подстроки [ править ]

• Самая длинная общая проблема с подстрокой : найдите самую длинную строку (или строки), которая является подстрокой (или являются подстроками) из двух или более строк
• Поиск подстроки
  • Алгоритм сопоставления строк Ахо – Корасика : алгоритм на основе trie для поиска всех совпадений подстроки с любой из конечного набора строк
  • Алгоритм поиска строки Бойера – Мура : амортизированный линейный ( в большинстве случаев сублинейный ) алгоритм поиска подстроки
  • Алгоритм Бойера – Мура – ​​Хорспула : упрощение алгоритма Бойера – Мура
  • Алгоритм Кнута – Морриса – Пратта : поиск подстроки без повторной проверки совпадающих символов
  • Алгоритм поиска строки Рабина – Карпа : эффективный поиск нескольких шаблонов
  • Алгоритм сопоставления строк Чжу – Такаока : вариант Бойера – Мура
• Алгоритм Укконена : а линейное время , онлайн алгоритм для построения деревьев суффиксов
• Подстановочные знаки соответствия
  • Богатые Salz ' wildmat : широко используется с открытым исходным кодом рекурсивный алгоритм
  • Алгоритм сопоставления подстановочных знаков Краусса : нерекурсивный алгоритм с открытым исходным кодом

Вычислительная математика [ править ]

Абстрактная алгебра [ править ]

• Поиск Чьен : рекурсивный алгоритм для определения корней многочленов, определенных над конечным полем
• Алгоритм Шрайера – Симса : вычисление базового и сильного порождающего набора (BSGS) группы перестановок
• Алгоритм Тодда – Кокстера : процедура генерации смежных классов .

Компьютерная алгебра [ править ]

• Алгоритм Бухбергера : находит базис Грёбнера
• Алгоритм Кантора – Цассенхауза : фактор-полиномы над конечными полями
• Алгоритм Faugère F4 : находит базис Грёбнера (также упоминает алгоритм F5)
• Алгоритм Госпера : найдите суммы гипергеометрических терминов, которые сами являются гипергеометрическими терминами
• Алгоритм завершения Кнута – Бендикса : для переписывания систем правил
• Алгоритм многомерного деления : для многочленов от нескольких неопределенностей
• Алгоритм кенгуру Полларда (также известный как лямбда-алгоритм Полларда): алгоритм для решения задачи дискретного логарифмирования
• Полиномиальное деление в столбик : алгоритм деления многочлена на другой многочлен той же или более низкой степени
• Алгоритм Риша : алгоритм для операции вычисления неопределенного интегрирования (то есть поиска первообразных )

Геометрия [ править ]

• Задача ближайшей пары : найти пару точек (из набора точек) с наименьшим расстоянием между ними
• Алгоритмы обнаружения столкновений : проверка столкновения или пересечения двух заданных тел.
• Алгоритм конуса : определение точек поверхности
• Алгоритмы корпусных Выпуклые : определение выпуклой оболочки в виде множества точек
  • Сканирование Грэма
  • Quickhull
  • Алгоритм упаковки подарков или марш Джарвиса
  • Алгоритм Чана
  • Алгоритм Киркпатрика – Зейделя
• Преобразование евклидова расстояния : вычисляет расстояние между каждой точкой в ​​сетке и дискретным набором точек.
• Геометрическое хеширование : метод эффективного поиска двумерных объектов, представленных дискретными точками, подвергшимися аффинному преобразованию.
• Алгоритм расстояния Гилберта – Джонсона – Кирти : определение наименьшего расстояния между двумя выпуклыми формами.
• Алгоритм Jump-and-Walk : алгоритм определения местоположения точки в триангуляции
• Лапласовское сглаживание : алгоритм сглаживания полигональной сетки
• Пересечение отрезка линии : определение того, пересекаются ли линии, обычно с помощью алгоритма развертки линии
  • Алгоритм Бентли – Оттмана
  • Алгоритм Шамоса – Хои
• Алгоритмы минимального ограничивающего прямоугольника : найти ориентированный минимальный ограничивающий прямоугольник, охватывающий набор точек
• Поиск ближайшего соседа : найти ближайшую точку или указывает на точку запроса
• Алгоритмы точки в многоугольнике : проверяет, находится ли данная точка в пределах данного многоугольника.
• Алгоритмы регистрации набора точек : находит преобразование между двумя наборами точек для их оптимального выравнивания.
• Вращающиеся штангенциркули : определить все противоположные пары точек и вершин на выпуклом многоугольнике или выпуклой оболочке .
• Алгоритм шнурка : определить площадь многоугольника, вершины которого описываются упорядоченными парами на плоскости
• Триангуляция
  • Триангуляция Делоне
    • Алгоритм Рупперта (также известный как уточнение Делоне): создание качественных триангуляций Делоне
    • Второй алгоритм Чу : создание триангуляции Делоне с ограничением качества
  • Марширующие треугольники : реконструируйте двумерную геометрию поверхности из неструктурированного облака точек.
  • Алгоритмы триангуляции многоугольника : разложите многоугольник на набор треугольников
  • Вороного , геометрический двойной из триангуляции Делоне
    • Алгоритм Бойера – Ватсона : создание диаграммы Вороного в любом количестве измерений
    • Алгоритм Фортуны : построение диаграммы Вороного
  • Квазитриангуляция

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

• Алгоритм двоичного НОД : эффективный способ вычисления НОД.
• Алгоритм умножения Бута
• Метод Чакравалы : циклический алгоритм для решения неопределенных квадратных уравнений, включая уравнение Пелла
• Дискретный логарифм :
  • Бэби-степ гигантский шаг
  • Алгоритм расчета индекса
  • Алгоритм ро Полларда для логарифмов
  • Алгоритм Полига – Хеллмана
• Алгоритм Евклида : вычисляет наибольший общий делитель
• Расширенный алгоритм Евклида : также решает уравнение ax  +  by  =  c .
• Целочисленная факторизация : разбиение целого числа на простые множители
  • Конгруэнтность квадратов
  • Алгоритм Диксона
  • Метод факторизации Ферма
  • Общее числовое поле сито
  • Факторизация эллиптической кривой Ленстры
  •  Алгоритм Полларда p - 1
  • Алгоритм ро Полларда
  • алгоритм простой факторизации
  • Квадратное сито
  • Алгоритм Шора
  • Специальное числовое сито
  • Судебное отделение
• Алгоритмы умножения : быстрое умножение двух чисел
  • Алгоритм Карацубы
  • Алгоритм Шёнхаге – Штрассена
  • Умножение Тоома – Кука
• Модульный квадратный корень : вычисление квадратных корней по модулю простого числа
  • Алгоритм Тонелли – Шанкса
  • Алгоритм Чиполлы
  • Алгоритм поиска корня Берлекампа
• Алгоритм Одлыжко – Шёнхаге : вычисляет нетривиальные нули дзета-функции Римана
• Алгоритм Ленстры – Ленстры – Ловаса (также известный как алгоритм LLL): найти короткий, почти ортогональный базис решетки за полиномиальное время
• Тесты на простоту : определение того, является ли данное число простым
  • Тест на простоту AKS
  • Тест на простоту Baillie-PSW
  • Тест на простоту Ферма
  • Тест на простоту Лукаса
  • Тест на простоту Миллера – Рабина
  • Сито Аткина
  • Сито Эратосфена
  • Сито Сундарама

Численные алгоритмы [ править ]

Решение дифференциального уравнения [ править ]

• Метод Эйлера
• Обратный метод Эйлера
• Правило трапеции (дифференциальные уравнения)
• Линейные многоступенчатые методы
• Методы Рунге – Кутты
  • Интегрирование Эйлера
• Многосеточные методы ( методы MG), группа алгоритмов решения дифференциальных уравнений с использованием иерархии дискретизаций.
• Уравнение в частных производных :
  • Метод конечных разностей
  • Метод Кранка – Николсона для уравнений диффузии.
  • Лакса-Вендрофа для волновых уравнений
• Интегрирование Верле ( французское произношение: [vɛʁlɛ] ): интегрировать уравнение движения Ньютона

Элементарные и специальные функции [ править ]

• Вычисление π :
  • Алгоритм Борвейна : алгоритм для вычисления значения 1 / π
  • Алгоритм Гаусса – Лежандра : вычисляет цифры числа пи
  • Алгоритм Чудновского : быстрый метод вычисления цифр числа π
  • Формула Бейли – Борвейна – Плуффа : (формула BBP) втулочный алгоритм для вычисления n-й двоичной цифры числа π
• Алгоритмы деления : для вычисления частного и / или остатка двух чисел
  • Длинное деление
  • Восстановление деления
  • Невосстанавливающееся подразделение
  • Отделение СТО
  • Деление Ньютона-Рафсона : использует метод Ньютона для нахождения обратной величины D и умножает эту обратную величину на N, чтобы найти конечное частное Q.
  • Подразделение Гольдшмидта
• Гиперболические и тригонометрические функции:
  • Алгоритм BKM : вычисление элементарных функций с использованием таблицы логарифмов
  • CORDIC : вычисление гиперболических и тригонометрических функций с использованием таблицы арктангенсов
• Возведение в степень:
  • Возведение в степень цепочки сложения : возведение в степень положительными целыми степенями, которое требует минимального числа умножений
  • Возведение в степень возведения в квадрат : алгоритм, используемый для быстрого вычисления больших целых степеней числа
• Редукция Монтгомери : алгоритм, который позволяет эффективно выполнять модульную арифметику при большом модуле
• Алгоритмы умножения : быстрое умножение двух чисел
  • Алгоритм умножения Бута: алгоритм умножения, который умножает два двоичных числа со знаком в системе дополнения до двух.
  • Алгоритм Фюрера: алгоритм целочисленного умножения для очень больших чисел, обладающий очень низкой асимптотической сложностью
  • Алгоритм Карацубы : эффективная процедура умножения больших чисел
  • Алгоритм Шёнхаге – Штрассена : асимптотически быстрый алгоритм умножения для больших целых чисел
  • Умножение Тоома – Кука : (Тоом3) алгоритм умножения для больших целых чисел.
• Мультипликативные обратные алгоритмы : для вычисления мультипликативного обратного числа (обратного).
  • Метод Ньютона
• Функции округления : классические способы округления чисел
• Алгоритм втулки : способ вычислить значение математической константы, не зная предшествующих цифр.
• Квадрат и корень N-й степени числа:
  • Алгоритм альфа макс плюс бета мин : приближение квадратного корня из суммы двух квадратов
  • Методы вычисления квадратных корней
  • n- й корневой алгоритм
  • Алгоритм смещения корня n-й степени : извлечение корня по цифрам
• Суммирование:
  • Двоичное разбиение : метод « разделяй и властвуй» , который ускоряет численное вычисление многих типов рядов с помощью рациональных членов.
  • Алгоритм суммирования Кахана : более точный метод суммирования чисел с плавающей запятой
• Неограниченный алгоритм

Геометрический [ править ]

• Отфильтрованная обратная проекция : эффективное вычисление обратного двумерного преобразования Радона .
• Метод установки уровня (LSM): численный метод отслеживания границ раздела фаз и форм.

Интерполяция и экстраполяция [ править ]

• Интерполяция Биркгофа : расширение полиномиальной интерполяции
• Кубическая интерполяция
• Эрмита интерполяция
• Интерполяция Лагранжа : интерполяция с использованием полиномов Лагранжа
• Линейная интерполяция : метод аппроксимации кривой с использованием линейных полиномов
• Монотонная кубическая интерполяция : вариант кубической интерполяции, сохраняющий монотонность интерполируемого набора данных.
• Многомерная интерполяция
  • Бикубическая интерполяция , обобщение кубической интерполяции до двух измерений
  • Билинейная интерполяция : расширение линейной интерполяции для интерполяции функций двух переменных на регулярной сетке
  • Фильтр ланцош ( «Lanzosh»): многомерный метод интерполяции используется для вычисления новых значений для любых данных в цифровой выборке
  • Интерполяция ближайшего соседа
  • Трикубическая интерполяция , обобщение кубической интерполяции до трех измерений
• Интерполяция Парето : метод оценки медианы и других свойств населения, который следует распределению Парето .
• Полиномиальная интерполяция
  • Алгоритм Невилла
• Сплайн-интерполяция : уменьшает ошибку с помощью феномена Рунге .
  • Алгоритм Де Бура : B-сплайны
  • Алгоритм де Кастельжау : кривые Безье
• Тригонометрическая интерполяция

Линейная алгебра [ править ]

• Алгоритмы собственных значений
  • Итерация Арнольди
  • Обратная итерация
  • Метод Якоби
  • Итерация Ланцоша
  • Итерация мощности
  • QR-алгоритм
  • Итерация фактора Рэлея
• Процесс Грама – Шмидта : ортогонализирует набор векторов
• Алгоритмы умножения матриц
  • Алгоритм Кэннона : распределенный алгоритм для умножения матриц, особенно подходящий для компьютеров, размещенных в сетке N × N
  • Алгоритм Копперсмита – Винограда : умножение квадратных матриц
  • Алгоритм Фрейвальдса : рандомизированный алгоритм, используемый для проверки умножения матриц.
  • Алгоритм Штрассена : более быстрое умножение матриц

• Решение систем линейных уравнений
  • Метод двусопряженных градиентов : решает системы линейных уравнений
  • Сопряженный градиент : алгоритм численного решения частных систем линейных уравнений
  • Гауссово исключение
  • Метод исключения Гаусса – Жордана : решает системы линейных уравнений.
  • Метод Гаусса – Зейделя : итеративное решение систем линейных уравнений.
  • Рекурсия Левинсона : решает уравнение, содержащее матрицу Теплица
  • Метод Стоуна : также известный как строго неявная процедура или SIP, представляет собой алгоритм решения разреженной линейной системы уравнений.
  • Последовательная избыточная релаксация (SOR): метод, используемый для ускорения сходимости метода Гаусса – Зейделя.
  • Алгоритм трехдиагональной матрицы ( алгоритм Томаса): решает системы трехдиагональных уравнений
• Алгоритмы разреженных матриц
  • Алгоритм Cuthill-Макки : уменьшить полосу пропускания в виде симметричной разреженной матрицы
  • Алгоритм минимальной степени : переставьте строки и столбцы симметричной разреженной матрицы перед применением разложения Холецкого
  • Символьное разложение Холецкого : эффективный способ хранения разреженной матрицы

Монте-Карло [ править ]

• Выборка Гиббса : сгенерируйте последовательность выборок из совместного распределения вероятностей двух или более случайных величин.
• Гибридный Монте-Карло : сгенерируйте последовательность выборок с использованием гамильтоновой взвешенной цепи Маркова Монте-Карло из распределения вероятностей, которое трудно выбрать напрямую.
• Алгоритм Метрополиса – Гастингса : используется для создания последовательности выборок из распределения вероятностей одной или нескольких переменных.
• Алгоритм Ванга и Ландау : расширение выборки алгоритма Метрополиса – Гастингса

Численное интегрирование [ править ]

• Алгоритм MISER : моделирование методом Монте-Карло, численное интегрирование

Обнаружение корня [ править ]

• Метод деления пополам
• Метод ложного положения : аппроксимирует корни функции
• Метод ИТП : оптимальная минимаксная и суперлинная сходимость одновременно
• Метод Ньютона : находит нули функций с помощью исчисления
• Метод Галлея : использует первую и вторую производные
• Метод секущей : 2-х точечный, односторонний
• Метод ложного положения и метод Иллинойса: 2 точки, брекетинг
• Метод Риддера : 3-точечное экспоненциальное масштабирование
• Метод Мюллера : трехточечная квадратичная интерполяция

Алгоритмы оптимизации [ править ]

• Отсечение альфа – бета : поиск по уменьшению количества узлов в алгоритме минимакс.
• Ветвь и переплет
• Алгоритм Брюсса : см. Алгоритм шансов
• Цепное умножение матриц
• Комбинаторная оптимизация : задачи оптимизации, в которых множество допустимых решений дискретно
  • Жадная рандомизированная процедура адаптивного поиска (GRASP): последовательное построение жадного рандомизированного решения и последующие итерационные улучшения его посредством локального поиска
  • Венгерский метод : комбинаторный алгоритм оптимизации, который решает задачу о назначении за полиномиальное время
• Удовлетворение ограничений
  • Общие алгоритмы выполнения ограничений
    • Алгоритм AC-3
    • Алгоритм карты различий
    • Алгоритм минимальных конфликтов
  • Алгоритм Чаффа : алгоритм для решения экземпляров проблемы логической выполнимости
  • Алгоритм Дэвиса – Патнэма : проверка правильности логической формулы первого порядка
  • Дэвис-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 ² ), как при моделировании с прямой суммой.
  • Быстрый многополюсный метод (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 (сферическая линейная интерполяция): кватернионная интерполяция с целью анимации трехмерного вращения.
• Таблица суммированных площадей (также известная как целостное изображение): алгоритм для вычисления суммы значений в прямоугольном подмножестве сетки за постоянное время.

Криптография [ править ]

• Асимметричное (с открытым ключом) шифрование :
  • Эль-Гамаль
  • Криптография на эллиптических кривых
  • MAE1
  • NTRUEncrypt
  • ЮАР
• Цифровые подписи (асимметричная аутентификация):
  • DSA и его варианты:
    • ECDSA и детерминированный ECDSA
    • EdDSA (Ed25519)
  • ЮАР
• Криптографические хеш-функции (см. Также раздел о кодах аутентификации сообщений):
  • БЛЕЙК
  • 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 слабые или были сломаны)
  • Алгоритм тысячелистника
• Обмен ключами
  • Обмен ключами Диффи – Хеллмана
  • Эллиптическая кривая Диффи-Хеллмана (ECDH)
• Функции вывода ключей , часто используемые для хеширования паролей и растягивания ключей
  • bcrypt
  • PBKDF2
  • зашифровать
  • Аргон2
• Коды аутентификации сообщений (симметричные алгоритмы аутентификации, которые принимают ключ в качестве параметра):
  • HMAC : аутентификация сообщения с использованием хэша с ключом
  • Поли1305
  • SipHash
• Совместное использование секрета, разделение секрета, разделение ключа, M из N алгоритмов
  • Схема Блейки
  • Схема Шамира
• Симметричное (секретный ключ) шифрование :
  • Advanced Encryption Standard (AES), победитель конкурса NIST , также известный как Rijndael
  • Blowfish
  • Twofish
  • Три рыбы
  • Стандарт шифрования данных (DES), иногда алгоритм DE, победитель отборочного конкурса NBS, заменен на AES для большинства целей
  • ИДЕЯ
  • RC4 (шифр)
  • Крошечный алгоритм шифрования (TEA)
  • Salsa20 и его обновленный вариант ChaCha20
• Постквантовая криптография
• Алгоритмы доказательства работы

Цифровая логика [ править ]

• Логическая минимизация
  • Алгоритм Куайна – Маккласки : также называется алгоритмом QM, программируемым методом упрощения булевых уравнений.
  • Метод Петрика : еще один алгоритм логического упрощения.
  • Минимизатор эвристической логики эспрессо : быстрый алгоритм минимизации логических функций.

Машинное обучение и статистическая классификация [ править ]

• ALOPEX : алгоритм машинного обучения на основе корреляции
• Изучение правил ассоциации : обнаруживайте интересные отношения между переменными, используемые в интеллектуальном анализе данных.
  • Алгоритм априори
  • Алгоритм Eclat
  • Алгоритм FP-роста
  • Правило одного атрибута
  • Правило нулевого атрибута
• Повышение (метаалгоритм) : используйте много слабых учеников, чтобы повысить эффективность
  • AdaBoost : адаптивное ускорение
  • BrownBoost : алгоритм повышения, который может быть устойчивым к зашумленным наборам данных
  • LogitBoost : ускорение логистической регрессии
  • LPBoost : ускорение линейного программирования
• Агрегирование бутстрапа (упаковка): метод повышения стабильности и точности классификации
• Компьютерное зрение
  • Grabcut на основе разрезов графика
• Деревья решений
  • Алгоритм C4.5 : расширение ID3
  • Алгоритм ID3 (Iterative Dichotomiser 3): используйте эвристику для генерации небольших деревьев решений
• Кластеризация : класс алгоритмов обучения без учителя для группировки и сортировки связанных входных векторов.
  • k-ближайшие соседи (k-NN): метод классификации объектов на основе ближайших обучающих примеров в пространстве признаков
• Алгоритм Линде – Бузо – Грея : алгоритм векторного квантования, используемый для получения хорошей кодовой книги
• Хеширование с учетом местоположения (LSH): метод выполнения вероятностного уменьшения размерности данных большой размерности.
• Нейронная сеть
  • Обратное распространение : метод обучения с учителем, который требует от учителя, который знает или может вычислить желаемый результат для любого заданного ввода.
  • Сеть Хопфилда : рекуррентная нейронная сеть, в которой все связи симметричны
  • Персептрон : простейший вид нейронной сети прямого распространения: линейный классификатор .
  • Импульсно-связанные нейронные сети (PCNN): нейронные модели, предложенные путем моделирования зрительной коры головного мозга кошки и разработанные для высокопроизводительной биомиметической обработки изображений.
  • Сеть радиальных базисных функций : искусственная нейронная сеть, которая использует радиальные базисные функции в качестве функций активации.
  • Самоорганизующаяся карта : неконтролируемая сеть, которая создает низкоразмерное представление входного пространства обучающих выборок.
• Случайный лес : классифицируйте с использованием множества деревьев решений
• Обучение с подкреплением :
  • Q-обучение : изучите функцию ценности действия, которая дает ожидаемую полезность выполнения данного действия в данном состоянии и последующего следования фиксированной политике.
  • State-Action-Reward-State-Action (SARSA): изучите политику процесса принятия решений Маркова
  • Обучение временной разнице
• Вектор релевантности (RVM): аналогичен SVM, но обеспечивает вероятностную классификацию
• Обучение с учителем : обучение на примерах (помеченный набор данных, разделенный на набор для обучения и набор для тестирования)
• Машины опорных векторов (SVM): набор методов, которые разделяют многомерные данные путем нахождения разделяющей гиперплоскости с максимальным запасом между двумя наборами.
  • Структурированная SVM : позволяет обучить классификатор для общих структурированных выходных меток.
• Алгоритм Винноу : связан с перцептроном, но использует схему обновления мультипликативного веса.

Теория языка программирования [ править ]

• C3 линеаризация : алгоритм, используемый в основном для получения последовательной линеаризации иерархии множественного наследования в объектно-ориентированном программировании.
• Алгоритм Чейтина : восходящий алгоритм распределения регистров раскраски графа, который использует стоимость / степень в качестве метрики распространения
• Алгоритм вывода типа Хиндли-Милнера
• Алгоритм Rete : эффективный алгоритм сопоставления с образцом для реализации систем производственных правил
• Алгоритм Сетхи-Уллмана : создание оптимального кода для арифметических выражений

Разбор [ править ]

• Алгоритм CYK : алгоритм O (n ³ ) для разбора контекстно-свободных грамматик в нормальной форме Хомского
• Парсер Эрли : еще один алгоритм O (n ³ ) для разбора любой контекстно-свободной грамматики
• РВО анализатор : алгоритм для разбора любой контекстно-свободной грамматики по Масару Томита . Он настроен для детерминированных грамматик, на которых он выполняет почти линейное время и O (n ³ ) в худшем случае.
• Внутренний-внешний алгоритм : алгоритм O (n ³ ) для переоценки производственных вероятностей в вероятностных контекстно-свободных грамматиках
• LL-синтаксический анализатор : относительно простой алгоритм синтаксического анализа с линейным временем для ограниченного класса контекстно-свободных грамматик.
• Парсер LR : более сложный алгоритм синтаксического анализа с линейным временем для более широкого класса контекстно-свободных грамматик . Варианты:
  • Канонический парсер LR
  • Парсер LALR (упреждающий LR)
  • Парсер приоритета операторов
  • Парсер SLR (Simple 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)
• Энтропийное кодирование : схема кодирования, которая назначает коды символам, чтобы согласовать длину кода с вероятностями символов.
  • Арифметическое кодирование : расширенное энтропийное кодирование
    • Кодирование диапазона : то же, что и арифметическое кодирование , но немного по-другому.
  • Кодирование Хаффмана : простое сжатие без потерь с использованием относительных частот символов
    • Адаптивное кодирование Хаффмана : метод адаптивного кодирования на основе кодирования Хаффмана
    • Алгоритм слияния пакетов : оптимизирует кодирование Хаффмана с учетом ограничения длины кодовых строк.
  • Кодирование Шеннона – Фано
  • Кодирование Шеннона – Фано – Элиаса : предшественник арифметического кодирования ^[1]
• Энтропийное кодирование с известными энтропийными характеристиками
  • Кодирование Голомба : форма энтропийного кодирования, оптимальная для алфавитов, следующих геометрическим распределениям
  • Кодирование риса : форма энтропийного кодирования, оптимальная для алфавитов, следующих геометрическим распределениям.
  • Усеченное двоичное кодирование
  • Унарное кодирование : код, представляющий число 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. ^{[2] [3]}
• Деконволюция Ричардсона – Люси : алгоритм устранения размытия изображения
• Слепая деконволюция : алгоритм устранения размытости изображения, когда функция рассеяния точки неизвестна.
• Медианная фильтрация
• Резьба по шву : алгоритм изменения размера изображения с учетом содержимого
• Сегментация : разделите цифровое изображение на две или более областей.
  • Алгоритм GrowCut : интерактивный алгоритм сегментации
  • Алгоритм случайного блуждания
  • Регион растет
  • Трансформация водораздела : класс алгоритмов, основанный на аналогии водораздела

Программная инженерия [ править ]

• Алгоритмы кеширования
• Преобразование CHS : преобразование между системами адресации дисков
• Double dabble : преобразование двоичных чисел в BCD
• Хеш-функция : преобразование большого объема данных, возможно, переменного размера, в небольшой элемент данных, обычно одно целое число, которое может служить индексом в массиве.
  • Хеш-функция Фаулера – Нолла – Во : быстрая с низкой частотой конфликтов
  • Хеширование Пирсона : вычисляет только 8-битное значение, оптимизировано для 8-битных компьютеров.
  • Зобристское хеширование : используется при реализации таблиц транспонирования
• Алгоритм сортировки Unicode
• Алгоритм обмена Xor : меняет местами значения двух переменных без использования буфера

Алгоритмы базы данных [ править ]

• Алгоритмы восстановления и изоляции, использующие семантику (ARIES): восстановление транзакций
• Алгоритмы соединения
  • Блокировать вложенный цикл
  • Хеш-соединение
  • Присоединение к вложенному циклу
  • Сортировка-объединение

Алгоритмы распределенных систем [ править ]

• Синхронизация часов
  • Алгоритм Беркли
  • Алгоритм Кристиана
  • Алгоритм пересечения
  • Алгоритм Марзулло
• Консенсус (информатика) : согласование одного значения или истории среди ненадежных процессоров
  • Алгоритм консенсуса Chandra-Toueg
  • Алгоритм Paxos
  • Raft (информатика)
• Обнаружение завершения процесса
  • Алгоритм Дейкстры-Шолтена
  • Алгоритм Хуанга
• Упорядочение Лампорта : а частичное упорядочение событий на основе произошли, до связи
• Выборы лидера : метод динамического выбора координатора
  • Алгоритм хулигана
• Взаимное исключение
  • Распределенный алгоритм взаимного исключения Лэмпорта
  • Журнал Наими-Трехель (n) Алгоритм
  • Алгоритм Маэкавы
  • Алгоритм Раймонда
  • Алгоритм Рикарта-Агравала
• Алгоритм моментального снимка : запись согласованного глобального состояния асинхронной системы
  • Алгоритм Чанди-Лэмпорта
• Векторные часы : создание частичного упорядочивания событий в распределенной системе и обнаружение нарушений причинно-следственной связи.

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

• Распределение памяти приятеля : алгоритм распределения памяти таким образом, чтобы фрагментация была меньше.
• Сборщики мусора
  • Алгоритм Чейни : улучшение полупространственного коллектора
  • Сборщик мусора поколений : быстрые сборщики мусора, которые разделяют память по возрасту.
  • Алгоритм Mark-compact : комбинация алгоритма mark-sweep и алгоритма копирования Чейни
  • Отметить и развернуть
  • Коллекционер полупространства : коллекционер раннего копирования.
• Подсчет ссылок

Сеть [ править ]

• Алгоритм Карна : решает проблему получения точных оценок времени приема-передачи сообщений при использовании TCP.
• Алгоритм Лулео : метод эффективного хранения и поиска таблиц интернет-маршрутизации
• Перегрузка сети
  • Экспоненциальная отсрочка
  • Алгоритм Нагла : повышение эффективности сетей TCP / IP за счет объединения пакетов
  • Усеченная двоичная экспоненциальная отсрочка

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

• Алгоритм Банкира : алгоритм, используемый для предотвращения тупиковых ситуаций.
• Алгоритмы замены страниц : выбор страницы-жертвы в условиях нехватки памяти.
  • Адаптивный кеш замены : производительность лучше, чем у LRU
  • Часы с адаптивной заменой (CAR): это алгоритм замены страниц, который имеет производительность, сопоставимую с адаптивным кешем замены.

Синхронизация процессов [ править ]

• Алгоритм Деккера
• Алгоритм пекарни Лэмпорта
• Алгоритм Петерсона

Планирование [ править ]

• Первое планирование на самый ранний срок
• Планирование справедливого распределения
• Планирование минимального перерыва в работе
• Составление расписания
• Многоуровневая очередь обратной связи
• Скоростно-монотонное планирование
• Планирование с циклическим перебором
• Самая короткая работа следующая
• Наименьшее оставшееся время
• Алгоритм верхних узлов : управление календарем ресурсов

Планирование ввода / вывода [ править ]

Планирование диска [ править ]

• Алгоритм лифта : алгоритм планирования диска, который работает как лифт.
• Кратчайший поиск в первую очередь : алгоритм планирования диска для сокращения времени поиска .

См. Также [ править ]

• Список структур данных
• Список алгоритмов машинного обучения
• Список алгоритмов поиска пути
• Список общих тем алгоритмов
• Список терминов, относящихся к алгоритмам и структурам данных
• Эвристический

Ссылки [ править ]