算法設(shè)計(jì)、分析與應(yīng)用教程
定 價(jià)：49 元
叢書名：算法設(shè)計(jì)、分析與應(yīng)用教程
當(dāng)前圖書已被 2 所學(xué)校薦購(gòu)過(guò)！
查看明細(xì)
- 作者：李文書，何利力
- 出版時(shí)間：2014/8/1
- ISBN：9787301243527
- 出 版 社：北京大學(xué)出版社
- 中圖法分類：TP301.6
- 頁(yè)碼：376
- 紙張：膠版紙
- 版次：1
- 開本：16K
《算法設(shè)計(jì)、分析與應(yīng)用教程》通過(guò)設(shè)計(jì)、分析ACM庫(kù)的經(jīng)典問(wèn)題，把理論與實(shí)踐結(jié)合。各章遵循從一個(gè)例子或故事中引出本章知識(shí)點(diǎn)，簡(jiǎn)述相關(guān)理論，分析經(jīng)典問(wèn)題及算法實(shí)現(xiàn)。主要包括算法概述、遞歸與分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯算法、分支限界算法、圖的搜索算法、加密算法與安全機(jī)制、P和NP問(wèn)題等內(nèi)容。有故事、有理論、有公式、有實(shí)踐。所有算法實(shí)現(xiàn)結(jié)果都經(jīng)參加ACM的隊(duì)員驗(yàn)證。本書適合高樣計(jì)算機(jī)專業(yè)以及相關(guān)專業(yè)做為教材使用，也可供編程愛好者參考使用。
《算法設(shè)計(jì)、分析與應(yīng)用教程》適合高樣計(jì)算機(jī)專業(yè)以及相關(guān)專業(yè)做為教材使用，也可供編程愛好者參考使用。
李文書，教授，工學(xué)博士，現(xiàn)任浙江理工大學(xué)信息學(xué)院，智能檢測(cè)與系統(tǒng)實(shí)驗(yàn)室主任，碩士生導(dǎo)師。IEEE (1-1163129461)、中國(guó)計(jì)算機(jī)學(xué)會(huì)（E200016385M）會(huì)員和杭州市計(jì)算機(jī)學(xué)會(huì)會(huì)員；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è)計(jì) 5
1.3 算法的分析 8
1.3.1 正確性分析 9
1.3.2 時(shí)空效率分析 10
1.3.3 時(shí)空特性分析 13
1.4 解決問(wèn)題的一般步驟 13
1.5 小結(jié) 15
1.6 習(xí)題 16
第2章 遞歸與分治策略 17
2.1 遞歸算法 18
2.1.1 遞歸的概念 18
2.1.2 具有遞歸特性的問(wèn)題 19
2.1.3 遞歸算法分析 22
2.2 分治策略 28
2.2.1 分治法的基本步驟 28
2.2.2 分治法的適用條件 29
2.2.3 二分搜索技術(shù) 29
2.2.4 棋盤覆蓋問(wèn)題 30
2.2.5 快速排序 33
2.2.6 大整數(shù)乘法 36
2.2.7 矩陣乘法 39
2.3 ACM經(jīng)典問(wèn)題解析 45
2.3.1 蜂窩問(wèn)題
(難度：★☆☆☆☆) 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章 動(dòng)態(tài)規(guī)劃 62
3.1 何謂動(dòng)態(tài)規(guī)劃 63
3.1.1 動(dòng)態(tài)規(guī)劃的基本思想 63
3.1.2 設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟 63
3.1.3 動(dòng)態(tài)規(guī)劃問(wèn)題的特征 63
3.1.4 動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系 64
3.2 矩陣連乘積問(wèn)題 65
3.2.1 分析最優(yōu)解的結(jié)構(gòu) 67
3.2.2 建立遞歸關(guān)系 68
3.2.3 計(jì)算最優(yōu)值 69
3.2.4 構(gòu)造最優(yōu)解 71
3.3 動(dòng)態(tài)規(guī)劃算法的基本要素 72
3.3.1 最優(yōu)子結(jié)構(gòu) 72
3.3.2 重疊子問(wèn)題 72
3.3.3 備忘錄方法 73
3.4 最長(zhǎng)公共子序列 75
3.4.1 最長(zhǎng)公共子序列的結(jié)構(gòu) 75
3.4.2 子問(wèn)題的遞歸結(jié)構(gòu) 76
3.4.3 計(jì)算最優(yōu)值 76
3.4.4 構(gòu)造最長(zhǎng)公共子序列 78
3.5 最大子段和 78
3.5.1 遞歸關(guān)系分析 78
3.5.2 算法實(shí)現(xiàn) 79
3.6 0-1背包問(wèn)題 80
3.6.1 遞歸關(guān)系分析 81
3.6.2 算法實(shí)現(xiàn) 81
3.7 ACM經(jīng)典問(wèn)題解析 83
3.7.1 數(shù)塔(難度：★★☆☆☆) 83
3.7.2 免費(fèi)餡餅
(難度：★★★☆☆) 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 活動(dòng)安排問(wèn)題 102
4.2 貪心算法的理論基礎(chǔ) 104
4.2.1 貪心算法的基本思想 105
4.2.2 貪心算法的基本要素 105
4.2.3 貪心算法的基本步驟 106
4.3 刪數(shù)問(wèn)題 107
4.3.1 貪心策略選擇 107
4.3.2 最優(yōu)子結(jié)構(gòu) 107
4.3.3 算法實(shí)現(xiàn) 107
4.3.4 復(fù)雜度分析 108
4.4 背包問(wèn)題 109
4.4.1 最優(yōu)子結(jié)構(gòu)性質(zhì) 109
4.4.2 貪心選擇性質(zhì) 110
4.4.3 算法實(shí)現(xiàn) 110
4.4.4 復(fù)雜度分析 112
4.5 最優(yōu)裝載問(wèn)題 112
4.5.1 貪心選擇性質(zhì) 113
4.5.2 最優(yōu)子結(jié)構(gòu)性質(zhì) 113
4.5.3 算法實(shí)現(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算法實(shí)現(xiàn) 117
4.6.5 復(fù)雜度分析 119
4.7 多處最優(yōu)服務(wù)次序問(wèn)題 120
4.7.1 貪心選擇策略 120
4.7.2 貪心選擇性質(zhì) 120
4.7.3 最優(yōu)子結(jié)構(gòu)性質(zhì) 120
4.7.4 算法實(shí)現(xiàn) 121
4.7.5 復(fù)雜度分析 122
4.8 ACM經(jīng)典問(wèn)題解析 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 釣魚問(wèn)題
(難度：★★★★☆) 130
4.8.7 樹形DP問(wèn)題
(難度：★★★★☆) 133
4.8.8 Frogs' Neighborhood
(難度：★★★☆☆) 135
4.9 小結(jié) 137
4.10 習(xí)題 138
第5章 回溯法 140
5.1 回溯法的基本思想 140
5.1.1 問(wèn)題的解空間 141
5.1.2 搜索的解空間 143
5.1.3 回溯的基本步驟 144
5.1.4 回溯法實(shí)現(xiàn) 145
5.2 圖的m著色問(wèn)題 147
5.2.1 問(wèn)題的解空間 147
5.2.2 確定約束條件 148
5.2.3 搜索解空間 148
5.2.4 代碼實(shí)現(xiàn) 148
5.2.5 算法時(shí)間復(fù)雜度分析 150
5.3 n皇后問(wèn)題 150
5.3.1 解空間 151
5.3.2 約束條件 151
5.3.3 搜索過(guò)程 151
5.3.4 算法的時(shí)間復(fù)雜度分析 154
5.4 裝載問(wèn)題 154
5.4.1 問(wèn)題的解空間 154
5.4.2 約束條件 154
5.4.3 限界條件 154
5.4.4 搜索過(guò)程 155
5.4.5 算法效率分析 157
5.5 0-1背包問(wèn)題 157
5.5.1 解空間 157
5.5.2 約束條件 157
5.5.3 限界條件 157
5.5.4 搜索過(guò)程 158
5.5.5 算法效率分析 160
5.6 旅行商問(wèn)題 160
5.6.1 解空間 161
5.6.2 約束條件 161
5.6.3 限界條件 161
5.6.4 搜索解空間 161
5.6.5 時(shí)間復(fù)雜度分析 163
5.7 批處理流水作業(yè)調(diào)度問(wèn)題 163
5.7.1 解空間 163
5.7.2 約束條件 164
5.7.3 限界條件 164
5.7.4 搜索過(guò)程 164
5.7.5 時(shí)間復(fù)雜度分析 166
5.8 ACM經(jīng)典問(wèn)題解析 166
5.8.1 Dreisam Equations
(難度：★★★☆☆) 166
5.8.2 A Plug for UNIX
(難度：★★★☆☆) 170
5.8.3 回文構(gòu)詞檢測(cè)(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é)點(diǎn)的選擇 185
6.1.3 限界函數(shù) 185
6.2 單源最短路徑問(wèn)題 186
6.2.1 問(wèn)題描述 186
6.2.2 算法描述與設(shè)計(jì) 186
6.2.3 算法實(shí)現(xiàn) 188
6.3 裝載問(wèn)題 190
6.3.1 問(wèn)題描述 190
6.3.2 算法設(shè)計(jì)與實(shí)現(xiàn) 191
6.4 0-1背包問(wèn)題 196
6.4.1 問(wèn)題描述 196
6.4.2 算法描述與設(shè)計(jì) 196
6.4.3 算法實(shí)現(xiàn) 198
6.5 旅行商問(wèn)題 202
6.5.1 問(wèn)題描述 202
6.5.2 算法描述與設(shè)計(jì) 203
6.5.3 算法實(shí)現(xiàn) 204
6.7 ACM經(jīng)典問(wèn)題 209
6.7.1 布線問(wèn)題
(難度：★★★☆☆) 209
6.7.2 方格調(diào)整問(wèn)題
(難度：★★★☆☆) 212
6.7.3 旅行售貨員問(wèn)題
(難度：★★★☆☆) 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 有向無(wú)圈圖的拓?fù)渑判?237
7.3 有向圖的強(qiáng)連通分支 244
7.3.1 算法描述與分析 244
7.3.2 程序?qū)崿F(xiàn) 247
7.4 無(wú)向圖的雙連通分支 250
7.4.1 算法描述與分析 250
7.4.2 程序?qū)崿F(xiàn) 254
7.5 流網(wǎng)絡(luò)與最大流問(wèn)題 256
7.5.1 算法描述與分析 256
7.5.2 程序?qū)崿F(xiàn) 263
7.6 ACM經(jīng)典問(wèn)題解析 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 素?cái)?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 離散對(duì)數(shù)密碼算法 293
8.3.1 Diffie-Hellman密鑰交換
協(xié)議 293
8.3.2 ElGamal公鑰密碼算法 294
8.4 離散對(duì)數(shù)算法 295
8.4.1 小步/大步法 295
8.4.2 Pohlig-Hellman法 297
8.5 ACM的經(jīng)典問(wèn)題 299
8.5.1 簡(jiǎn)單的加密算法
(難度：★★☆☆☆) 299
8.5.2 古代密碼
(難度：★★★☆☆) 300
8.6 小結(jié) 302
8.7 習(xí)題 303
第9章 P和NP問(wèn)題淺析 304
9.1 決策問(wèn)題和優(yōu)化問(wèn)題 305
9.2 何謂P類和NP類問(wèn)題 306
9.2.1 P類問(wèn)題 306
9.2.2 NP類問(wèn)題 307
9.3 (確定性)圖靈機(jī) 307
9.3.1 圖靈機(jī)的定義 307
9.3.2 k帶圖靈機(jī)形式化描述 308
9.3.3 圖靈機(jī)計(jì)算實(shí)例 308
9.4 非確定性圖靈機(jī) 311
9.4.1 非確定性圖靈機(jī)定義 311
9.4.2 非確定性圖靈機(jī)形式化
描述 312
9.4.3 非確定性圖靈機(jī)計(jì)算實(shí)例 312
9.4.4 非確定性算法 313
9.4.5 NP類問(wèn)題的定義 314
9.4.6 NP難(NP-hard) 315
9.5 NP完全問(wèn)題P* 315
9.5.1 定義 316
9.5.2 多項(xiàng)式時(shí)間規(guī)約 316
9.5.3 庫(kù)克定理 318
9.5.4 3-SAT問(wèn)題 320
9.5.5 NP完全問(wèn)題的近似算法 321
9.6 NP難問(wèn)題的近似算法* 332
9.6.1 旅行商問(wèn)題的近似算法 333
9.6.2 背包問(wèn)題的近似算法 339
9.7 小結(jié) 342
9.8 習(xí)題 343
附錄A 求和 345
附錄B 數(shù)論入門 352
參考文獻(xiàn) 356
書單推薦
