Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)
Циклопедия:Списки:Алгоритмы
Перейти к навигации
Перейти к поиску
→ Алгоритм
Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и списке основных разделов теории алгоритмов[1]
Комбинаторные алгоритмы[править]
Общие комбинаторные алгоритмы[править]
- Алгоритм Флойда для нахождения циклов находит цикл в итерациях
- Генераторы псевдослучайных чисел:
Генерация комбинаторных объектов[править]
- Алгоритм Робинсона — Шенстеда — генерация перестановок из пар таблиц Юнга
- Алгоритм Нарайаны
- [[|en]] (Steinhaus–Johnson–Trotter algorithm)
Алгоритмы на графах[править]
- Алгоритм Беллмана — Форда — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
- Алгоритм Борувки — находит минимальное остовное дерево в графе
- Алгоритм Брона — Кербоша — нахождение наибольших максимальных независимых по включению множеств вершин графа.
- Алгоритм Флойда — Уоршелла — вычисляет все кратчайшие пути во взвешенном графе
- Алгоритм Дейкстры — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
- Алгоритм Левита — находит кратчайшее расстояние от одной из вершин графа до всех остальных
- Алгоритм Джонсона — вычисляет все кратчайшие пути во взвешенном графе
- Алгоритм Краскала — находит остовный лес минимального веса в графе
- [[|en]] (Spring based algorithm) — алгоритм для рисования графа
- Алгоритм Прима — находит остовное дерево минимального веса в связном графе
- Алгоритм Кристофидеса — эвристический приближенный алгоритм для решения метрической задачи коммивояжера на графе.
- Метод ближайшего соседа — «жадный» алгоритм, один из простейших эвристических методов решения задачи коммивояжёра
- Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
- Построение транзитивного замыкания графа (установление факта достижимости вершин)
Алгоритмы нахождения максимального потока[править]
— число вершин, — число рёбер, — наибольшая величина максимальной пропускной способности сети.
- Алгоритм Форда — Фалкерсона (1956) — .
- Алгоритм Эдмондса — Карпа, кратчайших увеличивающихся цепей (1969) — .
- Алгоритм Диница (1970) — .
- Алгоритм Эдмондса — Карпа, локально-максимального увеличения (1972) — .
- Алгоритм Диница 2 (1973) — .
- Алгоритм Карзанова (1974) — .
- Алгоритм Черкаского (1977) — .
- Алгоритм Малхотры — Кумара — Махешвари (1977) — .
- Алгоритм Галила (1980) — .
- Алгоритм Галила — Наамада (1980) — .
- Алгоритм Слейтора — Тарьяна (1983) — .
- Алгоритм Габоу (1985) — .
- Алгоритм Голдберга — Тарьяна (1988) — .
- Алгоритм Ахьюа — Орлина (1989) — .
- Алгоритм Ахьюа — Орлина — Тарьяна (1989) — .
- Алгоритм Кинга — Рао — Тарьяна 1 (1992) — .
- Алгоритм Кинга — Рао — Тарьяна 2 (1994) — .
- Алгоритм Черияна — Хейджрапа — Мехлхорна (1996) — .
- Алгоритм Голдберга — Рао (1998) — .
- Алгоритм Кёлнера — Мондры — Спилмана — Тена (2010) — .
- Алгоритм Орлина 1 (2012) — .
- Алгоритм Орлина 2 (2012) — , если .
Алгоритмы нахождения максимального паросочетания[править]
Алгоритмы поиска[править]
- Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
- Алгоритм выбора — модификация алгоритма линейного поиска; находит -й по величине элемент в списке;
- Двоичное дерево поиска , в худшем случае — использует бинарное дерево для хранения элементов;
- Красно-чёрное дерево — использует дополнительный атрибут узла дерева — «цвет»
- АВЛ-дерево — в каждом узле хранит разницу высот (целое число от −1 до +1)
- Расширяющееся дерево — вместо дополнительных полей в узлах дерева «расширяющие операции» выполняются при каждом обращении к дереву.
- Двоичный поиск — находит элемент в отсортированном списке
- Интерполяционный поиск (Предсказывающий поиск, Поиск по словарю)
- Линейный поиск — находит элемент в неотсортированном списке
- Локальный поиск (оптимизация)
- Метод штрафов
- Поиск в глубину — проходит граф ветка за веткой
- Поиск в ширину — проходит граф уровень за уровнем
- Поиск по первому наилучшему совпадению (англ. Best-first search) — проходит граф в порядке важности, используя очередь приоритетов
- Троичный поиск — находит максимум или минимум функции
- Поиск в хеш-таблице
- Алгоритм Ли (волновой алгоритм) — поиск пути на карте.
Алгоритмы на строках[править]
Алгоритмы поиска строки[править]
- Префикс-функция
- -функция
- Алгоритм Кнута — Морриса — Пратта
- Алгоритм Рабина — Карпа поиска строки
- Алгоритм Бойера — Мура поиска строки
- Алгоритм Ахо — Корасик
- Алгоритм Битапа (также известен как shift-or, shift-and)
- Задача поиска наибольшей общей подпоследовательности
- Задача поиска наибольшей увеличивающейся подпоследовательности
- [[|en]] (Shortest common supersequence problem)
- Задача поиска наибольшей общей подстроки
- Задача поиска количества подпалиндромов
Алгоритмы вычисления расстояния между строками[править]
Алгоритмы приближенного сравнения строк с шаблоном[править]
Вычисление характеристических паттернов[править]
- Алгоритм Крочемора поиска всех кратных строк
- Алгоритм Мейна — Лоренца поиска всех кратных строк
- Алгоритм Мейна поиска крайних левых серий
- Алгоритм Колпакова — Кучерова поиска всех серий
- Алгоритм Ли — Смита поиска всех оболочек
- Алгоритм Франека — Смита — Танга поиска всех раппортов
- Алгоритм Шмидта поиска -приближенных раппортов
- Алгоритмы Сима — Илиопулоса — Парка — Смита поиска -приближенных периодов
Примерное соответствие[править]
- Расстояние Левенштейна
- Расстояние Хэмминга
- Расстояние Дамерау — Левенштейна
- Алгоритм Нидлмана — Вунша
- [[|en]] (Smith-Waterman algorithm)
- Soundex
- Metaphone
Индексы подстрок[править]
- Суффиксный автомат
- Суффиксное дерево
- Алгоритм Мак-Крейта
- Алгоритм Укконена
- Алгоритм Вайнера
- Алгоритм Фрача
- Суффиксный массив
Алгоритмы сортировки[править]
- Bogosort
- Stooge sort
- Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием
- Наивная сортировка — генерация всех возможных перестановок и проверка на отсортированность
- Блинная сортировка
- Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной
- Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
- Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — .
- Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
- Плавная сортировка
- Поразрядная сортировка — сортирует строки буква за буквой.
- Сортировка Бентли — Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
- Сортировка с помощью двоичного дерева (англ. Tree sort)
- Сортировка методом вставок — определяем, где текущий элемент должен находиться в отсортированном списке, и вставляем его туда
- Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
- Сортировка перемешиванием (Сортировка коктейлем)
- Сортировка подсчётом — используется диапазон входных данных, подсчитывается число одинаковых элементов (3 варианта)
- Сортировка пузырьком
- Сортировка расчёской
- Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
- Сортировка Шелла — попытка улучшить сортировку вставками
- Топологическая сортировка
- Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
- Цифровая сортировка — то же, что и Поразрядная сортировка.
Алгоритмы слияния[править]
- Простой алгоритм слияния (англ. Simple Merge algorithm )
- -мерный алгоритм слияния (англ. k-way Merge algorithm )
Минимизация булевых функций[править]
- Алгоритм Квайна
- Алгоритм Мак-Класки
- Карты Карно
- Алгоритм Свободы
- Алгоритм Хва
- Получение простых импликант на основе разбиения по кодам разности
- Метод поразрядного выращивания
- Метод Блейка
Алгоритмы сжатия данных[править]
Алгоритмы сжатия без потерь[править]
- Преобразование Барроуза — Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
- Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза — Уилера
- Алгоритм DEFLATE — популярный свободный алгоритм сжатия (используется в библиотеке zlib)
- Дельта-кодирование — эффективно для сжатия данных с часто повторяющимися последовательностями
- Инкрементное кодирование — дельта-кодирование, применяемое к последовательности строк
- Семейство алгоритмов словарного сжатия Лемпеля — Зива:
- Алгоритм сжатия PPM
- Кодирование длин серий (Групповое кодирование, также известен как англ. RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
- [[|en]] (SEQUITUR algorithm) — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
- [[|en]] (Embedded Zerotree Wavelet) (EZW-кодирование)
- Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
- Алгоритм Шеннона — Фано — самый простой алгоритм кодирования
- Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
- [[|en]] (Adaptive Huffman coding) — техника адаптивного кодирования, основывающаяся на коде Хаффмана
- [[|en]] (Truncated binary encoding) — используется для однородного вероятностного распределения с конечным алфавитом
- Арифметическое кодирование — развитие энтропийного кодирования
- Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании
- [[|en]] (Range encoding) — метод сжатия данных, который близок по эффективности к арифметическому кодированию
- Энтропийное кодирование с известными характеристиками
- Унарное кодирование — код, который представляет число в виде единиц с замыкающим нулём
- дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
- Кодирование Фибоначчи — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
- Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
- Кодирование Райса — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
Алгоритмы сжатия с потерями[править]
- [[|en]] (Linear predictive coding) — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
- -закон — стандартный алгоритм компандирования. Применяется в РФ.
- Мю-закон — стандартный алгоритм компандирования
- Фрактальное сжатие — метод, использующий фракталы для сжатия изображений
- [[|en]] (Transform coding) — тип сжатия данных для «естественных» данных, таких как аудиосигналы или фотографические изображения
- Векторное квантование — техника, часто используемая в сжатии данных с потерями
- Вейвлетное сжатие — тип компрессии данных, хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)
Вычислительная геометрия[править]
- Алгоритм Гилберта — Джонсона — Кёрти — определение наименьшего расстояния между двумя выпуклыми множествами
- [[|en]] (Closest pair of points problem) — трудоёмкость .
- Поиск диаметра множества точек
- Алгоритм Кируса — Бека — отсечение отрезков выпуклым многоугольником.
- Алгоритм Сазерленда — Ходжмана — отсечение многоугольника.
- Построения контура прямоугольников (стороны параллельны осям координат).
- Нахождение ядра многоугольника
- Регуляризация многоугольника — декомпозиция многоугольника на монотонные части.
Построение выпуклой оболочки набора точек[править]
- Построение ВП через треугольники — трудоёмкость .
- Построение ВП перебором рёбер на принадлежность — трудоёмкость .
- Алгоритм сканирования Грэхема — трудоёмкость .
- Алгоритм Экла — Туссена — трудоёмкость . Улучшение алгоритма Грэхема.
- Алгоритм Эндрю — трудоёмкость . Улучшение алгоритма Грэхема.
- Алгоритм быстрой оболочки — трудоёмкость , в среднем — .
- Алгоритм Киркпатрика — построение выпуклой оболочки набора точек на плоскости методом «разделяй и властвуй» через мосты. Трудоёмкость .
- Построение методом «разделяй и властвуй» через построение касательных — трудоёмкость .
- Алгоритм заворачивания подарков (Джарвиса) — трудоёмкость , — количество точек в выпуклой оболочке.
- [[|en]] (Kirkpatrick–Seidel_algorithm) — трудоёмкость , — количество точек в выпуклой оболочке.
- Алгоритм Чана — трудоёмкость , — количество точек в выпуклой оболочке.
- Инкрементальный алгоритм (fast online hull) — через построение касательных , с помощью сбалансированного дерева — .
- Приближённая выпуклая оболочка снизу (lower approximate hull) — методом полос. Трудоёмкость , где — количество полос.
- Приближённая выпуклая оболочка сверху (upper approximate hull) — методом полос. Трудоёмкость , где — количество полос.
- Алгоритм Ли (выпуклые оболочки) — построение выпуклой оболочки простого многоугольника через отрезание карманов. Трудоёмкость .
Триангуляция[править]
- Триангуляция через поиск диагоналей — ищется диагональ, многоугольник делится на два и далее рекурсивно. Трудоёмкость .
- Триангуляция через отрезание ушей — ищется образующая треугольник диагональ, соседние с треугольником вершины — следующие претенденты на отрезание. Трудоёмкость .
- Триангуляция монотонного простого многоугольника — трудоёмкость .
- Жадная триангуляция — трудоёмкость .
- Оптимальная триангуляция — -полная задача. Суммарная длина всех рёбер минимальна среди всех триангуляций данного множества.
Триангуляция Делоне[править]
- Итеративные алгоритмы построения триангуляции Делоне — трудоёмкость .
- Алгоритмы построения триангуляции Делоне слиянием — трудоёмкость и .
- Алгоритмы прямого построения триангуляции Делоне — трудоёмкость .
- Двухпроходные алгоритмы построения триангуляции Делоне — трудоёмкость и .
- Триангуляция Делоне с ограничениями — трудоёмкость .
Квазитриангуляция[править]
Диаграмма Вороного[править]
- Простой алгоритм построения диаграммы Вороного — трудоёмкость .
- Алгоритм построения диаграммы Вороного через заметающую прямую — трудоёмкость .
- Рекурсивный алгоритм построения диаграммы Вороного — трудоёмкость .
[[|en]] (Point location)[править]
- Локализация точки для выпуклого многоугольника — время запроса .
- Локализация точки в звездном многоугольнике — время запроса .
- Алгоритм точки в многоугольнике — проверка принадлежности данной точки простому многоугольнику .
- Метод луча — принадлежность точки простому многоугольнику .
- Метод углов — принадлежность точки выпуклому многоугольнику. Трудоёмкость .
- Метод полос — простой многоугольник. Время запроса , память .
- Метод детализации триангуляции Киркпатрика — простой многоугольник. Время запроса , память .
- Трапецоидальная карта — простой многоугольник. Рандомизированный алгоритм, время запроса , память .
- Метод цепей — простой многоугольник. Время запроса , память .
Пересечения[править]
- Алгоритм Бентли — Оттманна — поиск всех точек пересечения отрезков на плоскости , — количество точек пересечения.
- Алгоритм Чазелла — Эдельсбруннера — пересечение отрезков за .
- [[|en]] (Line segment intersection) (алгоритм Шеймоса — Гоя) — трудоёмкость .
- Алгоритм Коэна — Сазерленда — для выпуклых многоугольников. Трудоёмкость .
- Пересечения выпуклых многоугольников — трудоёмкость .
- Алгоритм Шеймоса — Хоуи — для выпуклых многоугольников методом полос. Трудоёмкость .
- Пересечения выпуклых многоугольников с заметающей прямой — трудоёмкость .
- Пересечение звёздных многоугольников — трудоёмкость .
- Пересечение полуплоскостей — трудоёмкость .
- Алгоритм Лианга — Барски
- [[|en]] (Fast-clipping)
- Алгоритм Кируса — Бека
- [[|en]] (Nicholl–Lee–Nicholl)
- [[|en]] (Sutherland–Hodgman algorithm)
- Алгоритм Уайлера — Атертона
[[|en]] (Rotating calipers)[править]
- Поиск диаметра множества точек через вращающиеся калиперы
- [[|en]] (Minimum bounding box algorithms)
- [[|en]] (Minimum bounding box algorithms)
- Определение ширины многоугольника
- Построение суммы Минковского двух выпуклых многоугольников
- Поиск максимального расстояния между двумя множествами точек
- Поиск минимального расстояния между двумя выпуклыми многоугольниками
- Построение мостов для двух выпуклых многоугольников
- Построение критических опорных прямых для выпуклых многоугольников
Компьютерная графика[править]
- Алгоритмы построения отрезка — алгоритмы для аппроксимации отрезка на дискретной графической поверхности
- Алгоритм Брезенхэма — растеризует отрезок линии с заданными координатами начала и конца
- Алгоритм DDA-линии — чертит точки двухмерного массива в форме прямой линии между двумя заданными точками (использует вычисления с плавающей точкой)
- Алгоритм Ву — алгоритм растеризации отрезка со сглаживанием
- Алгоритм закраски с затравкой — заполняет соединённый регион многомерного массива указанным значением
- Алгоритм художника — определяет видимые части трёхмерной сцены
- Трассировка лучей — рендеринг реалистичных изображений
- [[|en]] (Shading)
- Затенение по Фонгу — модель освещения и метод интерполяции в трёхмерной компьютерной графике
- Затенение по Гуро — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
- Модель освещения Блинна — Фонга
- Модель освещения Кука — Торренса
- [[|en]] (Scanline rendering) (англ. Scanline rendering) — конструирует образ с помощью перемещения воображаемой линии над образом
- Глобальное освещение — рассматривает прямое освещение и отражение от других объектов
- Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
- [[|en]] (Spline interpolation) — уменьшение ошибки феномена Рунге
Компьютерное зрение[править]
- [[|en]] (Epitome) — представление образа или видео при помощи меньшего образа или видео
Криптографические алгоритмы[править]
- См. также Разделы в криптографии для аналитического глоссария
- Шифрование с симметричным (скрытым) ключом:
- ГОСТ 28147-89
- AES (англ. Advanced Encryption Standard) — победитель соревнования NIST, также известен как Rijndael
- Blowfish
- DES (англ. Data Encryption Standard) — иногда, алгоритм DEA (англ. Data Encryption Algorithm), победитель соревнования NBS, заменён на AES для большинства применений
- RC2
- IDEA (англ. International Data Encryption Algorithm)
- RC4
- Алгоритмы выработки общего ключа
- Алгоритмы цифровой подписи:
- ГОСТ Р 34.10-94 — устаревший российский стандарт цифровой подписи, модификация схемы Эль-Гамаля
- ГОСТ Р 34.10-2001 — российский стандарт цифровой подписи, основанный на эллиптических кривых
- DSA (англ. Digital Signature Algorithm) — базируется на схеме Эль-Гамаля
- ECDSA (англ. Elliptic Curve Digital Signature Algorithm) — перенос DSA на эллиптические кривые
- Алгоритмы разделения секрета
- Рюкзак — на данный момент доказана нестойкость схемы
- Схема Шамира
- Схема Blakey
- Алгоритмы подбрасывания монеты по телефону
- Криптографические функции дайджестов сообщений:
- ГОСТ Р 34.11-94
- MD5 Резюме сообщения 5 (Message Digest 5) Разработан Рональдом Ривестом (RFC 1321) — существует метод генерации коллизий
- RIPEMD-160
- SHA-1
- HMAC — аутентификация сообщение с помощью хеш-ключа
- Тигр — обычно используется в TTH
- Криптостойкие генераторы псевдослучайных чисел
- Алгоритм Блюма — Блюма — Шуба — базируется на сложности факторизации
- Алгоритм Ярроу
- Алгоритм Fortuna — улучшение алгоритма Ярроу
- Генерация случайных простых чисел
- Алгоритм аутентификации сообщений Message authentication algorithm
Цифровая обработка сигналов[править]
- CORDIC — быстрая техника вычисления тригонометрических функций.
- Медианный фильтр для одномерного массива
- [[|en]] (Rainflow-counting algorithm) — уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
- Osem — алгоритм для обработки медицинских изображений
- Алгоритм Гёрцеля — может быть использован для декодирования цифр тональных сигналов
- [[|en]] (Richardson-Lucy deconvolution) — алгоритм увеличения резкости образа
Разработка программного обеспечения[править]
- [[|en]] (Algorithms for Recovery and Isolation Exploiting Semantics)
- [[|en]] (Unicode Collation Algorithm)
- [[|en]] (CHS conversion) — Преобразование между системами адресации диска
- Алгоритм вычисления контрольной суммы (CRC или FCS) Циклическая избыточная сумма (англ. Cyclic Redunancy Check), или контрольная последовательность кадра (англ. Frame Check Sequence) — вычисление кода проверки.
- Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
- Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.
Алгоритмы распределённых систем[править]
- [[|en]] (Lamport ordering) — Частичное упорядочение событий в зависимости от того, что случилось раньше
- [[|en]] (Snapshot algorithm) — снимок процесса, записывающий глобальное состояние системы
- [[|en]] (vector clocks) — Полное упорядочение событий
- Алгоритм Марзулло — распределённая синхронизация часов
- [[|en]] (intersection algorithm) — другой алгоритм синхронизации часов
Алгоритмы выделения и освобождения памяти[править]
- [[|en]] (Boehm garbage collector) — «скромный» сборщик мусора
- [[|en]] (Buddy memory allocation) — алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
- Сборщик мусора с поколениями — быстрые сборщики мусора, которые разделяют память по возрасту
- [[|en]] (Mark and sweep)
- Подсчёт ссылок
Алгоритмы в операционных системах[править]
- [[|en]] (Banker's algorithm) — Алгоритм, использующийся для избежания взаимных блокировок
- [[|en]] (Page replacement algorithms) — выбор страницы-жертвы при условиях небольшого объёма памяти
- [[|en]] (Adaptive replacement cache): скорость выполнения лучше, чем у LRU
- [[|en]] (Clock with Adaptive Replacement) (CAR): алгоритм замены страниц со скоростью выполнения, сравнимой с адаптивным алгоритмом замещения кэша
- Алгоритм забияки — выбор нового лидера среди множества компьютеров
- rsync — алгоритм, использующийся для эффективной передачи файлов между двумя компьютерами
Дисковые алгоритмы-планировщики[править]
- [[|en]] (Elevator algorithm) — дисковый алгоритм планирования, который работает как лифт
- [[|en]] (Shortest seek first) — дисковый алгоритм планирования для уменьшения времени поиска
Сетевые алгоритмы[править]
- Алгоритм Карна: получение точных оценок времени распространения пакетов сообщений при использовании TCP/IP
- [[|en]] (Luleå algorithm): техника эффективного сохранения и поиска в таблицах роутинга
- [[|en]] (Network congestion)
- [[|en]] (Exponential backoff)
- [[|en]] (Nagle's algorithm): улучшение эффективности TCP/IP за счёт объединения пакетов
- [[|en]] (Truncated binary exponential backoff)
- Шейпинг
- Алгоритм текущего ведра
- [[|en]] (Token bucket)
Алгоритмы синхронизации процессов[править]
Алгоритмы планирования[править]
- [[|en]] (Rate-monotonic scheduling)
- [[|en]] (Earliest deadline first scheduling)
- [[|en]] (Fair-share scheduling)
- Планирование Round-robin
- [[|en]] (Multi level feedback queue) (англ. Multi level feedback queue)
- [[|en]] (Shortest remaining time)
- [[|en]] (Least slack time scheduling)
- [[|en]] (List scheduling) (англ. List scheduling)
- [[|en]] (Top-nodes algorithm)
- Кратчайшая работа следующей
- [[|en]] (Shortest remaining time)
Генетические алгоритмы[править]
- [[|en]] (Fitness proportionate selection) — также известен как выбор рулеточного колеса
Медицинские алгоритмы[править]
Нейронные сети[править]
- Метод обратного распространения ошибки
- Самоорганизующееся отображение (Карты Кохонена, SOM)
- Метод коррекции ошибки
- Метод коррекции с обратной передачей сигнала ошибки
Вычислительная теория групп[править]
- Алгоритм Тодда — Коксетера — перечисление смежных классов подгруппы
- Алгоритм Шрайера — Симса — эффективное представление конечно-порождённой подгруппы
Вычислительная алгебра[править]
- [[|en]] (Buchberger's algorithm) — находит базис Грёбнера
- Процесс Грама ― Шмидта — ортогонализация набора векторов
- [[|en]] (Knuth-Bendix completion algorithm)
- [[|en]] (Multivariate division algorithm) — для многочленов в некоторых неопределённостях
- Алгоритмы умножения матриц
- Алгоритм Штрассена — быстрое умножение матриц
- Алгоритм Копперсмита — Винограда
- [[|en]] (Chain matrix multiplication) (англ. Chain matrix multiplication)
- Алгоритм Катхилла — Макки — алгоритм уменьшения ширины ленты разреженных симметричных матриц
- Алгоритмы вычисления дискретного преобразования Фурье
- Быстрое преобразование Фурье
- [[|en]] (Cooley-Tukey FFT algorithm)
- [[|en]] (Rader's FFT algorithm)
- [[|en]] (Bluestein's FFT algorithm)
- [[|en]] (Bruun's FFT algorithm)
- [[|en]] (Prime-factor FFT algorithm)
- [[|en]] (Eigenvalue algorithm)
- Преобразования Хаусхолдера (-разложение) — вычисление обратной матрицы, собственных векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
- Решение систем линейных уравнений
- Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений
- Структурированное гауссово исключение — применяется, когда матрица системы является разреженной
- Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления
- Разложение Холецкого — метод, эффективный для ленточных и разреженных матриц
- Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам
Теоретико-числовые алгоритмы[править]
- Целочисленная арифметика (алгоритмы для работы с большими числами)
- Умножение столбиком больших чисел
- «Быстрый столбик»
- Умножение Карацубы — алгоритм быстрого умножения чисел
- [[|en]] (Toom–Cook multiplication) — обобщённый алгоритм умножения Карацубы (известен также как Toom-3)
- Метод умножения Шёнхаге — Штрассена — более быстрый алгоритм умножения
- Алгоритм Фюрера — на данный момент самый быстрый алгоритм умножения больших чисел
- Деление на одноразрядное число (DO)
- [[|en]] (Division algorithm)
- Быстрое возведение в степень — вычисляет степени чисел при помощи возведения в квадрат
- Алгоритмы модулярной арифметики
- Алгоритм Монтгомери — модулярное умножение и возведение в степень
- Алгоритм нахождения порядка элемента
- Алгоритм Тонелли — Шенкса — решение квадратичных сравнений
- Метод Берлекэмпа — вероятностный алгоритм для нахождения корней многочленов над конечным полем
- Алгоритм Берлекэмпа — факторизация многочленов над конечным полем
- Алгоритм Берлекэмпа — Мэсси — поиск линейного рекуррентного соотношения наименьшего порядка, которому удовлетворяет последовательность
- Решение систем линейных сравнений
- Решение систем линейных уравнений над полем
- Алгоритм Ланцоша — эффективен над полем характеристики 2
- Алгоритм Видемана
- Дискретное логарифмирование:
- В простом конечном поле
- Алгоритм Шенкса (алгоритм больших и маленьких шагов, англ. baby-step giant-step)
- Алгоритм Полига — Хеллмана — эффективен, если все делители — небольшие
- ρ-метод Полларда дискретного логарифмирования
- Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования
- Алгоритм COS (алгоритм Копперсмита — Одлыжко — Шреппеля) — достаточно эффективный субэкспоненциальный алгоритм
- Решето числового поля — наиболее эффективный на данный момент алгоритм дискретного логарифмирования
- В произвольном конечном поле
- Алгоритм исчисления индексов (алгоритм index-calculus) — сведение дискретного логарифмирования в произвольном конечном поле к аналогичной задаче в простом поле
- Алгоритм Копперсмита — эффективный алгоритм дискретного логарифмирования в конечном поле характеристики 2
- В простом конечном поле
- Алгоритмы нахождения наибольшего общего делителя (НОД) двух чисел
- Алгоритм Евклида
- Расширенный алгоритм Евклида — также решает уравнение , где НОД, НОДНОД
- Бинарный алгоритм вычисления НОД — эффективный способ вычисления НОД
- Расширенный бинарный алгоритм — модификация бинарного алгоритма нахождения НОД, аналогичная расширенному алгоритму Евклида
- Простые числа:
- Нахождение простых чисел:
- Перебор делителей
- Решето Эратосфена
- Решето Аткина — оптимизированная версия решета Эратосфена
- Решето Сундарама
- Тесты простоты — проверка, является ли данное число простым:
- Детерминированные тесты простоты:
- Тест на основе малой теоремы Ферма
- Тест Миллера — модификация теста на основе малой теоремы Ферма; опирается на расширенную гипотезу Римана
- (N-1)–метод проверки простоты — тест на простоту при известном разложении на множители числа ; также используется для построения больших простых чисел
- (N+1)–метод проверки простоты — тест на простоту при известном разложении на множители числа
- Алгоритм Конягина — Померанса — модификация -метода
- Алгоритм Ленстры — использует суммы Якоби и некоторые тесты, обобщающие малую теорему Ферма
- Тест Люка — Лемера для чисел Мерсенна
- Тест Пепина для чисел Ферма
- Тест Агравала — Каяла — Саксены — полиномиальный детерминированный тест простоты
- Вероятностные тесты простоты:
- Тест Соловея — Штрассена — опирается на малую теорему Ферма и свойства символа Лежандра
- Тест Миллера — Рабина — эффективная модификация теста Соловея — Штрассена
- Детерминированные тесты простоты:
- Факторизация — разложение числа на простые множители:
- Алгоритмы с экспоненциальной сложностью:
- Алгоритмы с субэкспоненциальной сложностью:
- Алгоритм Диксона
- Метод квадратичного решета (англ. QS)
- Специальный метод решета числового поля (англ. SNFS)
- Общий метод решета числового поля (англ. GNFS)
- Факторизация с помощью эллиптических кривых — вероятностный алгоритм факторизации с помощью эллиптических кривых
- Нахождение простых чисел:
- Дроби
- Жадный алгоритм для египетских дробей — преобразует рациональные числа в египетские дроби
- Прочие
- Алгоритм Шуфа — вычисление порядка группы точек эллиптической кривой
- Алгоритм Ленстры — Ленстры — Ловаса (LLL-алгоритм, L³-алгоритм)
Численные алгоритмы[править]
- См. также: Список разделов численного анализа
- Алгоритм де Кастельжо — вычисление кривых Безье
- Методы интерполяции
- Приближенное вычисление решений
- [[|en]] (False position method) (False position method, regula falsi method) — аппроксимирует корни функции
- Метод бисекции — нахождение нуля (корня) нелинейной функции
- Метод Ньютона (метод касательных) — нахождение нулей функций с помощью производной
- Метод секущих (метод хорд) — аппроксимирует корни функции
- Метод градиентов (градиентный спуск) — аппроксимирует решение системы уравнений
- Метод сопряжённого градиента
- Алгоритм Гаусса — Ньютона — алгоритм для решения нелинейных уравнений методом наименьших квадратов
- Алгоритм Левенберга — Марквардта — алгоритм для решения нелинейных уравнений методом наименьших квадратов
- [[|en]] (Dancing Links) — нахождение всех решений задачи точного покрытия
- [[|en]] (De Boor algorithm) — вычисление сплайнов
- [[|en]] (Gauss-Legendre algorithm) — вычисление цифр числа пи
- Алгоритм Кэхэна — более аккуратный метод суммирования чисел с плавающей точкой
- [[|en]] (MISER algorithm) — моделирование методом Монте-Карло, численное интегрирование
- [[|en]] (Rounding functions) — классические способы округления чисел
- [[|en]] (Shifting nth-root algorithm) — извлечение корня цифра за цифрой
- Вычисление квадратного корня:
- Алгоритм Герона
- школьный (ручной) алгоритм — аппроксимирует квадратный корень числа
- Вычисление корня -ной степени
Алгоритмы оптимизации[править]
- Линейное программирование
- Симплекс-метод
- «Венгерский метод» — решение задач целочисленного линейного программирования
- Метод Мака решения задачи о назначениях
- Алгоритм имитации отжига
- Метод роя частиц
- Муравьиные алгоритмы
- Метод ветвей и границ
- Дифференциальная эволюция
- Эволюционная стратегия
- Метод Нелдера — Мида (downhill simplex method) — алгоритм нелинейной оптимизации
- [[|en]] (Random-restart hill climbing)
- [[|en]] (Stochastic tunneling)
- Задача о сумме подмножеств
- Метод перебора
- Метод Фибоначчи поиска экстремума — метод выбора точек для нахождения экстремума функции одной переменной
- Градиентный спуск
- Алгоритм Левенберга — Маркардта — комбинация метода Ньютона и наискорейшего спуска
- Метод Ньютона в оптимизации, основанный на методе Ньютона поиска корня
- Квазиньютоновские методы — методы, основанные на замене матрицы Гессе её приближением.
- Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно — квазиньютоновский алгоритм нелинейной оптимизации
Грамматический разбор[править]
- Рекурсивный нисходящий парсер — нисходящий парсер, подходящий для -грамматик
- LL-парсер — относительно простой алгоритм разбора за линейное время для ограниченного класса контекстно-свободных грамматик
- [[|en]] (LR parser) — более сложный алгоритм разбора за линейное время для большего класса контекстно-свободных грамматик. Варианты:
- [[|en]] (Operator-precedence parser)
- [[|en]] (Simple LR parser) (англ. Simple LR parser)
- [[|en]] (Look-ahead LR parser) (англ. Look-ahead LR parser)
- [[|en]] (Canonical LR parser)
- [[|en]] (Packrat parser) — алгоритм разбора за линейное время, поддерживающий некоторые контекстно-свободные грамматики и грамматики разбора выражений
- Алгоритм Коука — Янгера — Касами (алгоритм CYK) — -алгоритм для разбора любой контекстно-свободной грамматики
- Алгоритм Эрли — другой -алгоритм для разбора любой контекстно-свободной грамматики
- -парсер — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и в худшем случае.
- Метод рекурсивного спуска — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной грамматикой
- Алгоритм Рутисхаузера — работает в предположении о полной скобочной структуре выражения
- Алгоритм сортировочной станции
Квантовые алгоритмы[править]
Приложения квантовых вычислений к различным категориям проблем и алгоритмы
- Алгоритм Гровера — позволяет выполнять поиск среди вариантов за проверок
- Алгоритм Шора — полиномиальный алгоритм факторизации числа
- Алгоритм Дойча — Йожи — критерий баланса для булевой функции
- Задача Фейнмана
Теория вычислений и автоматов[править]
- Конструирование набора подмножеств[en] — алгоритм для преобразования недетерминированного автомата в детерминированный
- Алгоритм Тодда — Коксетера — процедура для создания сомножеств
Другие[править]
- Астрономические алгоритмы
- Алгоритмы восстановления фазы волнового фронта (Гершберга-Сакстона, Фиенапа, Бейтса, Альморо и др.)
- Алгоритм Баума — Велша
- Алгоритмы манипуляции битами
- Алгоритм создания битовой маски
- Алгоритм обмена при помощи исключающего ИЛИ — обмен значений двух переменных без использования буфера
- Алгоритм вычисления дня недели (Алгоритм Судного Дня)
- Алгоритм Витерби
- Алгоритм Луна — метод проверки правильности идентификационных чисел
- Алгоритм стемматизации (стемминга) — процесс нахождения основы слова
- Алгоритм Риша — нахождение первообразных
- Алгоритм синтеза многосвязной сети
- Алгоритм распространения доверия (алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях
- Быстрый метод мультиполей — алгоритм вычисления сил взаимодействия частиц[2]
- Алгоритм Зиккурат — алгоритм генерации неравномерно распределенных случайных чисел
См. также[править]
- Список структур данных
- Список классов сложности, Класс сложности
- Список основных разделов теории алгоритмов
- Циклопедия:Списки:Алгоритмы решения транспортных задач
- Алгоритм северо-западного угла для ТЗ
- Алгоритм расчёта потенциалов для ТЗ
Примечания[править]
- ↑ В тематическом проекте есть также список терминов, относящихся к алгоритмам и структурам данных, составленный на основе словаря Американского национального института стандартов. Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание. Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «[[|en]] (Wikipedia:Algorithms on Wikipedia)» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.
- ↑ Barry A. Cipra The Best of the 20th Century: Editors Name Top 10 Algorithms (англ.) // SIAM News. — 2000. — Vol. 33. — № 4.
Литература[править]
- Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. — Издательский дом «Вильямс», 2000. — 384 с. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.).
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
- Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, Volume 1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — 720 с. — ISBN 5-8459-0080-8.
- Дональд Кнут Искусство программирования, том 1, выпуск 1. MMIX — RISC-компьютеры нового тысячелетия = The Art of Computer Programming, Volume 1, Fascicle 1: MMIX — A RISC Computer for the New Millennium. — М.: «Вильямс», 2007. — 160 с. — ISBN 978-5-8459-1163-6.
- Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, Volume 2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — 832 с. — ISBN 5-8459-0081-6.
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, Volume 3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4.
- Дональд Кнут Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. — М.: «Вильямс», 2013. — 960 с. — ISBN 978-5-8459-1744-7.
- Д-р Сидни Фейт TCP/IP: Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) = TCP/IP: Arhitecture, Protocols, and Implementation with IPv6 and IP Security. — 2nd. ed. Dr. Sidnie Feit Copyright 1997, 1993 by The McGraw-Hill Companies, Inc. (включая IP версии 6 и IP Security). — 2-е изд. — М.: Издательство «Лори», 2003. — 424 с. — ISBN 5-85582-072-6 (рус.) / ISBN 0-07-021389-5 (англ.).
- Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. — М.: «Вильямс», 2007. — 480 с. — ISBN 978-5-8459-1244-2.
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2013. — 1328 с. — ISBN 978-5-8459-1794-2.
- Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — 672 с. — ISBN 5-93772-081-4.
- Роберт Седжвик Фундаментальные алгоритмы на C. Алгоритмы на графах = Algorithms in C. Graph Algorithms. — СПб.: ДиаСофтЮП, 2003. — 480 с. — ISBN 5-93772-082-2.
- Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Algorithms. — The McGraw-Hill Companies, 2006. — 320 с. — ISBN 0-07-352340-2.
- Ричард Берд Жемчужины проектирования алгоритмов. Функциональный подход = Pearls of Functional Algorithm Design. — ДМК Пресс, 2013. — (Функциональное программирование). — ISBN 978-5-94074-867-0.
- Препарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М.: Мир, 1989. — 478 с.
- Берг М., Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения = Computational Geometry: Algorithms and Applications. — М.: ДМК-Пресс, 2016. — 438 с. — ISBN 978-5-97060-406-9.
Ссылки[править]
- Сайт по методам сжатия данных
- Дискретная математика: Алгоритмы — библиотека алгоритмов и визуализаторов
- Алгоритмы, методы, исходники
- Множество алгоритмов с примерами их реализации
- «Алгоритмика»