《算法設計、分析與應用教程》通過設計、分析ACM庫的經典問題，把理論與實踐結合。各章遵循從一個例子或故事中引出本章知識點，簡述相關理論，分析經典問題及算法實現(xiàn)。主要包括算法概述、遞歸與分治策略、動態(tài)規(guī)劃、貪心算法、回溯算法、分支限界算法、圖的搜索算法、加密算法與安全機制、P和NP問題等內容。有故事、有理論、有公式、有實踐。所有算法實現(xiàn)結果都經參加ACM的隊員驗證。本書適合高樣計算機專業(yè)以及相關專業(yè)做為教材使用，也可供編程愛好者參考使用。
《算法設計、分析與應用教程》適合高樣計算機專業(yè)以及相關專業(yè)做為教材使用，也可供編程愛好者參考使用。
李文書，教授，工學博士，現(xiàn)任浙江理工大學信息學院，智能檢測與系統(tǒng)實驗室主任，碩士生導師。IEEE (1-1163129461)、中國計算機學會（E200016385M）會員和杭州市計算機學會會員；151第三層次培養(yǎng)人才。
第1章 算法概述 1
1.1 引言 1
1.1.1 算法的描述 2
1.1.2 算法的特性 2
1.1.3 為什么學習算法 3
1.2 算法的設計 5
1.3 算法的分析 8
1.3.1 正確性分析 9
1.3.2 時空效率分析 10
1.3.3 時空特性分析 13
1.4 解決問題的一般步驟 13
1.5 小結 15
1.6 習題 16
第2章 遞歸與分治策略 17
2.1 遞歸算法 18
2.1.1 遞歸的概念 18
2.1.2 具有遞歸特性的問題 19
2.1.3 遞歸算法分析 22
2.2 分治策略 28
2.2.1 分治法的基本步驟 28
2.2.2 分治法的適用條件 29
2.2.3 二分搜索技術 29
2.2.4 棋盤覆蓋問題 30
2.2.5 快速排序 33
2.2.6 大整數(shù)乘法 36
2.2.7 矩陣乘法 39
2.3 ACM經典問題解析 45
2.3.1 蜂窩問題
(難度：★☆☆☆☆) 45
2.3.2 Humble Numbers
(難度：★★☆☆☆) 46
2.3.3 Copying Books
(難度：★★★☆☆) 48
2.3.4 Fractal(難度：★★★☆☆) 51
2.3.5 TOYS(難度：★★☆☆☆) 53
2.3.6 Cable master
(難度：★★☆☆☆) 56
2.4 小結 58
2.5 習題 59
第3章 動態(tài)規(guī)劃 62
3.1 何謂動態(tài)規(guī)劃 63
3.1.1 動態(tài)規(guī)劃的基本思想 63
3.1.2 設計動態(tài)規(guī)劃法的步驟 63
3.1.3 動態(tài)規(guī)劃問題的特征 63
3.1.4 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關系 64
3.2 矩陣連乘積問題 65
3.2.1 分析最優(yōu)解的結構 67
3.2.2 建立遞歸關系 68
3.2.3 計算最優(yōu)值 69
3.2.4 構造最優(yōu)解 71
3.3 動態(tài)規(guī)劃算法的基本要素 72
3.3.1 最優(yōu)子結構 72
3.3.2 重疊子問題 72
3.3.3 備忘錄方法 73
3.4 最長公共子序列 75
3.4.1 最長公共子序列的結構 75
3.4.2 子問題的遞歸結構 76
3.4.3 計算最優(yōu)值 76
3.4.4 構造最長公共子序列 78
3.5 最大子段和 78
3.5.1 遞歸關系分析 78
3.5.2 算法實現(xiàn) 79
3.6 0-1背包問題 80
3.6.1 遞歸關系分析 81
3.6.2 算法實現(xiàn) 81
3.7 ACM經典問題解析 83
3.7.1 數(shù)塔(難度：★★☆☆☆) 83
3.7.2 免費餡餅
(難度：★★★☆☆) 84
3.7.3 Dividing
(難度：★★★☆☆) 86
3.7.4 Win the Bonus
(難度：★★★★☆) 88
3.7.5 Monkey and Banana
(難度：★★★★☆) 90
3.7.6 Railroad(難度：★★★★☆) 93
3.8 小結 96
3.9 習題 97
第4章 貪心算法 101
4.1 活動安排問題 102
4.2 貪心算法的理論基礎 104
4.2.1 貪心算法的基本思想 105
4.2.2 貪心算法的基本要素 105
4.2.3 貪心算法的基本步驟 106
4.3 刪數(shù)問題 107
4.3.1 貪心策略選擇 107
4.3.2 最優(yōu)子結構 107
4.3.3 算法實現(xiàn) 107
4.3.4 復雜度分析 108
4.4 背包問題 109
4.4.1 最優(yōu)子結構性質 109
4.4.2 貪心選擇性質 110
4.4.3 算法實現(xiàn) 110
4.4.4 復雜度分析 112
4.5 最優(yōu)裝載問題 112
4.5.1 貪心選擇性質 113
4.5.2 最優(yōu)子結構性質 113
4.5.3 算法實現(xiàn) 113
4.5.4 復雜度分析 114
4.6 單源最短路徑 115
4.6.1 算法基本思想 115
4.6.2 貪心選擇性質 116
4.6.3 最優(yōu)子結構性質 117
4.6.4 Dijkstra算法實現(xiàn) 117
4.6.5 復雜度分析 119
4.7 多處最優(yōu)服務次序問題 120
4.7.1 貪心選擇策略 120
4.7.2 貪心選擇性質 120
4.7.3 最優(yōu)子結構性質 120
4.7.4 算法實現(xiàn) 121
4.7.5 復雜度分析 122
4.8 ACM經典問題解析 122
4.8.1 Fat Mouse Trade
(難度：★★☆☆☆) 122
4.8.2 Sorting the Photos
(難度：★★★☆☆) 124
4.8.3 Moving Tables
(難度：★★★☆☆) 126
4.8.4 Box of Bricks
(難度：★★★★☆) 127
4.8.5 Wooden Sticks
(難度：★★★★☆) 128
4.8.6 釣魚問題
(難度：★★★★☆) 130
4.8.7 樹形DP問題
(難度：★★★★☆) 133
4.8.8 Frogs' Neighborhood
(難度：★★★☆☆) 135
4.9 小結 137
4.10 習題 138
第5章 回溯法 140
5.1 回溯法的基本思想 140
5.1.1 問題的解空間 141
5.1.2 搜索的解空間 143
5.1.3 回溯的基本步驟 144
5.1.4 回溯法實現(xiàn) 145
5.2 圖的m著色問題 147
5.2.1 問題的解空間 147
5.2.2 確定約束條件 148
5.2.3 搜索解空間 148
5.2.4 代碼實現(xiàn) 148
5.2.5 算法時間復雜度分析 150
5.3 n皇后問題 150
5.3.1 解空間 151
5.3.2 約束條件 151
5.3.3 搜索過程 151
5.3.4 算法的時間復雜度分析 154
5.4 裝載問題 154
5.4.1 問題的解空間 154
5.4.2 約束條件 154
5.4.3 限界條件 154
5.4.4 搜索過程 155
5.4.5 算法效率分析 157
5.5 0-1背包問題 157
5.5.1 解空間 157
5.5.2 約束條件 157
5.5.3 限界條件 157
5.5.4 搜索過程 158
5.5.5 算法效率分析 160
5.6 旅行商問題 160
5.6.1 解空間 161
5.6.2 約束條件 161
5.6.3 限界條件 161
5.6.4 搜索解空間 161
5.6.5 時間復雜度分析 163
5.7 批處理流水作業(yè)調度問題 163
5.7.1 解空間 163
5.7.2 約束條件 164
5.7.3 限界條件 164
5.7.4 搜索過程 164
5.7.5 時間復雜度分析 166
5.8 ACM經典問題解析 166
5.8.1 Dreisam Equations
(難度：★★★☆☆) 166
5.8.2 A Plug for UNIX
(難度：★★★☆☆) 170
5.8.3 回文構詞檢測(Anagram Checker)
(難度：★★☆☆☆) 174
5.8.4 Unshuffle
(難度：★★★☆☆) 178
5.9 小結 181
5.10 習題 181
第6章 分支限界算法 183
6.1 分支限界法的基本理論 184
6.1.1 分支限界法的搜索策略 184
6.1.2 分支結點的選擇 185
6.1.3 限界函數(shù) 185
6.2 單源最短路徑問題 186
6.2.1 問題描述 186
6.2.2 算法描述與設計 186
6.2.3 算法實現(xiàn) 188
6.3 裝載問題 190
6.3.1 問題描述 190
6.3.2 算法設計與實現(xiàn) 191
6.4 0-1背包問題 196
6.4.1 問題描述 196
6.4.2 算法描述與設計 196
6.4.3 算法實現(xiàn) 198
6.5 旅行商問題 202
6.5.1 問題描述 202
6.5.2 算法描述與設計 203
6.5.3 算法實現(xiàn) 204
6.7 ACM經典問題 209
6.7.1 布線問題
(難度：★★★☆☆) 209
6.7.2 方格調整問題
(難度：★★★☆☆) 212
6.7.3 旅行售貨員問題
(難度：★★★☆☆) 213
6.7.4 Grandpa's Estate
(難度：★★★☆☆) 216
6.7.5 Find The Multiple
(難度：★★★☆☆) 218
6.8 小結 220
6.9 習題 220
第7章 圖的搜索算法 222
7.1 圖的廣度優(yōu)先搜索遍歷 224
7.1.1 算法描述與分析 224
7.1.2 程序實現(xiàn) 227
7.2 圖的深度優(yōu)先搜索遍歷 232
7.2.1 算法描述與分析 232
7.2.2 程序實現(xiàn) 234
7.2.3 有向無圈圖的拓撲排序 237
7.3 有向圖的強連通分支 244
7.3.1 算法描述與分析 244
7.3.2 程序實現(xiàn) 247
7.4 無向圖的雙連通分支 250
7.4.1 算法描述與分析 250
7.4.2 程序實現(xiàn) 254
7.5 流網絡與最大流問題 256
7.5.1 算法描述與分析 256
7.5.2 程序實現(xiàn) 263
7.6 ACM經典問題解析 265
7.6.1 Is It A Tree?
(難度：★★★☆☆) 265
7.6.2 Stockbroker Grapevine
(難度：★★★☆☆) 267
7.6.3 A Plug for UNIX
(難度：★★★☆☆) 269
7.7 小結 273
7.8 習題 273
第8章 公鑰加密算法 281
8.1 RSA公鑰密碼算法 283
8.1.1 算法描述 283
8.1.2 快速模冪算法 284
8.1.3 素數(shù)的生成 285
8.1.4 擴展歐幾里得算法 288
8.2 因子分解算法 290
8.2.1 Pollard's p-1法 290
8.2.2 Pollard's rho法 291
8.3 離散對數(shù)密碼算法 293
8.3.1 Diffie-Hellman密鑰交換
協(xié)議 293
8.3.2 ElGamal公鑰密碼算法 294
8.4 離散對數(shù)算法 295
8.4.1 小步/大步法 295
8.4.2 Pohlig-Hellman法 297
8.5 ACM的經典問題 299
8.5.1 簡單的加密算法
(難度：★★☆☆☆) 299
8.5.2 古代密碼
(難度：★★★☆☆) 300
8.6 小結 302
8.7 習題 303
第9章 P和NP問題淺析 304
9.1 決策問題和優(yōu)化問題 305
9.2 何謂P類和NP類問題 306
9.2.1 P類問題 306
9.2.2 NP類問題 307
9.3 (確定性)圖靈機 307
9.3.1 圖靈機的定義 307
9.3.2 k帶圖靈機形式化描述 308
9.3.3 圖靈機計算實例 308
9.4 非確定性圖靈機 311
9.4.1 非確定性圖靈機定義 311
9.4.2 非確定性圖靈機形式化
描述 312
9.4.3 非確定性圖靈機計算實例 312
9.4.4 非確定性算法 313
9.4.5 NP類問題的定義 314
9.4.6 NP難(NP-hard) 315
9.5 NP完全問題P* 315
9.5.1 定義 316
9.5.2 多項式時間規(guī)約 316
9.5.3 庫克定理 318
9.5.4 3-SAT問題 320
9.5.5 NP完全問題的近似算法 321
9.6 NP難問題的近似算法* 332
9.6.1 旅行商問題的近似算法 333
9.6.2 背包問題的近似算法 339
9.7 小結 342
9.8 習題 343
附錄A 求和 345
附錄B 數(shù)論入門 352
參考文獻 356
書單推薦
