<menuitem id="tjl3v"></menuitem>
<var id="tjl3v"></var>
<var id="tjl3v"></var><var id="tjl3v"></var><menuitem id="tjl3v"><dl id="tjl3v"><progress id="tjl3v"></progress></dl></menuitem>
<cite id="tjl3v"><video id="tjl3v"><listing id="tjl3v"></listing></video></cite>
<var id="tjl3v"><strike id="tjl3v"><listing id="tjl3v"></listing></strike></var>
<menuitem id="tjl3v"><dl id="tjl3v"><progress id="tjl3v"></progress></dl></menuitem>
<cite id="tjl3v"></cite>
<var id="tjl3v"></var><var id="tjl3v"></var>
<var id="tjl3v"><strike id="tjl3v"></strike></var>
<var id="tjl3v"><dl id="tjl3v"><listing id="tjl3v"></listing></dl></var>
<cite id="tjl3v"><video id="tjl3v"><listing id="tjl3v"></listing></video></cite><var id="tjl3v"></var>

細數20世紀最偉大的十大算法

2015-12-29 10:12:00
coobic
原創
2068
摘要:作者July總結了一篇關于計算方法的文章《細數二十世紀最偉大的10大算法》,此文只是本人對算法比較感興趣,所以也做翻譯,學習研究下。以下是文章內容:

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

一、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:1,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 computingeigenvalues, 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 年圖靈獎。


八、1965 快速傅立葉變換

[1965: James Cooley of the IBM T.J. Watson Research Center and John Tukey of PrincetonUniversity 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圖的計算”。


十、1987 快速多極算法

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

1987年:萊斯利的Greengard,和耶魯大學的Rokhlin發明了快速多極算法。


此快速多極算法用來計算“經由引力或靜電力相互作用的N 個粒子運動的精確計算——例如銀河系中的星體,或者蛋白質中的原子間的相互作用”。ok,了解即可。  
發表評論
評論通過審核后顯示。
怎么买彩票