算法lecture考試時(shí)間12月29日下午

1、安排時(shí)間：12月29日 下午 2:004:00地點(diǎn)：二教 307, 308, 309注意事項(xiàng)：帶學(xué)生證、按指定教室進(jìn)入考場(chǎng)因病等特殊原因不能參加請(qǐng)表并經(jīng)主管院長簽字批準(zhǔn)答疑時(shí)間：12月28日下午2:00-5:00者需在填寫緩考申12月29日上午8:30-11:30答疑地點(diǎn)：1622 / 理科一號(hào)樓1要求數(shù)學(xué)基礎(chǔ)：估計(jì)函數(shù)的階、遞推方程求解、求和技術(shù)算法設(shè)計(jì)技術(shù)：分治策略、動(dòng)態(tài)規(guī)劃、貪心法、回溯與分支估界能進(jìn)行簡單應(yīng)用算法分析技術(shù)：對(duì)算法進(jìn)行和平均時(shí)間復(fù)雜度分析證明某些簡單問題的復(fù)雜度的下界計(jì)算復(fù)雜性理論圖靈機(jī)的定義理解計(jì)算復(fù)雜性理論的基本概念和重要結(jié)果NP-hard 問題的證明方法2處理難解問

2、題的策略對(duì)問題施加限制固定參數(shù)算法改進(jìn)指數(shù)時(shí)間算法3SAT、指數(shù)時(shí)間假設(shè)啟發(fā)式方法啟發(fā)式方法、隨機(jī)化策略、重啟策略、模擬退火平均情形的復(fù)雜性G(n,p)、回路、DistNP完全難解算例的生成對(duì)問題施加限制.SAT問題二元可滿足性（2SAT）屬于PHornSAT：輸入限制為公式（析取式中正文字，即不帶否定號(hào)的變量）至多出現(xiàn)一次，屬于P圖P問題D 2D 3VCHC2334頂點(diǎn)三23反饋頂點(diǎn)集給定D團(tuán)任意固定參數(shù)算法通常把優(yōu)化問題轉(zhuǎn)化為判定問題時(shí)，都會(huì)在輸入中引入一個(gè)參數(shù)，這是固定參數(shù)算法中參數(shù)的來源之一.輸入中帶有一個(gè)參數(shù) k，當(dāng)輸入規(guī)模為 n時(shí)運(yùn)行時(shí)間為O(f(k)nc) 的算法，這里的 f(k

3、)是與 n 無關(guān)的函數(shù)，c 是與 n和 k 都無關(guān)的常數(shù).例VC:給定圖G, 正整數(shù) K(不超過G的頂點(diǎn)數(shù))，問是否存在不超過 K 的頂點(diǎn)覆蓋？固定常數(shù) k，輸入為(G, k). 窮舉所有 k元 頂點(diǎn)子集，看看是否存在頂點(diǎn)覆蓋.算法復(fù)雜度大約是)=O(knk+1)O(k存在O(2kkn)的算法.5改進(jìn)的指數(shù)時(shí)間算法O*：表示忽略了多項(xiàng)式因子. 如O*(2n)=O(nO(1)2n)當(dāng)一個(gè)問題的蠻力算法為O*(2n)時(shí)間時(shí)，對(duì)任何滿足1 c 2的常數(shù)c，時(shí)間復(fù)雜度為O*(cn)的指數(shù)時(shí)間算法稱為非平凡的指數(shù)時(shí)間算法，或改進(jìn)的指數(shù)時(shí)間算法.可證明在O*(1.8393n)時(shí)間內(nèi)正確求解3SAT，截止到

4、2010年底 最好結(jié)果：O*(1.321n)時(shí)間的隨機(jī)算法和O*(1.439n)時(shí)間的確定型算法.問題都有O*(3n)的算法.任意色數(shù)的圖的頂點(diǎn)背包問題有比O*(2n/2)更好的算法.貨郎問題也有比O*(2n)更好的算法.6其他處理難解問題的策略啟發(fā)式方法（Heuristics）：目前無法從理論上給出任何性能保證，但在實(shí)踐中效果良好，就把這類方法統(tǒng)稱為啟發(fā)式方法（Heuristics）.常用的啟發(fā)式方法主要包括：回溯與分支限界法、局部搜索法（隨機(jī)化策略、重啟策略、模擬退火）、遺傳算法等.平均情況下的復(fù)雜度有些NP完全問題在平均復(fù)雜性度量下是易解的，回路問題的平均情況下對(duì)圖G(n,1/2)有O(

5、n3)時(shí)間的算法.難解算例生成:確定緊的實(shí)例基于統(tǒng)計(jì)物理的消息傳遞算法算法設(shè)計(jì)與分析的實(shí)例P2P的服務(wù)器文件配置NAND Flash控制器驗(yàn)證XML關(guān)鍵字的查詢改寫平面點(diǎn)集的凸包網(wǎng)絡(luò)優(yōu)化最大流及其應(yīng)用8問題1P2P的服務(wù)器文件配置背景決定P2P的服務(wù)器文件本的放置，在代價(jià)和代價(jià)的權(quán)衡中取得最優(yōu)實(shí)例S1, S2, , Sn為n個(gè)服務(wù)器, 每個(gè)Si 有代價(jià)ci用戶向 Si 發(fā)請(qǐng)求，若Si 沒文件，則順序Si+1,直到在 Sj找到，其問題代價(jià)為 ji，Sn必須存放1份文件要求一樣多（不妨設(shè)都等于1），假設(shè)每個(gè)服務(wù)器的如何放置文件，使得總代價(jià)（和）達(dá)到最?。?算法設(shè)計(jì)實(shí)例：服務(wù)器S1, S2, S3，

6、c1=5, c2=8, c3=2副本放 S3:副本放 S1,S3:代價(jià)=2+1+c3=2+1+2=5代價(jià)=c1+1+c3=8副本放 S2,S3:副本放 S1,S2,S3:代價(jià)=1+c2+c3=11代價(jià)=c1+c2+c3=15動(dòng)態(tài)規(guī)劃：OPT(j)表示副本放在Sj，從 S1到 Sj 的最小代價(jià)OPT( j) c j minOPT(i) C (i 1, j)j 10 i jC (i 1, j) ( j i 1) . 2 1 （ j i)( j i 1) / 2OTP(0) 01ii+1j時(shí)間復(fù)雜度：O(n2)10問題2NANDFlash控制器驗(yàn)證背景該控制器支持NANDFlash的操作：擦除、讀寫

7、用于實(shí)例系統(tǒng)的設(shè)計(jì)開發(fā)驗(yàn)證時(shí)需將內(nèi)存文件以頁為寫入NANDflash設(shè)備若文件字節(jié)數(shù)2112，放入1頁；大于2112，放入連續(xù)的幾頁給定t個(gè)文件的字節(jié)數(shù) f1,f2, ft(n+m=t)，n, m分別為字節(jié)大于和小于2112的文件數(shù)，通常n2112 thenfi=fi mod 2112先按從大到小次序把大于2112的文件裝入頁面，每個(gè)文件最后一個(gè)頁面大小改為2112fi 按照文件fi ( 不超過2112) 從大到小排序，然后裝入第一個(gè)適合它的頁面算法分析O(nlogn)+O(mlogm)+O(mn+m2)=O(m2 )近似比1.212實(shí)例f1=5560, f2=3124,f3=267, f4=

8、359,f5=123,f6=1560先放 f1,f2，頁面3 和 5 的剩余分別為776，1100排序f3, f4, f5, f6為：依次放入f6=1560,f4=359,f3=276,f5=1231100552f1f4f3f5問題3平面點(diǎn)集的凸包背景圖形處理中用于形狀識(shí)別：字形識(shí)別、碰撞檢測(cè)平面凸包算法是算法問題（平面凸包）給定大量離散點(diǎn)的集合Q，求一個(gè)最小的凸多邊形，使得Q中的點(diǎn)在該多邊形內(nèi)或者邊上.14分治算法算法以d=ymax,ymin 劃分L為左點(diǎn)集 Lleft 和右點(diǎn)集 LrightDeal(Llesft)；DeDeal(Lleft)bpymax把距離 d 最遠(yuǎn)點(diǎn) P 加入凸包檢查

9、 L中其他點(diǎn)是否在三角a形內(nèi)；在則從 L中刪除； 否則根據(jù)在 a 或 b 邊的外側(cè)劃分在兩個(gè)子問題中Deal(a)Deal(b)ymin15算法分析初始用d 劃分Deal 遞歸調(diào)用O(n)找凸包頂點(diǎn)PO(n)確定點(diǎn)是否在三角形O(n)(OW(n1)W( n )n(W1)情況為O(n2)1T(n)=O(n)+W(n)=O(n2)16問題4網(wǎng)絡(luò)優(yōu)化背景樹狀連通網(wǎng)絡(luò)，每條線路有傳輸延遲，只能改進(jìn)K條線路，以降低傳輸延遲，如何選擇？實(shí)例節(jié)點(diǎn)集 V=1,2, n，E=e1,e2,en-1，Kn-1wt 是邊 et 的傳輸延遲，t=1,2, n-1，W(i,j)是 i 到 j 的延遲 (從 i 到 j 路

10、徑上所有邊延遲之和)對(duì)ei 改進(jìn)后，邊上的延遲減少了pwi，p1為常數(shù)問題: 選 AE,|A|=K, 使得WA min WA (i , j ) ,| A| K , A E 1 i j n17貪心法設(shè)計(jì)與分析改進(jìn)ei之后總延遲減少了ci| Si | | Si | pwi選擇A后總延遲為eiSiSiW Wmaxc A貪心法iei Aj計(jì)算ci，i=1,2,n-1排序 ei 使得 c1 c2 cn-1A= e1, e2, , eK 利用交換論證可以證明算法得到最優(yōu)解18算法分析與實(shí)現(xiàn)主要工作量在于計(jì)算 ci選定樹根，DFS遍歷確定結(jié)點(diǎn)的深度自底向上按照深度為 d, d-1, , 1, 0層計(jì)算連接樹

11、葉 i 的邊的 葉端點(diǎn)Si 值 =1，Si= n-Si如果結(jié)點(diǎn) i 的子結(jié)點(diǎn)為a,b, c, 那么連接的邊 e 的 Si 值與Si 值分別為i 和它的父結(jié)點(diǎn)Si eSa+Sb+Sc+1,時(shí)間為O(n)Si=n-Sii cab算法時(shí)間為 O(n)+O(nlogn)SaSbSc19問題5XML關(guān)鍵字的查詢改寫背景基于XML的 key 的搜索中，通過把原始查詢Q的關(guān)鍵字序列改為新關(guān)鍵字序列，從而提高查全率實(shí)例設(shè)S=k1,k2,kn和T=k1,k2,km為key的序列R=r1,r2,r3,r4為操作集(替換,拆分,合并,刪除)，操作rj有代價(jià)c(rj)，從 S到T的改寫代價(jià)c(S,T)為把S 改寫成T

12、 的系列操作代價(jià)之和問題找到使 c(S,T) 最小的操作序列20查詢改寫實(shí)例21動(dòng)態(tài)規(guī)劃算法Ci表示改寫 k1, , ki 的最小代價(jià)，則if ki TCi1Ci 1 刪除 k 的代價(jià)if k TiiCi | l(r ) | 應(yīng)用 r 規(guī)則的代價(jià)jjif ki T and rj Rl(rj)表示從i向前改寫規(guī)則rj作用的關(guān)鍵字個(gè)數(shù)22問題6網(wǎng)絡(luò)的最大流流網(wǎng)絡(luò)是有向圖 G=(V,E)每條邊 e 關(guān)聯(lián)一個(gè)容量ce 0u2010單一源點(diǎn) sVtV一st30沒有邊進(jìn)入 s，沒有邊離開 t每個(gè)結(jié)點(diǎn)至少連接一條邊1020v23流的定義與最大流算法流定義一個(gè)s-t 流是函數(shù) f:ER+， f(e)表示邊 e 攜帶的流量，f 必須滿足下面性質(zhì):(容量條件) eE 有 0 f(e) ce(守恒條件) 除 s 與 t 之外，對(duì)每個(gè)結(jié)點(diǎn)v，有f (e) f (e)eve從 出v 來進(jìn)入Ford-Fulkerson算法增廣路徑技術(shù)若容量是整數(shù)，時(shí)間為O(mC)，m為邊數(shù)，C ce出s 發(fā)e從24實(shí)例增廣路徑：suvt ，增加流20u2010svut，增加流10解20101030s10tf(su) = 20,f(sv) =