定 價：49 元
叢書名：算法設(shè)計、分析與應(yīng)用教程
- 作者：李文書，何利力
- 出版時間：2014/8/1
- ISBN：9787301243527
- 出 版 社：北京大學(xué)出版社
- 中圖法分類：TP301.6
- 頁碼：376
- 紙張：膠版紙
- 版次：1
- 開本：16K
《算法設(shè)計、分析與應(yīng)用教程》通過設(shè)計、分析ACM庫的經(jīng)典問題，把理論與實踐結(jié)合。各章遵循從一個例子或故事中引出本章知識點，簡述相關(guān)理論，分析經(jīng)典問題及算法實現(xiàn)。主要包括算法概述、遞歸與分治策略、動態(tài)規(guī)劃、貪心算法、回溯算法、分支限界算法、圖的搜索算法、加密算法與安全機(jī)制、P和NP問題等內(nèi)容。有故事、有理論、有公式、有實踐。所有算法實現(xiàn)結(jié)果都經(jīng)參加ACM的隊員驗證。本書適合高樣計算機(jī)專業(yè)以及相關(guān)專業(yè)做為教材使用，也可供編程愛好者參考使用。
《算法設(shè)計、分析與應(yīng)用教程》適合高樣計算機(jī)專業(yè)以及相關(guān)專業(yè)做為教材使用，也可供編程愛好者參考使用。
李文書，教授，工學(xué)博士，現(xiàn)任浙江理工大學(xué)信息學(xué)院，智能檢測與系統(tǒng)實驗室主任，碩士生導(dǎo)師。IEEE (1-1163129461)、中國計算機(jī)學(xué)會（E200016385M）會員和杭州市計算機(jī)學(xué)會會員；151第三層次培養(yǎng)人才。
第1章 算法概述 1
1.1 引言 1
1.1.1 算法的描述 2
1.1.2 算法的特性 2
1.1.3 為什么學(xué)習(xí)算法 3
1.2 算法的設(shè)計 5
1.3 算法的分析 8
1.3.1 正確性分析 9
1.3.2 時空效率分析 10
1.3.3 時空特性分析 13
1.4 解決問題的一般步驟 13
1.5 小結(jié) 15
1.6 習(xí)題 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 二分搜索技術(shù) 29
2.2.4 棋盤覆蓋問題 30
2.2.5 快速排序 33
2.2.6 大整數(shù)乘法 36
2.2.7 矩陣乘法 39
2.3 ACM經(jīng)典問題解析 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 小結(jié) 58
2.5 習(xí)題 59
第3章 動態(tài)規(guī)劃 62
3.1 何謂動態(tài)規(guī)劃 63
3.1.1 動態(tài)規(guī)劃的基本思想 63
3.1.2 設(shè)計動態(tài)規(guī)劃法的步驟 63
3.1.3 動態(tài)規(guī)劃問題的特征 63
3.1.4 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系 64
3.2 矩陣連乘積問題 65
3.2.1 分析最優(yōu)解的結(jié)構(gòu) 67
3.2.2 建立遞歸關(guān)系 68
3.2.3 計算最優(yōu)值 69
3.2.4 構(gòu)造最優(yōu)解 71
3.3 動態(tài)規(guī)劃算法的基本要素 72
3.3.1 最優(yōu)子結(jié)構(gòu) 72
3.3.2 重疊子問題 72
3.3.3 備忘錄方法 73
3.4 最長公共子序列 75
3.4.1 最長公共子序列的結(jié)構(gòu) 75
3.4.2 子問題的遞歸結(jié)構(gòu) 76
3.4.3 計算最優(yōu)值 76
3.4.4 構(gòu)造最長公共子序列 78
3.5 最大子段和 78
3.5.1 遞歸關(guān)系分析 78
3.5.2 算法實現(xiàn) 79
3.6 0-1背包問題 80
3.6.1 遞歸關(guān)系分析 81
3.6.2 算法實現(xiàn) 81
3.7 ACM經(jīng)典問題解析 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 小結(jié) 96
3.9 習(xí)題 97
第4章 貪心算法 101
4.1 活動安排問題 102
4.2 貪心算法的理論基礎(chǔ) 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)子結(jié)構(gòu) 107
4.3.3 算法實現(xiàn) 107
4.3.4 復(fù)雜度分析 108
4.4 背包問題 109
4.4.1 最優(yōu)子結(jié)構(gòu)性質(zhì) 109
4.4.2 貪心選擇性質(zhì) 110
4.4.3 算法實現(xiàn) 110
4.4.4 復(fù)雜度分析 112
4.5 最優(yōu)裝載問題 112
4.5.1 貪心選擇性質(zhì) 113
4.5.2 最優(yōu)子結(jié)構(gòu)性質(zhì) 113
4.5.3 算法實現(xiàn) 113
4.5.4 復(fù)雜度分析 114
4.6 單源最短路徑 115
4.6.1 算法基本思想 115
4.6.2 貪心選擇性質(zhì) 116
4.6.3 最優(yōu)子結(jié)構(gòu)性質(zhì) 117
4.6.4 Dijkstra算法實現(xiàn) 117
4.6.5 復(fù)雜度分析 119
4.7 多處最優(yōu)服務(wù)次序問題 120
4.7.1 貪心選擇策略 120
4.7.2 貪心選擇性質(zhì) 120
4.7.3 最優(yōu)子結(jié)構(gòu)性質(zhì) 120
4.7.4 算法實現(xiàn) 121
4.7.5 復(fù)雜度分析 122
4.8 ACM經(jīng)典問題解析 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 小結(jié) 137
4.10 習(xí)題 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 算法時間復(fù)雜度分析 150
5.3 n皇后問題 150
5.3.1 解空間 151
5.3.2 約束條件 151
5.3.3 搜索過程 151
5.3.4 算法的時間復(fù)雜度分析 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 時間復(fù)雜度分析 163
5.7 批處理流水作業(yè)調(diào)度問題 163
5.7.1 解空間 163
5.7.2 約束條件 164
5.7.3 限界條件 164
5.7.4 搜索過程 164
5.7.5 時間復(fù)雜度分析 166
5.8 ACM經(jīng)典問題解析 166
5.8.1 Dreisam Equations
(難度：★★★☆☆) 166
5.8.2 A Plug for UNIX
(難度：★★★☆☆) 170
5.8.3 回文構(gòu)詞檢測(Anagram Checker)
(難度：★★☆☆☆) 174
5.8.4 Unshuffle
(難度：★★★☆☆) 178
5.9 小結(jié) 181
5.10 習(xí)題 181
第6章 分支限界算法 183
6.1 分支限界法的基本理論 184
6.1.1 分支限界法的搜索策略 184
6.1.2 分支結(jié)點的選擇 185
6.1.3 限界函數(shù) 185
6.2 單源最短路徑問題 186
6.2.1 問題描述 186
6.2.2 算法描述與設(shè)計 186
6.2.3 算法實現(xiàn) 188
6.3 裝載問題 190
6.3.1 問題描述 190
6.3.2 算法設(shè)計與實現(xiàn) 191
6.4 0-1背包問題 196
6.4.1 問題描述 196
6.4.2 算法描述與設(shè)計 196
6.4.3 算法實現(xiàn) 198
6.5 旅行商問題 202
6.5.1 問題描述 202
6.5.2 算法描述與設(shè)計 203
6.5.3 算法實現(xiàn) 204
6.7 ACM經(jīng)典問題 209
6.7.1 布線問題
(難度：★★★☆☆) 209
6.7.2 方格調(diào)整問題
(難度：★★★☆☆) 212
6.7.3 旅行售貨員問題
(難度：★★★☆☆) 213
6.7.4 Grandpa's Estate
(難度：★★★☆☆) 216
6.7.5 Find The Multiple
(難度：★★★☆☆) 218
6.8 小結(jié) 220
6.9 習(xí)題 220
第7章 圖的搜索算法 222
7.1 圖的廣度優(yōu)先搜索遍歷 224
7.1.1 算法描述與分析 224
7.1.2 程序?qū)崿F(xiàn) 227
7.2 圖的深度優(yōu)先搜索遍歷 232
7.2.1 算法描述與分析 232
7.2.2 程序?qū)崿F(xiàn) 234
7.2.3 有向無圈圖的拓?fù)渑判?237
7.3 有向圖的強(qiáng)連通分支 244
7.3.1 算法描述與分析 244
7.3.2 程序?qū)崿F(xiàn) 247
7.4 無向圖的雙連通分支 250
7.4.1 算法描述與分析 250
7.4.2 程序?qū)崿F(xiàn) 254
7.5 流網(wǎng)絡(luò)與最大流問題 256
7.5.1 算法描述與分析 256
7.5.2 程序?qū)崿F(xiàn) 263
7.6 ACM經(jīng)典問題解析 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 小結(jié) 273
7.8 習(xí)題 273
第8章 公鑰加密算法 281
8.1 RSA公鑰密碼算法 283
8.1.1 算法描述 283
8.1.2 快速模冪算法 284
8.1.3 素數(shù)的生成 285
8.1.4 擴(kuò)展歐幾里得算法 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的經(jīng)典問題 299
8.5.1 簡單的加密算法
(難度：★★☆☆☆) 299
8.5.2 古代密碼
(難度：★★★☆☆) 300
8.6 小結(jié) 302
8.7 習(xí)題 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 (確定性)圖靈機(jī) 307
9.3.1 圖靈機(jī)的定義 307
9.3.2 k帶圖靈機(jī)形式化描述 308
9.3.3 圖靈機(jī)計算實例 308
9.4 非確定性圖靈機(jī) 311
9.4.1 非確定性圖靈機(jī)定義 311
9.4.2 非確定性圖靈機(jī)形式化
描述 312
9.4.3 非確定性圖靈機(jī)計算實例 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 小結(jié) 342
9.8 習(xí)題 343
附錄A 求和 345
附錄B 數(shù)論入門 352
參考文獻(xiàn) 356
書單推薦
