本書是國際著名算法專家李德財教授主編的系列叢書Lecture Notes Series on Computing中的一本。本書涵蓋了絕大多數(shù)算法設(shè)計中的一般技術(shù)， 在講解每一種技術(shù)時， 闡述了它的應(yīng)用背景， 注重用與其他技術(shù)相比較的方法說明它的特征， 并提供大量實際問題的例子。本書同時也強調(diào)了對每一種算法的詳細的復(fù)雜性分析。全書分七部分共18 章， 從算法設(shè)計與算法分析的基本概念和方法入手， 先后介紹了遞歸、分治、動態(tài)規(guī)劃、貪心算法、圖的遍歷等技術(shù)， 對NP 完全問題進行了基本但清晰的討論。作者對概率算法、近似算法和計算幾何這些發(fā)展迅猛的領(lǐng)域也用一定的篇幅講述了基本內(nèi)容。書中每章后都附有大量的練習(xí)， 有利于讀者對書中內(nèi)容的理解和應(yīng)用。
M. H. Alsuwaiyel在沙特阿拉伯的King Fahd University of Petroleum&Minerals（KFUPM，皇家法哈德石油礦業(yè)大學(xué)）完成大學(xué)學(xué)業(yè)，在南加州（USC）大學(xué)獲得計算機科學(xué)碩士和博士學(xué)位。作者曾任KFUPM的計算機科學(xué)系主任、工程與計算機學(xué)院院長。他在國際上有著廣泛的學(xué)術(shù)影響，也是相關(guān)機構(gòu)的高級顧問。
曹霑懋，工學(xué)博士，現(xiàn)供職于華南師范大學(xué)計算機學(xué)院副教授，研究生導(dǎo)師。曾作為美國Memphis 大學(xué)計算機系訪問學(xué)者。其研究涉及機器學(xué)習(xí)，主要從事網(wǎng)狀網(wǎng)算法開發(fā)以及應(yīng)用系統(tǒng)模型開發(fā)。
目 錄
第一部分 基本概念和算法導(dǎo)引第1章 算法分析基本概念
1.1 引言
1.2 歷史背景
1.3 二分搜索
1.4 合并兩個已排序的表
1.5 選擇排序
1.6 插入排序
1.7 自底向上合并排序
1.8 時間復(fù)雜性
1.9 空間復(fù)雜性
1.10 最優(yōu)算法
1.11 如何估計算法的運行時間
1.12 最壞情況和平均情況的分析
1.13 平攤分析
1.14 輸入大小和問題實例
1.15 分治遞推式
1.16 練習(xí)
1.17 參考注釋第2章 數(shù)據(jù)結(jié)構(gòu)
2.1 引言
2.2 鏈表
2.3 圖
2.4 樹
2.5 根樹
2.6 二叉樹
2.7 練習(xí)
2.8 參考注釋第3章 堆和不相交集數(shù)據(jù)結(jié)構(gòu)
3.1 引言
3.2 堆
3.3 不相交集數(shù)據(jù)結(jié)構(gòu)
3.4 練習(xí)
3.5 參考注釋
第二部分 基于遞歸的技術(shù)第4章 歸納法
4.1 引言
4.2 尋找多數(shù)元素
4.3 整數(shù)冪
4.4 多項式求值（Horner規(guī)則）
4.5 基數(shù)排序
4.6 生成排列
4.7 練習(xí)
4.8 參考注釋第5章 分治
5.1 引言
5.2 二分搜索
5.3 合并排序
5.4 分治范式
5.5 選擇： 尋找中項和第k小的元素
5.6 快速排序
5.7 多選
5.8 大整數(shù)乘法
5.9 矩陣乘法
5.10 最近點對問題
5.11 練習(xí)
5.12 參考注釋第6章 動態(tài)規(guī)劃
6.1 引言
6.2 最長公共子序列問題
6.3 矩陣鏈相乘
6.4 動態(tài)規(guī)劃范式
6.5 所有點對的最短路徑問題
6.6 背包問題
6.7 練習(xí)
6.8 參考注釋
第三部分 最先割技術(shù)第7章 貪心算法
7.1 引言
7.2 最短路徑問題
7.3 最小耗費生成樹（Kruskal算法）
7.4 最小耗費生成樹(Prim算法)
7.5 文件壓縮
7.6 練習(xí)
7.7 參考注釋第8章 圖的遍歷
8.1 引言
8.2 深度優(yōu)先搜索
8.3 深度優(yōu)先搜索的應(yīng)用
8.4 廣度優(yōu)先搜索
8.5 廣度優(yōu)先搜索的應(yīng)用
8.6 練習(xí)
8.7 參考注釋
第四部分 問題的復(fù)雜性第9章 NP完全問題
9.1 引言
9.2 P類
9.3 NP類
9.4 NP完全問題的分析
9.5 coNP類
9.6 三種復(fù)雜性類之間的關(guān)系
9.7 練習(xí)
9.8 參考注釋第10章 計算復(fù)雜性引論
10.1 引言
10.2 計算模型：圖靈機
10.3 k帶圖靈機和時間復(fù)雜性
10.4 離線圖靈機和空間復(fù)雜性
10.5 帶壓縮和線性加速
10.6 復(fù)雜性類之間的關(guān)系
10.7 歸約
10.8 完全性
10.9 多項式時間層次
10.10 練習(xí)
10.11 參考注釋第11章 下界
11.1 引言
11.2 平凡下界
11.3 決策樹模型
11.4 代數(shù)決策樹模型
11.5 線性時間歸約
11.6 練習(xí)
11.7 參考注釋
第五部分 克服困難性第12章 回溯法
12.1 引言
12.2 3著色問題
12.3 8皇后問題
12.4 一般回溯法
12.5 分支限界法
12.6 練習(xí)
12.7 參考注釋第13章 隨機算法
13.1 引言
13.2 Las Vegas和Monte Carlo算法
13.3 兩個簡單的例子
13.4 隨機快速排序
13.5 隨機選擇
13.6 占有問題
13.7 尾部界
13.8 Chernoff界的應(yīng)用：多選
13.9 隨機取樣
13.10 最小割問題
13.11 測試串的相等性
13.12 模式匹配
13.13 素數(shù)測試
13.14 練習(xí)
13.15 參考注釋第14章 近似算法
14.1 引言
14.2 基本定義
14.3 差界
14.4 相對性能界
14.5 多項式近似方案
14.6 完全多項式近似方案
14.7 練習(xí)
14.8 參考注釋
第六部分 域指定問題的迭代改進第15章 網(wǎng)絡(luò)流
15.1 引言
15.2 預(yù)備知識
15.3 FordFulkerson方法
15.4 最大容量增值
15.5 最短路徑增值
15.6 Dinic算法
15.7 MPM算法
15.8 練習(xí)
15.9 參考注釋第16章 匹配
16.1 引言
16.2 預(yù)備知識
16.3 二分圖上的網(wǎng)絡(luò)流方法
16.4 二分圖的匈牙利樹方法
16.5 一般圖中的最大匹配
16.6 二分圖的On2.5算法
16.7 練習(xí)
16.8 參考注釋
第七部分 計算幾何技術(shù)第17章 幾何掃描
17.1 引言
17.2 一個簡單的例子：計算點集中的極大點
17.3 幾何預(yù)備知識
17.4 計算線段的交點
17.5 凸包問題
17.6 計算點集的直徑
17.7 練習(xí)
17.8 參考注釋第18章 Voronoi圖解
18.1 引言
18.2 最近點Voronoi圖解
18.3 Voronoi圖解的應(yīng)用
18.4 最遠點Voronoi圖解
18.5 最遠點Voronoi圖解的應(yīng)用
18.6 練習(xí)
18.7 參考注釋附錄A 數(shù)學(xué)預(yù)備知識
附錄B 離散概率簡介
參考文獻
書單推薦
