[導(dǎo)讀]推薦關(guān)注下方公眾號(hào)學(xué)習(xí)更多嵌入式知識(shí)！導(dǎo)讀：作者July總結(jié)了一篇關(guān)于計(jì)算方法的文章《細(xì)數(shù)二十世紀(jì)最偉大的10大算法》。一、1946蒙特卡洛方法[1946:JohnvonNeumann,StanUlam,andNickMetropolis,allattheLosAlamosSci...
導(dǎo)讀：作者July總結(jié)了一篇關(guān)于計(jì)算方法的文章《 細(xì)數(shù)二十世紀(jì)最偉大的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年，美國(guó)拉斯阿莫斯國(guó)家實(shí)驗(yàn)室的三位科學(xué)家John von Neumann,Stan Ulam 和 Nick Metropolis共同發(fā)明，被稱(chēng)為蒙特卡洛方法。它的具體定義是：在廣場(chǎng)上畫(huà)一個(gè)邊長(zhǎng)一米的正方形，在正方形內(nèi)部隨意用粉筆畫(huà)一個(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è)平面上，相互之間沒(méi)有重疊。蒙特卡洛方法可用于近似計(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ù)，（圓面積和正方形面積之比為PI:1，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ā)明了單純形方法。單純形法，此后成為了線(xiàn)性規(guī)劃學(xué)科的重要基石。所謂線(xiàn)性規(guī)劃，簡(jiǎn)單的說(shuō)，就是給定一組線(xiàn)性（所有變量都是一次冪）約束條件（例如a1*x1 b1*x2 c1*x3>0)，求一個(gè)給定的目標(biāo)函數(shù)的極值。這么說(shuō)似乎也太太太抽象了，但在現(xiàn)實(shí)中能派上用場(chǎng)的例子可不罕見(jiàn)——比如對(duì)于一個(gè)公司而言，其能夠投入生產(chǎn)的人力物力有限（“線(xiàn)性約束條件”），而公司的目標(biāo)是利潤(rùn)最大化（“目標(biāo)函數(shù)取最大值”），看，線(xiàn)性規(guī)劃并不抽象吧！線(xiàn)性規(guī)劃作為運(yùn)籌學(xué)(operation research)的一部分，成為管理科學(xué)領(lǐng)域的一種重要工具。而Dantzig提出的單純形法便是求解類(lèi)似線(xiàn)性規(guī)劃問(wèn)題的一個(gè)極其有效的方法。三、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年：美國(guó)國(guó)家標(biāo)準(zhǔn)局?jǐn)?shù)值分析研究所的，馬格努斯Hestenes，愛(ài)德華施蒂費(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(yíng)的矩陣，而迭代形式的算法的妙處在于，它將復(fù)雜問(wèn)題化簡(jiǎn)為階段性的易于計(jì)算的子步驟。四、1951 矩陣計(jì)算的分解方法[1951: Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations.]1951年，阿爾斯通橡樹(shù)嶺國(guó)家實(shí)驗(yàn)室的Alston Householder提出，矩陣計(jì)算的分解方法。這個(gè)算法證明了任何矩陣都可以分解為三角、對(duì)角、正交和其他特殊形式的矩陣，該算法的意義使得開(kāi)發(fā)靈活的矩陣計(jì)算軟件包成為可能。五、1957 優(yōu)化的Fortran編譯器[1957: John Backus leads a team at IBM in developing the Fortran optimizing compiler.]1957年：約翰巴庫(kù)斯領(lǐng)導(dǎo)開(kāi)發(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算法[1959–61: J.G.F. Francis of Ferranti Ltd, London, finds a stable method for computingeigenvalues, known as the QR algorithm.]1959-61：倫敦費(fèi)倫蒂有限公司的J.G.F. Francis，找到了一種穩(wěn)定的特征值的計(jì)算方法，這就是著名的QR算法。這也是一個(gè)和線(xiàn)性代數(shù)有關(guān)的算法，學(xué)過(guò)線(xiàn)性代數(shù)的應(yīng)該記得“矩陣的特征值”，計(jì)算特征值是矩陣計(jì)算的最核心內(nèi)容之一，傳統(tǒng)的求解方案涉及到高次方程求根，當(dāng)問(wèn)題規(guī)模大的時(shí)候十分困難。QR算法把矩陣分解成一個(gè)正交矩陣(希望讀此文的你，知道什么是正交矩陣。:D。)與一個(gè)上三角矩陣的積，和前面提到的Krylov 方法類(lèi)似，這又是一個(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)用的影子隨處可見(jiàn)。快速排序算法最早由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)。關(guān)于快速排序算法的具體認(rèn)識(shí)與應(yīng)用，請(qǐng)參考我寫(xiě)的一篇文章，精通八大排序算法系列。一、快速排序算法：http://blog.csdn.net/v_JULY_v/archive/2011/01/04/6116297.aspx快速排序的平均時(shí)間復(fù)雜度僅僅為O(Nlog(N))，相比于普通選擇排序和冒泡排序等而言，實(shí)在是歷史性的創(chuàng)舉。八、1965 快速傅立葉變換[1965: James Cooley of the IBM T.J. Watson Research Center and John Tukey of PrincetonUniversity and AT
欲知詳情，請(qǐng)下載word文檔
下載文檔
本站聲明： 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布，目的在于傳遞更多信息，并不代表本站贊同其觀(guān)點(diǎn)，本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專(zhuān)欄作者，如若文章內(nèi)容侵犯您的權(quán)益，請(qǐng)及時(shí)聯(lián)系本站刪除。
