算法設計（第3版） The Algorithm Design Manual, 3/e

 

目   錄

捲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