算法導論.原書第3版

在有關算法的書中，有一些敘述非常嚴謹，但不夠全面；另一些涉及了大量的題材，但又缺乏嚴謹性。《算法導論(原書第3版)》將嚴謹性和全面性融為一體，深入討論各類算法，並着力使這些算法的設計和分析能為各個層次的讀者接受。全書各章自成體系，可以作為獨立的學習單元；算法以英語和偽代碼的形式描述，具備初步程序設計經驗的人就能看懂；說明和解釋力求淺顯易懂，不失深度和數學嚴謹性。全書選材經典、內容豐富、結構合理、邏輯清晰，對本科生的數據結構課程和研究生的算法課程都是非常實用的教材，在IT專業人員的職業生涯中，《算法導論(原書第3版)》也是一本案頭必備的參考書或工程實踐手冊。

第3版的主要變化：

•新增了van Emde Boas樹和多線程算法，並且將矩陣基礎移至附錄。

•修訂了遞歸式（現在稱為「分治策略」）那一章的內容，更廣泛地覆蓋分治法。

•移除兩章很少講授的內容：二項堆和排序網絡。

•修訂了動態規划和貪心算法相關內容。

•流網絡相關材料現在基於邊上的全部流。

•由於關於矩陣基礎和Strassen算法的材料移到了其他章，矩陣運算這一章的內容所占篇幅更小。

•修改了對Knuth-Morris-Pratt字符串匹配算法的討論。

•新增100道練習和28道思考題，還更新並補充了參考文獻。

托馬斯•科爾曼（Thomas H. Cormen）達特茅斯學院計算機科學系教授、系主任。目前的研究興趣包括：算法工程、並行計算、具有高延遲的加速計算。他分別於1993年、1986年獲得麻省理工學院電子工程和計算機科學博士、碩士學位，師從Charles E. Leiserson教授。由於他在計算機教育領域的突出貢獻，Cormen教授榮獲2009年ACM傑出教員獎。

出版者的話
譯者序
前言

第一部分 基礎知識

第1章 算法在計算中的作用
1.1算法
1.2作為一種技術的算法
思考題
本章注記

第2章 算法基礎
2.1插入排序
2.2分析算法
2.3設計算法
2.3.1分治法
2.3.2分析分治算法
思考題
本章注記

第3章 函數的增長
3.1漸近記號
3.2標准記號與常用函數
思考題
本章注記

第4章 分治策略
4.1最大子數組問題
4.2矩陣乘法的Strassen算法
4.3用代入法求解遞歸式
4.4用遞歸樹方法求解遞歸式
4.5用主方法求解遞歸式
4.6證明主定理
4.6.1對6的冪證明主定理
4.6.2向下取整和向上取整
思考題
本章注記

第5章 概率分析和隨機算法
5.1雇用問題
5.2指示器隨機變量
5.3隨機算法
*5.4概率分析和指示器隨機變量的進一步使用
5.4.1生日悖論
5.4.2球與箱子
5.4.3特征序列
5.4.4在線雇用問題
思考題
本章注記

第二部分 排序和順序統計量

第6章 堆排序
6.1堆
6.2維護堆的性質
6.3建堆
6.4堆排序算法
6.5優先隊列
思考題
本章注記

第7章 快速排序
7.1快速排序的描述
7.2快速排序的性能
7.3快速排序的隨機化版本
7.4快速排序分析
7.4.1最壞情況分析
7.4.2期望運行時間
思考題
本章注記

第8章 線性時間排序
8.1排序算法的下界
8.2計數排序
8.3基數排序
8.4桶排序
思考題
本章注記

第9章 中位數和順序統計量
9.1最小值和最大值
9.2期望為線性時間的選擇算法
9.3最壞情況為線性時間的選擇算法
思考題
本章注記

第三部分 數據結構

第10章 基本數據結構
10.1棧和隊列
10.2鏈表
10.3指針和對象的實現
10.4有根樹的表示
思考題
本章注記

第11章 散列表
11.1直接尋址表
11.2散列表
11.3散列函數
11.3.1除法散列法
11.3.2乘法散列法
*11.3.3全域散列法
11.4開放尋址法
11.5完全散列
思考題
本章注記

第12章 二叉搜索樹
12.1什麼是二叉搜索樹
12.2查詢二叉搜索樹
12.3插入和刪除
12.4隨機構建二叉搜索樹
思考題
本章注記

第13章 紅黑樹
13.1紅黑樹的性質
13.2旋轉
13.3插入
13.4刪除
思考題
本章注記

第14章 數據結構的擴張
14.1動態順序統計
14.2如何擴張數據結構
14.3區間樹
思考題
本章注記

第四部分 高級設計和分析技術

第15章 動態規划
15.1鋼條切割
15.2矩陣鏈乘法
15.3動態規划原理
15.4最長公共子序列
15.5最優二叉搜索樹
思考題
本章注記

第16章 貪心算法
16.1活動選擇問題
16.2貪心算法原理
16.3赫夫曼編碼
*16.4擬陣和貪心算法
*16.5用擬陣求解任務調度問題
思考題
本章注記

第17章 攤還分析
17，1聚合分析
17.2核算法
17.3勢能法
17.4動態表
17.4.1表擴張
17.4.2表擴張和收縮
思考題
本章注記

第五部分 高級數據結構

第18章 B樹
18.1B樹的定義
18.2B樹上的基本操作
18.3從B樹中刪除關鍵字
思考題
本章注記

第19章 斐波那契堆
19.1斐波那契堆結構
19.2可合並堆操作
19.3關鍵字減值和刪除一個結點
19.4最大度數的界
思考題
本章注記

第20章 van Emde Boas樹
20.1基本方法
20.2遞歸結構
20.2.1原型van Emde Boas結構
20.2.2原型van Emde Boas結構上的操作
20.3van Emde Boas樹及其操作
20.3.1van Emde Boas樹
20.3.2van Emde Boas樹的操作
思考題
本章注記

第21章 用於不相交集合的數據結構
21.1不相交集合的操作
21.2不相交集合的鏈表表示
21.3不相交集合森林
*21.4帶路徑壓縮的按秩合並的分析
思考題
本章注記

第六部分 圖算法

第22章 基本的圖算法
22.1圖的表示
22.2廣度優先搜索
22.3深度優先搜索
22.4拓撲排序
22.5強連通分量
思考題
本章注記

第23章 最小生成樹
23.1最小生成樹的形成
23.2Kruskal算法和Prim算法
思考題
本章注記

第24章 單源最短路徑
24.1Bellman—Ford算法
24.2有向無環圖中的單源最短路徑問題
24.3Dijkstra算法
24.4差分約束和最短路徑
24.5最短路徑性質的證明
思考題
本章注記

第25章 所有結點對的最短路徑問題
25.1最短路徑和矩陣乘法
25.2Floyd—Warshall算法
25.3用於稀疏圖的Johnson算法
思考題
本章注記

第26章 最大流
26.1流網絡
26.2Ford—Fulkerson方法
26.3最大二分匹配
*26.4推送一重貼標簽算法
*26.5前置重貼標簽算法
思考題
本章注記

第七部分 算法問題選編

第27章 多線程算法
27.1動態多線程基礎
27.2多線程矩陣乘法
27.3多線程歸並排序
思考題
本章注記

第28章 矩陣運算
28.1求解線性方程組
28.2矩陣求逆
28.3對稱正定矩陣和最小二乘
逼近
思考題
本章注記

第29章 線性規划
29.1標准型和松弛型
29.2將問題表達為線性規划
29.3單純形算法
29.4對偶性
29.5初始基本可行解
思考題
本章注記

第30章 多項式與快速傅里葉變換
30.1多項式的表示
30.2DFT與FFT
30.3高效FFT實現
思考題
本章注記

第31章 數論算法
31.1基礎數論概念
31.2最大公約數
31.3模運算
31.4求解模線性方程
31.5中國余數定理
31.6元素的冪
31.7RSA公鑰加密系統
*31.3素數的測試
*31.9整數的因子分解
思考題
本章注記

第32章 字符串匹配
32.1朴素字符串匹配算法
32.2Rabin—Karp算法
32.3利用有限自動機進行字符串匹配
*32.4Knuth—Morris—Pratt算法
思考題
本章注記

第33章 計算幾何學
33.1線段的性質
33.2確定任意一對線段是否相交
33.3尋找凸包
33.4尋找最近點對
思考題
本章注記

第34章 NP完全性
34.1多項式時間
34.2多項式時間的驗證
34.3NP完全性與可歸約性
34.4NP完全性的證明
34.5NP完全問題
34.5.1團問題
34.5.2頂點覆蓋問題
34.5.3哈密頓回路問題
34.5.4旅行商問題
34.5.5子集和問題
思考題
本章注記

第35章 近似算法
35.1頂點覆蓋問題
35.2旅行商問題
35.2.1滿足三角不等式的旅行商問題
35.2.2一般旅行商問題
35.3集合覆蓋問題
35.4隨機化和線性規划
35.5子集和問題
思考題
本章注記

第八部分 附錄：數學基礎知識

附錄A 求和
A.1求和公式及其性質
A.2確定求和時間的界
思考題
附錄注記

附錄B 集合等離散數學內容
B.1集合
B.2關系
B.3函數
B.4圖
B.5樹
B.5.1自由樹
B.5.2有根樹和有序樹
B.5.3二叉樹和位置樹
思考題
附錄注記

附錄C 計數與概率
C.1計數
C.2概率
C.3離散隨機變量
C.4幾何分布與二項分布
思考題
附錄注記

附錄D 矩陣
D.1矩陣與矩陣運算
D.2矩陣的基本性質
思考題
附錄注記
參考文獻
索引