第1章_算法在計算中的作用_算法分析與設(shè)計_杭電_褚一平

1、1. 算法在計算機中的作用指導思想解決問題的方法學習、不是數(shù)據(jù)結(jié)構(gòu)學習：如何解決問題算法分析是重點，知道方法比較容易，分析該方法的復(fù)雜度、優(yōu)缺點才是重要基本的算法及其分析方法講全，高級設(shè)計與分析技術(shù)都講授，而算法研究的問題非常多，因此選擇主題講授數(shù)據(jù)結(jié)構(gòu)、包括高級數(shù)據(jù)結(jié)構(gòu)不是本課程的講授內(nèi)容課程教材以MIT的算法導論為基本教材，可參考：計算機算法導論、盧開澄、清華Introduction to Algorithms, A Creative Approach、Ubi Manber（算法大師）Algorithms Design Techniques and Analysis、沙特（強調(diào)分析）Pro

2、gramming Pearls（編程珠璣I和II）對算法課的看法核心是分析算法復(fù)雜性的方法第一部分是核心 基礎(chǔ)算法（應(yīng)用最廣泛）+分析（最重要）解決問題的思路是關(guān)鍵第二部分 方法+分析+應(yīng)用算法無止境第三部分是提升（數(shù)學很重要）算法的應(yīng)用：論文增色如何在各個方向應(yīng)用則是重點，算法本身的研究不是目的。實際應(yīng)用當中需要考慮計算機系統(tǒng)的結(jié)構(gòu)內(nèi)存訪問讀寫操作等等實用的才是最好的三大部分都將提供部分最新研究成果或者相應(yīng)應(yīng)用的paper，課后學習和閱讀。算法的概念算法是求解某個問題的長度有限的指令序列，每條指令都是確定的、簡單的、機械的和可執(zhí)行的?！扒蠼鈹?shù)學問題（如尋找最大公約數(shù)）的一個過程，該過程步驟有

3、限，通常還涉及重復(fù)的操作?！本S基百科求解某一具體問題的數(shù)學過程收斂算法迭代算法對于任一屬于這個問題的實例的有效輸入，應(yīng)在有限步（一步執(zhí)行一條指令）內(nèi)給出結(jié)果（輸出），并中止。形象的算法例子DEMO視頻p( x) 3x 2x 1; x 4實例：2問題：抽象描述；實例：問題的具體化；【例1】多項式計算問題：給定多項式 p( x) an xn an1 xn1 a1 x和x求p(x)的值人類基因：10萬種基因；30億種化學基對排序和比對快速地訪問和檢索因特網(wǎng)上的信息數(shù)據(jù)傳輸路徑尋找；搜索引擎檢索技術(shù)；電子商務(wù)領(lǐng)域的信息安全公共密鑰加密技術(shù)數(shù)字簽名技術(shù)規(guī)劃（動態(tài)、線性）石油公司確定該在何處打井？總統(tǒng)選舉

4、確定宣傳基金花在何處？航空公司的機組人員調(diào)配？因特網(wǎng)服務(wù)提供商確定服務(wù)器安置位置？交通圖中任何兩個交叉點之間的最短路徑：最短路徑n個矩陣相乘:動態(tài)規(guī)劃A*x=b (mod n); a,b,n為整數(shù)：數(shù)論平面上n個點的凸殼：計算幾何共同特征：有很多解決方案-算法分析：復(fù)雜性有著實際的應(yīng)用算法需要考慮的問題排序算法要考慮的因素：待排序的數(shù)據(jù)項數(shù)數(shù)據(jù)項已經(jīng)排好序的程度對數(shù)據(jù)項取值的可能相知打算采用的存儲設(shè)備的類型內(nèi)存磁盤磁帶對多項式計算：變元個數(shù)、次冪、系數(shù)范圍等等算法的正確性如果一個算法對其每一個輸入實例，都能輸出正確的結(jié)果并停止，則稱它是正確的。正確的算法解決了給定的計算問題不正確的算法：可能不

5、會停止或者給出的結(jié)果不正確不正確的算法不是都沒用近似模擬可計算性從理論上判斷什么問題可以給出算法利用計算機求解，什么問題不可以，屬于“可計算性理論”研究的問題。比如：“停機問題”就是不可計算的?？捎嬎憷碚撜J為可計算的問題，都有求解的算法，這樣的算法不是唯一的（有無限多個），它們的計算復(fù)雜性也不一樣。復(fù)雜性較小的才是實際可計算的。算法概念的總結(jié)算法是求解某個問題的長度有限的指令序列，每條指令都是確定的、簡單的、機械的、可執(zhí)行的。算法給出了某一實際問題的計算/處理過程對算法的研究算法設(shè)計算法復(fù)雜度分析單個算法的復(fù)雜性算法復(fù)雜性比較：效率更近一步：算法的使用場景算法的復(fù)雜性評價一個算法可以從不同方面

6、來考慮，如正確性，簡單性，時間復(fù)雜性，空間復(fù)雜性，還可以提出求解某問題的最優(yōu)算法這樣的問題。我們將著重討論時間復(fù)雜性，并且是從數(shù)學的角度來討論，而不從具體的機器、語言、編程技巧來看。時間復(fù)雜性將歸結(jié)為某些基本操作的次數(shù)問題，基本操作的次數(shù)與問題的規(guī)模有關(guān)。那么如何確定問題的規(guī)模？一般我們考慮對基本操作的次數(shù)影響最大的量。算法效率求解同一個問題可以有不同的算法，效率或復(fù)雜性也可能不同。多項式值計算的基本操作乘法兩個已排好序的數(shù)據(jù)合并；算法效率比較：排序法比較：插入排序和合并排序設(shè)進行長度為n的數(shù)組的排序則：f (1) 2f (n) f (n 1) 2, 2n方法1：多項式：1110111101(

7、 )()nnnnnnnnnp xa xaxa xaa xxaxa xa 次則：f (n) f (n 1) 1, nf (1) 1方法2：多項式：1110121101( )()nnnnnnnnnp xa xaxa xaa xaxaxa 次算法1算法21. y 12. p a03. 對i從1到n做4 y xy5. p ai y + p6. 輸出p乘法：2n次加法：n次1. p an2. 對i從n到1做3p px + ai 14. 輸出p乘法：n次加法：n次算法分析即指對一個算法所需要的資源進行預(yù)測；資源：內(nèi)存、通信帶寬或計算機硬件，但通常，資源是指我們希望測度的計算時間；對于一個問題，通過分析幾種

8、候選算法，選出一個最有效地算法；分析的結(jié)果可能是找出不止一個的候選算法，但在這一過程中，通常都要去掉幾個較差的算法；算法分析模型20世紀30年代：問題的可解和不可解計算模型-建立算法求解問題（可解）計算模型：哥德爾(Godel)的遞歸函數(shù)丘齊(Church)的伽馬演算波斯特(Post)的波斯特機圖靈(Turing) 的圖靈機RAM模型丘齊：所有這些模型是等效的（可解層次）算法分析的模型：RAM模型分析一個算法之前，要建立有關(guān)實現(xiàn)技術(shù)的模型；包括描述所用資源及代價的模型單處理器、隨即存?。≧andom AccessMachine, RAM）計算模型指令一條接一條執(zhí)行，沒有并發(fā)操作常見指令：算術(shù)指

9、令（加、減、乘、除、取余、向上和向下取整）數(shù)據(jù)移動指令（裝入、存儲、復(fù)制）控制指令（條件和非條件轉(zhuǎn)移、子程序調(diào)用和返回指令）RAM模型數(shù)據(jù)類型有整數(shù)類型和浮點實數(shù)類型一般不關(guān)心數(shù)據(jù)的精度問題一些應(yīng)用中，精度是非常關(guān)鍵的存儲層次建模：高速緩存和虛擬內(nèi)存RAM模型分析算法需要：組合、代數(shù)、數(shù)論、概率等簡單明了的公式形式來總結(jié)分析的結(jié)果和行為“幾乎所有”的問題都是不可解的：被計算的函數(shù)集是不可數(shù)的（非負整數(shù)-實數(shù)）任何算法可對應(yīng)一個唯一的正整數(shù)，是可數(shù)的；Pi中是否存在連續(xù)的7個“1”？多個變元的多形式方程是否存在整數(shù)解？問題的可判定性和可解性屬于可計算性理論。計算機出現(xiàn)的時候：滿足于一個簡單的程序能夠在它需要的時間內(nèi)求解一個特定的問題；之后：提出了對盡可能少使用資源的有效算法的需求；資源的有限性開發(fā)復(fù)雜算法計算復(fù)雜性：可解類問題的效