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

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

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

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

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

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