計算理論與算法分析設(shè)計第一章

1、教材教材: 1王王 王曉東王曉東,計算機算法設(shè)計與分析計算機算法設(shè)計與分析(第第4版版),電子工業(yè)電子工業(yè). 2S 唐常杰等譯唐常杰等譯, Sipser著著, 計算理論導引計算理論導引, 機械工業(yè)機械工業(yè). 參考資料參考資料:3C 潘金貴等譯潘金貴等譯, Cormen等著等著, 算法導論算法導論, 機械工業(yè)機械工業(yè). 4M 黃林鵬等譯黃林鵬等譯, Manber著著, 算法引論算法引論-一種創(chuàng)造性方一種創(chuàng)造性方法法, 電子電子. 5劉劉 劉汝佳等劉汝佳等, 算法藝術(shù)與信息學競賽算法藝術(shù)與信息學競賽, 清華大學清華大學.6L Lewis等著等著, 計算理論基礎(chǔ)計算理論基礎(chǔ), 清華大學清華大學. 計

2、算理論與計算理論與算法分析設(shè)計算法分析設(shè)計 劉劉 慶慶 暉暉 課程內(nèi)容課程內(nèi)容l算法算法: 概述概述, 遞歸與分治遞歸與分治, 動態(tài)規(guī)劃動態(tài)規(guī)劃, 貪心法貪心法, 回溯法回溯法, 分支限界法分支限界法, 概率算法概率算法, 線性規(guī)劃與網(wǎng)絡(luò)流線性規(guī)劃與網(wǎng)絡(luò)流l計算理論基礎(chǔ)計算理論基礎(chǔ): 集合關(guān)系與語言集合關(guān)系與語言, 有窮自動機有窮自動機, 圖靈機圖靈機, 不可判定性不可判定性, 計算復雜性計算復雜性, NP完全性等完全性等.l 56學時學時l成績成績l平時成績平時成績30%, 期末閉卷成績期末閉卷成績70 第一章第一章 算法概述算法概述第一部分第一部分 什么是算法什么是算法 第二部分第二部分

3、算法分析與分析起步算法分析與分析起步 第一部分第一部分什么是算法什么是算法什么是算法什么是算法教材教材(王王)上的解釋上的解釋是指解決問題的一種方法或一個過程是指解決問題的一種方法或一個過程是若干指令的有窮序列是若干指令的有窮序列, 滿足滿足: (1) 輸入輸入: 零個或多個外部提供的量零個或多個外部提供的量 (2) 輸出輸出: 產(chǎn)生至少一個量作為輸出產(chǎn)生至少一個量作為輸出 (3) 確定性確定性: 每條指令是清晰每條指令是清晰, 無歧義無歧義 (4) 有限性有限性: 每條指令的執(zhí)行次數(shù)每條指令的執(zhí)行次數(shù), 時間有限時間有限什么是算法什么是算法算法導論算法導論C:解決可計算問題的一個工具解決可計

4、算問題的一個工具將輸入轉(zhuǎn)換為輸出的一個可計算步驟序列將輸入轉(zhuǎn)換為輸出的一個可計算步驟序列韋氏大學詞典韋氏大學詞典:求解問題的一個過程求解問題的一個過程, 步驟有限步驟有限, 通常有重復操作通常有重復操作; 廣義地說廣義地說, 是按部就班解決一個問題的過程是按部就班解決一個問題的過程.以上這些都可以說是算法的直觀解釋以上這些都可以說是算法的直觀解釋 . 會不會有問題沒有算法呢會不會有問題沒有算法呢?找最大數(shù)問題找最大數(shù)問題l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: max a1,an .l輸入樣例輸入樣例: 1.1, 2.3, 4, 10, 8, 7, 3, 8對應輸出對應輸

5、出: 10 l算法算法: l1. 令令max=a1. l2. 對對 i = 2 到到 n, l3. 若若 max ai , 則則 max = ai . l4. 輸出輸出max. 輸入輸入,輸出輸出 確定性確定性有限性有限性可計算步驟可計算步驟 一個過程一個過程 有重復操作有重復操作 按部就班按部就班PCP問題沒有算法問題沒有算法Post Corresponding Problem(S)輸入輸入: 一簇骨牌一簇骨牌t1b1,t2b2tkbk解解(匹配匹配)是一個序列是一個序列i1,i2,il1,k, 使得使得lliiiiiibbbttt2121 l 輸出輸出: 給定骨牌簇是否有解給定骨牌簇是否有

6、解. bcaaabcaaabcc,2 1 3 2 43n+1問題目前不知道有沒有算法問題目前不知道有沒有算法l輸入輸入: 一個整數(shù)一個整數(shù)n,l映射映射: f(n) = n/2, 若若n是偶數(shù)是偶數(shù); f(n) = 3n+1, 若若n是奇數(shù)是奇數(shù). l迭代迭代: 5168, 到到1則停止則停止l輸出輸出: n可在可在f迭代下是否能停止迭代下是否能停止 l直接模擬是正確的算法嗎直接模擬是正確的算法嗎?l27需迭代需迭代111步步(見右圖見右圖) l151018都能到都能到1.(wiki)什么是正確的算法什么是正確的算法l對每個輸入樣例對每個輸入樣例, l 都能停機都能停機, 并輸出正確的結(jié)果并輸

7、出正確的結(jié)果. (C)l什么是不正確的算法什么是不正確的算法? 為什么需要嚴格定義算法為什么需要嚴格定義算法? l什么問題被解決了什么問題被解決了? (找最大數(shù)找最大數(shù))什么問題沒有被解決什么問題沒有被解決? (3n+1問題問題)什么問題沒有解決方案什么問題沒有解決方案? (PCP問題問題)l將在計算理論部分給出算法的嚴格定義將在計算理論部分給出算法的嚴格定義. 程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法l數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)是l為方便獲取和修改數(shù)據(jù)而存儲組織數(shù)據(jù)的方為方便獲取和修改數(shù)據(jù)而存儲組織數(shù)據(jù)的方式式 l本課程主要關(guān)注算法本課程主要關(guān)注算法, l僅在有必要的時候講解相關(guān)數(shù)據(jù)結(jié)構(gòu)僅在有必要的時候

8、講解相關(guān)數(shù)據(jù)結(jié)構(gòu) 算法技術(shù)算法技術(shù)l很多著名算法書很多著名算法書:計算機程序設(shè)計藝術(shù)、算法導論計算機程序設(shè)計藝術(shù)、算法導論 等等可作為算法可作為算法“菜譜菜譜”.l但實際工作中總會遇到菜譜中沒有的問題但實際工作中總會遇到菜譜中沒有的問題.l所以需要學習算法設(shè)計和分析技術(shù)所以需要學習算法設(shè)計和分析技術(shù)l本課程涉及的技術(shù)本課程涉及的技術(shù)(王王)有有:分治分治, 動態(tài)規(guī)劃動態(tài)規(guī)劃, 貪心貪心, 回溯回溯, 分支限界分支限界, 隨機等隨機等 l本課程約涉及本課程約涉及50個問題個問題(王王):01背包問題背包問題,單源最短路單源最短路, 旅行售貨員問題等旅行售貨員問題等算法的效率算法的效率l什么是高效

9、的算法什么是高效的算法?l 運行速度和占用空間可以用來度量效率運行速度和占用空間可以用來度量效率輸入規(guī)模輸入規(guī)模n n耗費時間耗費時間1 1小時小時/ /天天/ /年可解的問題實例的最大規(guī)模年可解的問題實例的最大規(guī)模計算機計算機快快100100倍計算機倍計算機快快10001000倍計算機倍計算機多多項項式式時時間間n nN1N1100 N1100 N11000 N11000 N1n2n2N2N210 N210 N231.6 N231.6 N2n3n3N3N34.64 N34.64 N310 N310 N3n5n5N4N42.5 N42.5 N43.98 N43.98 N4指數(shù)指數(shù)時間時間2n2

10、nN5N5N5 + 6.64N5 + 6.64N5 + 9.97N5 + 9.973n3nN6N6N6 + 4.19N6 + 4.19N6 + 6.29N6 + 6.29高效的算法高效的算法l多項式時間算法在理論上是高效的算法多項式時間算法在理論上是高效的算法l指數(shù)時間完全問題指數(shù)時間完全問題l 例例: 全量詞化布爾公式是否真全量詞化布爾公式是否真(TQBF)x1y1x2y2P(x1,y1,x2,y2,) 其中其中P是布爾是布爾公式公式lNP(非確定性多項式時間非確定性多項式時間)完全問題完全問題l 也是可以多項式時間驗證解正確性的問題也是可以多項式時間驗證解正確性的問題.l 例例: 布爾公式

11、是否有真賦值布爾公式是否有真賦值(CNF-SAT)=(x)y) (x(z)有真賦值有真賦值(x,y,z)=(F,T,F) 例例: 3-SAT, CLIQUE, 頂點覆蓋頂點覆蓋, 哈密頓回路等哈密頓回路等 NP完全問題完全問題l目前還沒有找到多項式時間算法目前還沒有找到多項式時間算法七大千禧問題之一七大千禧問題之一l密碼系統(tǒng)設(shè)計密碼系統(tǒng)設(shè)計l說明目前沒有好算法說明目前沒有好算法l解決方案解決方案: 修改問題修改問題, 或使用近似算法或使用近似算法第二部分第二部分算法設(shè)計與分析起步算法設(shè)計與分析起步設(shè)計算法的步驟設(shè)計算法的步驟: 確定問題確定問題 給出算法給出算法, 分析算法復雜度分析算法復雜度

12、 尋求最優(yōu)算法尋求最優(yōu)算法 找最大數(shù)問題找最大數(shù)問題l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: max a1,an .序列序列32572918最大最大33577999修改次數(shù)修改次數(shù)10110100比較次數(shù)比較次數(shù)01111111l輸入樣例的規(guī)模輸入樣例的規(guī)模 N = 8l輸入樣例輸入樣例 I = 3,2,5,7,2,9,1,8l時間復雜度時間復雜度: c1N T(N,I) c2 N (很難計算精確很難計算精確值值) l以比較次數(shù)以比較次數(shù)(N)計算時間復雜度比較合理計算時間復雜度比較合理關(guān)于算法復雜度的度量關(guān)于算法復雜度的度量l 如何計算算法的復雜度如何計算算法的復雜度?

13、l 時間時間: 時間復雜度時間復雜度l 空間空間: 空間復雜度空間復雜度l 輸入規(guī)模輸入規(guī)模l 同樣輸入規(guī)模需要的時間空間也經(jīng)常不同同樣輸入規(guī)模需要的時間空間也經(jīng)常不同l 最壞時間復雜度最壞時間復雜度, 平均時間復雜度平均時間復雜度 f(n)l 系統(tǒng)不同、緩存大小不同等系統(tǒng)不同、緩存大小不同等 諸多影響因素諸多影響因素 l 需要約定輸入規(guī)模的度量需要約定輸入規(guī)模的度量: 數(shù)列數(shù)列, 圖等圖等找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3次大次大2比較次數(shù)比較次

14、數(shù)1l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大35次大次大23比較次數(shù)比較次數(shù)11l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大357次大次大235比較次數(shù)比較次數(shù)111l輸入規(guī)模輸入

15、規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3577次大次大2355比較次數(shù)比較次數(shù)1112l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3577999次大次大2355778比較次數(shù)比較次數(shù)11121

16、22l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8l對所有規(guī)模對所有規(guī)模N輸入輸入, 比較次數(shù)最多比較次數(shù)最多2(N-2)+1=2N-3 l漸近意義上已經(jīng)最優(yōu)漸近意義上已經(jīng)最優(yōu) , 但是能否進一步改進但是能否進一步改進? 最大次大最大次大(M): 方法二方法二-分治分治l分治法分治法: 設(shè)規(guī)模設(shè)規(guī)模n比較次數(shù)最多比較次數(shù)最多T(n)T(n) = 2T(n/2) + 2, l T(2)=1, T(3)=3l若若n=2k, T(n)=1.5n-2; (M)l若若n=32k, T(n)=5n/3-2l對一般對一般n, 可歸納證明可歸納證明 1.5n-2 T(n) 5n/3-

17、2 l 證明見本證明見本ppt附錄附錄. 3 2 5 7 2 9 1 83 2 5 72 9 1 8759898找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3次大次大2比較次數(shù)比較次數(shù)1找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大377次大次大255比較次數(shù)比較次數(shù)112找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l

18、輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大37799次大次大25527比較次數(shù)比較次數(shù)11212找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l輸入輸入: 一個實數(shù)序列一個實數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3779989次大次大2552718比較次數(shù)比較次數(shù)1121212對所有規(guī)模對所有規(guī)模n輸入輸入, 比較次數(shù)最多比較次數(shù)最多 3(n-2)/2 +1 = 3 n/2 - 2 1.5n-2 注注: C中對最大最小數(shù)問題使用了這個算法中對最大最小

19、數(shù)問題使用了這個算法. 找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法四方法四3 2 5 7 2 9 1 83 2 5 72 9 1 875,398,297,8,22 95 71 83 2修改的分治修改的分治: 維護可能次大集維護可能次大集 比較次數(shù)比較次數(shù):n-1+log2n32759281復雜度復雜度f(n)的漸近記法的漸近記法l稱稱g(n)是是f(n)的漸進上界的漸進上界, 即即f(n) = O(g(n), 若若 c0, N0, nN, f(n) c g(n) 例例: n2 n = O(n3), n2 n = O(n2) l稱稱g(n)是是f(n)的漸進下界的漸進下界, 即即f(n) =

20、 (g(n), 若若 c0, N0, nN, f(n) c g(n)例例: n2 n = (n), n2 n = (n2) lf(n) = (g(n) 漸近同階漸近同階 ( 王王, C), 若若 f(n) = O(g(n) 且且 f(n) = (g(n) 例例: n2 n = (n2) l注注: n0, n2 n2 n 10001n2. 漸近記法的等價極限定義漸近記法的等價極限定義O, , 示意圖示意圖f(n)c0g(n)c1g(n)n0f(n) = (g(n) f(n)cg(n)n0f(n) = O(g(n) f(n)cg(n)n0f(n) = (g(n) 常用漸近函數(shù)常用漸近函數(shù)f(n)

21、= O(g(n) 為方便為方便, g(n)通常取通常取 nk, /多項式多項式 nklogn, /含對數(shù)項含對數(shù)項 en 或或 eO(n) /指數(shù)函數(shù)指數(shù)函數(shù)注注: 為本課程為本課程ppt書寫方便書寫方便logn是是log2n 例如例如: log n3 = O(log n), log 3n = O(n)時間復雜度的分析技巧時間復雜度的分析技巧l直接估計、遞推關(guān)系直接估計、遞推關(guān)系l均攤分析均攤分析l 累計法累計法, 記賬法記賬法, 勢能法勢能法(C) l例例: k位二進制計數(shù)器問題位二進制計數(shù)器問題l從從0執(zhí)行加執(zhí)行加1操作操作, 直到到直到到n. l關(guān)鍵量關(guān)鍵量: 位反轉(zhuǎn)次數(shù)位反轉(zhuǎn)次數(shù)l粗略

22、估計粗略估計O(kn)或或O(nlogn) 從從0到到n需要的時間需要的時間-累計法累計法累計法累計法: 每位反轉(zhuǎn)總次數(shù)每位反轉(zhuǎn)總次數(shù) n+n/2+n/4+2n 均攤均攤: (累計后均攤累計后均攤) 每次操作平均反轉(zhuǎn)每次操作平均反轉(zhuǎn)2次次 從從0到到n需要的時間需要的時間-記賬法記賬法Ai我我時間時間0變變11變變02元元1元元0元元1元元 每次每次+1 只有只有1位從位從0變變1 總收入總收入 = 2n, 總支出總支出 2n 2n-k 從從0到到n需要的時間需要的時間-勢能法勢能法勢能法的原理勢能法的原理Di : 第第i次操作后的數(shù)據(jù)結(jié)構(gòu)次操作后的數(shù)據(jù)結(jié)構(gòu), i=0:n ci : 第第i次操

23、作的實際耗費時間次操作的實際耗費時間, i=1:n : 勢能函數(shù)勢能函數(shù), 將將Di映射為一個實數(shù)映射為一個實數(shù) (Di) di = ci + (Di) - (Di-1)第第i次操作的均攤時間次操作的均攤時間 i=1n di = i=1n (ci + (Di) - (Di-1) = i=1n ci + (Dn) - (D0)若若 (Di) (D0) (勢能勢能), 則則 i=1n di i=1n ci . 應用到計數(shù)器問題應用到計數(shù)器問題. (Di) = Di中中1的個數(shù)的個數(shù). di = ci + (Di) - (Di-1) = 2 證明證明: 設(shè)從設(shè)從Di-1到到Di有有b位位1變變0,

24、1位位0變變1, 則則ci=1+b, (Di) - (Di-1) =1-b一些符號和公式一些符號和公式 x : 小于等于小于等于x的最大整數(shù)的最大整數(shù), x :大于等于大于等于x 的最小整數(shù)的最小整數(shù) anbbnaloglog )1(1()(2!nennnn 1110 xxxnnkknkOnk1) 1 (ln1log n! = (n log n) 等比級數(shù)求和等比級數(shù)求和 調(diào)和級數(shù)調(diào)和級數(shù) Stirling公式公式本章小結(jié)和作業(yè)本章小結(jié)和作業(yè)算法分析題算法分析題 1-1, 1-2, 1-4 1-1 求下列函數(shù)的漸近表達式求下列函數(shù)的漸近表達式: 3n2+10n; n2/10+2n; 21+1/

25、n; log n3; 10log3n. 1-2 試論試論O(1)與與O(2)的區(qū)別的區(qū)別. 1-4 (1) 假設(shè)某算法在輸入規(guī)模為假設(shè)某算法在輸入規(guī)模為n時的計算時間為時的計算時間為T(n)=32n. 在某臺計算機在某臺計算機上上實現(xiàn)并完成該算法的時間為實現(xiàn)并完成該算法的時間為t秒秒. 現(xiàn)有另一臺計算機現(xiàn)有另一臺計算機, 其運行速度是第一臺的其運行速度是第一臺的64倍倍, 那么在這臺新機器上用同一算法在那么在這臺新機器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題秒內(nèi)能解輸入規(guī)模為多大的問題?(2) 若上述算法的計算時間改進為若上述算法的計算時間改進為T(n)=n2, 其余條件不變其余條件不變, 則在新機器上用則在新機器上用t秒秒時間能解輸入規(guī)模為多大的問題時間能解輸入規(guī)模為多大的問題?(3) 若上述算法的計算時間改進為若上述算法的計算時間改進為T(n