91欧美在线免费观看,漂亮的人妻中文字幕,国产精品免费在线观看视频,男女一起插插插视频,四虎国产精品久久久久,人妻精品有码一区二区三区,亚洲 欧美 你懂的,亚洲制服一区二区三区在线,高中女厕偷拍一区二区三区

數(shù)學(xué)技術(shù)之算法概論篇（3）

3.算法中的問題及其描述

對(duì)一個(gè)問題的求解可以選用多種不同的模型、方法和算法，難易差異極大。由于機(jī)器字長的限制和存貯空間的有限性，不同的模型由于誤差的存在，往往使計(jì)算的結(jié)果存在很大的差異。若執(zhí)行的結(jié)果與精確解之間的誤差很大的話，勢必會(huì)影響與之相關(guān)的數(shù)據(jù)的精確度，這就引出了算法穩(wěn)定性、收斂性和復(fù)雜度等諸多問題。下面，對(duì)上述問題進(jìn)行一些簡單介紹。

①算法的穩(wěn)定性

對(duì)一個(gè)數(shù)值型算法，計(jì)算過程中已有的各類誤差會(huì)繼續(xù)積累并向前發(fā)展。若輸入數(shù)據(jù)的誤差在計(jì)算過程中迅速增長而得不到控制，則稱該算法是不穩(wěn)定的，否則是算法穩(wěn)定的。所以，算法穩(wěn)定性說的是計(jì)算過程中的誤差（含舍入誤差、截?cái)嗾`差等）的敏感性。
算法的穩(wěn)定性是指算法對(duì)于計(jì)算過程中的誤差不敏感，即穩(wěn)定的算法能得到原問題相鄰問題的精確解。一個(gè)算法計(jì)算得到的近似解可以看作原計(jì)算問題中的參數(shù)經(jīng)適當(dāng)擾動(dòng)后的準(zhǔn)確解，若擾動(dòng)是微小的，就說這個(gè)算法是數(shù)值穩(wěn)定的，否則就說算法是不穩(wěn)定的。
對(duì)一個(gè)非數(shù)值型算法，如排序算法的穩(wěn)定性其意義和數(shù)值型算法不同，這里算法穩(wěn)定性意思是說原本鍵值一樣的元素排序后相對(duì)位置不變。對(duì)一個(gè)復(fù)雜類型的數(shù)組排序，而排序的鍵實(shí)際上只是這個(gè)元素中的一個(gè)屬性，對(duì)于一個(gè)簡單類型，數(shù)字值就是其全部意義，即使交換了也看不出什么不同。但是對(duì)于復(fù)雜的類型，交換的話可能就會(huì)使原本不應(yīng)該交換的元素交換了。比如，一個(gè)“學(xué)生”數(shù)組，按照年齡排序，“學(xué)生”這個(gè)對(duì)象不僅含有“年齡”，還有其他很多屬性，穩(wěn)定的排序會(huì)保證比較時(shí)，如果兩個(gè)學(xué)生年齡相同，一定不交換。

②算法的收斂性

算法的收斂性和穩(wěn)定性不是一個(gè)層次的概念，它只在部分算法中出現(xiàn)，比如迭代求解，迭代中的收斂指經(jīng)過有限步驟的迭代計(jì)算可以得到一個(gè)穩(wěn)定的解。但是這個(gè)解是不是原問題的解，要看問題的病態(tài)性了。如果問題是病態(tài)的，則很有可能不是準(zhǔn)確的解。
算法的數(shù)值穩(wěn)定性的判別是和(舍入)誤差分析密切相關(guān)聯(lián)。對(duì)代數(shù)求解過程的舍入誤差作深入細(xì)致的分析，計(jì)算結(jié)果的精度不但依賴于所用的算法，而且也和問題是良態(tài)或病態(tài)有關(guān)。一個(gè)計(jì)算問題，如果其中的參數(shù)(如線性代數(shù)方程組的系數(shù)，自由項(xiàng))的微小擾動(dòng)只對(duì)解的精度產(chǎn)生不大的影響，便說這個(gè)計(jì)算問題是良態(tài)的，否則便稱為病態(tài)的。

③算法的復(fù)雜度

算法的復(fù)雜度含算法時(shí)間復(fù)雜度和空間復(fù)雜度，它們合稱為算法復(fù)雜度。
算法復(fù)雜度理論是理論計(jì)算機(jī)科學(xué)的分支學(xué)科，使用數(shù)學(xué)方法對(duì)計(jì)算中所需的各種資源的耗費(fèi)作定量的分析，并研究各類問題之間在計(jì)算復(fù)雜程度上的相互關(guān)系和基本性質(zhì)，是算法分析的理論基礎(chǔ)。其他資源亦可考慮，例如在并行計(jì)算中，需要多少并行處理器才能解決問題等。
時(shí)間復(fù)雜度是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模的函數(shù)。算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)，是衡量一個(gè)算法優(yōu)劣的重要參數(shù)。時(shí)間復(fù)雜度越小，說明該算法效率越高，算法越有價(jià)值。
漸近時(shí)間復(fù)雜度是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。
空間復(fù)雜度是某個(gè)算法的空間耗費(fèi)，它也是該算法所求解問題規(guī)模的函數(shù)，是算法優(yōu)劣的重要度量指標(biāo)之一?？臻g復(fù)雜度越小，算法越好。假設(shè)用一個(gè)圖靈機(jī)來解決某一類問題，設(shè)有X個(gè)字（word）屬于這個(gè)問題，把X放入這個(gè)圖靈機(jī)的輸入端，空間復(fù)雜度就是這個(gè)圖靈機(jī)為解決此問題所需要的工作帶格子數(shù)總量。
算法復(fù)雜度按求解問題規(guī)模數(shù)量級(jí)n遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log₂n)、線性階O(n)、線性對(duì)數(shù)階O(nlog₂n)、平方階O(n²)、立方階O(n³)、……k次方階O(n^k)、指數(shù)階O(2ⁿ)等。
復(fù)雜度理論和可計(jì)算性理論不同，可計(jì)算性理論的重心在于問題能否解決，不管需要多少資源，而復(fù)雜性理論作為計(jì)算理論的分支，某種程度上被認(rèn)為和算法理論是一種“矛”與“盾”的關(guān)系，即算法復(fù)雜度理論專注于設(shè)計(jì)有效的算法，并可依此對(duì)同一問題的不同算法進(jìn)行比較，而可計(jì)算性理論專注于理解為什么對(duì)于某類問題不存在有效的算法。

4.十大算法

算法對(duì)我們極其重要，一些模不著、看不見的算法正在掌控著我們的數(shù)字世界，現(xiàn)在是一個(gè)“算法為王”的時(shí)代，已經(jīng)到了我們必須透徹地了解算法的時(shí)候了。軟件正在統(tǒng)治世界，而軟件的核心是算法。算法千千萬萬，又有哪些算法屬于 “皇冠上的珍珠” 呢？下面分別列出從不同角度、不同時(shí)段、不同領(lǐng)域得到的十大算法，供參考。
顯然，不同領(lǐng)域、不同時(shí)代的人，對(duì)什么是“十大算法”自然會(huì)有不同看法和不同的選擇，不可能統(tǒng)一，也沒有必要統(tǒng)一。應(yīng)該說，受時(shí)間、經(jīng)驗(yàn)、領(lǐng)域和參選人數(shù)等諸多限制，入選的十大算法，不一定個(gè)個(gè)都是最優(yōu)秀的；受條件和個(gè)數(shù)所限，沒有入選的有些算法，也不能說是不好的；有些算法在不同選法中出現(xiàn)，也是自然的；每類算法都選成“十大”，確有湊數(shù)之嫌，不無道理，但10是最小的兩位數(shù)，選10也有一定的道理。
下面在互聯(lián)網(wǎng)上分別從發(fā)展過程、研究方向和領(lǐng)域、考慮問題的重點(diǎn)、所處時(shí)間區(qū)間、評(píng)價(jià)優(yōu)劣的標(biāo)準(zhǔn)和評(píng)選方法不同等各個(gè)不同方面的考慮給出不同類別的十大算法并對(duì)其進(jìn)行一些簡要的介紹，供大家參考。稍后，對(duì)其中一項(xiàng)重要的算法，再進(jìn)行較詳細(xì)的一些介紹。

① 二十世紀(jì)的十大算法

21世紀(jì)初，美國物理學(xué)會(huì)(American Institute of Physics)和IEEE計(jì)算機(jī)社團(tuán)(IEEE Computer Society)的聯(lián)合刊物《科學(xué)與工程中的計(jì)算》發(fā)表了由田納西大學(xué)的Jack Dongarra和橡樹嶺國家實(shí)驗(yàn)室的Francis Sullivan聯(lián)名撰寫的“20世紀(jì)十大算法”一文，該文“試圖整理出在20世紀(jì)對(duì)科學(xué)和工程領(lǐng)域的發(fā)展產(chǎn)生最大影響力的十大算法”。作者苦于“任何選擇都將充滿爭議，因?yàn)閷?shí)在是沒有最好的算法”，他們只好用編年順序依次列出了這十項(xiàng)算法領(lǐng)域人類智慧的巔峰之作——給出了一份沒有排名的算法排行榜。這里帶領(lǐng)網(wǎng)友走馬觀花，一同回顧一下二十世紀(jì)算法界的發(fā)展歷程，并對(duì)這些算法進(jìn)行一些簡短介紹。
（1）1946蒙特卡羅方法
1946年：蒙特卡羅方法，是一類基于“隨機(jī)數(shù)”的計(jì)算方法。由于該方法應(yīng)用域多面廣，有數(shù)十種不同的名稱或叫法，如蒙特卡羅計(jì)算、統(tǒng)計(jì)試驗(yàn)方法、隨機(jī)模擬方法等；又由于該方法特點(diǎn)顯著、能和其他學(xué)科與方法廣泛深入結(jié)合，因而有了眾多的分支，如擬蒙特卡羅方法、多群蒙特卡羅方法、動(dòng)態(tài)蒙特卡羅方法、量子蒙特卡羅方法、變分蒙特卡羅方法、馬氏鏈蒙特卡羅方法和并行蒙特卡羅方法等。
蒙特卡羅方法以概率和統(tǒng)計(jì)理論為基礎(chǔ)，將所求解的問題同概率模型相聯(lián)系，用計(jì)算機(jī)上產(chǎn)生的隨機(jī)數(shù)實(shí)現(xiàn)統(tǒng)計(jì)模擬或抽樣，以獲得問題的近似解。為象征性地表明這一方法的概率統(tǒng)計(jì)特征，借用歐洲賭城蒙特卡羅(Monte Carlo)命名，由S.M.烏拉姆和J.馮 諾伊曼在20世紀(jì)40年代為研制核武器而首先提出。它的基本思想是，為了求解數(shù)學(xué)、物理、工程技術(shù)以及管理等方面的問題，首先建立一個(gè)概率模型或隨機(jī)過程，使它們的參數(shù)，如概率分布或數(shù)學(xué)期望等成為問題的解，然后通過對(duì)模型或過程的觀察或抽樣試驗(yàn)來計(jì)算所求參數(shù)的統(tǒng)計(jì)特征，并用算術(shù)平均值作為所求解的近似值。
蒙特卡羅方法有很強(qiáng)的適應(yīng)性，問題的幾何形狀的復(fù)雜性對(duì)它的影響不大。該方法的收斂性是指概率意義下的收斂，因此問題維數(shù)的增加不會(huì)影響它的收斂速度，而且存貯單元也很省，這些是用該方法處理大型復(fù)雜問題時(shí)的優(yōu)勢。因此，隨著電子計(jì)算機(jī)的發(fā)展和科學(xué)技術(shù)問題的日趨復(fù)雜，蒙特卡羅方法的應(yīng)用也越來越廣泛。它不僅較好地解決了多重積分計(jì)算、微分方程求解、積分方程求解、特征值計(jì)算和非線性方程組求解等高難度和復(fù)雜的數(shù)學(xué)計(jì)算問題，而且在統(tǒng)計(jì)物理、核物理、真空技術(shù)、系統(tǒng)科學(xué)、信息科學(xué)、公用事業(yè)、地質(zhì)、醫(yī)學(xué)，可靠性及計(jì)算機(jī)科學(xué)等廣泛的領(lǐng)域都得到成功的應(yīng)用。
（2）1947單純形法
1947年：單純形法，是由“預(yù)測未來”的蘭德公司的Grorge Dantzig發(fā)明的，成為線性規(guī)劃學(xué)科的重要基石。
所謂線性規(guī)劃，簡單的說，就是在給定一組線性約束條件（如a₁*x₁+a₂*x₂+a₃*x₃>0)，求一個(gè)給定的目標(biāo)函數(shù)的極值。在現(xiàn)實(shí)中能派上用場的例子并不罕見——比如對(duì)于一個(gè)公司而言，其能夠投入生產(chǎn)的人力物力有限（“線性約束條件”），而公司的目標(biāo)是利潤最大化（“目標(biāo)函數(shù)取大值”），所以線性規(guī)劃并不抽象。線性規(guī)劃作為運(yùn)籌學(xué)研究的一部分，成為管理科學(xué)領(lǐng)域的一種重要工具，Dantzig提出的單純形法便是求解這類線性規(guī)劃問題的一個(gè)極其有效的算法。
（3）1950 Krylov子空間迭代法
1950年：美國國家標(biāo)準(zhǔn)局?jǐn)?shù)值分析研究所Hestenes，Lanczos，發(fā)明了Krylov子空間迭代法。
Krylov子空間迭代法是用來求解形如Ax=b的線代數(shù)方程組，A是一個(gè)n*n的矩陣，當(dāng)n很大時(shí)，直接計(jì)算非常困難，而Krylov方法則巧妙地將其變?yōu)镵x_i+1=Kx_i+b-Ax_i的迭代形式來求解。這里的K(來源于作者俄國人Nikolai Krylov姓氏的首字母)是一個(gè)構(gòu)造出來的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復(fù)雜問題化簡為階段性的易于計(jì)算的子步驟。
（4）1951矩陣計(jì)算的分解方法
1951年：由阿爾斯通橡樹嶺國家實(shí)驗(yàn)室的Alston Householder提出矩陣計(jì)算的分解方法。該算法證明任何矩陣都可以分解為三角、對(duì)角、正交和其他特殊形式的矩陣，其重大意義使得開發(fā)靈活的矩陣計(jì)算軟件包成為可能。
（5）1957優(yōu)化的Fortran編譯器
1957年：Fortran編譯器，由Fortran之父——John Backus發(fā)明的人類歷史上第一個(gè)計(jì)算機(jī)高級(jí)語言。
說實(shí)話，在這份學(xué)術(shù)氣息無比濃郁的榜單里突然冒出一個(gè)編譯器如此工程化的東西實(shí)在讓人有“關(guān)公戰(zhàn)秦瓊”的感覺。不過換個(gè)角度想想，F(xiàn)ortran這一門幾乎為科學(xué)計(jì)算度身定制的編程語言，對(duì)于科學(xué)家（尤其是數(shù)學(xué)家，物理學(xué)家）們實(shí)在是太重要了，簡直是他們形影不離的一把瑞士軍刀，這也難怪他們紛紛搶著要把票投給了它。要知道，F(xiàn)ortran是第一個(gè)能將數(shù)學(xué)公式轉(zhuǎn)化為計(jì)算機(jī)程序的高級(jí)語言，它的誕生使得科學(xué)家們真正開始利用計(jì)算機(jī)作為計(jì)算工具為他們的研究服務(wù)，這是計(jì)算機(jī)應(yīng)用技術(shù)的一個(gè)里程碑級(jí)別的貢獻(xiàn)。
（6）1959-61計(jì)算矩陣特征值的QR算法
1959-61年：矩陣特征值的QR算法，也是一個(gè)和線性代數(shù)有關(guān)的算法，發(fā)明者為來自英國倫敦的J.G.F.Francis。
計(jì)算特征值是矩陣計(jì)算的最核心內(nèi)容之一，傳統(tǒng)的求解方案涉及到高次方程求根，當(dāng)問題規(guī)模大的時(shí)候十分困難。QR算法把矩陣分解成一個(gè)正交矩陣與一個(gè)上三角矩陣的積，和前面提到的Krylov方法類似，又是一個(gè)迭代算法，它把復(fù)雜的高次方程求根問題化簡為階段性的易于計(jì)算的子步驟，使得用計(jì)算機(jī)求解大規(guī)模矩陣特征值成為可能。
（7）1962快速排序算法
1962年：快速排序算法，最早由Tony Hoare爵士設(shè)計(jì)，它的基本思想是將待排序數(shù)序列分為兩半，左邊的一半總是“小的”，右邊的一半總是“大的”，這一過程不斷遞歸持續(xù)下去，直到整個(gè)序列有序。說起這位Tony Hoare爵士，快速排序算法其實(shí)只是他不經(jīng)意間的小小發(fā)現(xiàn)而已，他對(duì)于計(jì)算機(jī)貢獻(xiàn)主要包括形式化方法理論，以及ALGOL 60編程語言的發(fā)明等，他也因這些成就獲得1980年圖靈獎(jiǎng)。
快速排序的平均時(shí)間復(fù)雜度為O(Nlog(N))，相比于普通選擇排序和冒泡排序等而言，實(shí)在是歷史性的創(chuàng)舉。
（8）1965快速傅立葉變換
1965年：快速傅立葉變換FFT，由IBM華生研究院的James Cooley和普林斯頓大學(xué)的John Tukey共同提出。
如果要評(píng)選對(duì)我們的日常生活影響最大的算法，快速傅立葉變換算法應(yīng)該是當(dāng)仁不讓的冠軍——每天當(dāng)拿起話筒，打開手機(jī)，聽mp3，看DVD，用DC拍照——毫不夸張的說，哪里有數(shù)字信號(hào)處理，哪里就有快速傅立葉變換?？焖俑盗⑷~算法是離散傅立葉算法的一種快速算法，時(shí)間復(fù)雜度僅為O(Nlog(N))；比時(shí)間效率更為重要的是，快速傅立葉算法非常容易用硬件實(shí)現(xiàn)，因此它在電子技術(shù)領(lǐng)域得到極其廣泛的應(yīng)用。
（9）1977整數(shù)關(guān)系探測算法
1977年：整數(shù)關(guān)系探測算法，由Brigham Young大學(xué)的Helaman Ferguson和Rodney Forcade解決。
整數(shù)關(guān)系探測是個(gè)古老的問題，其歷史甚至可以追溯到歐幾里德的時(shí)代。具體的說：給定—組實(shí)數(shù)X₁，X₂，...，X_n，是否存在不全為零的整數(shù)a₁，a₂，...a_n，使得:a₁x₁+a₂x₂+...+a_nx_n＝0，該算法可用于簡化量子場論中的Feynman圖的計(jì)算。
（10）1987快速多極算法
1987年：快速多極算法，耶魯大學(xué)Leslie Greengard和Vladimir Rokhlin提出的快速多極算法用來計(jì)算經(jīng)由引力或靜電力相互作用的N個(gè)粒子運(yùn)動(dòng)的精確計(jì)算——例如銀河系中的星體，或者蛋白質(zhì)中的原子間的相互作用。
浪花淘盡英雄，這些算法的發(fā)明者許多已經(jīng)駕鶴西去。二十一世紀(jì)的前十五年也已經(jīng)在不知不覺中從我們指尖滑過，不知下一次十大算法評(píng)選的盛事何時(shí)再有。