一、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年，美國拉斯阿莫斯國家實驗室的三位科學(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為圓周率。

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

　　二、1947 單純形法

　?。?947： George Dantzig， at the RAND Corporation， creates the simplex method for linear programming.］

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

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

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

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

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

　　三、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年：美國國家標準局數(shù)值分析研究所的，馬格努斯Hestenes，愛德華施蒂費爾和科尼利厄斯的Lanczos，發(fā)明了Krylov子空間迭代法。

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

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

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

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

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

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

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

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

　　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 of Ferranti Ltd， London， finds a stable method for computing eigenvalues， known as the QR algorithm.］

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

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

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

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

　　七、1962 快速排序算法

　?。?962： Tony Hoare of Elliott Brothers， Ltd.， London， presents Quicksort.］

　　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 快速傅立葉變換

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

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

　　［1977： Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm.］

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

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

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

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

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

　　十、1987 快速多極算法

　　［1987： Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm.］

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

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