算法設計與分析

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

參考文獻 ^[1]