電子發燒友App
一、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年，美國拉斯阿莫斯國家實驗室的三位科學家John von Neumann，Stan Ulam 和 Nick Metropolis 共同發明，被稱為蒙特卡洛方法。
它的具體定義是：
在廣場上畫一個邊長一米的正方形，在正方形內部隨意用粉筆畫一個不規則的形狀，現在要計算這個不規則圖形的面積，怎么計算列？
蒙特卡洛（Monte Carlo）方法告訴我們，均勻的向該正方形內撒N（N 是一個很大的自然數）個黃豆，隨后數數有多少個黃豆在這個不規則幾何形狀內部，比如說有M個，那么，這個奇怪形狀的面積便近似于M/N，N越大，算出來的值便越精確。
在這里我們要假定豆子都在一個平面上，相互之間沒有重疊。（撒黃豆只是一個比喻。）
蒙特卡洛方法可用于近似計算圓周率：
讓計算機每次隨機生成兩個0到1之間的數，看這兩個實數是否在單位圓內。
生成一系列隨機點，統計單位圓內的點數與總點數，內接圓面積和正方形面積之比為PI:4，PI為圓周率。
當隨機點取得越多（但即使取10的9次方個隨機點時，其結果也僅在前4位與圓周率吻合）時，其結果越接近于圓周率。
二、1947 單純形法
?。?947： 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 子空間迭代法
?。?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年：美國國家標準局數值分析研究所的，馬格努斯Hestenes，愛德華施蒂費爾和科尼利厄斯的Lanczos，發明了Krylov子空間迭代法。
Krylov子空間迭代法是用來求解形如Ax=b 的方程，A是一個n*n 的矩陣，當n充分大時，直接計算變得非常困難，而Krylov方法則巧妙地將其變為Kxi+1=Kxi+b-Axi的迭代形式來求解。
這里的K（來源于作者俄國人Nikolai Krylov姓氏的首字母）是一個構造出來的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復雜問題化簡為階段性的易于計算的子步驟。
四、1951 矩陣計算的分解方法
?。?951： Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations.］
1951年，阿爾斯通橡樹嶺國家實驗室的Alston Householder提出，矩陣計算的分解方法。
這個算法證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣，該算法的意義使得開發靈活的矩陣計算軟件包成為可能。
五、1957 優化的Fortran編譯器
?。?957： John Backus leads a team at IBM in developing the Fortran optimizing compiler.］
1957年：約翰巴庫斯領導開發的IBM的團隊，創造了Fortran優化編譯器。
Fortran，亦譯為福傳，是由Formula Translation兩個字所組合而成，意思是“公式翻譯”。它是世界上第一個被正式采用并流傳至今的高級編程語言。這個語言現在，已經發展到了，Fortran 2008，并為人們所熟知。
六、1959-61 計算矩陣特征值的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：倫敦費倫蒂有限公司的J.G.F. Francis，找到了一種穩定的特征值的計算方法，這就是著名的QR算法。
這也是一個和線性代數有關的算法，學過線性代數的應該記得“矩陣的特征值”，計算特征值是矩陣計算的最核心內容之一，傳統的求解方案涉及到高次方程求根，當問題規模大的時候十分困難。
QR算法把矩陣分解成一個正交矩陣（希望讀此文的你，知道什么是正交矩陣。：D。）與一個上三角矩陣的積，和前面提到的Krylov 方法類似，這又是一個迭代算法，它把復雜的高次方程求根問題化簡為階段性的易于計算的子步驟，使得用計算機求解大規模矩陣特征值成為可能。
這個算法的作者是來自英國倫敦的J.G.F. Francis。
七、1962 快速排序算法
?。?962： Tony Hoare of Elliott Brothers， Ltd.， London， presents Quicksort.］
1962年：倫敦的，托尼埃利奧特兄弟有限公司，霍爾提出了快速排序。
哈哈，恭喜你，終于看到了可能是你第一個比較熟悉的算法~。
快速排序算法作為排序算法中的經典算法，它被應用的影子隨處可見?？焖倥判蛩惴ㄗ钤缬蒚ony Hoare爵士設計，它的基本思想是將待排序列分為兩半，左邊的一半總是“小的”，右邊的一半總是“大的”，這一過程不斷遞歸持續下去，直到整個序列有序。
說起這位Tony Hoare爵士，快速排序算法其實只是他不經意間的小小發現而已，他對于計算機貢獻主要包括形式化方法理論，以及ALGOL60 編程語言的發明等，他也因這些成就獲得1980 年圖靈獎。
快速排序的平均時間復雜度僅僅為O（Nlog（N）），相比于普通選擇排序和冒泡排序等而言，實在是歷史性的創舉。
八、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，和普林斯頓大學的John Tukey，AT＆T貝爾實驗室共同推出了快速傅立葉變換。
快速傅立葉算法是離散傅立葉算法（這可是數字信號處理的基石）的一種快速算法，其時間復雜度僅為O（Nlog（N））；比時間效率更為重要的是，快速傅立葉算法非常容易用硬件實現，因此它在電子技術領域得到極其廣泛的應用。
九、1977 整數關系探測算法
?。?977： Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm.］
1977年：Helaman Ferguson和 伯明翰大學的Rodney Forcade，提出了Forcade檢測算法的整數關系。
整數關系探測是個古老的問題，其歷史甚至可以追溯到歐幾里德的時代。具體的說：
給定—組實數X1，X2，…，Xn，是否存在不全為零的整數a1，a2，…an，使得：a1x1 + a2x2 + 。 . 。 + anxn ＝0？
這一年BrighamYoung大學的Helaman Ferguson 和Rodney Forcade解決了這一問題。
該算法應用于“簡化量子場論中的Feynman圖的計算”。ok，它并不要你懂，了解即可。：D。
十、1987 快速多極算法
?。?987： Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm.］
1987年：Greengard，和耶魯大學的Rokhlin發明了快速多極算法。
此快速多極算法用來計算“經由引力或靜電力相互作用的N 個粒子運動的精確計算——例如銀河系中的星體，或者蛋白質中的原子間的相互作用”。ok，了解即可。
工商網監
評論