細數二十世紀最偉大的十大演算法

作者|By Barry A. Cipra譯者|July

轉載自xiazdong的博客

發明十大演算法的其中幾位演算法大師

一、1946 蒙特卡洛方法

[1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.]

1946年，美國拉斯阿莫斯國家實驗室的三位科學家John von Neumann,Stan Ulam 和 Nick Metropolis共同發明，被稱為蒙特卡洛方法。

它的具體定義是：在廣場上畫一個邊長一米的正方形，在正方形內部隨意用粉筆畫一個不規則的形狀，現在要計算這個不規則圖形的面積，怎麼計算列?

蒙特卡洛(Monte Carlo)方法告訴我們，均勻的向該正方形內撒N（N 是一個很大的自然數）個黃豆，隨後數數有多少個黃豆在這個不規則幾何形狀內部，比如說有M個，那麼，這個奇怪形狀的面積便近似於M/N，N越大，算出來的值便越精確。

在這裡我們要假定豆子都在一個平面上，相互之間沒有重疊。(撒黃豆只是一個比喻。)蒙特卡洛方法可用於近似計算圓周率：讓計算機每次隨機生成兩個0到1之間的數，看這兩個實數是否在單位圓內。生成一系列隨機點，統計單位圓內的點數與總點數，內接圓面積和正方形面積之比為PI:4，PI為圓周率。當隨機點取得越多（但即使取10的9次方個隨機點時，其結果也僅在前4位與圓周率吻合）時，其結果越接近於圓周率。

二、1947 單純形法

[1947: George Dantzig, at the RAND Corporation, creates the simplex method for linear programming.]

1947年，蘭德公司的，Grorge Dantzig，發明了單純形方法。

單純形法，此後成為了線性規劃學科的重要基石。

所謂線性規劃，簡單的說，就是給定一組線性（所有變數都是一次冪）約束條件（例如a1*x1+b1*x2+c1*x3>0)，求一個給定的目標函數的極值。

這麼說似乎也太太太抽象了，但在現實中能派上用場的例子可不罕見——比如對於一個公司而言，其能夠投入生產的人力物力有限（「線性約束條件」），而公司的目標是利潤最大化（「目標函數取最大值」），看，線性規劃並不抽象吧！

線性規劃作為運籌學(operation research)的一部分，成為管理科學領域的一種重要工具。而Dantzig提出的單純形法便是求解類似線性規劃問題的一個極其有效的方法。

三、1950 Krylov子空間迭代法

[1950: Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos, all from the Institute for Numerical Analysis at the National Bureau of Standards, initiate the development of Krylov subspace iteration methods.]

1950年：美國國家標準局數值分析研究所的，馬格努斯Hestenes，愛德華施蒂費爾和科尼利厄斯的Lanczos，發明了Krylov子空間迭代法。

Krylov子空間迭代法是用來求解形如Ax=b 的方程，A是一個n*n 的矩陣，當n充分大時，直接計算變得非常困難，而Krylov方法則巧妙地將其變為Kxi+1=Kxi+b-Axi的迭代形式來求解。

這裡的K(來源於作者俄國人Nikolai Krylov姓氏的首字母)是一個構造出來的接近於A的矩陣，而迭代形式的演算法的妙處在於，它將複雜問題化簡為階段性的易於計算的子步驟。

四、1951 矩陣計算的分解方法

[1951: Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations.]

1951年，阿爾斯通橡樹嶺國家實驗室的Alston Householder提出，矩陣計算的分解方法。這個演算法證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣，該演算法的意義使得開發靈活的矩陣計算軟體包成為可能。

五、1957 優化的Fortran編譯器

[1957: John Backus leads a team at IBM in developing the Fortran optimizing compiler.]

1957年：約翰巴庫斯領導開發的IBM的團隊，創造了Fortran優化編譯器。Fortran，亦譯為福傳，是由Formula Translation兩個字所組合而成，意思是「公式翻譯」。它是世界上第一個被正式採用併流傳至今的高級編程語言。這個語言現在，已經發展到了，Fortran 2008，並為人們所熟知。

六、1959-61 計算矩陣特徵值的QR演算法

[1959–61: J.G.F. Francis of Ferranti Ltd, London, finds a stable method for computing eigenvalues, known as the QR algorithm.]

1959-61：倫敦費倫蒂有限公司的J.G.F. Francis，找到了一種穩定的特徵值的計算方法，這就是著名的QR演算法。這也是一個和線性代數有關的演算法，學過線性代數的應該記得「矩陣的特徵值」，計算特徵值是矩陣計算的最核心內容之一，傳統的求解方案涉及到高次方程求根，當問題規模大的時候十分困難。

QR演算法把矩陣分解成一個正交矩陣(希望讀此文的你，知道什麼是正交矩陣。:D。)與一個上三角矩陣的積，和前面提到的Krylov 方法類似，這又是一個迭代演算法，它把複雜的高次方程求根問題化簡為階段性的易於計算的子步驟，使得用計算機求解大規模矩陣特徵值成為可能。這個演算法的作者是來自英國倫敦的J.G.F. Francis。

七、1962 快速排序演算法

[1962: Tony Hoare of Elliott Brothers, Ltd., London, presents Quicksort.]

1962年：倫敦的，托尼埃利奧特兄弟有限公司，霍爾提出了快速排序。哈哈，恭喜你，終於看到了可能是你第一個比較熟悉的演算法~。

快速排序演算法作為排序演算法中的經典演算法，它被應用的影子隨處可見。快速排序演算法最早由Tony Hoare爵士設計，它的基本思想是將待排序列分為兩半，左邊的一半總是「小的」，右邊的一半總是「大的」，這一過程不斷遞歸持續下去，直到整個序列有序。

說起這位Tony Hoare爵士，快速排序演算法其實只是他不經意間的小小發現而已，他對於計算機貢獻主要包括形式化方法理論，以及ALGOL60 編程語言的發明等，他也因這些成就獲得1980 年圖靈獎。快速排序的平均時間複雜度僅僅為O(Nlog(N))，相比於普通選擇排序和冒泡排序等而言，實在是歷史性的創舉。

八、1965 快速傅立葉變換

[1965: James Cooley of the IBM T.J. Watson Research Center and John Tukey of Princeton University and AT&T Bell Laboratories unveil the fast Fourier transform.]

1965年：IBM 華生研究院的James Cooley，和普林斯頓大學的John Tukey，AT＆T貝爾實驗室共同推出了快速傅立葉變換。快速傅立葉演算法是離散傅立葉演算法（這可是數字信號處理的基石）的一種快速演算法，其時間複雜度僅為O(Nlog(N))；比時間效率更為重要的是，快速傅立葉演算法非常容易用硬體實現，因此它在電子技術領域得到極其廣泛的應用。日後，我會在我的經典演算法研究系列，著重闡述此演算法。

九、1977 整數關係探測演算法

[1977: Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integerrelation detection algorithm.]

1977年：Helaman Ferguson和 伯明翰大學的Rodney Forcade，提出了Forcade檢測演算法的整數關係。

整數關係探測是個古老的問題，其歷史甚至可以追溯到歐幾里德的時代。具體的說:給定—組實數X1,X2,...,Xn，是否存在不全為零的整數a1,a2,...an，使得:a1 x 1 +a2 x2 + . . . + an xn ＝0?

這一年BrighamYoung大學的Helaman Ferguson 和Rodney Forcade解決了這一問題。該演算法應用於「簡化量子場論中的Feynman圖的計算」。ok，它並不要你懂，了解即可。:D

十、1987 快速多極演算法

[1987: Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipolealgorithm.]

1987年：Greengard，和耶魯大學的Rokhlin發明了快速多極演算法。此快速多極演算法用來計算「經由引力或靜電力相互作用的N 個粒子運動的精確計算——例如銀河系中的星體，或者蛋白質中的原子間的相互作用」。

參考文獻：The Best of the 20th Century: Editors Name Top 10 Algorithms。

地址：http://www.uta.edu/faculty/rcli/TopTen/topten.pdf。

請您繼續閱讀更多來自 大數據文摘 的精彩文章:

TAG:大數據文摘 |

※細數十大最美皇后
※細數全球十二大神奇絕妙的天坑
※細數三國七大成功人士
※細數崇禎帝是大清國卧底的八大理由
※細數大明王朝的各種世界第一
※細數中國十大貪官的情婦
※細數韓國大學裡十大奇葩課程
※細數十二星座的優點
※細數中國十大國粹
※細數史上專坑皇帝的十大丞相
※細數影史上的十大最賠錢角色，第一名是大名鼎鼎的他
※弱宋？細數鐵血大宋十大名將，有一人被列入千古十大名將之一
※細數春秋戰國的八大名將，廉頗倒數，白起第二
※細數英國三大名校之最
※細數被經紀人坑的最慘明星，王寶強第二，第一公認娛樂圈大腕
※細數歷史上十大好色文人
※殘忍坑殺二十萬人 劉邦細數項羽十大罪狀！
※細數五大梁山好漢的剋星：第二獨斬七人，第一無爭議
※細數中國的六大武將：呂布上榜，第一千古無二