書籍信息
作者：Sanjoy Dasgupta，王沛
定價：39.99元
印次：1-5
ISBN：9787302179399
出版日期：2008.07.01
印刷日期：2014.06.11
內容簡介
作為一本介紹算法技術和思想的書籍，本書不僅可以面向信息學科大學生作為基本的教材（或參考書），更是將任何具有初等數學基礎的人引入算法套用與研究殿堂的一塊引路石。本書循序漸進、深入淺出地展示了算法研究與套用中，從模型分析、算法構造到複雜性分析和算法最佳化的方方面面。涉及的內容從古老的算術算法、排序算法、簡單圖論到近現代出現的計算圖論、貪心算法、分治算法、線性規劃、動態規劃、隨機算法以及NP複雜性理論，甚至是尚未完全顯現全貌的量子計算，覆蓋了經典、現代和未來算法發展的眾多代表性工作。 本書選材新穎，內容豐富，適用於作為計算機學科以及相關學科算法課程的教材和參考書，同時也可作為從事算法研究的一本好的入門書籍。
圖書目錄
第0章序言 1
0.1書籍和算法 1
0.2從Fibonacci數列開始 3
0.3大O符號 6
習題 9
第1章數字的算法 13
1.1基本算術 13
1.1.1加法 13
1.1.2乘法和除法 16
1.2模運算 18
1.2.1模的加法和乘法 21
1.2.2模的指數運算 21
1.2.3Euclid的最大公因數算法 23
1.2.4Euclid算法的一種擴展 24
1.2.5模的除法 27
1.3素性測試 28
1.4密碼學 35
1.4.1密鑰機制：一次一密亂碼本和AES 36
1.4.2RSA 38
1.5通用散列表 40
1.5.1散列表 41
1.5.2散列函式族 41
習題 44
第2章分治算法 53
2.1乘法 53
2.2遞推式 57
2.3合併排序 59
2.4尋找中項 62
2.5矩陣乘法 66
2.6快速Fourier變換 67
2.6.1多項式的另一種表示法 68
2.6.2計算步驟的分治實現 71
2.6.3插值 75
2.6.4快速Fourier變換的細節 78
習題 83
第3章圖的分解 93
3.1為什麼是圖 93
3.2無向圖的深度優先搜尋 96
3.2.1迷宮探索 96
3.2.2深度優先搜尋 99
3.2.3無向圖的連通性 100
3.2.4前序和後序 100
3.3有向圖的深度優先搜尋 101
3.3.1邊的類型 101
3.3.2有向無環圖 103
3.4強連通部件 105
3.4.1定義有向圖的連通性 105
3.4.2一個有效的算法 106
習題 110
第4章圖中的路徑 119
4.1距離 119
4.2廣度優先搜尋 120
4.3邊的長度 122
4.4Dijkstra算法 123
4.4.1廣度優先搜尋的一個改進 123
4.4.2另一種解釋 127
4.4.3運行時間 129
4.5優先佇列的實現 129
4.5.1數組 129
4.5.2二分堆 130
4.5.3d堆 131
4.6含有負邊的圖的最短路徑 131
4.6.1負邊 131
4.6.2負環 135
4.7有向無環圖中的最短路徑 135
習題 136
第5章貪心算法 143
5.1最小生成樹 143
5.1.1一個貪心方法 144
5.1.2分割性質 146
5.1.3Kruskal算法 147
5.1.4一種用於分離集的數據結構 148
5.1.5Prim算法 153
5.2Huffman編碼 156
5.3Horn公式 160
5.4集合覆蓋 162
習題 164
第6章動態規劃 173
6.1重新審視有向無環圖的最短路徑問題 173
6.2最長遞增子序列 175
6.3編輯距離 177
6.4背包問題 183
6.5矩陣鏈式相乘 186
6.6最短路徑問題 189
6.7樹中的獨立集 193
習題 195
第7章線性規劃與歸約 205
7.1線性規劃簡介 205
7.1.1示例：利潤最大化 206
7.1.2示例：生產計畫 210
7.1.3示例：最優頻寬分配 212
7.1.4線性規劃的變體 214
7.2網路流 216
7.2.1石油運輸 216
7.2.2最大流 216
7.2.3對算法的深入觀察 217
7.2.4最優性的保證 221
7.2.5算法的效率 222
7.3二部圖的匹配 222
7.4對偶 224
7.5零和博弈(遊戲) 228
7.6單純形算法 232
7.6.1n維空間中的頂點和鄰居 232
7.6.2算法 233
7.6.3補遺 236
7.6.4單純形法的運行時間 238
7.7後記：電路值 241
習題 243
第8章NP-完全問題 253
8.1搜尋問題 253
8.2NP-完全問題 264
8.3所有的歸約 268
習題 286
第9章NP-完全問題的處理 293
9.1智慧型窮舉搜尋 294
9.1.1回溯 294
9.1.2分支定界 297
9.2近似算法 299
9.2.1頂點覆蓋 300
9.2.2聚類 302
9.2.3TSP 304
9.2.4背包問題 306
9.2.5逼近的層次 307
9.3局部搜尋中的啟發方法 308
9.3.1重新審視旅行商問題 308
9.3.2圖劃分 311
9.3.3處理局部最優 313
習題 316
第10章量子算法 321
10.1量子位元、疊加狀態和度量 321
10.2算法設計 325
10.3量子傅立葉變換 327
10.4周期性 329
10.5量子電路 331
10.5.1基本量子門 331
10.5.2量子電路的兩種基本類型 332
10.5.3量子傅立葉變換電路 333
10.6將因子分解問題轉化為周期求解問題 335
10.7因子分解的量子算法 337
習題 339
歷史背景及深入閱讀的資料 343
