《算法設計（第3版）》是清華大學出版社出版的圖書。
出版信息,內容簡介,目錄,
出版信息
算法設計（第3版）
作者：（美）斯蒂文·斯金納（Steven S. Skiena） 著 謝勰，王輝，劉小佳，任方 譯
叢書名：清華計算機圖書譯叢
定價：128元
印次：1-1
ISBN：9787302670940
出版日期：2024.08.01
印刷日期：2024.08.22
內容簡介
本書長期位居算法設計暢銷書排行榜前列，由算法領域的知名專家Steven Skiena教授編寫，歷經多年後推出了第3版，其主要內容包括算法基礎知識、數據結構、排序與查找、分治算法、散列與隨機化算法、圖算法、組合搜尋、動態規劃以及難解問題與近似算法。“設計”是本書的核心，作者不但以生動有趣的語言講授了算法設計中的常用技術與思想，還著重強調從已有經典設計和實現中汲取力量來完成問題求解，而這正是一個優秀算法設計工作者所必備的素養。
目錄
目 錄
卷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
