基本介紹
- 書名：計算機算法（C++語言描述）第2版
- 作者：Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekeran
- ISBN：9787302379669
- 定價：79元
- 出版社：清華大學出版社
- 出版時間：2015-2-2
- 裝幀：平裝
圖書簡介,圖書目錄,
圖書簡介
本書全面介紹算法設計思想以及算法分析原理。全書共分為四個部分：第一部分是基礎知識，包含第1章與第2章，主要介紹算法的基本概念、算法複雜度分析的基本方法、隨機算法以及理解本書所需掌握的數據結構知識等；第二部分包含第3～9章，介紹各種算法設計思想，包括分治策略、貪心策略、動態規劃、搜尋與遍歷、回溯、分支定界、代數方法等；第三部分包含第10～12章，介紹算法複雜度理論知識，包括下界定理、NP難和NP完全問題以及近似算法等；最後一部分是並行算法，包括第13～15章，介紹PRAM算法、格線算法以及超立方算法。
本書結構完整，內容從易到難，包含豐富實例與習題，對所涉及算法均提供C++或偽代碼，不僅可作為計算機專業本科或研究生的算法課程教材，也可作為算法愛好者的自學參考書。
圖書目錄
第1章 導論 1
1.1 什麼是算法 1
1.2 算法規範 3
1.2.1 導論 3
1.2.2 遞歸算法 5
1.3 性能分析 8
1.3.1 空間複雜度 8
1.3.2 時間複雜度 9
1.3.3 平攤複雜度 16
1.3.4 漸進符號（
1.3.5 實際複雜度 29
1.3.6 性能測量 31
1.4 機率算法 39
1.4.1 機率論基礎 39
1.4.2 隨機算法：正規描述 42
1.4.3 確認重複元素 43
1.4.4 素數測試 44
1.4.5 優缺點 47
1.5 參考文獻及閱讀 49
第2章 數據結構基礎 50
2.1 棧與佇列 50
2.2 樹 56
2.2.1 術語 57
2.2.2 二叉樹 58
2.3 字典 60
2.3.1 二叉搜尋樹 61
2.4 優先佇列 66
2.4.1 堆 67
2.4.2 堆排序 71
2.5 集合與不相交集合的並集 73
2.5.1 導論 73
2.5.2 求並集及查找操作 74
2.6 圖 80
2.6.1 導論 80
2.6.2 定義 81
2.6.3 圖的表示 83
2.7 參考文獻及閱讀 89
第3章 分治策略 90
3.1 一般方法 90
3.2 殘缺棋盤 93
3.3 二分搜尋 96
3.4 找最大值和最小值 101
3.5 合併排序 105
3.6 快速排序 111
3.6.1 性能測量 114
3.6.2 隨機排序算法 115
3.7 選擇 117
3.7.1 最差情況下的最優算法 120
3.7.2 Select2的實現 122
3.8 矩陣相乘 127
3.9 凸包 130
3.9.1 幾種幾何基本 130
3.9.2 QuickHull算法 131
3.9.3 Graham掃描 132
3.9.4 O(nlogn)的分治算法 134
3.10 參考文獻及閱讀 136
3.11 附加習題 137
第4章 貪心法 139
4.1 一般方法 139
4.2 貨櫃裝船 142
4.3 背包問題 144
4.4 樹節點分裂 147
4.5 有期限的工作序列化 150
4.6 最小生成樹 156
4.6.1 Prim算法 157
4.6.2 Kruskal算法 159
4.6.3 最優的隨機算法（*） 162
4.7 磁帶最優存儲 164
4.8 最優合併模式 168
4.9 單源最短路徑 172
4.10 參考文獻及閱讀 177
4.11 附加習題 178
第5章 動態規劃 180
5.1 一般方法 180
5.2 多段圖 183
5.3 每對頂點間最短路徑 187
5.4 單源最短路徑：一般權重 190
5.5 最優二叉搜尋樹（*） 193
5.6 串編輯 198
5.7 0/1背包 201
5.8 可靠性設計 207
5.9 旅行商問題 209
5.10 流水車間調度 211
5.11 參考文獻及閱讀 215
5.12 附加習題 215
第6章 基本遍歷及搜尋技術 219
6.1 二叉樹的遍歷及搜尋 219
6.2 圖的遍歷及搜尋 222
6.2.1 廣度優先搜尋及遍歷 223
6.2.2 深度優先搜尋及遍歷 225
6.3 連通分支及生成樹 226
6.4 雙連通分支 228
6.5 參考文獻及閱讀 234
第7章 回溯 235
7.1 一般方法 235
7.2 八皇后問題 243
7.3 子集求和 246
7.4 圖著色 248
7.5 哈密爾頓迴路 251
7.6 背包問題 253
7.7 參考文獻及閱讀 256
7.8 附加習題 257
第8章 分支定界 260
8.1 方法 260
8.1.1 最少代價（LC）搜尋 260
8.1.2 15拼圖：一個例子 262
8.1.3 最少代價搜尋的控制抽象 265
8.1.4 定界 266
8.1.5 FIFO分支定界 268
8.1.6 LC分支定界 268
8.2 0/1背包問題 269
8.2.1 LC分支定界解法 270
8.2.2 FIFO分支定界解法 272
8.3 旅行商問題（*） 275
8.4 效率 280
8.5 參考文獻及閱讀 282
第9章 代數問題 283
9.1 一般方法 283
9.2 求值與插值 284
9.3 快速傅立葉變換（FFT） 292
9.3.1 In-place版本的快速傅立葉變換 296
9.3.2 繼續思考 298
9.4 模算術 299
9.5 更快的求值和插值 305
9.6 參考文獻及閱讀 310
第10章 下界理論 312
10.1 比較樹 312
10.1.1 有序搜尋 313
10.1.2 排序 314
10.1.3 選擇 316
10.2 預言及對手論證 318
10.2.1 合併 318
10.2.2 最大和次大 319
10.2.3 狀態空間法 320
10.2.4 選擇 321
10.3 規約求下界 322
10.3.1 找凸包 323
10.3.2 不相交集合問題 324
10.3.3 線上中位數查找 324
10.3.4 三角形矩陣相乘 325
10.3.5 下三角形矩陣求逆 326
10.3.6 計算傳遞閉包 327
10.4 代數問題中的技巧（*） 329
10.5 參考文獻及閱讀 335
第11章 難及完全問題 336
11.1 基本概念 336
11.1.1 非確定算法 336
11.1.2
11.2 Cook定理（*） 344
11.3 ______
11.3.1 團判定問題（CDP） 350
11.3.2 點覆蓋判定問題（NCDP） 351
11.3.3 色數判定問題（CNDP） 352
11.3.4 有向圖哈密爾頓迴路問題（DHC）（*） 353
11.3.5 旅行商判定問題（TSP） 355
11.3.6 AND/OR圖判定問題（AOG） 355
11.4 D_Dd___
11.4.1 調度相同處理器 360
11.4.2 流水車間調度 362
11.4.3 作業車間調度 363
11.5 難的代碼生成問題 364
11.5.1 有公共子表達式的代碼生成 366
11.5.2 實現並行賦值指令 369
11.6 簡化的 D_Dd
11.7 參考文獻及閱讀 372
11.8 附加習題 373
第12章 近似算法 375
12.1 導論 375
12.2 絕對近似 377
12.2.1 平面圖著色 377
12.2.2 最大程式存儲問題 378
12.2.3 D_Dd___
12.3 ε近似 380
12.3.1 調度獨立任務 380
12.3.2 裝箱 382
12.3.3 ________
12.4 多項式時間近似方案 388
12.4.1 調度獨立任務 388
12.4.2 0/1背包 389
12.5 完全多項式時間近似方案 393
12.5.1 捨入 394
12.5.2 區間劃分 397
12.5.3 間隔 397
12.6 機率上好的近似方案（*） 400
12.7 參考文獻及閱讀 402
12.8 附加習題 402
第13章 PRAM算法 406
13.1 介紹 406
13.2 計算模型 408
13.3 基本技巧和算法 412
13.3.1 前綴計算 413
13.3.2 表排列 414
13.4 選取 420
13.4.1 使用n2個處理器選取最大元 420
13.4.2 使用 D_Dd______
13.4.3 整數範圍內的最大元 421
13.4.4 使用n2個處理進行一般性選擇 423
13.4.5 工作最優的隨機化選擇算法（*） 423
13.5 歸併 426
13.5.1 對數時間的算法 426
13.5.2 奇偶歸併 426
13.5.3 工作最優的算法 428
13.5.4 一個運行時間為O(log log m)的算法 429
13.6 排序 430
13.6.1 奇偶歸併排序 430
13.6.2 一個可供選擇的隨機化算法 431
13.6.3 Preparata算法 431
13.6.4 Reischuk隨機化算法（*） 432
13.7 圖問題 434
13.7.1 傳遞閉包的另一種計算方法 436
13.7.2 全點對的最小路徑問題 436
13.8 凸包計算 437
13.9 下界 439
13.9.1 排序的平均運行時間下界 440
13.9.2 尋找最大元 441
13.10 參考文獻及閱讀 442
13.11 附加習題 443
第14章 格線算法 445
14.1 計算模型 445
14.2 數據包路由 446
14.2.1 線性數組中的數據包路由 447
14.2.2 格線上PPR問題的貪心算法 450
14.2.3 使用小佇列的隨機化算法 450
14.3 基本算法 452
14.3.1 廣播 453
14.3.2 前綴計算 454
14.3.3 數據聚集 455
14.3.4 稀疏列舉排序 456
14.4 選取 459
14.4.1 n = p′情形下的隨機化算法（*） 459
14.4.2 n > p情形下的隨機化算法（*） 460
14.4.3 n > p情形下的確定性算法 460
14.5 歸併 463
14.5.1 通過秩實現線性數組上的歸併 463
14.5.2 線性數組上的奇偶歸併 464
14.5.3 格線上的奇偶歸併 465
14.6 排序 466
14.6.1 線性數組上的排序 466
14.6.2 格線上的排序 467
14.7 圖問題 470
14.7.1 n×n 格線上的傳遞閉包算法 471
14.7.2 全點對最短路徑算法 472
14.8 凸包計算 472
14.9 參考文獻及閱讀 475
14.10 附加習題 477
第15章 超立方算法 479
15.1 計算模型 479
15.1.1 超立方 479
15.1.2 蝴蝶網路 480
15.1.3 其他網路的嵌入 482
15.2 偏轉置路由 484
15.2.1 貪心算法 484
15.2.2 隨機化算法 485
15.3 基本算法 487
15.3.1 廣播 487
15.3.2 前綴計算 488
15.3.3 數據聚集 489
15.3.4 稀疏列舉排序 491
15.4 選取 492
15.4.1 n= p情形下的隨機化算法（*） 492
15.4.2 n > p情形下的隨機化選取算法（*） 493
15.4.3 n > p情形下的確定性算法 493
15.5 歸併 495
15.5.1 奇偶歸併 495
15.5.2 雙調歸併 496
15.6 排序 498
15.6.1 奇偶歸併排序 498
15.6.2 雙調排序 498
15.7 圖問題 499
15.8 凸包計算 500
15.9 參考文獻及閱讀 501
15.10 附加習題 502
