一、1946 蒙特卡洛方法

　?。?946： 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年，美國(guó)拉斯阿莫斯國(guó)家實(shí)驗(yàn)室的三位科學(xué)家John von Neumann，Stan Ulam 和 Nick Metropolis 共同發(fā)明，被稱為蒙特卡洛方法。

　　它的具體定義是：

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

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

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

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

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

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

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

　　二、1947 單純形法

　　［1947： George Dantzig， at the RAND Corporation， creates the simplex method for linear programming.］

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

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

　　所謂線性規(guī)劃，簡(jiǎn)單的說(shuō)，就是給定一組線性（所有變量都是一次冪）約束條件（例如a1*x1+b1*x2+c1*x3》0），求一個(gè)給定的目標(biāo)函數(shù)的極值。

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

　　線性規(guī)劃作為運(yùn)籌學(xué)（operation research）的一部分，成為管理科學(xué)領(lǐng)域的一種重要工具。而Dantzig提出的單純形法便是求解類似線性規(guī)劃問(wèn)題的一個(gè)極其有效的方法。

　　三、1950 Krylov 子空間迭代法

　?。?950： 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年：美國(guó)國(guó)家標(biāo)準(zhǔn)局?jǐn)?shù)值分析研究所的，馬格努斯Hestenes，愛德華施蒂費(fèi)爾和科尼利厄斯的Lanczos，發(fā)明了Krylov子空間迭代法。

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

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

　　四、1951 矩陣計(jì)算的分解方法

　?。?951： Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations.］

　　1951年，阿爾斯通橡樹嶺國(guó)家實(shí)驗(yàn)室的Alston Householder提出，矩陣計(jì)算的分解方法。

　　這個(gè)算法證明了任何矩陣都可以分解為三角、對(duì)角、正交和其他特殊形式的矩陣，該算法的意義使得開發(fā)靈活的矩陣計(jì)算軟件包成為可能。

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

　?。?957： John Backus leads a team at IBM in developing the Fortran optimizing compiler.］

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

　　Fortran，亦譯為福傳，是由Formula Translation兩個(gè)字所組合而成，意思是“公式翻譯”。它是世界上第一個(gè)被正式采用并流傳至今的高級(jí)編程語(yǔ)言。這個(gè)語(yǔ)言現(xiàn)在，已經(jīng)發(fā)展到了，F(xiàn)ortran 2008，并為人們所熟知。

　　六、1959-61 計(jì)算矩陣特征值的QR算法

　?。?959–61： J.G.F. Francis of Ferranti Ltd， London， finds a stable method for computing eigenvalues， known as the QR algorithm.］

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

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

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

　　這個(gè)算法的作者是來(lái)自英國(guó)倫敦的J.G.F. Francis。

　　七、1962 快速排序算法

　　［1962： Tony Hoare of Elliott Brothers， Ltd.， London， presents Quicksort.］

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

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

　　快速排序算法作為排序算法中的經(jīng)典算法，它被應(yīng)用的影子隨處可見。快速排序算法最早由Tony Hoare爵士設(shè)計(jì)，它的基本思想是將待排序列分為兩半，左邊的一半總是“小的”，右邊的一半總是“大的”，這一過(guò)程不斷遞歸持續(xù)下去，直到整個(gè)序列有序。

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

　　快速排序的平均時(shí)間復(fù)雜度僅僅為O（Nlog（N）），相比于普通選擇排序和冒泡排序等而言，實(shí)在是歷史性的創(chuàng)舉。

　　八、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，和普林斯頓大學(xué)的John Tukey，AT＆T貝爾實(shí)驗(yàn)室共同推出了快速傅立葉變換。

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

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

　?。?977： Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm.］

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

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

　　給定—組實(shí)數(shù)X1，X2，…，Xn，是否存在不全為零的整數(shù)a1，a2，…an，使得：a1x1 + a2x2 + 。 . 。 + anxn ＝0？

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

　　該算法應(yīng)用于“簡(jiǎn)化量子場(chǎng)論中的Feynman圖的計(jì)算”。ok，它并不要你懂，了解即可。：D。

　　十、1987 快速多極算法

　?。?987： Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm.］

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

　　此快速多極算法用來(lái)計(jì)算“經(jīng)由引力或靜電力相互作用的N 個(gè)粒子運(yùn)動(dòng)的精確計(jì)算——例如銀河系中的星體，或者蛋白質(zhì)中的原子間的相互作用”。ok，了解即可。