演演算法設計與分析

本書內容主要包括非常經典的演演算法設計技術，例如遞歸與分治、動態規劃、貪心、回溯、分支限界、圖演演算法，也包括了一些高級的演演算法設計主題，例如網路流和匹配、啟髮式搜索、線性規劃、數論以及計算幾何。在演演算法分析方面，介紹了概率分析以及最新的分攤分析和實驗分析方法。在演演算法的理論方面，介紹了問題的下界、演演算法的正確性證明以及NP完全理論等方面的內容。

本書內容基本上涵蓋了目前程序設計競賽所要掌握的演演算法，並在書後精選了部分ACM國際大學生程序設計競賽的題目，供大家練習。

本書可作為計算機科學系、數學系、軟體學院等專業本科及研究生課程的教材，特別適合於有志於參加程序設計競賽的學生學習和訓練。

第1章 入門

1.1 問題

1.2 演演算法的概念

1.3 演演算法的正確性

1.4 演演算法的效率

1.5 問題的下界

1.6 小結

習題

實驗題

第2章 漸近符號

2.1 θ符號

2.2 O符號

2.3 η符號

2.4 漸近符號的性質

2.5 常用函數的直觀含義

2.6 小結

習題

第3章 演演算法分析方法

3.1 概率分析

3.2 分攤分析

3.2.1 合計方法

3.2.2 記賬方法

3.2.3 勢能方法

3.3 實驗分析

3.4 小結

習題

第4章 遞歸

4.1 演演算法思想

4.1.1 遞歸演演算法的應用

4.1.2 遞歸與迭代

4.2 遞歸方程的求解

4.2.1 替換方法

4.2.2 遞歸樹方法

4.2.3 式：去

4.3 多項式求值實驗

4.4 小結

習題

實驗題

第5章 分治演演算法

5.1 演演算法思想

5.2 合併排序

5.3 快速排序

5.4 大整數乘法

5.5 矩陣乘法

5.6 殘缺棋盤遊戲、

5.7 快速傅里葉變換(FFT)

5.8 小結

習題

實驗題

第6章 動態規劃

6.1 演演算法思想

6.2 裝配線調度問題

6.3 矩陣鏈乘法問題

6.4 最長公共子序列問題

6.5 0/1背包問題

6.6 最優二叉搜索樹問題

6.7 動態規劃的基本性質

6.8 小結

習題

實驗題

第7章 貪心演演算法

7.1 演演算法思想

7.2 任務選擇問題

7.3 背包問題

7.4 哈夫曼編碼問題

7.5 緩存維護問題

7.6 任務選擇問題實驗

7.7 小結

習題

實驗題

第8章 圖演演算法

8.1 圖的搜索問題

8.1.1 寬度優先搜索

8.1.2 深度優先搜索

8.2 最小生成樹問題

8.2.1 Kruskall演演算法

8.2.2 Prim演演算法

8.3 最短路徑問題

8.3.1 單個源點的最短路徑問題

8.3.2 所有點對的最短路徑問題

8.4 小結

習題

實驗題

第9章 網路流與匹配

9.1 最大流問題

9.1.1 FordFulkerson方法

9.1.2 最短路徑增廣演演算法

9.1.3 Dinic演演算法

9.1.4 MPM演演算法

9.1.5 最大流問題的變形

9.2 最小費用流問題

9.2.1 消除迴路演演算法

9.2.2 最小費用路演演算法

9.2.3 最小費用路演演算法的改進

9.3 匹配問題

9.3.1 二分圖匹配

9.3.2 一般圖的匹配

9.4 小結

習題

實驗題

第10章 線性規劃

10.1 線性規劃問題

10.1.1 線性規劃問題的標準形式

10.1.2 線性規劃問題的鬆弛形式

10.2 求解演演算法

10.2.1 圖解法

10.2.2 單純形演演算法

10.3 對偶

10.4 小結

習題

實驗題

第11章 NIP完全理論

11.1 判定問題

11.2 P和NP

11.3 NPC

11.3.1 NPC的定義

11.3.2 電路可滿足性問題

11.4 NPC的證明

11.4.1 可滿足性問題

11.4.2 3.CNF可滿足性問題

11。4.3 團問題

11.4.4 頂點覆蓋問題

11.5 其他NP完全問題

11.6 小結

習題

第12章 回溯

12.1 演演算法思想

12.2 裝載問題

12.3 0/1背包問題

12.4 著色問題

12.5 n皇后問題

12.6 旅行商問題

12.7 流水作業調度問題

12.8 零件切割問題

12.9 小結

習題

實驗題

第13章 分支限界

第14章 啟髮式搜索

第15章 數論

第16章 計算幾何

參考文獻