算法導論(原書第3版) 內容簡介：

在有關算法的書中，有一些敘述非常嚴謹，但不夠全面；另一些涉及了大量的題材，但又缺乏嚴謹性。本書將嚴謹性和全面性融為一體，深入討論各類算法，并著力使這些算法的設計和分析能為各個層次的讀者接受。全書各章自成體系，可以作為獨立的學習單元；算法以英語和偽代碼的形式描述，具備初步程序設計經驗的人就能看懂；說明和解釋力求淺顯易懂，不失深度和數學嚴謹性。

《算法導論(原書第3版)》選材經典、內容豐富、結構合理、邏輯清晰，對本科生的數據結構課程和研究生的算法課程都是非常實用的教材，在it專業(yè)人員的職業(yè)生涯中，本書也是一本案頭必備的參考書或工程實踐手冊。

第3版的主要變化：
新增了van emde boas樹和多線程算法，并且將矩陣基礎移至附錄。
修訂了遞歸式（現在稱為“分治策略”）那一章的內容，更廣泛地覆蓋分治法。
移除兩章很少講授的內容：二項堆和排序網絡。
修訂了動態(tài)規(guī)劃和貪心算法相關內容。
流網絡相關材料現在基于邊上的全部流。
由于關于矩陣基礎和strassen算法的材料移到了其他章，矩陣運算這一章的內容所占篇幅更小。
修改了對knuth-morris-pratt字符串匹配算法的討論。
新增100道練習和28道思考題，還更新并補充了參考文獻。

算法導論(原書第3版)  目錄：
第一部分　基礎知識
第1章　算法在計算中的作用3
1.1　算法3
1.2　作為一種技術的算法6
思考題8 本章注記8
第2章　算法基礎9
2.1　插入排序9
2.2　分析算法13
2.3　設計算法16
2.3.1　分治法16
2.3.2　分析分治算法20
思考題22
本章注記24
第3章　函數的增長25
3.1　漸近記號25
3.2　標準記號與常用函數30
思考題35 本章注記36
第4章　分治策略37
4.1　最大子數組問題38
4.2　矩陣乘法的strassen算法43
4.3　用代入法求解遞歸式47
4.4　用遞歸樹方法求解遞歸式50
4.5　用主方法求解遞歸式53
4.6　證明主定理55
4.6.1　對b的冪證明主定理56
4.6.2　向下取整和向上取整58
思考題60
本章注記62
第5章　概率分析和隨機算法65
5.1　雇用問題65
5.2　指示器隨機變量67
5.3　隨機算法69
?5.4　概率分析和指示器隨機變量的進一步使用73
5.4.1　生日悖論73
5.4.2　球與箱子75
5.4.3　特征序列76
5.4.4　在線雇用問題78
思考題79
本章注記80
第二部分　排序和順序統(tǒng)計量
第6章　堆排序84
6.1　堆84
6.2　維護堆的性質85
6.3　建堆87
6.4　堆排序算法89
6.5　優(yōu)先隊列90
思考題93
本章注記94
第7章　快速排序95
7.1　快速排序的描述95
7.2　快速排序的性能97
7.3　快速排序的隨機化版本100
7.4　快速排序分析101
7.4.1　最壞情況分析101
7.4.2　期望運行時間101
思考題103
本章注記106
第8章　線性時間排序107
8.1　排序算法的下界107
8.2　計數排序108
8.3　基數排序110
8.4　桶排序112
思考題114
本章注記118
第9章　中位數和順序統(tǒng)計量119
9.1　最小值和最大值119
9.2　期望為線性時間的選擇算法120
9.3　最壞情況為線性時間的選擇算法123
思考題125
本章注記126
第三部分　數據結構
第10章　基本數據結構129
10.1　棧和隊列129
10.2　鏈表131
10.3　指針和對象的實現134
10.4　有根樹的表示137
思考題139
本章注記141
第11章　散列表142
11.1　直接尋址表142
11.2　散列表143
11.3　散列函數147
11.3.1　除法散列法147
11.3.2　乘法散列法148
11.3.3　全域散列法148
11.4　開放尋址法151
11.5　完全散列156
思考題158
本章注記160
第12章　二叉搜索樹161
12.1　什么是二叉搜索樹161
12.2　查詢二叉搜索樹163
12.3　插入和刪除165
12.4　隨機構建二叉搜索樹169
思考題171
本章注記173
第13章　紅黑樹174
13.1　紅黑樹的性質174
13.2　旋轉176
13.3　插入178
13.4　刪除183
思考題187
本章注記191
第14章　數據結構的擴張193
14.1　動態(tài)順序統(tǒng)計193
14.2　如何擴張數據結構196
14.3　區(qū)間樹198
思考題202
本章注記202
第四部分　高級設計和分析技術
第15章　動態(tài)規(guī)劃204
15.1　鋼條切割204
15.2　矩陣鏈乘法210
15.3　動態(tài)規(guī)劃原理215
15.4　最長公共子序列222
15.5　最優(yōu)二叉搜索樹226
思考題231 本章注記236
第16章　貪心算法237
16.1　活動選擇問題237
16.2　貪心算法原理242
16.3　赫夫曼編碼245
16.4　擬陣和貪心算法250
16.5　用擬陣求解任務調度問題253
思考題255
本章注記257
第17章　攤還分析258
17.1　聚合分析258
17.2　核算法261
17.3　勢能法262
17.4　動態(tài)表264
17.4.1　表擴張265
17.4.2　表擴張和收縮267
思考題270
本章注記273
第五部分　高級數據結構
第18章　b樹277
18.1　b樹的定義279
18.2　b樹上的基本操作281
18.3　從b樹中刪除關鍵字286
思考題288 本章注記289
第19章　斐波那契堆290
19.1　斐波那契堆結構291
19.2　可合并堆操作292
19.3　關鍵字減值和刪除一個結點298
19.4　最大度數的界300
思考題302
本章注記305
第20章　van emde boas樹306
20.1　基本方法306
20.2　遞歸結構308
20.2.1　原型van emde boas結構310
20.2.2　原型van emde boas結構上的操作311
20.3　van emde boas樹及其操作314
20.3.1　van emde boas樹315
20.3.2　van emde boas樹的操作317
思考題322
本章注記323
第21章　用于不相交集合的數據結構324
21.1　不相交集合的操作324
21.2　不相交集合的鏈表表示326
21.3　不相交集合森林328
*21.4　帶路徑壓縮的按秩合并的分析331
思考題336
本章注記337
第六部分　圖算法
第22章　基本的圖算法341
22.1　圖的表示341
22.2　廣度優(yōu)先搜索343
22.3　深度優(yōu)先搜索349
22.4　拓撲排序355
22.5　強連通分量357
思考題360
本章注記361
第23章　最小生成樹362
23.1　最小生成樹的形成362
23.2　kruskal算法和prim算法366
思考題370 本章注記373
第24章　單源最短路徑374
24.1　bellman?ford算法379
24.2　有向無環(huán)圖中的單源最短路徑問題381
24.3　dijkstra算法383
24.4　差分約束和最短路徑387
24.5　最短路徑性質的證明391
思考題395
本章注記398
第25章　所有結點對的最短路徑問題399
25.1　最短路徑和矩陣乘法400
25.2　floyd?warshall算法404
25.3　用于稀疏圖的johnson算法409
思考題412 本章注記412
第26章　最大流414
26.1　流網絡414
26.2　ford?fulkerson方法418
26.3　最大二分匹配428
26.4　推送重貼標簽算法431
26.5　前置重貼標簽算法438
思考題446
本章注記449
第七部分　算法問題選編
第27章　多線程算法453
27.1　動態(tài)多線程基礎454
27.2　多線程矩陣乘法465
27.3　多線程歸并排序468
思考題472
本章注記476
第28章　矩陣運算478
28.1　求解線性方程組478
28.2　矩陣求逆486
28.3　對稱正定矩陣和最小二乘逼近489
思考題493
本章注記494
第29章　線性規(guī)劃495
29.1　標準型和松弛型499
29.2　將問題表達為線性規(guī)劃504
29.3　單純形算法507
29.4　對偶性516
29.5　初始基本可行解520
思考題525
本章注記526
第30章　多項式與快速傅里葉變換527
30.1　多項式的表示528
30.2　dft與fft531
30.3　高效fft實現536
思考題539
本章注記541
第31章　數論算法543
31.1　基礎數論概念543
31.2　最大公約數547
31.3　模運算550
31.4　求解模線性方程554
31.5　中國余數定理556
31.6　元素的冪558
31.7　rsa公鑰加密系統(tǒng)561
31.8　素數的測試565
31.9　整數的因子分解571
思考題574 本章注記576
第32章　字符串匹配577
32.1　樸素字符串匹配算法578
32.2　rabin?karp算法580
32.3　利用有限自動機進行字符串匹配583
32.4　knuth?morris?pratt算法588
思考題594
本章注記594
第33章　計算幾何學595
33.1　線段的性質595
33.2　確定任意一對線段是否相交599
33.3　尋找凸包604
33.4　尋找最近點對610
思考題613
本章注記615
第34章　np完全性616
34.1　多項式時間619
34.2　多項式時間的驗證623
34.3　np完全性與可歸約性626
34.4　np完全性的證明633
34.5　np完全問題638
34.5.1　團問題638
34.5.2　頂點覆蓋問題640
34.5.3　哈密頓回路問題641
34.5.4　旅行商問題644
34.5.5　子集和問題645
思考題647
本章注記649
第35章　近似算法651
35.1　頂點覆蓋問題652
35.2　旅行商問題654
35.2.1　滿足三角不等式的旅行商問題654
35.2.2　一般旅行商問題656
35.3　集合覆蓋問題658
35.4　隨機化和線性規(guī)劃661
35.5　子集和問題663
思考題667
本章注記669
第八部分　附錄：數學基礎知識
附錄a　求和672
a.1　求和公式及其性質672
a.2　確定求和時間的界674
思考題678 附錄注記678
附錄b　集合等離散數學內容679
b.1　集合679
b.2　關系682
b.3　函數683
b.4　圖685
b.5　樹687
b.5.1　自由樹688
b.5.2　有根樹和有序樹689
b.5.3　二叉樹和位置樹690
思考題691
附錄注記692
附錄c　計數與概率693
c.1　計數693
c.2　概率696
c.3　離散隨機變量700
c.4　幾何分布與二項分布702
*c.5　二項分布的尾部705
思考題708
附錄注記708
附錄d　矩陣709
d.1　矩陣與矩陣運算709
d.2　矩陣基本性質712
思考題714
附錄注記715
參考文獻716