算法設計(第3版) The Algorithm Design Manual, 3/e
(美)斯蒂文·斯金納(Steven S. Skiena) 著 謝勰,王輝,劉小佳,任方 譯
- 出版商: 清華大學
- 出版日期: 2024-08-01
- 售價: $768
- 貴賓價: 9.5 折 $730
- 語言: 簡體中文
- ISBN: 7302670943
- ISBN-13: 9787302670940
- 此書翻譯自: The Algorithm Design Manual, 3/e (Hardcover)
立即出貨
相關主題
商品描述
"本書由算法領域的知名專家Steven Skiena教授編寫,其主要內容包括基本算法設計、算法分析、數據結構、排序與查找、圖算法、動態規劃以及難解問題與近似算法。 “設計”是本書的核心,作者不但以生動有趣的語言講授了算法設計中的常用技術與思想,還著重教導我們應從已有經典設計和實現中汲取力量來完成問題求解,而這正是一個優秀算法工作者所必備的素養。為了更全面真實地展現作者的算法設計觀,本書每章都給出了若乾取自現實案例的精彩War Story,讀者可以從中深刻體驗到優秀算法設計的曲折歷程。為了減輕閱讀的難度,作者淡化了繁難的算法分析而僅僅給出性能結論與對比,這在同類算法書中是相當少見的。此外,本書配套網站包含大量算法設計資源以及作者本人的授課視頻,為算法設計者提供了極大的便利。 "
目錄大綱
目 錄
捲I 實用算法設計
第1章 算法設計簡論 3
1.1 機器人巡游最優化 4
1.2 合理挑選工作 8
1.3 關於正確性的推理 11
1.3.1 問題和特性 11
1.3.2 表述算法 12
1.3.3 論證非正確性 13
1.4 歸納與遞歸 14
1.5 建立問題的模型 16
1.5.1 組合式對象 17
1.5.2 遞歸式對象 18
1.6 反證法 20
1.7 關於“算法徵戰逸事” 20
1.8 算法徵戰逸事: 通靈者的模型建立 21
1.9 估算 24
1.10 習題 25
第2章 算法分析 30
2.1 RAM計算模型 30
2.2 大O記號 32
2.3 增長量級與強弱關系 35
2.4 以大O來推演公式 37
2.4.1 函數相加 38
2.4.2 函數相乘 38
2.5 關於效率的推理 39
2.5.1 選擇排序 39
2.5.2 插入排序 40
2.5.3 字符串模式匹配 41
2.5.4 矩陣乘法 43
2.6 求和 44
2.7 對數及其應用 46
2.7.1 對數與二分查找 46
2.7.2 對數與樹 46
2.7.3 對數與比特 46
2.7.4 對數與乘法 47
2.7.5 快速求冪 47
2.7.6 對數與求和 48
2.7.7 對數與司法正義 48
2.8 對數的特性 50
2.9 算法徵戰逸事: 錐體之秘 51
2.10 高等分析(*) 53
2.10.1 一些深奧難懂的函數 54
2.10.2 極限與強弱關系 55
2.11 習題 56
第3章 數據結構. 65
3.1 緊接數據結構與鏈接數據結構 65
3.1.1 數組. 66
3.1.2 指針與鏈接結構 67
3.1.3 對比. 69
3.2 容器: 棧與隊列. 70
3.3 字典 71
3.4 二叉查找樹 75
3.4.1 實現二叉查找樹 76
3.4.2 二叉查找樹究竟能有多好. 80
3.4.3 平衡查找樹 80
3.5 優先級隊列 82
3.6 算法徵戰逸事: 剝離三角剖分 84
3.7 散列 87
3.7.1 碰撞消除 87
3.7.2 憑借散列實現副本檢測. 89
3.7.3 其他散列技巧. 91
3.7.4 規範化 91
3.7.5 精簡. 91
3.8 專用數據結構 92
3.9 算法徵戰逸事: 把它們串起來 93
3.10 習題 96
第4章 排序 103
4.1 排序的應用 103
4.2 排序的範式 107
4.3 堆排序: 借助數據結構而得的最優排序. 108
4.3.1 堆 109
4.3.2 建堆. 111
4.3.3 取最小元 112
4.3.4 更快的建堆算法(*) 114
4.3.5 利用增量式插入來排序. 116
4.4 算法徵戰逸事: 給我一張機票 117
4.5 歸並排序: 通過分治來排序 119
4.6 快速排序: 通過隨機化來排序 122
4.6.1 快速排序期望情況的直觀解釋 124
4.6.2 隨機化算法. 125
4.6.3 快速排序真的快嗎 127
4.7 分配排序: 通過裝桶來排序 127
4.8 算法徵戰逸事: 為被告辯護的Skiena 129
4.9 習題 131
第5章 分治 138
5.1 二分查找及相關算法 138
5.1.1 出現次數的計數 139
5.1.2 單側二分查找. 140
5.1.3 平方根和其他方根 140
5.2 算法徵戰逸事: 錯中揪錯. 141
5.3 遞推關系 142
5.4 求解分治遞推關系 144
5.5 快速乘法 145
5.6 最大子範圍與最近點對 . 146
5.7 並行算法 148
5.7.1 數據並行化. 149
5.7.2 並行化的陷阱. 149
5.8 算法徵戰逸事: 毫無進展. 150
5.9 捲積(*). 151
5.9.1 捲積的應用. 152
5.9.2 快速多項式乘法(**) . 153
5.10 習題 155
第6章 散列與隨機化算法 158
6.1 重溫概率論 159
6.1.1 概率. 159
6.1.2 復合事件與獨立性 160
6.1.3 條件概率 161
6.1.4 概率分佈 162
6.1.5 均值與方差. 163
6.1.6 投擲硬幣 163
6.2 理解球與箱 165
6.3 為什麽散列是隨機化算法. 167
6.4 Bloom過濾器 168
6.5 生日悖論和完美散列 170
6.6 取小式散列 172
6.7 高效字符串匹配. 174
6.8 素性檢驗 176
6.9 算法徵戰逸事: 將我的中間名首字母告訴Knuth 177
6.10 隨機數從何而來 178
6.11 習題 179
第7章 圖的遍歷 182
7.1 圖的風格 183
7.2 用於圖的數據結構 187
7.3 算法徵戰逸事: 我曾是摩爾定律的受害者 191
7.4 算法徵戰逸事: 圖的獲取. 194
7.5 遍歷圖 196
7.6 廣度優先搜索 196
7.6.1 實現. 198
7.6.2 發掘遍歷的功用 199
7.6.3 尋找路徑 199
7.7 廣度優先搜索的應用 200
7.7.1 連通分量 200
7.7.2 雙色圖 201
7.8 深度優先搜索 202
7.9 深度優先搜索的應用 205
7.9.1 尋找環 206
7.9.2 關節點 206
7.10 有向圖的深度優先搜索. 210
7.10.1 拓撲排序 211
7.10.2 強連通分量. 212
7.11 習題 215
第8章 加權圖算法 222
8.1 最小生成樹 222
8.1.1 Prim算法 223
8.1.2 Kruskal算法. 226
8.1.3 合並—查找數據結構 228
8.1.4 最小生成樹的變種 230
8.2 算法徵戰逸事: 網絡之外別無他求. 231
8.3 最短路徑 234
8.3.1 Dijkstra算法. 234
8.3.2 全圖點對最短路徑 237
8.3.3 傳遞閉包 239
8.4 算法徵戰逸事: 撥出文檔. 239
8.5 網絡流和二部匹配 243
8.5.1 二部匹配 243
8.5.2 計算網絡流. 244
8.6 隨機化最小割 247
8.7 去設計圖, 而非算法 248
8.8 習題 251
第9章 組合搜索 255
9.1 回溯 255
9.2 回溯實例 258
9.2.1 構建全部子集. 258
9.2.2 構建全部置換. 259
9.2.3 構建圖的全部路徑 260
9.3 搜索剪枝法 262
9.4 數獨 263
9.5 算法徵戰逸事: 覆蓋棋盤. 267
9.6 最佳優先搜索 271
9.7 A.啟發式方法. 272
9.8 習題 274
第10章 動態規劃 279
10.1 緩存與計算 280
10.1.1 以遞歸計算Fibonacci數 280
10.1.2 以緩存計算Fibonacci數 281
10.1.3 以動態規劃計算Fibonacci數 283
10.1.4 二項式系數. 283
10.2 字符串近似匹配 285
10.2.1 以遞歸計算編輯距離 .286
10.2.2 以動態規劃求解編輯距離 287
10.2.3 重建路徑 289
10.2.4 編輯距離的變種 291
10.3 最長遞增子序列 293
10.4 算法徵戰逸事: 條碼的文本壓縮. 295
10.5 無次序劃分/子集和值 . 298
10.6 算法徵戰逸事: 功率平衡 .300
10.7 依次序劃分問題 302
10.8 上下文無關語言的語法分析 305
10.9 動態規劃的局限性: TSP. 307
10.9.1 動態規劃算法什麽時候是正確的?. 308
10.9.2 動態規劃算法什麽時候是高效的?. 309
10.10 算法徵戰逸事: 過去所發生的事就是Prolog 310
10.11 習題 313
第11章 NP完全 321
11.1 問題和歸約 321
11.1.1 關鍵思想 322
11.1.2 判定問題 323
11.2 算法的歸約 323
11.2.1 最近點對 324
11.2.2 最長遞增子序列 324
11.2.3 最小公倍數. 325
11.2.4 凸包(*) 326
11.3 基礎性的難解性歸約 327
11.3.1 哈密頓環 328
11.3.2 獨立集和頂點覆蓋 329
11.3.3 團 332
11.4 可滿足性 333
11.5 創造性的歸約 335
11.5.1 頂點覆蓋 335
11.5.2 整數規劃 337
11.6 難解性證明的藝術 339
11.7 算法徵戰逸事: 爭分奪秒亦難. 340
11.8 算法徵戰逸事: 後來我失敗了 .343
11.9 P與NP 345
11.9.1 驗證與發現 .345
11.9.2 P類和NP類. 345
11.9.3 可滿足性問題為何如此之難 346
11.9.4 是NP難解還是NP完全? 346
11.10 習題 348
第12章 處理難解問題 354
12.1 近似算法 354
12.2 頂點覆蓋問題的近似算法 355
12.3 歐氏空間旅行商問題 357
12.4 何時平均已經夠好 360
12.4.1 最大化k-SAT 360
12.4.2 最大無環子圖 361
12.5 集合覆蓋 361
12.6 啟發式搜索方法 363
12.6.1 隨機抽樣 364
12.6.2 局部搜索 366
12.6.3 模擬退火 368
12.6.4 模擬退火的應用 372
12.7 算法徵戰逸事: 只不過它不是收音機而已 .373
12.8 算法徵戰逸事: 對陣列退火 376
12.9 遺傳算法與其他啟發式搜索方法 .379
12.10 量子計算 380
12.10.1 “Quantum”電腦的特性 .380
12.10.2 Grover數據庫搜索算法 382
12.10.3 更快的“Fourier”變換 383
12.10.4 整數因子分解的Shor算法 384
12.10.5 展望量子計算 385
12.11 習題 387
第13章 如何設計算法 390
捲II 算法世界搭車客指南
第14章 算法問題目錄冊 397
第15章 數據結構 399
15.1 字典 399
15.2 優先級隊列 404
15.3 後綴樹和後綴數組 407
15.4 圖數據結構 410
15.5 集合數據結構 413
15.6 k維樹. 416
第16章 數值問題 420
16.1 解線性方程組 421
16.2 帶寬約減 424
16.3 矩陣乘法 426
16.4 行列式與積和式 428
16.5 約束最優化與無約束最優化 430
16.6 線性規劃 434
16.7 隨機數生成 437
16.8 因子分解與素性檢驗 440
16.9 精確算術 443
16.10 背包問題 446
16.11 離散傅里葉變換 449
第17章 組合問題 453
17.1 排序 453
17.2 查找 457
17.3 中位數和選擇 461
17.4 生成置換 463
17.5 生成子集 467
17.6 生成劃分 469
17.7 圖的生成 473
17.8 日歷計算 477
17.9 作業調度 478
17.10 可滿足性 481
第18章 圖問題: 多項式時間. 484
18.1 連通分量 484
18.2 拓撲排序 487
18.3 最小生成樹 489
18.4 最短路徑 494
18.5 傳遞閉包與傳遞約簡 498
18.6 匹配 500
18.7 歐拉環/中國郵遞員 503
18.8 邊連通度與頂點連通度 .506
18.9 網絡流 508
18.10 精緻繪圖 511
18.11 繪樹 514
18.12 平面性檢驗與嵌入 516
第19章 圖問題: NP難解 520
19.1 團 520
19.2 獨立集 523
19.3 頂點覆蓋 525
19.4 旅行商問題 527
19.5 哈密頓環 530
19.6 圖劃分 533
19.7 頂點著色 535
19.8 邊著色 539
19.9 圖同構 540
19.10 Steiner樹 544
19.11 反饋邊集/反饋頂點集 .547
第20章 計算幾何 551
20.1 穩健的幾何基元操作 551
20.2 凸包 555
20.3 三角剖分 558
20.4 Voronoi圖 561
20.5 最近鄰搜索 563
20.6 範圍搜索 566
20.7 點定位 569
20.8 相交檢測 571
20.9 裝箱問題 574
20.10 中軸變換 577
20.11 多邊形劃分 579
20.12 簡化多邊形 582
20.13 形狀相似度 584
20.14 運動規劃 587
20.15 直線排布維護 .590
20.16 Minkowski和 .592
第21章 集合與字符串問題 595
21.1 集合覆蓋 595
21.2 組集 598
21.3 字符串匹配 600
21.4 字符串近似匹配 603
21.5 文本壓縮 607
21.6 密碼學 610
21.7 有限狀態機最小化 613
21.8 最長公共子串/最長公共子序列 616
21.9 最短公共超串 618
第22章 算法相關資源 621
22.1 算法庫 621
22.1.1 LEDA 621
22.1.2 CGAL 622
22.1.3 Boost圖庫 622
22.1.4 Netlib 622
22.1.5 ACM算法集萃 623
22.1.6 GitHub與SourceForge. 623
22.1.7 The Stanford GraphBase 623
22.1.8 Combinatorica 624
22.1.9 源自書籍的程序 624
22.2 數據源 625
22.3 在線文獻資源 626
22.4 專業咨詢服務 626
參考文獻 627