算法設計技巧與分析 (修訂版) Algorithms: Design Techniques and Analysis

本書是國際著名算法專家李德財教授主編的系列叢書Lecture Notes Series on Computing中的一本。本書涵蓋了絕大多數算法設計中的一般技術， 在講解每一種技術時， 闡述了它的應用背景， 註重用與其他技術相比較的方法說明它的特徵， 並提供大量實際問題的例子。本書同時也強調了對每一種算法的詳細的復雜性分析。全書分七部分共18 章， 從算法設計與算法分析的基本概念和方法入手， 先後介紹了遞歸、分治、動態規劃、貪心算法、圖的遍歷等技術， 對NP 完全問題進行了基本但清晰的討論。作者對概率算法、近似算法和計算幾何這些發展迅猛的領域也用一定的篇幅講述了基本內容。書中每章後都附有大量的練習， 有利於讀者對書中內容的理解和應用。

目 錄

第一部分 基本概念和算法導引第1章 算法分析基本概念

1.1 引言

1.2 歷史背景

1.3 二分搜索

1.4 合並兩個已排序的表

1.5 選擇排序

1.6 插入排序

1.7 自底向上合並排序

1.8 時間復雜性

1.9 空間復雜性

1.10 最優算法

1.11 如何估計算法的運行時間

1.12 最壞情況和平均情況的分析

1.13 平攤分析

1.14 輸入大小和問題實例

1.15 分治遞推式

1.16 練習

1.17 參考註釋第2章 數據結構

2.1 引言

2.2 鏈表

2.3 圖

2.4 樹

2.5 根樹

2.6 二叉樹

2.7 練習

2.8 參考註釋第3章 堆和不相交集數據結構

3.1 引言

3.2 堆

3.3 不相交集數據結構

3.4 練習

3.5 參考註釋

第二部分 基於遞歸的技術第4章 歸納法

4.1 引言

4.2 尋找多數元素

4.3 整數冪

4.4 多項式求值（Horner規則）

4.5 基數排序

4.6 生成排列

4.7 練習

4.8 參考註釋第5章 分治

5.1 引言

5.2 二分搜索

5.3 合並排序

5.4 分治範式

5.5 選擇： 尋找中項和第k小的元素

5.6 快速排序

5.7 多選

5.8 大整數乘法

5.9 矩陣乘法

5.10 最近點對問題

5.11 練習

5.12 參考註釋第6章 動態規劃

6.1 引言

6.2 最長公共子序列問題

6.3 矩陣鏈相乘

6.4 動態規劃範式

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

6.6 背包問題

6.7 練習

6.8 參考註釋

第三部分 最先割技術第7章 貪心算法

7.1 引言

7.2 最短路徑問題

7.3 最小耗費生成樹（Kruskal算法）

7.4 最小耗費生成樹(Prim算法)

7.5 文件壓縮

7.6 練習

7.7 參考註釋第8章 圖的遍歷

8.1 引言

8.2 深度優先搜索

8.3 深度優先搜索的應用

8.4 廣度優先搜索

8.5 廣度優先搜索的應用

8.6 練習

8.7 參考註釋

第四部分 問題的復雜性第9章 NP完全問題

9.1 引言

9.2 P類

9.3 NP類

9.4 NP完全問題的分析

9.5 coNP類

9.6 三種復雜性類之間的關系

9.7 練習

9.8 參考註釋第10章 計算復雜性引論

10.1 引言

10.2 計算模型：圖靈機

10.3 k帶圖靈機和時間復雜性

10.4 離線圖靈機和空間復雜性

10.5 帶壓縮和線性加速

10.6 復雜性類之間的關系

10.7 歸約

10.8 完全性

10.9 多項式時間層次

10.10 練習

10.11 參考註釋第11章 下界

11.1 引言

11.2 平凡下界

11.3 決策樹模型

11.4 代數決策樹模型

11.5 線性時間歸約

11.6 練習

11.7 參考註釋

第五部分 剋服困難性第12章 回溯法

12.1 引言

12.2 3著色問題

12.3 8皇後問題

12.4 一般回溯法

12.5 分支限界法

12.6 練習

12.7 參考註釋第13章 隨機算法

13.1 引言

13.2 Las Vegas和Monte Carlo算法

13.3 兩個簡單的例子

13.4 隨機快速排序

13.5 隨機選擇

13.6 占有問題

13.7 尾部界

13.8 Chernoff界的應用：多選

13.9 隨機取樣

13.10 最小割問題

13.11 測試串的相等性

13.12 模式匹配

13.13 素數測試

13.14 練習

13.15 參考註釋第14章 近似算法

14.1 引言

14.2 基本定義

14.3 差界

14.4 相對性能界

14.5 多項式近似方案

14.6 完全多項式近似方案

14.7 練習

14.8 參考註釋

第六部分 域指定問題的迭代改進第15章 網絡流

15.1 引言

15.2 預備知識

15.3 FordFulkerson方法

15.4 最大容量增值

15.5 最短路徑增值

15.6 Dinic算法

15.7 MPM算法

15.8 練習

15.9 參考註釋第16章 匹配

16.1 引言

16.2 預備知識

16.3 二分圖上的網絡流方法

16.4 二分圖的匈牙利樹方法

16.5 一般圖中的最大匹配

16.6 二分圖的On2.5算法

16.7 練習

16.8 參考註釋

第七部分 計算幾何技術第17章 幾何掃描

17.1 引言

17.2 一個簡單的例子：計算點集中的極大點

17.3 幾何預備知識

17.4 計算線段的交點

17.5 凸包問題

17.6 計算點集的直徑

17.7 練習

17.8 參考註釋第18章 Voronoi圖解

18.1 引言

18.2 最近點Voronoi圖解

18.3 Voronoi圖解的應用

18.4 最遠點Voronoi圖解

18.5 最遠點Voronoi圖解的應用

18.6 練習

18.7 參考註釋附錄A 數學預備知識

附錄B 離散概率簡介

參考文獻