南京郵電大學(xué)通達(dá)學(xué)院2012年算法考點(diǎn)

1、第一章算法求解基礎(chǔ)算法特征(輸入、輸出、確定性、可行性、有窮性)描述算法的方法(自然語(yǔ)言、流程圖、偽代碼、程序設(shè)計(jì)語(yǔ)言)*歐幾里德算法(輾轉(zhuǎn)相除法)一一遞歸/迭代常見(jiàn)算法種類一一精確算法、啟發(fā)式算法、近似算法、概率算法 I數(shù)學(xué)歸納法證明；第二章算法分析基礎(chǔ)算法復(fù)雜度一運(yùn)行一個(gè)算法所需的時(shí)間和空間。好算法的四個(gè)特征(正確性、簡(jiǎn)明性、效率、最優(yōu)性)最優(yōu)性一算法(最壞情況下)的執(zhí)行時(shí)間已達(dá)到求解該類問(wèn)題所需時(shí)間的 下界。影響程序運(yùn)行時(shí)間的因素(程序所依賴的算法*、問(wèn)題規(guī)模和輸入數(shù)據(jù)、計(jì) 算機(jī)系統(tǒng)性能)算法的漸近時(shí)間復(fù)雜度一 量級(jí)上估計(jì)(O、。、。)最好、最壞、平均一課后習(xí)題2-8 (通過(guò)考察關(guān)鍵操作

2、的執(zhí)行次數(shù))時(shí)間復(fù)雜度證明課后習(xí)題2-10, 2-13, 2-17算法按時(shí)間復(fù)雜度分類：多項(xiàng)式時(shí)間算法、指數(shù)時(shí)間算法多項(xiàng)式時(shí)間算法：O( 1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時(shí)間算法：O(2n)O(n!) （而不是事件i）來(lái)確定關(guān)鍵路徑。*弗洛伊德算法*最長(zhǎng)公共子序列問(wèn)題課后習(xí)題7-90/1背包問(wèn)題及其啟發(fā)式方法求解注意：被支配的階躍點(diǎn)和所有XM的階躍點(diǎn)均應(yīng)該去除。課后習(xí)題7-15第八章回溯法狀態(tài)空間樹(shù)一一描述問(wèn)題解空間的樹(shù)形結(jié)構(gòu)問(wèn)題狀態(tài)（樹(shù)中每個(gè)結(jié)點(diǎn)）解狀態(tài)（候選解元組）答案狀態(tài)（可行解元組）最優(yōu)答案結(jié)點(diǎn)（目標(biāo)函數(shù)取最優(yōu)值的答案結(jié)點(diǎn)）剪枝函數(shù)（約束函數(shù)、限界函數(shù)

3、）約束函數(shù)一剪去不含答案結(jié)點(diǎn)的子樹(shù)限界函數(shù)一剪去不含最優(yōu)答案結(jié)點(diǎn)的子樹(shù)約束函數(shù)（顯式約束、隱式約束）顯示約束一 定了所有可能的元組，組成問(wèn)題的候選解集（解空間）L排列樹(shù)一一用于確定n個(gè)元素的排列滿足某些性質(zhì)的狀態(tài)空間樹(shù)， 一般有n!個(gè)葉結(jié)點(diǎn)（解狀態(tài)）。L子集樹(shù)一一從n個(gè)元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)空 間樹(shù)，一般有2n個(gè)解狀態(tài)。隱式約束一出了判定一個(gè)候選解是否為可行解的條件?；厮莘ㄉ疃葍?yōu)先搜索問(wèn)題的狀態(tài)空間樹(shù)，用剪枝函數(shù)（往往是約束函數(shù)）進(jìn) 行剪枝，通常求問(wèn)題的一個(gè)或全部可行解蒙特卡羅（Monte Carlo）算一一計(jì)回溯法處理一個(gè)實(shí)例時(shí),狀態(tài)空間樹(shù)上 實(shí)際生成的結(jié)點(diǎn)數(shù)的方法：m=1

4、+m +m m1+m m1m2+.U 01 U 12*n-皇后問(wèn)題（狀態(tài)空間樹(shù)，Monte Carlo算法估計(jì)實(shí)際生成的狀態(tài)空間樹(shù)結(jié) 點(diǎn)數(shù)）一課后習(xí)題8-2子集和數(shù)問(wèn)題（狀態(tài)空間樹(shù)）；課后習(xí)題8-6*圖的m-著色問(wèn)題；第九章分枝限界法分枝限界法廣度優(yōu)先搜索問(wèn)題的狀態(tài)空間樹(shù)，用剪枝函數(shù)（往往是限界函數(shù)） 進(jìn)行剪枝，通常求問(wèn)題的最優(yōu)解根據(jù)活結(jié)點(diǎn)表采用的數(shù)據(jù)結(jié)構(gòu)不同，分枝限界法分類：FIFO分枝限界法LIFO分枝限界法LC分枝限界法I十五謎問(wèn)題（定理9-1：判定初始狀態(tài)是否可以到達(dá)目標(biāo)狀態(tài)） FIFO、 LIFO、LC分枝限界法（代價(jià)估計(jì)函數(shù)3）和相對(duì)代價(jià)估計(jì)函數(shù)g （X）搜 索代價(jià)）上、下界函數(shù)一

5、與最優(yōu)化問(wèn)題的目標(biāo)函數(shù)有關(guān)c（x）是代價(jià)函數(shù)c（X）的下界函數(shù)u（x）是代價(jià)函數(shù)c（X）的上界函數(shù)如何用上、下界函數(shù)進(jìn)行剪枝：（若目標(biāo)函數(shù)取最小值時(shí)為最優(yōu)解）則用上界變量U記錄迄今為止已知的最小代價(jià)上界（即迄今為止已知的 可行解中目標(biāo)函數(shù)最小值），可以確定最小代價(jià)答案結(jié)點(diǎn)（最優(yōu)解）的代價(jià)值不會(huì)超過(guò)U。對(duì)任意結(jié)點(diǎn)，若c（X） NU,則X子樹(shù)可以剪枝。為了不至誤剪去包含最小代價(jià)答案結(jié)點(diǎn)的子樹(shù)，若X代表部分向量，則 U=min u（X）+e,U；若 X 是答案結(jié)點(diǎn)，則 U=min cost（X）,U。（若目標(biāo)函數(shù)取最大值時(shí)為最優(yōu)解）則用下界變量L記錄迄今為止已知的最大代價(jià)下界（即迄今為止已知的 可行

6、解中目標(biāo)函數(shù)最大值），最大代價(jià)答案結(jié)點(diǎn)（最優(yōu)解）的代價(jià)值不 會(huì)小于Lo對(duì)任意結(jié)點(diǎn)，若（X） WL，則X子樹(shù)可以剪枝。為了不至誤剪去包含最大代價(jià)答案結(jié)點(diǎn)的子樹(shù)，若X代表部分向量，則L=max c（x） f ,L；若 X 是答案結(jié)點(diǎn)，則 L=max cost（X）,L。帶時(shí)限的作業(yè)排序問(wèn)題（狀態(tài)空間樹(shù)，難點(diǎn)）；一課后習(xí)題9-2第十章NP完全問(wèn)題不確定算法及其時(shí)間復(fù)雜度最優(yōu)化問(wèn)題與判定問(wèn)題間的轉(zhuǎn)換關(guān)系I 理解P類問(wèn)題、NP類問(wèn)題、NP難度問(wèn)題、NP完全問(wèn)題的概念什么是多項(xiàng)式約化？課后習(xí)題10-6、10-7I 了解Cook定理的內(nèi)容（Steven Cook，1971年，證明了可滿足性問(wèn)題是NP完全的）NP難度（爬完全）問(wèn)題的證明步驟（例：最大集團(tuán)問(wèn)題）一課后習(xí)題10-8第十三章密碼算法信息安全的目標(biāo)機(jī)密性加密完整性一消息