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

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

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

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

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

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