Алгоритм — это простейшая система действий для решения задачи или класса задач. Алгоритмы состоят из конечного числа четко определенных отдельных шагов. Сформулированные на естественном языке, они реализовываются в компьютерных программах. При решении задачи специфические исходные данные преобразуются в конкретные результаты.
Вот пять алгоритмов, которые оказали значительное влияние на наш мир.
1. Алгоритм Метрополиса для метода Монте-Карло
Алгоритм Метрополиса — это метод Монте-Карло с цепями Маркова, который применяется для генерации состояний системы в соответствии с распределением Больцмана.
На основе этого алгоритма был выведен более обобщенный алгоритм Метрополиса-Гастингса, который позволяет моделировать последовательности случайных величин, точнее цепи Маркова.
В цепях Маркова целевое распределение сходится со стационарным распределением. Чаще всего это наблюдается в случаях, когда распределения случайных величин не могут быть смоделированы естественным образом.
2. Симплексный метод линейного программирования
Симплексный метод (также известный как симплексный алгоритм) — это численный метод оптимизации для решения задач линейной оптимизации, также известных как линейные программы (LP). Он решает такую задачу только после конечного числа шагов либо определяет ее неразрешимость или неограниченность.
Основную идею симплексных методов представил Джордж Данциг в 1947 году. С тех пор они стали важнейшими методами решения задач линейной оптимизации на практике благодаря многочисленным улучшениям. Симплексные методы — это методы нахождения опорного плана.
3. Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ) — это алгоритм для ускоренного вычисления дискретного преобразования Фурье (ДПФ). Он может быть использован для разложения цифрового сигнала на частотные компоненты с последующим их анализом. Аналогично применяют обратное быстрое преобразование Фурье (ОБПФ) для дискретного обратного преобразования Фурье. ОБПФ использует те же алгоритмы, но с сопряженными коэффициентами.
БПФ находит множество применений в инженерии, естественных науках и прикладной математике. Он также используется в мобильных технологиях, таких как UMTS и LTE, и беспроводной передаче данных, например, в WLAN.
4. Алгоритм быстрой сортировки
Быстрая сортировка — это скоростной, рекурсивный, нестабильный алгоритм сортировки, который работает по принципу “разделяй и властвуй”. Он был разработан примерно в 1960 году К. Энтони Р. Хоаром и впоследствии усовершенствован многими исследователями.
Преимуществом алгоритма является очень короткий внутренний цикл (что значительно увеличивает скорость выполнения). Он не требует дополнительной памяти (кроме дополнительного пространства, необходимого в стеке вызовов для рекурсии).
5. QR-алгоритм вычисления собственных значений
QR-алгоритм — это численный метод вычисления всех собственных значений и зачастую собственных векторов квадратичной матрицы. QR-метод, или QR-итерация, основан на QR-декомпозиции и был введен независимо Джоном Г. Ф. Фрэнсисом и В. Н. Кублановской в 1961–1962 годах. Предшественником QR-алгоритма был LR-алгоритм Хайнца Рутисхаузера (1958), основанный на LR-декомпозиции и менее стабильный.
Часто итерации из QR-алгоритма сходятся к форме Шура матрицы. Поэтому исходная процедура довольно сложна — даже на современных компьютерах — и не применима для матриц с сотнями тысяч строк и столбцов.
Производные варианты, такие как многосменный метод З. Бая и Джеймса Деммеля (1989 г.) и численно более стабильный вариант К. Брамана, Р. Байерса и Р. Матиаса (2002 г.) имеют оперативные периоды выполнения с кубической зависимостью от размера матрицы. Последний метод реализован в библиотеке численных расcчётов LAPACK, которая используется во многих системах компьютерной алгебры для численных матричных алгоритмов.
Если бы мне пришлось выбрать один из этих алгоритмов, моим фаворитом стал бы БПФ. Быстрое преобразование Фурье (БПФ) не только находит множество применений в инженерии, естественных науках и прикладной математике, но и восхищает присущей ему красотой.
Читайте также:
- Алгоритмы ограничения скорости
- Завораживающая последовательность Фибоначчи
- Графы и пути: Алгоритм Брона-Кербоша, максимальные группы
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Murat Durmus: 5 Algorithms that Changed the World
