一、1946 蒙特卡洛方法

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

　　它的具體定義是：

　　在廣場上畫一個邊長一米的正方形，在正方形內(nèi)部隨意用粉筆畫一個不規(guī)則的形狀，現(xiàn)在要計算這個不規(guī)則圖形的面積，怎么計算列？

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

　　在這里我們要假定豆子都在一個平面上，相互之間沒有重疊。（撒黃豆只是一個比喻。）

　　蒙特卡洛方法可用于近似計算圓周率：

　　讓計算機每次隨機生成兩個0到1之間的數(shù)，看這兩個實數(shù)是否在單位圓內(nèi)。

　　生成一系列隨機點，統(tǒng)計單位圓內(nèi)的點數(shù)與總點數(shù)，內(nèi)接圓面積和正方形面積之比為PI:4，PI為圓周率。

　　當(dāng)隨機點取得越多（但即使取10的9次方個隨機點時，其結(jié)果也僅在前4位與圓周率吻合）時，其結(jié)果越接近于圓周率。

　　二、1947 單純形法

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

　　單純形法，此后成為了線性規(guī)劃學(xué)科的重要基石。

　　所謂線性規(guī)劃，簡單的說，就是給定一組線性（所有變量都是一次冪）約束條件

　?。ɡ鏰1*x1+b1*x2+c1*x3》0），求一個給定的目標(biāo)函數(shù)的極值。

　　這么說似乎也太太太抽象了，但在現(xiàn)實中能派上用場的例子可不罕見——比如對于一個公司而言，其能夠投入生產(chǎn)的人力物力有限（“線性約束條件”），而公司的目標(biāo)是利潤最大化（“目標(biāo)函數(shù)取最大值”），看，線性規(guī)劃并不抽象吧！

　　線性規(guī)劃作為運籌學(xué)（operation research）的一部分，成為管理科學(xué)領(lǐng)域的一種重要工具。

　　而Dantzig提出的單純形法便是求解類似線性規(guī)劃問題的一個極其有效的方法。

　　三、1950 Krylov子空間迭代法

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

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

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

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

　　1951年，阿爾斯通橡樹嶺國家實驗室的Alston Householder提出，矩陣計算的分解方法。

　　這個算法證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣，

　　該算法的意義使得開發(fā)靈活的矩陣計算軟件包成為可能。

　　五、1957 優(yōu)化的Fortran編譯器

　　1957年：約翰巴庫斯領(lǐng)導(dǎo)開發(fā)的IBM的團隊，創(chuàng)造了Fortran優(yōu)化編譯器。

　　Fortran，亦譯為福傳，是由Formula Translation兩個字所組合而成，意思是“公式翻譯”。

　　它是世界上第一個被正式采用并流傳至今的高級編程語言。

　　這個語言現(xiàn)在，已經(jīng)發(fā)展到了，F(xiàn)ortran 2008，并為人們所熟知。

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

　　1959-61：倫敦費倫蒂有限公司的J.G.F. Francis，找到了一種穩(wěn)定的特征值的計算方法，這就是著名的QR算法。

　　這也是一個和線性代數(shù)有關(guān)的算法，學(xué)過線性代數(shù)的應(yīng)該記得“矩陣的特征值”，計算特征值是矩陣計算的最核心內(nèi)容之一，傳統(tǒng)的求解方案涉及到高次方程求根，當(dāng)問題規(guī)模大的時候十分困難。

　　QR算法把矩陣分解成一個正交矩陣（希望讀此文的你，知道什么是正交矩陣。：D。）與一個上三角矩陣的積，和前面提到的Krylov 方法類似，這又是一個迭代算法，它把復(fù)雜的高次方程求根問題化簡為階段性的易于計算的子步驟，使得用計算機求解大規(guī)模矩陣特征值成為可能。

　　這個算法的作者是來自英國倫敦的J.G.F. Francis。

　　七、1962 快速排序算法

　　1962年：倫敦的，托尼埃利奧特兄弟有限公司，霍爾提出了快速排序。

　　哈哈，恭喜你，終于看到了可能是你第一個比較熟悉的算法~。

　　快速排序算法作為排序算法中的經(jīng)典算法，它被應(yīng)用的影子隨處可見。

　　快速排序算法最早由Tony Hoare爵士設(shè)計，它的基本思想是將待排序列分為兩半，左邊的一半總是“小的”，右邊的一半總是“大的”，這一過程不斷遞歸持續(xù)下去，直到整個序列有序。

　　說起這位Tony Hoare爵士，快速排序算法其實只是他不經(jīng)意間的小小發(fā)現(xiàn)而已，他對于計算機貢獻主要包括形式化方法理論，以及ALGOL60 編程語言的發(fā)明等，他也因這些成就獲得1980 年圖靈獎。

　　快速排序的平均時間復(fù)雜度僅僅為O（Nlog（N）），相比于普通選擇排序和冒泡排序等而言，

　　實在是歷史性的創(chuàng)舉。

　　八、1965 快速傅立葉變換

　　1965年：IBM 華生研究院的James Cooley，和普林斯頓大學(xué)的John Tukey，AT＆T貝爾實驗室共同推出了快速傅立葉變換。

　　快速傅立葉算法是離散傅立葉算法（這可是數(shù)字信號處理的基石）的一種快速算法，其時間復(fù)雜度僅為O（Nlog（N））；比時間效率更為重要的是，快速傅立葉算法非常容易用硬件實現(xiàn)，因此它在電子技術(shù)領(lǐng)域得到極其廣泛的應(yīng)用。

　　九、1977 整數(shù)關(guān)系探測算法

　　1977年：Helaman Ferguson和 伯明翰大學(xué)的Rodney Forcade，提出了Forcade檢測算法的整數(shù)關(guān)系。

　　整數(shù)關(guān)系探測是個古老的問題，其歷史甚至可以追溯到歐幾里德的時代。具體的說：

　　給定—組實數(shù)X1，X2，。..，Xn，是否存在不全為零的整數(shù)

　　a1，a2，。..an，使得：a1 x 1 +a2 x2 + 。 . 。 + an x n ＝0？

　　這一年BrighamYoung大學(xué)的Helaman Ferguson 和Rodney Forcade解決了這一問題。

　　該算法應(yīng)用于“簡化量子場論中的Feynman圖的計算”。

　　十、1987 快速多極算法

　　1987年：Greengard，和耶魯大學(xué)的Rokhlin發(fā)明了快速多極算法。

　　此快速多極算法用來計算“經(jīng)由引力或靜電力相互作用的N 個粒子運動的精確計算

　　——例如銀河系中的星體，或者蛋白質(zhì)中的原子間的相互作用”。