中文名: 算法分析與設計
原名: Algorithm Design: Foundations, Analysis, and Internet Examples
作者: Michael T.Goodrich
Roberto Tamassia
譯者: 霍紅衛
圖書分類: 網絡
資源格式: PDF
版本: 掃描版
出版社: 人民郵電出版社
書號: 7115150540
發行時間: 2006年9月15日
地區: 大陸
語言: 簡體中文
簡介:

評論處1樓有網盤鏈接
內容介紹：
　　本書系統地闡述了算法設計的方法、技術和應用實例。全書內容包括基礎算法、基本數據結構、基本算法設計技術、圖算法、網絡流和匹配、文本處理算法、數論算法、網絡算法、np完全性、近似算法、回溯法和分枝限界法、外存算法、並行算法和在線算法。java實現示例覆蓋了軟件設計方法、面向對象實現問題和算法的實驗性分析。這些典型問題的java應用示例分布在不同的章節中。此外，書中以大量圖例說明算法的工作過程，使算法更加易於理解和掌握。.
　　 本書適合作為高等院校計算機專業本科生和研究生算法設計課程的教材，也可作為從事軟件開發和工程設計的專業人員的參考書。此外，算法愛好者和參加各種程序設計大賽的選手也可把本書作為參考用書。...
內容截圖：



目錄:
第一部分 基礎工具.
第1章 算法分析 2
1.1 算法的分析方法學 2
1.1.1 偽代碼 4
1.1.2 隨機存取機(ram)模型 5
1.1.3 統計基本操作的數量 6
1.1.4 遞歸算法分析 7
1.2 漸近符號 8
1.2.1 大o符號 8
1.2.2 與大“o”相關的漸近符號 10
1.2.3 漸近表示的重要性 12
1.3 數學概覽 13
1.3.1 求和 13
1.3.2 對數和指數 14
1.3.3 簡單證明技術 16
1.3.4 概率基礎 18
1.4 算法分析案例研究 20
1.4.1 二次時間前綴平均值算法 21
1.4.2 線性時間前綴平均值算法 22
1.5 平攤方法 22
.1.5.1 平攤技術 23
1.5.2 擴展數組實現分析 25
1.6 實驗 28
1.6.1 實驗組織 28
1.6.2 數據分析和可視化 29
1.7 習題 31
基礎題 31
創新題 33
程序設計 35
1.8 本章注記 36
第2章 基本數據結構 37
2.1 棧和隊列 37
2.1.1 棧 37
2.1.2 隊列 40
2.2 向量、表和序列 43
2.2.1 向量 43
2.2.2 表 44
2.2.3 序列 48
2.3 樹 49
2.3.1 樹抽象數據類型 51
2.3.2 樹的遍歷 52
2.3.3 二叉樹 55
2.3.4 表示樹的數據結構 60
2.4 優先隊列和堆 62
2.4.1 優先隊列抽象數據類型 63
2.4.2 pq排序、選擇排序和插入排序 64
2.4.3 堆數據結構 66
2.4.4 堆排序 71
2.5 字典與散列表 76
2.5.1 無序字典adt 76
2.5.2 散列表 77
2.5.3 散列函數 78
2.5.4 壓縮映射 80
2.5.5 沖突處理模式 80
2.5.6 通用散列 83
2.6 java示例：堆 85
2.7 習題 87
基礎題 87
創新題 89
程序設計 91
2.8 本章注記 91
第3章 查找樹和跳躍表 93
3.1 有序字典和二叉查找樹 94
3.1.1 有序表 94
3.1.2 二叉查找樹 96
3.1.3 二叉查找樹中的查找 96
3.1.4 二叉查找樹中的插入 98
3.1.5 二叉查找樹中的刪除 99
3.1.6 二叉查找樹的性能 100
3.2 avl樹 101
3.2.1 更新操作 102
3.2.2 性能 105
3.3 深度有界查找樹 106
3.3.1 多路查找樹 106
3.3.2 (2,4)樹 108
3.3.3 紅黑樹 113
3.4 伸展樹 123
3.4.1 伸展 123
3.4.2 伸展過程的平攤分析 128
3.5 跳躍表 131
3.5.1 查找 132
3.5.2 更新操作 133
3.5.3 跳躍表的概率分析 135
3.6 java示例：avl樹和紅黑樹 136
3.6.1 avl樹的java實現 138
3.6.2 紅黑樹的java實現 141
3.7 習題 143
基礎題 143
創新題 144
程序設計 145
3.8 本章注記 146
第4章 排序、集合和選擇 147
4.1 歸並排序 147
4.1.1 分治法 148
4.1.2 歸並排序和遞歸方程 151
4.2 集合抽象數據類型 152
4.2.1 簡單的集合實現 152
4.2.2 具有union-find操作的劃分 153
4.2.3 基於樹的劃分實現 154
4.3 快速排序 159
4.4 基於比較的排序下界 162
4.5 桶排序和基數排序 163
4.5.1 桶排序 163
4.5.2 基數排序 164
4.6 比較排序算法 165
4.7 選擇 166
4.7.1 剪枝-查找法 166
4.7.2 隨機化快速選擇 166
4.7.3 隨機化快速選擇分析 167
4.8 java示例：原位快速排序 168
4.9 習題 170
基礎題 170
創新題 171
程序設計 172
4.10 本章注記 173
第5章 基本技術 174
5.1 貪心法 174
5.1.1 背包問題 175
5.1.2 任務調度 176
5.2 分治法 177
5.2.1 分治遞歸方程 177
5.2.2 整數相乘 182
5.2.3 矩陣相乘 183
5.3 動態規劃 185
5.3.1 矩陣鏈乘 185
5.3.2 一般技術 187
5.3.3 0-1背包問題 188
5.4 習題 190
基礎題 190
創新題 191
程序設計 191
5.5 本章注記 192
第二部分 圖算法
第6章 圖 194
6.1 圖抽象數據類型 194
6.2 圖的數據結構 199
6.2.1 邊表結構 199
6.2.2 鄰接表結構 201
6.2.3 鄰接矩陣結構 203
6.3 圖的遍歷 204
6.3.1 深度優先查找 204
6.3.2 雙連通分量 206
6.3.3 廣度優先查找 211
6.4 有向圖 213
6.4.1 遍歷有向圖 214
6.4.2 傳遞閉包 216
6.4.3 dfs和垃圾收集 218
6.4.4 有向無環圖 219
6.5 java示例：深度優先查找 222
6.5.1 修飾模式 222
6.5.2 dfs引擎 223
6.5.3 模板方法設計模式 224
6.6 習題 227
基礎題 227
創新題 228
程序設計 229
6.7 本章注記 229
第7章 加權圖 230
7.1 單源點最短路徑 231
7.1.1 dijkstra算法 231
7.1.2 bellman-ford最短路徑算法 236
7.1.3 有向無環圖中的最短路徑 238
7.2 所有頂點對之間的最短路徑 240
7.2.1 動態規劃最短路徑算法.. 240
7.2.2 利用矩陣相乘計算最短路徑 241
7.3 最小生成樹 244
7.3.1 kruskal算法 245
7.3.2 prim-jarník算法 249
7.3.3 bar?vka算法 251
7.3.4 mst算法比較 253
7.4 java示例：dijkstra算法 253
7.5 習題 256
基礎題 256
創新題 256
程序設計 257
7.6 本章注記 258
第8章 網絡流和匹配 259
8.1 流和割 260
8.1.1 流網絡 260
8.1.2 割 261
8.2 最大流 262
8.2.1 剩余容量和增大路徑 262
8.2.2 ford-fulkerson算法 264
8.2.3 ford-fulkerson算法分析 266
8.2.4 edmonds-karp算法 267
8.3 最大二分匹配 269
8.4 最小代價流 270
8.4.1 增大回路 271
8.4.2 連續最短路徑 272
8.4.3 修改權值 273
8.5 java示例：最小代價流 276
8.6 習題 281
基礎題 281
創新題 281
程序設計 282
8.7 本章注記 282
第三部分 因特網算法
第9章 文本處理 284
9.1 串和模式匹配算法 284
9.1.1 串操作 285
9.1.2 蠻力模式匹配 286
9.1.3 boyer-moore算法 287
9.1.4 knuth-morris-pratt算法 289
9.2 trie 292
9.2.1 標准trie 292
9.2.2 壓縮trie 294
9.2.3 後綴trie 295
9.2.4 搜索引擎 298
9.3 文本壓縮 298
9.3.1 赫夫曼編碼算法 299
9.3.2 修正貪心法 300
9.4 文本相似性測試 301
9.4.1 最長公共子序列問題 301
9.4.2 應用動態規劃求解lcs問題 301
9.5 習題 303
基礎題 303
創新題 304
程序設計 305
9.6 本章注記 305
第10章 數論和密碼學 306
10.1 與數有關的基本算法 306
10.1.1 基本數論的一些事實 307
10.1.2 歐幾裡得gcd算法 308
10.1.3 模運算 310
10.1.4 模指數運算 313
10.1.5 模乘法逆元 315
10.1.6 素性測試 316
10.2 密碼計算 320
10.2.1 對稱加密模式 321
10.2.2 公鑰密碼系統 322
10.2.3 rsa密碼系統 323
10.2.4 el gamal密碼系統 325
10.3 信息安全算法和協議 326
10.3.1 單向散列函數 326
10.3.2 時間戳和認證字典 327
10.3.3 硬幣拋擲和比特承諾 327
10.3.4 安全電子傳輸(set)協議 328
10.3.5 密鑰分發和交換 329
10.4 快速傅裡葉變換 330
10.4.1 本原單位根 332
10.4.2 離散傅裡葉變換 333
10.4.3 快速傅裡葉變換算法 335
10.4.4 大整數相乘 337
10.5 java示例：fft 339
10.6 習題 345
基礎題 345
創新題 345
程序設計 346
10.7 本章注記 346
第11章 網絡算法 348
11.1 復雜性測度和模型 349
11.1.1 網絡協議棧 349
11.1.2 消息傳遞模型 349
11.1.3 網絡算法的復雜性測度 350
11.2 基本分布式算法 351
11.2.1 環網上的領導人選舉 351
11.2.2 樹網上的領導人選舉 354
11.2.3 廣度優先查找 356
11.2.4 最小生成樹 359
11.3 廣播路由和單播路由 360
11.3.1 廣播路由的洪泛算法 360
11.3.2 單播路由的距離矢量算法 361
11.3.3 單播路由的鏈路-狀態算法 362
11.4 多播路由 363
11.4.1 逆向路徑轉發 363
11.4.2 中心樹 364
11.4.3 steiner樹 365
11.5 習題 367
基礎題 367
創新題 367
程序設計 369
11.6 本章注記 369
第四部分 其他主題
第12章 計算幾何 372
12.1 范圍樹 372
12.1.1 一維范圍查找 373
12.1.2 二維范圍查找 375
12.2 優先查找樹 377
12.2.1 構造一棵優先查找樹 378
12.2.2 優先查找樹中的查找 378
12.2.3 優先范圍樹 380
12.3 四叉樹和k-d樹 380
12.3.1 四叉樹 381
12.3.2 k-d樹 382
12.4 平面掃描技術 383
12.4.1 正交線段相交 383
12.4.2 查找最近點對 385
12.5 凸包 388
12.5.1 幾何對象表示 388
12.5.2 點方位測試 389
12.5.3 凸包的基本性質 390
12.5.4 禮品包扎算法 392
12.5.5 graham掃描算法 393
12.6 java示例：凸包 395
12.7 習題 398
基礎題 398
創新題 398
程序設計 400
12.8 本章注記 400
第13章 np完全性 401
13.1 p類和np類 402
13.1.1 定義復雜類p和復雜類np 402
13.1.2 np中的一些有趣問題 404
13.2 np完全性 406
13.2.1 多項式時間歸約和np困難度 406
13.2.2 cook-levin定理 407
13.3 重要的np完全問題 408
13.3.1 cnf-sat和3sat 410
13.3.2 vertex-cover 412
13.3.3 clique和set-cover 413
13.3.4 subset-sum和knapsack 415
13.3.5 hamiltonian-cycle和tsp 417
13.4 近似算法 419
13.4.1 多項式時間的近似模式 420
13.4.2 vertex-cover的2-近似算法 422
13.4.3 tsp特例的2-近似算法 423
13.4.4 set-cover的對數近似算法 424
13.5 回溯法和分枝限界法 426
13.5.1 回溯法 426
13.5.2 分枝限界法 429
13.6 習題 433
基礎題 433
創新題 434
程序設計 435
13.7 本章注記 435
第14章 算法框架 437
14.1 外存算法 437
14.1.1 分層的存儲器管理 438
14.1.2 (a, 樹和b樹 440
14.1.3 外存排序 443
14.2 並行算法 445
14.2.1 並行計算模型 445
14.2.2 簡單並行分治法 446
14.2.3 串行子集和brent定理 447
14.2.4 遞歸倍增 447
14.2.5 並行歸並和排序 450
14.2.6 找出凸多邊形的直徑 450
14.3 在線算法 452
14.3.1 高速緩存算法 452
14.3.2 拍賣策略 457
14.3.3 競爭查找樹 458
14.4 習題 461
基礎題 461
創新題 461
程序設計 462
14.5 本章注記 462
附錄a 有用的數學知識 464
a.1 對數和指數 464
a.2 整型函數和關系 465
a.3 求和 466
a.4 有用的數學技術 467
參考書目 468
索引... 476