Прим. Эта статья была опубликована в майском номере 2000 года журнала SIAM. На рубеже веков появилась «мода» на подведение итогов уходящего столетия. И алгоритмы этой участи не избежали. В этой статье авторы делают обзор 10 лучших алгоритмов 20 века. Возможно, вам будет интересно узнать, какие алгоритмы, по мнению авторов списка, внесли наибольший вклад в развитие науки.
Algos — греческое слово, означающее боль. Algor — латинское слово, означающее холод. Но ни то, ни другое не является корнем слова «алгоритм», которое происходит от имени Аль-Хорезми – арабского ученого девятого века – чья книга «al-jabr wa’l muqabalah» (Китаб аль-джебр ва-ль-мукабала) переросла современные учебники по алгебре для средней школы. Аль-Хорезми подчеркивал важность методических процедур для решения задач. Будь он сегодня здесь, то, несомненно, был бы впечатлен вершинами математического метода, названного в его честь.
Часть из лучших алгоритмов компьютерной эры были освещены в январско-февральском выпуске 2000 года журнала Computing in Science & Engineering — совместном издании Американского института физики и Компьютерного общества IEEE. Приглашенные редакторы Jack Dongarra (Джек Донгарра) из Университета Теннесси и Francis Sullivan (Фрэнсис Салливан) из Института оборонного анализа составили список из 10 алгоритмов, который они назвали «Top Ten Algorithms of the Century».
«Мы попытались собрать 10 алгоритмов, оказавших наибольшее влияние на развитие и практику науки и техники в 20 веке», — пишут Донгарра и Салливан. По признанию авторов, как и в любом рейтинге, их выборы неизбежно будут спорными. Когда дело доходит до выбора лучшего алгоритма, кажется, что он и вовсе не существует.
Итак, вот список 10 лучших алгоритмов в хронологическом порядке. (Все даты и имена стоит воспринимать как аппроксимацию первого порядка. Большинство алгоритмов формируются в течение времени при участии многих ученых).
Джон фон Нейман, Станислав Улам и Николас Метрополис, работая в Лос-Аламосской научной лаборатории, разработали алгоритм Метрополиса, также известный как метод Монте-Карло.
Алгоритм Метрополиса предназначен для получения приближенных решений численных задач с неуправляемым числом степеней свободы и комбинаторных задач факториального размера путем имитации случайного процесса. Учитывая репутацию цифрового компьютера как детерминированного устройства, вполне уместно считать, что одним из самых ранних его применений была генерация случайных чисел.
Джордж Данциг, работавший в корпорации RAND, создал симплекс-метод для линейного программирования. С точки зрения широты применения алгоритм Данцига является одним из самых успешных за все время: линейное программирование доминирует в мире промышленности, где экономическое выживание зависит от способности к оптимизации в рамках бюджета и других ограничений. (Конечно, «реальные» проблемы промышленности зачастую нелинейны; использование линейного программирования иногда диктуется computational budget). Симплекс-метод — это элегантный способ решения оптимизационных задач. Хотя в теории алгоритм и подвержен экспоненциальным задержкам, на практике он очень эффективен, что само по себе говорит кое-что интересное о природе вычислений.
Магнус Хестенес, Эдуард Штифель и Корнелий Ланцош, все из Института численного анализа при Национальном бюро стандартов, начали разработку итерационных алгоритмов подпространства Крылова.
Эти алгоритмы решают, казалось бы, простую задачу — решение уравнений вида Ax = b. Загвоздка заключалась в том, что A — это огромная матрица n * n, так что алгебраический ответ x = b/A не так-то просто вычислить. (И действительно, «деление» матрицы не является особенно полезным понятием.) Итерационные методы, например решение уравнений такого вида:
с более простой матрицей K, которая идеально «близка» к матрице A, привели к изучению подпространств Крылова. Ланцош нашел отличный способ сгенерировать ортогональный базис для такого подпространства, когда матрица является симметричной. Хестенес и Штифель предложили еще более хитрый метод, известный как метод сопряженного градиента, для систем, которые являются симметричными и положительно определенными. За последние 50 лет большое количество исследователей внесли свой вклад в развитие этих алгоритмов, улучшив и расширив их.
Современный набор алгоритмов включает методы для несимметричных систем с такие, как GMRES и Bi-CGSTAB. (GMRES и Bi-CGSTAB были впервые опубликованы в журнале SIAM Journal on Scientific and Statistical Computing в 1986 и 1992 гг, соответственно).
Элстон Хаусхолдер из Окриджской национальной лаборатории формализовал декомпозиционный подход к матричным вычислениям.
Возможность разложения матриц на треугольные, диагональные, ортогональные и другие специальные формы оказалась чрезвычайно полезной. Декомпозиционный подход позволил разработчикам программного обеспечения создавать гибкие и эффективные матричные пакеты. Также такой подход облегчил анализ ошибок округления, одной из главных проблем численной линейной алгебры. (В 1961 году Джеймс Уилкинсон из Национальной физической лаборатории в Лондоне опубликовал в журнале ACM основополагающую работу под названием «Анализ ошибок прямых методов инверсии матриц», основанный на LU-разложении матрицы как произведения нижнего и верхнего треугольных коэффициентов).
Джон Бэкус возглавлял группу в IBM по разработке оптимизирующего компилятора Fortran.
Создание Fortran может считаться одним из самых важных событий в истории компьютерного программирования: наконец-то ученые (и другие пользователи) могли сообщить компьютеру, чего они хотят без необходимости погружаться в мир машинного кода.
Хотя, конечно, по современным стандартам компиляторы были скромными — Фортран I состоял всего из 23 500 инструкций на языке ассемблера. Но, тем не менее, «ранний» компилятор был способен на удивительно сложные вычисления. По воспоминания самого Джона Бэкуса (в опубликованной в 1998 году статье) компилятор создавал невероятно эффективный код, поражавший программистов.
Джон Фрэнсис из компании Ferranti Ltd. нашел устойчивый метод вычисления собственных значений, известный как QR-алгоритм.
Собственные значения — это, пожалуй, самые важные числа, связанные с матрицами, и порой их очень сложно вычислить. Относительно легко преобразовать квадратную матрицу в «почти» верхнетреугольную матрицу с дополнительным набором ненулевых записей чуть ниже главной диагонали. Но убрать эти ненулевые значения, не допустив лавины из ошибок — нетривиальная задача. Алгоритм QR — это как раз то, что нужно для решения этой задачи. На основе QR-разложения, которое записывает матрицу A как произведение ортогональной матрицы Q и верхнетреугольной матрицы R, этот подход итеративно меняет
на 
, с несколькими дополнениями для ускорения сходимости к верхнетреугольной форме. К середине 1960-х годов алгоритм QR превратил некогда серьезные проблемы собственных значений в рутинные вычисления.
Тони Хоар из компании Elliott Brothers, Ltd., Лондон разработал алгоритм Quicksort.
Расположить N предметов в числовом или алфавитном порядке — это скучная рутина. Интеллектуальный вызов заключается в том, чтобы сделать это быстро. Алгоритм Хоара использует вековую рекурсивную стратегию «разделяй и властвуй» для решения проблемы: необходимо выбрать один элемент в качестве «стержня», разделить остальные на кучи «больших» и «маленьких» элементов (по сравнению со стержнем), а затем повторить процедуру с каждой кучей. Хотя можно и встрять, выполнив все N(N — 1)/2 итераций (особенно выбрать в качестве стержня первый элемент отсортированного списка), средняя сложность Quicksort составляет O(N log N). Элегантная простота сделала Quicksort образцом вычислительной сложности
Джеймс Кули из Исследовательского центра IBM и Джон Тьюки из Принстонского Университета разработали быстрые преобразования Фурье.
Несомненно, как самый масштабный алгоритм в прикладной математике, БПФ произвели революцию в области обработке сигналов. Основополагающая идея восходит к Гауссу (которому когда-то нужно было вычислить орбиты астероидов), но именно из работы Кули-Тьюки стало ясно, насколько легко могут вычисляться преобразования Фурье.
Подобно Quicksort, БПФ опирается на стратегию «разделяй и властвуй», чтобы сократить якобы квадратичную сложность до O(N log N). Но в отличие от Quicksort, реализация БПФ (на первый взгляд) нетривиальна и не интуитивна. Это дало толчок к исследованию сложности, присущей вычислительным задачам и алгоритмам.
Хеламан Фергюсон и Родни Форкейд из Университета Бригама Янга разработали алгоритм обнаружения целочисленных отношений.
Формулировка проблемы такая: пусть
— набор вещественных чисел. Существует ли набор целых числа 
(хотя бы одно из которых не равно нулю), для которых 
? При n = 2 с этой задачей справляется старый добрый алгоритм Евклида, работающий на дробном разложении x1/x2. Если x1/x2 рационально, то разложение, в конечном счете, завершится и, при правильном подходе, даст наименьшие целые a1 и a2.
Если алгоритм Евклида не завершается (или если вы просто устали его вычислять), то алгоритм, по крайней мере, даёт нижнюю границу наименьшего целочисленного отношения. Обобщение Фергюсона и Форкейда, которое гораздо сложнее реализовать и понять, является более мощным. Их алгоритм обнаружения, например, был использован для нахождения точные коэффициенты полиномов, которым удовлетворяют третья и четвертая точки бифуркации: B3 = 3,544090 и B4 = 3,564407, логистической карты. (Последний полином имел степень 120; его наибольший коэффициент равен 25730). Этот подход также оказался полезным для упрощения вычислений с диаграммами Фейнмана в квантовой теории поля.
Лесли Грингард и Владимир Рохлин из Йельского университета изобретают метод быстрого мультиполя.
Этот алгоритм преодолевает одну из самых больших головных болей при моделировании системы из N тел: точные расчеты движения N частиц, взаимодействующих посредством гравитационных или электростатических силы (вспомните звезды в галактике или атомы в белке), казалось бы, требуют O(N2) вычислений — по одному для каждой пары частиц. Но сложность быстрого метода мультиполя равна O(N). Это достигается путем использования мультипольных разложения (чистый заряд или масса, дипольный момент, квадруполь и т.д.) для аппроксимации влияния удаленной группы частиц на локальную группу. Иерархическая декомпозиция пространства используется для определения всё более крупных групп по мере увеличения расстояния.
Одно из явных преимуществ быстрого мультипольного алгоритма заключается в том, что он оснащен строгими оценками ошибок, чего не хватает многим другим методам.
Какие новые идеи и алгоритмы принесет 21 век? Полный ответ на этот вопрос, очевидно, будет известен лишь через сто лет. Одно кажется несомненным. Как пишет Салливан во введении «новый век не будет для нас очень спокойным, но и скучным он тоже не будет!»
Algos — греческое слово, означающее боль. Algor — латинское слово, означающее холод. Но ни то, ни другое не является корнем слова «алгоритм», которое происходит от имени Аль-Хорезми – арабского ученого девятого века – чья книга «al-jabr wa’l muqabalah» (Китаб аль-джебр ва-ль-мукабала) переросла современные учебники по алгебре для средней школы. Аль-Хорезми подчеркивал важность методических процедур для решения задач. Будь он сегодня здесь, то, несомненно, был бы впечатлен вершинами математического метода, названного в его честь.
Часть из лучших алгоритмов компьютерной эры были освещены в январско-февральском выпуске 2000 года журнала Computing in Science & Engineering — совместном издании Американского института физики и Компьютерного общества IEEE. Приглашенные редакторы Jack Dongarra (Джек Донгарра) из Университета Теннесси и Francis Sullivan (Фрэнсис Салливан) из Института оборонного анализа составили список из 10 алгоритмов, который они назвали «Top Ten Algorithms of the Century».
«Мы попытались собрать 10 алгоритмов, оказавших наибольшее влияние на развитие и практику науки и техники в 20 веке», — пишут Донгарра и Салливан. По признанию авторов, как и в любом рейтинге, их выборы неизбежно будут спорными. Когда дело доходит до выбора лучшего алгоритма, кажется, что он и вовсе не существует.
Итак, вот список 10 лучших алгоритмов в хронологическом порядке. (Все даты и имена стоит воспринимать как аппроксимацию первого порядка. Большинство алгоритмов формируются в течение времени при участии многих ученых).
1946. Метод Монте-Карло
Джон фон Нейман, Станислав Улам и Николас Метрополис, работая в Лос-Аламосской научной лаборатории, разработали алгоритм Метрополиса, также известный как метод Монте-Карло.
Алгоритм Метрополиса предназначен для получения приближенных решений численных задач с неуправляемым числом степеней свободы и комбинаторных задач факториального размера путем имитации случайного процесса. Учитывая репутацию цифрового компьютера как детерминированного устройства, вполне уместно считать, что одним из самых ранних его применений была генерация случайных чисел.
1947. Симплекс-метод
Джордж Данциг, работавший в корпорации RAND, создал симплекс-метод для линейного программирования. С точки зрения широты применения алгоритм Данцига является одним из самых успешных за все время: линейное программирование доминирует в мире промышленности, где экономическое выживание зависит от способности к оптимизации в рамках бюджета и других ограничений. (Конечно, «реальные» проблемы промышленности зачастую нелинейны; использование линейного программирования иногда диктуется computational budget). Симплекс-метод — это элегантный способ решения оптимизационных задач. Хотя в теории алгоритм и подвержен экспоненциальным задержкам, на практике он очень эффективен, что само по себе говорит кое-что интересное о природе вычислений.
1950. Подпространство Крылова
Магнус Хестенес, Эдуард Штифель и Корнелий Ланцош, все из Института численного анализа при Национальном бюро стандартов, начали разработку итерационных алгоритмов подпространства Крылова.
Эти алгоритмы решают, казалось бы, простую задачу — решение уравнений вида Ax = b. Загвоздка заключалась в том, что A — это огромная матрица n * n, так что алгебраический ответ x = b/A не так-то просто вычислить. (И действительно, «деление» матрицы не является особенно полезным понятием.) Итерационные методы, например решение уравнений такого вида:
с более простой матрицей K, которая идеально «близка» к матрице A, привели к изучению подпространств Крылова. Ланцош нашел отличный способ сгенерировать ортогональный базис для такого подпространства, когда матрица является симметричной. Хестенес и Штифель предложили еще более хитрый метод, известный как метод сопряженного градиента, для систем, которые являются симметричными и положительно определенными. За последние 50 лет большое количество исследователей внесли свой вклад в развитие этих алгоритмов, улучшив и расширив их.
Современный набор алгоритмов включает методы для несимметричных систем с такие, как GMRES и Bi-CGSTAB. (GMRES и Bi-CGSTAB были впервые опубликованы в журнале SIAM Journal on Scientific and Statistical Computing в 1986 и 1992 гг, соответственно).
1951. Матричные вычисления
Элстон Хаусхолдер из Окриджской национальной лаборатории формализовал декомпозиционный подход к матричным вычислениям.
Возможность разложения матриц на треугольные, диагональные, ортогональные и другие специальные формы оказалась чрезвычайно полезной. Декомпозиционный подход позволил разработчикам программного обеспечения создавать гибкие и эффективные матричные пакеты. Также такой подход облегчил анализ ошибок округления, одной из главных проблем численной линейной алгебры. (В 1961 году Джеймс Уилкинсон из Национальной физической лаборатории в Лондоне опубликовал в журнале ACM основополагающую работу под названием «Анализ ошибок прямых методов инверсии матриц», основанный на LU-разложении матрицы как произведения нижнего и верхнего треугольных коэффициентов).
1957. Fortran
Джон Бэкус возглавлял группу в IBM по разработке оптимизирующего компилятора Fortran.
Создание Fortran может считаться одним из самых важных событий в истории компьютерного программирования: наконец-то ученые (и другие пользователи) могли сообщить компьютеру, чего они хотят без необходимости погружаться в мир машинного кода.
Хотя, конечно, по современным стандартам компиляторы были скромными — Фортран I состоял всего из 23 500 инструкций на языке ассемблера. Но, тем не менее, «ранний» компилятор был способен на удивительно сложные вычисления. По воспоминания самого Джона Бэкуса (в опубликованной в 1998 году статье) компилятор создавал невероятно эффективный код, поражавший программистов.
1959-1961. QR-алгоритм
Джон Фрэнсис из компании Ferranti Ltd. нашел устойчивый метод вычисления собственных значений, известный как QR-алгоритм.
Собственные значения — это, пожалуй, самые важные числа, связанные с матрицами, и порой их очень сложно вычислить. Относительно легко преобразовать квадратную матрицу в «почти» верхнетреугольную матрицу с дополнительным набором ненулевых записей чуть ниже главной диагонали. Но убрать эти ненулевые значения, не допустив лавины из ошибок — нетривиальная задача. Алгоритм QR — это как раз то, что нужно для решения этой задачи. На основе QR-разложения, которое записывает матрицу A как произведение ортогональной матрицы Q и верхнетреугольной матрицы R, этот подход итеративно меняет
на , с несколькими дополнениями для ускорения сходимости к верхнетреугольной форме. К середине 1960-х годов алгоритм QR превратил некогда серьезные проблемы собственных значений в рутинные вычисления.1962. Quicksort
Тони Хоар из компании Elliott Brothers, Ltd., Лондон разработал алгоритм Quicksort.
Расположить N предметов в числовом или алфавитном порядке — это скучная рутина. Интеллектуальный вызов заключается в том, чтобы сделать это быстро. Алгоритм Хоара использует вековую рекурсивную стратегию «разделяй и властвуй» для решения проблемы: необходимо выбрать один элемент в качестве «стержня», разделить остальные на кучи «больших» и «маленьких» элементов (по сравнению со стержнем), а затем повторить процедуру с каждой кучей. Хотя можно и встрять, выполнив все N(N — 1)/2 итераций (особенно выбрать в качестве стержня первый элемент отсортированного списка), средняя сложность Quicksort составляет O(N log N). Элегантная простота сделала Quicksort образцом вычислительной сложности
1965. Быстрые преобразования Фурье
Джеймс Кули из Исследовательского центра IBM и Джон Тьюки из Принстонского Университета разработали быстрые преобразования Фурье.
Несомненно, как самый масштабный алгоритм в прикладной математике, БПФ произвели революцию в области обработке сигналов. Основополагающая идея восходит к Гауссу (которому когда-то нужно было вычислить орбиты астероидов), но именно из работы Кули-Тьюки стало ясно, насколько легко могут вычисляться преобразования Фурье.
Подобно Quicksort, БПФ опирается на стратегию «разделяй и властвуй», чтобы сократить якобы квадратичную сложность до O(N log N). Но в отличие от Quicksort, реализация БПФ (на первый взгляд) нетривиальна и не интуитивна. Это дало толчок к исследованию сложности, присущей вычислительным задачам и алгоритмам.
1977. Поиск целочисленных соотношений
Хеламан Фергюсон и Родни Форкейд из Университета Бригама Янга разработали алгоритм обнаружения целочисленных отношений.
Формулировка проблемы такая: пусть
— набор вещественных чисел. Существует ли набор целых числа (хотя бы одно из которых не равно нулю), для которых ? При n = 2 с этой задачей справляется старый добрый алгоритм Евклида, работающий на дробном разложении x1/x2. Если x1/x2 рационально, то разложение, в конечном счете, завершится и, при правильном подходе, даст наименьшие целые a1 и a2.Если алгоритм Евклида не завершается (или если вы просто устали его вычислять), то алгоритм, по крайней мере, даёт нижнюю границу наименьшего целочисленного отношения. Обобщение Фергюсона и Форкейда, которое гораздо сложнее реализовать и понять, является более мощным. Их алгоритм обнаружения, например, был использован для нахождения точные коэффициенты полиномов, которым удовлетворяют третья и четвертая точки бифуркации: B3 = 3,544090 и B4 = 3,564407, логистической карты. (Последний полином имел степень 120; его наибольший коэффициент равен 25730). Этот подход также оказался полезным для упрощения вычислений с диаграммами Фейнмана в квантовой теории поля.
1987. Мультиполя
Лесли Грингард и Владимир Рохлин из Йельского университета изобретают метод быстрого мультиполя.
Этот алгоритм преодолевает одну из самых больших головных болей при моделировании системы из N тел: точные расчеты движения N частиц, взаимодействующих посредством гравитационных или электростатических силы (вспомните звезды в галактике или атомы в белке), казалось бы, требуют O(N2) вычислений — по одному для каждой пары частиц. Но сложность быстрого метода мультиполя равна O(N). Это достигается путем использования мультипольных разложения (чистый заряд или масса, дипольный момент, квадруполь и т.д.) для аппроксимации влияния удаленной группы частиц на локальную группу. Иерархическая декомпозиция пространства используется для определения всё более крупных групп по мере увеличения расстояния.
Одно из явных преимуществ быстрого мультипольного алгоритма заключается в том, что он оснащен строгими оценками ошибок, чего не хватает многим другим методам.
Какие новые идеи и алгоритмы принесет 21 век? Полный ответ на этот вопрос, очевидно, будет известен лишь через сто лет. Одно кажется несомненным. Как пишет Салливан во введении «новый век не будет для нас очень спокойным, но и скучным он тоже не будет!»
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
