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

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

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

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

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

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

②算法的收斂性

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

③算法的復雜度

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

4.十大算法

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

① 二十世紀的十大算法

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