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

Здесь содержится список статей для координации работ по развитию темы.

Нижеследующее — это список алгоритмов, описанных в Википедии. Также смотрите список структур данных, список основных разделов теории алгоритмов и список терминов, относящихся к алгоритмам и структурам данных.

Если вы планируете изложить новый алгоритм, пожалуйста прочитайте сначала руководство Алгоритмы в Википедии (на англ.), а потом добавьте ссылку на вашу статью и однострочное описание на эту страницу.

Содержание

Комбинаторные алгоритмы

Общие комбинаторные алгоритмы

Алгоритмы на графах

  • Алгоритм Беллмана-Форда (Bellman-Ford algorithm) — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
  • Алгоритм Дейкстры (Dijkstra’s algorithm) — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
  • Алгоритм Флойда-Варшалла (Floyd-Warshall algorithm) — решает проблему нахождения всех пар кратчайших путей во взвешенном направленном графе
  • Алгоритм Краскала (Kruskal’s algorithm) — находит остовный лес минимального веса в графе
  • Алгоритм Прима (Prim’s algorithm) — находит остовное дерево минимального веса в связном графе
  • Алгоритм Борувки (Boruvka’s algorithm) — находит минимальное остовное дерево в графе
  • Алгоритм Форда-Фалкерсона (Ford-Fulkerson algorithm) — вычисляет максимальный поток в графе
  • Алгоритм Эдмонса-Карпа (Edmonds-Karp algorithm) — реализация алгоритма Форда-Фалкерсона
  • Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
  • Алгоритм основанный на источнике (Spring based algorithm) — алгоритм для рисования графа
  • Топологическая сортировка (Topological sort)

Алгоритмы поиска

  • Линейный поиск (Linear search) — находит элемент в неотсортированном списке
  • Алгоритм выбора (Selection algorithm) — находит k-тый по величине элемент в списке
  • Двоичный поиск (Binary search) — находит элемент в отсортированном списке
  • Дерево двоичного поиска (Binary search tree)
  • Поиск в ширину (Breadth-first search) — проходит граф уровень за уровнем
  • Поиск в глубину (Depth-first search) — проходит граф ветка за веткой
  • Поиск лучшего первым (Best-first search) — проходит граф в порядке важности используя очередь приоритетов
  • Алгоритм поиска по A*-дереву (A* tree search) — особый случай поиска лучшего первым
  • Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю, Predictive search)
  • Хеш-таблица (Hash table) — находит элемент в неотсортированной коллекции за время O(1)
  • Алгоритм Гровера — квантовый алгоритм быстрого поиска в неупорядоченной базе данных за время O(N1/2).

Алгоритмы на строках

Алгоритмы поиска строки

  • Алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt algorithm)
  • Алгоритм Рабина-Карпа поиска строки (Rabin-Karp string search algorithm)
  • Алгоритм Бойера-Мура поиска строки (Boyer-Moore string search algorithm)
  • Алгоритм Ахо-Корасика (Aho-Corasick algorithm)
  • Алгоритм Битапа (Bitap algorithm, также известен как shift-or, shift-and или Baeza-Yates-Gonnet алгоритм)
  • Задача наибольшей общей подпоследовательности (Longest-common subsequence problem) — алгоритм динамического программирования
  • Задача наибольшей увеличивающейся подпоследовательности (Longest increasing subsequence problem)
  • Задача наикратчайшей общей надпоследовательности (Shortest common supersequence problem)
  • Задача наибольшей общей подстроки (Longest common substring problem)

Примерное соответствие


Алгоритмы сортировки

  • Сортировка бинарным деревом (Binary tree sort)
  • Алгоритм Bogosort
  • Сортировка пузырьком (Bubble sort)
  • Блочная сортировка (Корзинная сортировка, Bucket sort)
  • Сортировка расчёской (Comb sort)
  • Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort)
  • Сортировка подсчётом (Counting sort)
  • Гномья сортировка (Gnome sort)
  • Пирамидальная сортировка (Сортировка кучи, Heapsort) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
  • Сортировка методом вставок (Insertion sort) — определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда
  • Сортировка слиянием (Merge sort) — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
  • Блинная сортировка (Pancake sorting)
  • Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort)
  • Быстрая сортировка (Quicksort) — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
  • Поразрядная сортировка (Radix sort) — сортирует строки буква за буквой
  • Сортировка методом выбора (Selection sort) — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
  • Сортировка методом Шелла (Shell sort) — попытка улучшить сортировку вставками
  • Плавная сортировка (Smoothsort)
  • Глупая сортировка (Stupid sort)
  • Топологическая сортировка (Topological sort)

Алгоритмы слияния

  • Простой алгоритм слияния (Simple Merge algorithm)
  • К-мерный алгоритм слияния (k-way Merge algorithm)

Алгоритмы сжатия данных

Алгоритмы сжатия без потерь

  • Преобразование Барроуза-Уилера (англ. Burrows-Wheeler transform, BWT) — предварительная обработка данных для улучшения сжатия без потерь
  • Алгоритм DEFLATE — сжатие без потерь
  • Дельта-кодирование (англ. Delta encoding) — эффективно для сжатия данных в которых последовательности часто повторяются
  • Инкрементное кодирование (англ. Incremental encoding) — дельта-кодирование применяемое к последовательности строк
  • Семейство алгоритмов словарного сжатия Лемпеля-Зива:
    • LZ77 — родоначальник семейства LZ77-алгоритмов
      • LZ77-PM
      • LZFG
        • LZFG-PM
      • LZP
      • LZBW
      • LZSS
        • LZB
        • LZH
        • LZRW1
    • LZ78 — родоначальник семейства LZ78 алгоритмов
    • LZMA — сокращение от англ. Lempel-Ziv-Markov chain-Algorithm
    • LZO — алгоритм компрессии данных ориентированный на скорость
  • Алгоритм сжатия PPM (англ. PPM compression algorithm)
  • Кодирование длин серий (Групповое кодирование, англ. Run-length encoding, RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
  • Алгоритм SEQUITUR — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
  • Вейвлет-кодирование на основе вложенных нуль-деревьев (англ. Embedded Zerotree Wavelet, EZW)
  • Энтропийное кодирование (англ. Entropy encoding) — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
    • Кодирование Шеннона-Фано (англ. Shannon-Fano coding) — самый простой алгоритм кодирования
    • Алгоритм Хаффмана (англ. Huffman coding) — алгоритм построения кода при помощи кодовых деревьев
      • Адаптивное кодирование Хаффмана (англ. Adaptive Huffman coding) — техника адаптивного кодирования, основывающая на коде Хаффмана
    • Усечённое двоичное кодирование (англ. Truncated binary encoding) — используется для однородного вероятностного распределения с конечным алфавитом
    • Арифметическое кодирование (англ. Arithmetic coding) — развитие энтропийного кодирования
    • Кодирование расстояний (англ. Range encoding) — метод сжатия данных, который близок по эффективности к арифметическому кодированию
  • Энтропийное кодирование с известными характеристиками
    • Унарное кодирование (англ. Unary coding) — код, который представляет число n в виде n единиц с замыкающим нулём
    • дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
    • Кодирование Фибоначчи (англ. Fibonacci coding) — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
    • Кодирование Голомба (англ. Golomb coding) — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
    • Кодирование Райса (англ. Rice coding) — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

Алгоритмы сжатия с потерями

  • Линейное предсказывающее кодирование (Linear predictive coding) — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
  • А-закон (A-law algorithm) — стандартный алгоритм компандирования
  • Мю-закон (Mu-law algorithm) — стандартный алгоритм компандирования
  • Фрактальное сжатие (Fractal compression) — метод, использующий фракталы для сжатия изображений
  • Трансформирующее кодирование (Transform coding) — тип сжатия данных для «естественных» данных, таких как аудио-сигналы или фотографические изображения
  • Векторная квантизация (Vector quantization) — техника, часто используемая в сжатии данных с потерями
  • Вейвлетное сжатие (Wavelet compression) — тип компрессии данных хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)

Вычислительная геометрия

  • Алгоритм заворачивания подарков (Gift wrapping algorithm) — определение оболочки набора точек
  • Алгоритм расстояния Гильберта-Джонсона-Кеерти — определение наименьшего расстояния между двумя выпуклыми фигурами
  • Алгоритм сканирования Грэхема (Graham scan) — определение оболочки набора точек на плоскости
  • Алгоритм точки в многоугольнике (Point in polygon) — проверка принадлежности данной точки данному многоугольнику

Компьютерная графика

  • Алгоритм Брезенхэма (Bresenham’s line algorithm) — растеризует отрезок линии с заданными координатами начала и конца
  • Алгоритм рисования прямой (Line drawing algorithm) — алгоритм для аппроксимации отрезка на дискретной графической поверхности
  • Алгоритм DDA-линии (DDA line algorithm) — чертит точки двухмерного массива в форме прямой линии между двумя заданными точками (использует вычисления с плавающей точкой)
  • Алгоритм заливки потопом (Flood fill) — заливает соединённый регион многомерного массива указанным значением
  • Алгоритм прямой Ксяолинь-Ву (Xiaolin Wu’s line algorithm) — алгоритм для сглаживания прямой
  • Алгоритм рисовальщика (Painter’s algorithm) — определяет видимые части 3-хмерной сцены
  • Алгоритм лучевой трассировки (Ray tracing) — рендеринг реалистичных изображений
  • Затемнение Фонга (Phong shading) — модель освещения и метод интерполяции в трёхмерной компьютерной графике
  • Затемнение Гура (Gouraud shading) — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
  • Изображение сканирующей линией (Scanline rendering) — конструирует образ с помощью перемещения воображаемой линии над образом
  • Алгоритмы глобального освещения (Global illumination algorithms) — рассматривает прямое освещение и отражение от других объектов
  • Интерполяция (Interpolation) — конструирование новых точек данных, таких как в цифровом увеличителе
  • Интерполяция сплайнами (Spline interpolation) — уменьшение ошибки с помощью феномена Рунга (Runge’s phenomenon)

Компьютерное зрение

  • Epitome — представление образа или видео при помощи меньшего образа или видео

Криптографические алгоритмы

(Смотри также Разделы в криптографии для 'аналитического глоссария')

  • Криптографические функции дайджестов сообщений:
    • MD5 — Внимание! Существует метод генерации коллизий
    • RIPEMD-160
    • SHA-1
    • HMAC (keyed-hash message authentication code) аутентификация сообщение с помощью хеш-ключа
    • Тигр (Tiger,TTH) — обычно используется в Тигровых деревьях хэшей
  • Криптографически надёжные генераторы псевдослучайных чисел
  • Другие
    • Diffie-Hellman: обмен ключами Диффи-Хеллмана

Цифровая обработка сигналов

  • CORDIC — быстрая техника вычисления тригонометрических функций.
  • Дождевой алгоритм (Rainflow-counting algorithm) — Уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
  • Osem — алгоритм для обработки медицинских изображений
  • Алгоритм Гэртцеля (Goertzel algorithm) — Может быть использован для декодирования цифр тональных сигналов
  • Дискретное преобразование Фурье — определение частот, содержащихся в (куске) сигнала
    • Быстрое преобразование Фурье (Fast Fourier transform) — определяет частоты содержащиеся в (сегменте) сигнале(сигнала)
    • Алгоритм БПФ Кули-Туки (Cooley-Tukey FFT algorithm)
    • Алгоритм БПФ Рэдера (Rader’s FFT algorithm)
    • Алгоритм БПФ Блюштейна (Bluestein’s FFT algorithm)
    • Алгоритм БПФ Брууна (Bruun’s FFT algorithm)
    • Алгоритм БПФ при помощи простых сомножителей (Prime-factor FFT algorithm)
  • Развеяние Ричардсона-Люси (Richardson-Lucy deconvolution) — алгоритм увеличения резкости образа

Разработка ПО

  • Алгоритмы для восстановления и изоляции повреждённых семантик (Algorithms for Recovery and Isolation Exploiting Semantics)
  • Алгоритм сравнения Unicode (Unicode Collation Algorithm)
  • Алгоритм преобразования CHS (CHS conversion) — Преобразование между системами адресации диска
  • Алгоритм вычисления CRC (Cyclic redundancy check) — вычисление кода проверки
  • Чётность (Parity) — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
  • Алгоритм соединения (СУБД) — (Join algorithm) — реализация операции соединения реляционной алгебры.

Алгоритмы распределённых систем

  • Упорядочение Лампорта (Lamport ordering) — Частичное упорядочение сообщений в зависимости от того, что случилось раньше
  • Алгоритм мгновенного снимка (Snapshot algorithm) — снимок процесса записывающий глобальное состояние системы
  • Векторное упорядочение (Vector ordering, vector clocks) — Полное упорядочение событий
  • Алгоритм Марцулло (Marzullo’s algorithm) — распределённая синхронизация часов
  • Алгоритм пересечений (intersection algorithm) — другой алгоритм синхронизации часов

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

  • Сборщик мусора Боема (Boehm garbage collector) — скромный сборщик мусора
  • Дружеское выделение памяти (Buddy memory allocation) — алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
  • Обобщённый сборщик мусора (Generational garbage collector) — Быстрые сборщики мусора, которые разделяют память по возрасту
  • Пометить и вымести (Mark and sweep)
  • Подсчёт ссылок (Reference counting)

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

  • Алгоритм банкира (Banker’s algorithm) — Алгоритм, использующийся для избежания взаимных блокировок
  • Алгоритм замены страницы (Page replacement algorithms) — выбор страницы-жертвы при условиях небольшого объёма памяти
  • Алгоритм забияки (Bully algorithm) — выбор нового лидера среди множества компьютеров
  • rsync — алгоритм, использующийся для эффективной передачи файлов между двумя компьютерами

Дисковые алгоритмы-планировщики:

  • Алгоритм лифта (Elevator algorithm) — дисковый алгоритм планирования, который работает как лифт
  • Первым ищется кратчайший (Shortest seek first) — дисковый алгоритм планирования для уменьшения времени поиска

Алгоритмы синхронизации процессов:

  • Алгоритм Петерсона (Peterson’s algorithm)
  • Алгоритм пекарни Лампорта (Lamport’s Bakery algorithm)
  • Алгоритм Деккера (Dekker’s algorithm)

Алгоритмы планирования

  • Планирование с постоянной скоростью (Rate-monotonic scheduling)
  • Первый заканчивает раньше (планирование) (Earliest deadline first scheduling)
  • Честное разделение (планирование) (Fair-share scheduling)
  • Планирование по кругу (Round-robin scheduling)
  • Многоуровневая отдача (планирование) (Multi level feedback queue)
  • Кратчайшая работа следующей (планирование) (Shortest job next)
  • Кратчайшее оставшееся время (планирование) (Shortest remaining time)
  • Наименьшее время бездействия (планирование) (Least slack time scheduling)
  • Списковое планирование (List scheduling)

Генетические алгоритмы

  • Выбор пропорционально пригодности (Fitness proportionate selection) — также известен как выбор рулеточного колеса

Медицинские алгоритмы

  • Медицинский алгоритм (Medical algorithm)
  • Техасский проект медицинских алгоритмов (Texas Medication Algorithm Project)

Нейронные сети

  • Обратное распространение (Backpropagation)
  • Самоорганизующееся отображение (Self-organizing map)

Вычислительная алгебра

  • Алгоритм Бухбергера (Buchberger’s algorithm) — находит базис Грёбнера (Gröbner basis)
  • Алгоритм нахождения собственного числа (Eigenvalue algorithm)
  • Алгоритм возведения в степень через квадрат (Exponentiating by squaring) — быстро вычисляет степени чисел и матриц
  • Процесс Грэма-Шмидта (Gram-Schmidt process) — ортогонализация набора векторов
  • Алгоритм пополнения Кнута-Бендикса (Knuth-Bendix completion algorithm) — для перезаписи систем правил
  • Алгоритм мультивариационного деления (Multivariate division algorithm) — для многочленов в некоторых неопределённостях
  • Алгоритмы умножения матриц

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

  • Дискретное логарифмирование:
    • Алгоритм Шенкса (Shanks' «baby-step giant-step» algorithm)
    • ρ-алгоритм Полларда для логарифмов (Pollard’s rho algorithm for logarithms)
    • Алгоритм Похлига-Хеллмана (Pohlig-Hellman algorithm)
    • Исчисление индексов (Index calculus algorithm)
  • Алгоритм Евклида (Euclidean algorithm) — вычисляет наибольший общий делитель (НОД)
  • Расширенный алгоритм Евклида (Extended Euclidean algorithm) — также решает уравнение ax+by = c
  • Двоичный алгоритм нахождения НОД (Binary gcd algorithm) — эффективный способ вычисления НОД
  • Факторизация (Integer factorization) — разложение числа на простые множители
    • Алгоритм факторизации простыми числами (prime factorization algorithm)
    • Метод факторизации Ферма (Fermat’s factorization method)
    • Последовательное деление (Trial division)
    • Алгоритм Ленстры (Lenstra elliptic curve factorization) — алгоритм факторизации эллиптической кривой
    • ρ-алгоритм Полларда (Pollard’s rho algorithm)
    • (p-1)-алгоритм Полларда (Pollard’s p-1 algorithm)
    • Конгруэнтность квадратов (Congruence of squares)
    • Квадратичное решето (Quadratic sieve)
    • Алгоритм Диксона (Dixon’s algorithm)
    • Специальное решето числового поля (Special number field sieve)
    • Общее решета числового поля (General number field sieve)
  • Алгоритмы умножения(Multiplication algorithms) — быстрое умножение двух чисел

Численные алгоритмы

Смотри также главную статью Численный анализ и Список разделов численного анализа

  • Танцующие звенья (Dancing Links) — нахождение всех решений задачи точного покрытия
  • Алгоритм де Бура (De Boor algorithm) — вычисление сплайнов
  • Алгоритм де Кастельяу (De Casteljau’s algorithm) — вычисление кривых Безье
  • Метод фальшпозиции (False position method, regula falsi method) — аппроксимирует корни функции
  • Алгоритм Гаусса-Лежандра (Gauss-Legendre algorithm) — вычисление цифр числа пи
  • Алгоритм Гаусса-Ньютона (Gauss-Newton algorithm) — нахождение минимума функции нескольких переменных
  • Jones's period proxy algorithm — факторизация целых чисел
  • Алгоритм суммирования Кахана (Kahan summation algorithm) — более аккуратный метод суммирования чисел с плавающей точкой
  • Алгоритм Левенберга-Маркуардта (Levenberg-Marquardt algorithm) — нахождение минимума функции нескольких переменных
  • Алгоритм MISER (MISER algorithm): моделирование методом Монте-Карло, численное интегрирование
  • Метод Ньютона (Newton’s method) — нахождение нулей функций с помощью исчисления
  • Функции округления (Rounding functions) — классические способы округления чисел
  • Метод секущих (Secant method) — аппроксимирует корни функции
  • Сдвигающий алгоритм корня n-ой степени (Shifting nth-root algorithm) — извлечение корня цифра за цифрой
  • Вычисление квадратного корня (Square root): Алгоритм Герона, школьный (ручной) алгоритм — аппроксимирует квадратный корень числа
  • Алгоритм Риша (Risch algorithm) — перевод неопределённого интеграла в алгебраическую задачу

Вычислительные методы и алгоритмы линейной алгебры

  • Метод Гаусса (Gaussian elimination) — решение систем линейных уравнений
  • Метод Жордана — Гаусса (Gauss-Jordan elimination) — решение систем линейных уравнений
  • Преобразования Холеского (Cholesky decomposition)— решение систем линейных уравнений, эффективный для ленточных и разреженных матриц
  • Преобразования Хаусхолдера (QR decomposition) — вычисление обратной матрицы, собственный векторов и собственных значений матрицы
  • Метод Пранис-Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам

Алгоритмы оптимизации

  • Симплекс-метод (Simplex algorithm) Алгоритм для решения задачи линейного программирования
  • «Венгерский метод» решения задач целочисленного линейного программирования
  • Метод Мака (C.Mack) решения задачи о назначениях
  • Моделируемое отжигание (Simulated annealing)
  • Генетические алгоритмы (Genetic algorithms)
  • Рой частиц (Particle swarm)
  • Метод штрафов (Tabu search)
  • Локальный поиск (Local search)
  • Оптимизация муравейника (Ant colony optimization)
  • Метод БГФС (BFGS method) — алгоритм нелинейной оптимизации
  • Ответвление и ограничение (Branch and bound)
  • Умножение цепных матриц (Chain matrix multiplication)
  • Метод сопряжённого градиента (Conjugate gradient)
  • Дифференциальная эволюция (Differential evolution)
  • Эволюционная стратегия (Evolution strategy)
  • Алгоритм Гаусса-Ньютона (Gauss-Newton algorithm) — алгоритм для решения нелинейных задач методом наименьших квадратов
  • Градиентный спуск (Gradient descent)
  • Алгоритм Левенберга-Марквардта (Levenberg-Marquardt algorithm) — алгоритм для решения нелинейных задач методом наименьших квадратов
  • Линейный поиск (Line search)
  • Локальный поиск (Local search)
  • Метод Нелдера-Мида (Nelder-Mead method, downhill simplex method) — алгоритм нелинейной оптимизации
  • Метод Ньютона в оптимизации (Newton’s method in optimization)
  • Всхождение со случайным перезапуском (Random-restart hill climbing)
  • Стохастическое туннелирование (Stochastic tunneling)
  • Алгоритм суммирования подмножеств (Subset sum algorithm)

Грамматический разбор

  • Рекурсивный нисходящий парсер (Recursive descent parser) — Нисходящий парсер (top-down parser) подходящий для LL(k) грамматик
  • LL-парсер (LL parser) — Относительно простой алгоритм разбора за линейное время (linear time) для ограниченного класса контекстно-свободных грамматик (context-free grammar)
  • LR-парсер (LR parser) — Более сложный алгоритм разбора за линейное время (linear time) для большего класса контекстно-свободных грамматик (context-free grammar). Варианты:
    • Парсер первенства операторов (Operator-precedence parser)
    • SLR-парсер (SLR (Simple LR) parser)
    • LALR-парсер (LALR (Look-ahead LR) parser)
    • Канонический LR-парсер (Canonical LR parser)
  • Парсер старьёвщика (Packrat parser) — Алгоритм разбора за линейное время поддерживающий некоторые контекстно-свободные грамматики и грамматики разбора выражений
  • Алгоритм CYK (CYK algorithm) — O(n³)-алгоритм для разбора любой контекстно-свободной грамматики
  • Алгоритм Эрлея (Earley’s algorithm) — Другой O(n³)-алгоритм для разбора любой контекстно-свободной грамматики
  • GLR-парсер (GLR parser) — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик на которых он действует практически за линейное время и O(n³) в худшем случае.

Квантовые алгоритмы

Приложения квантовых вычислений к различным категориям проблем и алгоритмы

Теория вычислений и автоматов

  • Конструирование набора подмножеств (Powerset construction) — алгоритм для преобразования недетерминированного автомата в детерминированный
  • Алгоритм Тодда-Коксетера (Todd-Coxeter algorithm) — Процедура для создания сомножеств

Другие

  • Астрономические алгоритмы
  • Алгоритм Баума-Велша (Baum-Welch algorithm)
  • Алгоритмы манипуляции битами
  • Алгоритм дня страшного суда: День недели
  • Алгоритм Шрейера-Симса (Schreier-Sims algorithm)
  • Алгоритм Витерби (Viterbi algorithm)
  • Алгоритм Луна (Luhn algorithm) — метод проверки правильности идентификационных чисел
  • Зависание: никто ещё не знает, завершится ли эта 43байтная программа на языке C
  • Алгоритм Левенберга-Марквардта (Levenberg-Marquardt nonlinear least squares fitting algorithm)
  • Алгоритм Тодда-Коксетера (Todd-Coxeter algorithm)
  • Алгоритм Рутисхаузера для разбора выражений

Литература

  • Дональд Кнут Искусство программирования, Том 1 = The Art of Computer Programming. ISBN ISBN 5-8459-0080-8
  • Дональд Кнут Искусство программирования, Том 2 = The Art of Computer Programming. ISBN ISBN 5-8459-0081-6
  • Дональд Кнут Искусство программирования, Том 3 = The Art of Computer Programming. ISBN ISBN 5-8459-0082-4
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS, Second Edition. — Издательский дом "Вильямс", 2005. — С. 1296, с ил.. ISBN ISBN 5-8459-0857-4
  • Robert Sedgewick Algorithms in C (Part 1–4). — Addison-Wesley. ISBN ISBN 0-201-31452-5
  • Robert Sedgewick Algorithms in C (Part 5). — Addison-Wesley. ISBN ISBN 0-201-31663-3
  • Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Introduction to Algorithms. — McGraw-Hill Companies, The, 2006. — С. 320. ISBN ISBN 0-073-52340-2
  • Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. — Издательский дом "Вильямс", 2000. — С. 384. ISBN ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home