第1章-算法在計算中的作用

1.算法在計算機中的作用

指導(dǎo)思想解決問題的方法學(xué)習(xí)、不是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)：如何解決問題算法分析是重點，知道方法比較容易，分析該方法的復(fù)雜度、優(yōu)缺點才是重要基本的算法及其分析方法講全，高級設(shè)計與分析技術(shù)都講授，而算法研究的問題非常多，因此選擇主題講授數(shù)據(jù)結(jié)構(gòu)、包括高級數(shù)據(jù)結(jié)構(gòu)不是本課程的講授內(nèi)容課程教材以MIT的算法導(dǎo)論為基本教材，可參考：

《計算機算法導(dǎo)論》、盧開澄、清華

《IntroductiontoAlgorithms,ACreativeApproach》、UbiManber

（算法大師）

《AlgorithmsDesignTechniquesandAnalysis》、沙特（強調(diào)分 析）

《ProgrammingPearls》（編程珠璣I和II）對算法課的看法核心是分析算法復(fù)雜性的方法

第一部分是核心基礎(chǔ)算法（應(yīng)用最廣泛）+分析（最重要）解決問題的思路是關(guān)鍵

第二部分方法+分析+應(yīng)用算法無止境

第三部分是提升（數(shù)學(xué)很重要）算法的應(yīng)用：

論文增色 如何在各個方向應(yīng)用則是重點，算法本身的研究不是目的。 實際應(yīng)用當中需要考慮

計算機系統(tǒng)的結(jié)構(gòu) 內(nèi)存訪問 讀寫操作等等

實用的才是最好的三大部分都將提供部分最新研究成果或者相應(yīng)應(yīng)用的paper，課后學(xué)習(xí)和閱讀。

算法的概念

算法是求解某個問題的長度有限的指令序列，每條指令 都是確定的、簡單的、機械的和可執(zhí)行的。 “求解數(shù)學(xué)問題（如尋找最大公約數(shù)）的一個過程，該過 程步驟有限，通常還涉及重復(fù)的操作?！薄S基百科求解某一具體問題的數(shù)學(xué)過程

收斂算法 迭代算法對于任一屬于這個問題的實例的有效輸入，應(yīng)在有限步（一步執(zhí)行一條指令）內(nèi)給出結(jié)果（輸出），并中止。形象的算法例子DEMO視頻p(x)

3x

2x

1;x

4實例：2

問題：抽象描述；實例：問題的具體化；【例1】多項式計算問題：給定多項式p(x)

anxn

an

1xn

1

a1x和x

求p(x)的值

人類基因：10萬種基因；30億種化學(xué)基對

排序和比對

快速地訪問和檢索因特網(wǎng)上的信息

數(shù)據(jù)傳輸路徑尋找； 搜索引擎檢索技術(shù)；

電子商務(wù)領(lǐng)域的信息安全

公共密鑰加密技術(shù) 數(shù)字簽名技術(shù)

規(guī)劃（動態(tài)、線性）

石油公司確定該在何處打井？ 總統(tǒng)選舉確定宣傳基金花在何處？ 航空公司的機組人員調(diào)配？ 因特網(wǎng)服務(wù)提供商確定服務(wù)器安置位置？

交通圖中任何兩個交叉點之間的最短路 徑：最短路徑

n個矩陣相乘<A_1,A_2,…,A_n>:動態(tài)規(guī)劃

A*x=b(modn);a,b,n為整數(shù)：數(shù)論 平面上n個點的凸殼：計算幾何共同特征： 有很多解決方案->算法分析：復(fù)雜性 有著實際的應(yīng)用

算法需要考慮的問題

排序算法要考慮的因素：

待排序的數(shù)據(jù)項數(shù) 數(shù)據(jù)項已經(jīng)排好序的程度 對數(shù)據(jù)項取值的可能相知 打算采用的存儲設(shè)備的類型

內(nèi)存 磁盤 磁帶

對多項式計算：

變元個數(shù)、次冪、系數(shù)范圍等等算法的正確性如果一個算法對其每一個輸入實例，都能輸出正確的結(jié)果并停止，則稱它是正確的。正確的算法解決了給定的計算問題不正確的算法：

可能不會停止 或者給出的結(jié)果不正確不正確的算法不是都沒用

近似 模擬可計算性從理論上判斷什么問題可以給出算法利用計算機求解，什么問題不可以，屬于“可計算性理論”研究的問題。比如：“停機問題”就是不可計算的?？捎嬎憷碚撜J為可計算的問題，都有求解的算法，這樣的算法不是唯一的（有無限多個），它們的計算復(fù)雜性也不一樣。復(fù)雜性較小的才是實際可計算的。算法概念的總結(jié)

算法是求解某個問題的長度有限的指令序 列，每條指令都是確定的、簡單的、機械 的、可執(zhí)行的。 算法給出了某一實際問題的計算/處理過程 對算法的研究

算法設(shè)計 算法復(fù)雜度分析

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

2