《算法設計與分析：C++語言描述（第2版）》於2012年7月出版，作譯者陳慧南。這本書主要分為3部分：算法和算法分析、算法設計策略及求解困難問題，還介紹了兩種新的數據結構：跳表和伸展樹。本書結構清晰、內容翔實、邏輯嚴謹、深入淺出。
基本介紹
- 書名：算法設計與分析：C++語言描述（第2版）
- 作者：陳慧南
- 類別：C語言學習
- 原作品：卓越工程師培養計畫“十二五”規劃教材
- 譯者：陳慧南
- 出版社：電子工業出版社
- 出版時間：2012年07月
- 頁數：296 頁
- 開本：16(185*260)
- ISBN：9787121173998
- 千 字 數：524
- 版次：01-01
內容簡介,目錄信息,
內容簡介
本書為普通高等教育“十一五”國家級規劃教材。 本書內容分為3部分：算法和算法分析、算法設計策略及求解困難問題。第1部分介紹問題求解方法、算法複雜度和分析、遞歸算法和遞推關係；第2部分討論常用的算法設計策略：基本搜尋和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法；第3部分介紹NP完全問題、隨機算法、近似算法和密碼算法。書中還介紹了兩種新的數據結構：跳表和伸展樹，以及它們特定的算法分析方法，並對現代密碼學做了簡要論述。 本書結構清晰、內容翔實、邏輯嚴謹、深入淺出。書中算法有完整的C++程式，程式構思精巧，且有詳細注釋。所有程式都已在VC++環境下編譯通過並能正確運行，它們既是學習算法設計的示例，也能使複雜抽象的算法設計更易為學習者理解和掌握。書中包含大量實例和圖示，並附豐富的習題，便於自學。
目錄信息
第1部分 算法和算法分析
第1章 算法問題求解基礎 1
1.1 算法概述 1
1.1.1 什麼是算法 1
1.1.2 為什麼學習算法 3
1.2 問題求解方法 3
1.2.1 問題和問題求解 4
1.2.2 問題求解過程 4
1.2.3 系統生命周期 5
1.3 算法設計與分析 5
1.3.1 算法問題求解過程 5
1.3.2 如何設計算法 6
1.3.3 如何表示算法 6
1.3.4 如何確認算法 6
1.3.5 如何分析算法 7
1.4 遞歸和歸納 7
1.4.1 遞歸 7
1.4.2 遞歸算法示例 9
1.4.3 歸納證明 11
本章小結 12
習題1 13
第2章 算法分析基礎 14
2.1 算法複雜度 14
2.1.1 什麼是好的算法 14
2.1.2 影響程式運行時間的因素 15
2.1.3 算法的時間複雜度 16
2.1.4 使用程式步分析算法 17
2.1.5 算法的空間複雜度 18
2.2 漸近表示法 19
2.2.1 大O記號 19
2.2.2 記號 20
2.2.3 記號 21
2.2.4 小o記號 21
2.2.5 算法按時間複雜度分類 21
2.3 遞推關係 22
2.3.1 遞推方程 22
2.3.2 替換方法 23
2.3.3 疊代方法 23
2.3.4 主方法 24
2.4 分攤分析 25
2.4.1 聚集方法 26
2.4.2 會計方法 26
2.4.3 勢能方法 27
本章小結 28
習題2 28
第3章 伸展樹與跳表 30
3.1 伸展樹 30
3.1.1 二叉搜尋樹 30
3.1.2 自調節樹和伸展樹 30
3.1.3 伸展操作 31
3.1.4 伸展樹類 32
3.1.5 旋轉的實現 34
3.1.6 插入運算的實現 34
3.1.7 分攤分析 36
3.2 跳表 38
3.2.1 什麼是跳表 38
3.2.2 跳表類 39
3.2.3 級數分配 41
3.2.4 插入運算的實現 42
3.2.5 性能分析 43
本章小結 44
習題3 44
第2部分 算法設計策略
第4章 基本搜尋和遍歷方法 45
4.1 基本概念 45
4.2 圖的搜尋和遍歷 46
4.2.1 搜尋方法 46
4.2.2 鄰接表類 47
4.2.3 廣度優先搜尋 48
4.2.4 深度優先搜尋 50
4.3 雙連通分量 53
4.3.1 基本概念 53
4.3.2 發現關節點 54
4.3.3 構造雙連通圖 57
4.4 與或圖 58
4.4.1 問題分解 58
4.4.2 判斷與或樹是否可解 59
4.4.3 構建解樹 61
本章小結 62
習題4 62
第5章 分治法 64
5.1 一般方法 64
5.1.1 分治法的基本思想 64
5.1.2 算法分析 65
5.1.3 數據結構 66
5.2 求最大最小元 67
5.2.1 分治法求解 67
5.2.2 時間分析 68
5.3 二分搜尋 69
5.3.1 分治法求解 69
5.3.2 對半搜尋 70
5.3.3 二叉判定樹 71
5.3.4 搜尋算法的時間下界 73
5.4 排序問題 74
5.4.1 合併排序 74
5.4.2 快速排序 76
5.4.3 排序算法的時間下界 80
5.5 選擇問題 82
5.5.1 分治法求解 82
5.5.2 隨機選擇主元 82
5.5.3 線性時間選擇算法 84
5.5.4 時間分析 86
5.5.5 允許重複元素的選擇算法 86
5.6 斯特拉森矩陣乘法 87
5.6.1 分治法求解 87
5.6.2 斯特拉森分治法 88
本章小結 88
習題5 88
第6章 貪心法 91
6.1 一般方法 91
6.2 背包問題 92
6.2.1 問題描述 92
6.2.2 貪心法求解 92
6.2.3 算法正確性 94
6.3 帶時限的作業排序 95
6.3.1 問題描述 95
6.3.2 貪心法求解 95
6.3.3 算法正確性 97
6.3.4 可行性判定 97
6.3.5 作業排序貪心算法 98
6.3.6 一種改進算法 99
6.4 最佳合併模式 102
6.4.1 問題描述 102
6.4.2 貪心法求解 103
6.4.3 算法正確性 104
6.5 最小代價生成樹 105
6.5.1 問題描述 105
6.5.2 貪心法求解 105
6.5.3 普里姆算法 106
6.5.4 克魯斯卡爾算法 109
6.5.5 算法正確性 111
6.6 單源最短路徑 111
6.6.1 問題描述 112
6.6.2 貪心法求解 112
6.6.3 迪傑斯特拉算法 112
6.6.4 算法正確性 115
6.7 磁帶最優存儲 116
6.7.1 單帶最優存儲 116
6.7.2 多帶最優存儲 117
6.8 貪心法的基本要素 119
6.8.1 最優量度標準 119
6.8.2 最優子結構 119
本章小結 120
習題6 120
第7章 動態規劃法 122
7.1 一般方法和基本要素 122
7.1.1 一般方法 122
7.1.2 基本要素 123
7.1.3 多段圖問題 123
7.1.4 資源分配問題 126
7.1.5 關鍵路徑問題 127
7.2 每對結點間的最短路徑 129
7.2.1 問題描述 129
7.2.2 動態規劃法求解 130
7.2.3 弗洛伊德算法 131
7.2.4 算法正確性 132
7.3 矩陣連乘 132
7.3.1 問題描述 132
7.3.2 動態規劃法求解 133
7.3.3 矩陣連乘算法 134
7.3.4 備忘錄方法 136
7.4 最長公共子序列 137
7.4.1 問題描述 137
7.4.2 動態規劃法求解 137
7.4.3 最長公共子序列算法 138
7.4.4 算法的改進 140
7.5 最優二叉搜尋樹 140
7.5.1 問題描述 140
7.5.2 動態規劃法求解 141
7.5.3 最優二叉搜尋樹算法 143
7.6 0/1背包 144
7.6.1 問題描述 144
7.6.2 動態規劃法求解 145
7.6.3 0/1背包算法框架 147
7.6.4 0/1背包算法 150
7.6.5 性能分析 152
7.6.6 使用啟發式方法 153
7.7 流水作業調度 154
7.7.1 問題描述 154
7.7.2 動態規劃法求解 155
7.7.3 Johnson算法 157
本章小結 158
習題7 158
第8章 回溯法 160
8.1 一般方法 160
8.1.1 基本概念 160
8.1.2 剪枝函式和回溯法 161
8.1.3 回溯法的效率分析 163
8.2 n-皇后 163
8.2.1 問題描述 163
8.2.2 回溯法求解 164
8.2.3 n-皇后算法 165
8.2.4 時間分析 166
8.3 子集和數 167
8.3.1 問題描述 167
8.3.2 回溯法求解 167
8.3.3 子集和數算法 168
8.4 圖的著色 170
8.4.1 問題描述 170
8.4.2 回溯法求解 170
8.4.3 圖著色算法 171
8.4.4 時間分析 172
8.5 哈密頓環 172
8.5.1 問題描述 172
8.5.2 哈密頓環算法 173
8.6 0/1背包 174
8.6.1 問題描述 174
8.6.2 回溯法求解 174
8.6.3 限界函式 175
8.6.4 0/1背包算法 176
8.7 批處理作業調度 178
8.7.1 問題描述 178
8.7.2 回溯法求解 178
8.7.3 批處理作業調度算法 178
本章小結 180
習題8 180
第9章 分枝限界法 182
9.1 一般方法 182
9.1.1 分枝限界法概述 182
9.1.2 LC分枝限界法 184
9.1.3 15謎問題 185
9.2 求最優解的分枝限界法 187
9.2.1 上下界函式 187
9.2.2 FIFO分枝限界法 188
9.2.3 LC分枝限界法 189
9.3 帶時限的作業排序 190
9.3.1 問題描述 190
9.3.2 分枝限界法求解 190
9.3.3 帶時限作業排序算法 191
9.4 0/1背包 193
9.4.1 問題描述 193
9.4.2 分枝限界法求解 194
9.4.3 0/1背包算法 195
9.5 旅行商問題 197
9.5.1 問題描述 197
9.5.2 分枝限界法求解 198
9.6 批處理作業調度 201
9.6.1 問題描述 201
9.6.2 分枝限界法求解 201
9.6.3 批處理作業調度算法 202
本章小結 205
習題9 205
第3部分 求解困難問題
第10章 NP完全問題 207
10.1 基本概念 207
10.1.1 不確定算法和不確定機 208
10.1.2 可滿足性問題 210
10.1.3 P類和NP類問題 211
10.1.4 NP難度和NP完全問題 211
10.2 Cook定理和證明 212
10.2.1 Cook定理 212
10.2.2 簡化的不確定機模型 212
10.2.3 證明Cook定理 213
10.3 一些典型的NP完全問題 217
10.3.1 最大集團 217
10.3.2 頂點覆蓋 218
10.3.3 3元CNF可滿足性 219
10.3.4 圖的著色數 220
10.3.5 有向哈密頓環 221
10.3.6 恰切覆蓋 223
10.3.7 子集和數 225
10.3.8 分劃問題 225
本章小結 226
習題10 226
第11章 隨機算法 228
11.1 基本概念 228
11.1.1 隨機算法概述 228
11.1.2 隨機數發生器 228
11.1.3 隨機算法分類 228
11.2 拉斯維加斯算法 229
11.2.1 標識重複元素算法 229
11.2.2 性能分析 230
11.3 蒙特卡羅算法 231
11.3.1 素數測試問題 231
11.3.2 偽素數測試 231
11.3.3 米勒-拉賓算法 232
11.3.4 性能分析 233
11.4 舍伍德算法 234
11.4.1 隨機快速排序算法 234
11.4.2 舍伍德算法的其他套用 234
本章小結 234
習題11 235
第12章 近似算法 236
12.1 近似算法的性能 236
12.1.1 基本概念 236
12.1.2 絕對性能保證 236
12.1.3 相對性能保證 237
12.1.4 近似方案 238
12.2 絕對近似算法 238
12.2.1 最多程式存儲問題 238
12.2.2 NP難度絕對近似算法 239
12.3 -近似算法 240
12.3.1 頂點覆蓋近似算法 240
12.3.2 旅行商問題 241
12.3.3 NP難度-近似旅行商問題 242
12.3.4 具有三角不等式性質的旅行商問題 243
12.3.5 任務調度近似算法 244
12.4 (n)-近似算法 247
12.4.1 集合覆蓋問題 247
12.4.2 集合覆蓋近似算法 247
12.4.3 ln(n)-近似算法 248
12.5 多項式時間近似方案 249
12.5.1 任務調度近似方案 249
12.5.2 多項式時間近似方案 251
12.6 子集和數的完全多項式時間近似
方案 251
12.6.1 子集和數的指數時間算法 251
12.6.2 完全多項式時間近似方案 252
本章小結 254
習題12 254
第13章 密碼算法 256
13.1 信息安全和密碼學 256
13.1.1 信息安全 256
13.1.2 什麼是密碼 256
13.1.3 密碼體制 257
13.2 數論初步 258
13.3 背包密碼算法 259
13.3.1 背包算法 259
13.3.2 超遞增背包 260
13.3.3 由私人密鑰產生公開密鑰 261
13.3.4 加密方法 261
13.3.5 解密方法 261
13.3.6 背包安全性 262
13.4 RSA算法 262
13.4.1 RSA算法概述 262
13.4.2 RSA的安全性 263
13.5 散列函式和訊息認證 264
13.5.1 散列函式 264
13.5.2 散列函式結構 264
13.5.3 訊息認證 265
13.6 數字簽名 265
13.6.1 RSA數字簽名體制 265
13.6.2 需仲裁的數字簽名 266
本章小結 266
習題13 266
附錄A 專有名詞中英文對照表 267
附錄B C++程式設計概要 272
參考文獻 286
