Список алгоритмов
Материал из Википедии — свободной энциклопедии
 |
Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на статьи-списки. |
Нижеследующее — это список алгоритмов. Также смотрите список структур данных, список основных разделов теории алгоритмов и список терминов, относящихся к алгоритмам и структурам данных.
Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание.
Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство Алгоритмы в Википедии (англ.) или посмотрите несколько уже написанных статей, посвящённых алгоритмам.
[править] Комбинаторные алгоритмы
[править] Общие комбинаторные алгоритмы
- Алгоритм Флойда для нахождения циклов — находит цикл в итерациях
- Генераторы псевдослучайных чисел:
- Алгоритм Робинсона-Шенстеда (англ.) — генерация перестановок из пар таблиц Юнга
[править] Алгоритмы на графах
- Алгоритм Беллмана-Форда — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
- Алгоритм Борувки (англ.) — находит минимальное остовное дерево в графе
- Алгоритм Брона-Кербоша — нахождение наибольших максимальных независимых по включению множеств вершин графа.
- Алгоритм Варшалла — вычисляет все кратчайшие пути во взвешенном графе
- Алгоритм Дейкстры — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
- Алгоритм Краскала — находит остовный лес минимального веса в графе
- Алгоритм основанный на источнике (англ.)— алгоритм для рисования графа
- Алгоритм Прима — находит остовное дерево минимального веса в связном графе
- Алгоритм Флойда-Варшалла — решает проблему нахождения всех пар кратчайших путей во взвешенном направленном графе
- Алгоритм Форда-Фалкерсона (англ.)— вычисляет максимальный поток в графе
- Алгоритм Кристофидеса — эвристический приближенный алгоритм для решения метрической задачи коммивояжера на графе.
- Алгоритм Эдмонса-Карпа (англ.) — модификация алгоритма Форда-Фалкерсона
- Метод ближайшего соседа
- Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
[править] Алгоритмы поиска
- Алгоритм выбора (англ.) — модификация алгоритма линейного поиска; находит k-тый по величине элемент в списке;
- Дерево двоичного поиска (англ.) — использует бинарное дерево для хранения элементов;
- Двоичный поиск — находит элемент в отсортированном списке
- Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю)
- Линейный поиск — находит элемент в неотсортированном списке
- Локальный поиск (оптимизация)
- Метод штрафов (англ.)
- Поиск в глубину — проходит граф ветка за веткой
- Поиск в ширину — проходит граф уровень за уровнем
- Поиск по первому наилучшему совпадению (англ.) (англ. Best-first search)— проходит граф в порядке важности, используя очередь приоритетов
- Алгоритм поиска по A*-дереву (англ.)— особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
- Троичный поиск — находит элемент в отсортированном списке
- Поиск в хеш-таблице
[править] Алгоритмы на строках
[править] Алгоритмы поиска строки
- Алгоритм Кнута-Морриса-Пратта
- Алгоритм Рабина-Карпа поиска строки
- Алгоритм Бойера-Мура поиска строки
- Алгоритм Ахо-Корасик
- Алгоритм Битапа (англ.) (также известен как shift-or, shift-and или Baeza-Yates-Gonnet алгоритм)
- Задача поиска наибольшей общей подпоследовательности
- Задача поиска наибольшей увеличивающейся подпоследовательности (англ.)
- Задача поиска наикратчайшей общей надпоследовательности (англ.)
- Задача поиска наибольшей общей подстроки
[править] Примерное соответствие
- Расстояние Левенштейна
- Расстояние Хэмминга
- Расстояние Дамерау-Левенштейна (англ.)
- Алгоритм Нидлмана-Вунша (англ.)
- Алгоритм Смита-Вотермана (англ.)
- Soundex
- Metaphone
[править] Деревья для строковых последовательностей
[править] Алгоритмы сортировки
- Bogosort (англ.)
- Блинная сортировка (англ.)
- Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной
- Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
- Глупая сортировка, найти отличия от Bogosort
- Гномья сортировка (англ.)
- Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
- Плавная сортировка (англ.)
- Поразрядная сортировка — сортирует строки буква за буквой (ср. с блочной)
- Сортировка Бентли-Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
- Сортировка бинарным деревом
- Сортировка методом вставок — определяем, где текущий элемент должен находится в отсортированном списке, и вставляем его туда
- Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
- Сортировка методом Шелла— попытка улучшить сортировку вставками
- Сортировка перемешиванием (Сортировка коктейлем)
- Сортировка подсчётом
- Сортировка пузырьком
- Сортировка расчёской (англ.)
- Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
- Топологическая сортировка
- Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
- Цифровая сортировка (Сортировка по отделениям)
[править] Алгоритмы слияния
- Простой алгоритм слияния (англ. Simple Merge algorithm )
- К-мерный алгоритм слияния (англ. k-way Merge algorithm )
[править] Алгоритмы сжатия данных
[править] Алгоритмы сжатия без потерь
- Преобразование Барроуза-Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
- Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза-Уилера
- Алгоритм DEFLATE (англ.)
- Дельта-кодирование — эффективно для сжатия данных, в которых последовательности часто повторяются
- Инкрементное кодирование — дельта-кодирование применяемое к последовательности строк
- Семейство алгоритмов словарного сжатия Лемпеля-Зива:
- Алгоритм сжатия PPM
- Кодирование длин серий (Групповое кодирование, также известен как англ. RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
- Алгоритм SEQUITUR (англ.)— сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
- Вейвлет-кодирование на основе вложенных нуль-деревьев (англ.) (EZW-кодирование)
- Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
- Кодирование Шеннона-Фано — самый простой алгоритм кодирования
- Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
- Адаптивное кодирование Хаффмана (англ.) — техника адаптивного кодирования, основывающаяся на коде Хаффмана
- Усечённое двоичное кодирование (англ.) — используется для однородного вероятностного распределения с конечным алфавитом
- Арифметическое кодирование — развитие энтропийного кодирования
- Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании
- Кодирование расстояний (англ.) — метод сжатия данных, который близок по эффективности к арифметическому кодированию
- Энтропийное кодирование с известными характеристиками
- Унарное кодирование — код, который представляет число n в виде n единиц с замыкающим нулём
- дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
- Кодирование Фибоначчи (англ.)— универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
- Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
- Кодирование Райса (англ.)— форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
[править] Алгоритмы сжатия с потерями
- Линейное предсказывающее кодирование (англ.)— сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
- А-закон — стандартный алгоритм компандирования. Применяется в РФ.
- Мю-закон — стандартный алгоритм компандирования
- Фрактальное сжатие — метод, использующий фракталы для сжатия изображений
- Трансформирующее кодирование (англ.) — тип сжатия данных для «естественных» данных, таких как аудио-сигналы или фотографические изображения
- Векторная квантизация (англ.)— техника, часто используемая в сжатии данных с потерями
- Вейвлетное сжатие — тип компрессии данных хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)
[править] Вычислительная геометрия
- Алгоритм заворачивания подарков (англ.)— определение выпуклой оболочки набора точек
- Алгоритм расстояния Гильберта-Джонсона-Кеерти (англ.)— определение наименьшего расстояния между двумя выпуклыми фигурами
- Алгоритм сканирования Грэхема (англ.) — определение выпуклой оболочки набора точек на плоскости
- Алгоритм точки в многоугольнике — проверка принадлежности данной точки данному многоугольнику
[править] Компьютерная графика
- Алгоритм Брезенхэма — растеризует отрезок линии с заданными координатами начала и конца
- Алгоритм рисования прямой (англ.) — алгоритм для аппроксимации отрезка на дискретной графической поверхности
- Алгоритм DDA-линии — чертит точки двухмерного массива в форме прямой линии между двумя заданными точками (использует вычисления с плавающей точкой)
- Алгоритм заливки области (англ.) — заполняет соединённый регион многомерного массива указанным значением
- Алгоритм сглаживания прямой Сяолинь-У (англ.) — алгоритм для сглаживания прямой
- Алгоритм художника (англ.) — определяет видимые части 3-хмерной сцены
- Алгоритм лучевой трассировки (англ.) — рендеринг реалистичных изображений
- Затенение по Фонгу — модель освещения и метод интерполяции в трёхмерной компьютерной графике
- Затенение по Гуро — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
- Изображение сканирующей линией (англ.) (англ. Scanline rendering) — конструирует образ с помощью перемещения воображаемой линии над образом
- Алгоритмы глобального освещения (англ.) — рассматривает прямое освещение и отражение от других объектов
- Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
- Интерполяция сплайнами (англ.)— уменьшение ошибки с помощью феномена Рунге (англ.)
[править] Компьютерное зрение
[править] Криптографические алгоритмы
(См. также Разделы в криптографии для 'аналитического глоссария')
- Шифрование с симметричным (скрытым) ключом:
- ГОСТ 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 — аутентификация сообщение с помощью хеш-ключа
- Тигр — обычно используется в Тигровых деревьях хэшей
- Криптостойкие генераторы псевдослучайных чисел
- Алгоритм Блюма, Блюма и Шуба — базируется на сложности факторизации
- Алгоритм Ярроу (англ.)
- ГПСЧ Фортуна (англ.) — якобы улучшение алгоритма Ярроу
- Генерация случайных простых чисел
[править] Цифровая обработка сигналов
- CORDIC — быстрая техника вычисления тригонометрических функций.
- Медианный фильтр для 1-мерного массива
- Дождевой алгоритм (англ.) — Уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
- Osem — алгоритм для обработки медицинских изображений
- Алгоритм Гэртцеля (англ.)— Может быть использован для декодирования цифр тональных сигналов
- Развеяние Ричардсона-Люси (англ.)— алгоритм увеличения резкости образа
[править] Разработка ПО
- Алгоритмы для восстановления и изоляции повреждённых семантик (англ.)
- Алгоритм сравнения Unicode (англ.)
- Алгоритм преобразования CHS (англ.) — Преобразование между системами адресации диска
- Алгоритм вычисления контрольной суммы (CRC или FCS) Циклическая избыточная сумма (Ciclic Redunancy Check), или контрольная последовательность кадра (Frame Check Sequence) — вычисление кода проверки.
- Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
- Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.
[править] Алгоритмы распределённых систем
- Упорядочение Лампорта (англ.)— Частичное упорядочение событий в зависимости от того, что случилось раньше
- Алгоритм мгновенного снимка (англ.) — снимок процесса записывающий глобальное состояние системы
- Векторное упорядочение (англ.)— Полное упорядочение событий
- Алгоритм Марцулло (англ.) — распределённая синхронизация часов
- Алгоритм пересечений (англ.) — другой алгоритм синхронизации часов
[править] Алгоритмы выделения и освобождения памяти
- Сборщик мусора Боема (англ.)— «скромный» сборщик мусора
- Дружеское выделение памяти (англ.)— алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
- Обобщённый сборщик мусора (англ.)— Быстрые сборщики мусора, которые разделяют память по возрасту
- Пометить и вымести (англ.)
- Подсчёт ссылок (англ.)
[править] Алгоритмы в операционных системах
- Алгоритм банкира (англ.)— Алгоритм, использующийся для избежания взаимных блокировок
- Алгоритм замены страницы (англ.)— выбор страницы-жертвы при условиях небольшого объёма памяти
- Алгоритм забияки (англ.)— выбор нового лидера среди множества компьютеров
- rsync — алгоритм, использующийся для эффективной передачи файлов между двумя компьютерами
Дисковые алгоритмы-планировщики:
- Алгоритм лифта (англ.)— дисковый алгоритм планирования, который работает как лифт
- Первым ищется кратчайший (англ.)— дисковый алгоритм планирования для уменьшения времени поиска
Алгоритмы синхронизации процессов: