算法設計與分析——C++語言描述(第3版) ( 簡體 字) |
作者:陳慧南 | 類別:1. -> 程式設計 -> 演算法 |
譯者: |
出版社:電子工業出版社 | 3dWoo書號: 48208 詢問書籍請說出此書號!【缺書】 NT售價: 245 元 |
出版日:1/1/2018 |
頁數:316 |
光碟數:0 |
|
站長推薦: |
印刷:黑白印刷 | 語系: ( 簡體 版 ) |
|
加入購物車 │加到我的最愛 (請先登入會員) |
ISBN:9787121330544 |
作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
(簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
作者序: |
譯者序: |
前言:再 版 前 言 《算法設計與分析》一書自2006年出版以來,深受讀者歡迎,在此表示衷心感謝。本教材是為高等學校計算機和其他相關專業本科高年級和研究生的“算法設計與分析”課程編寫的。此次再版,增加了“遺傳算法”一章,而將原第13章密碼算法改為第14章。 這是因為,遺傳算法的應用領域越來越廣泛,目前,遺傳算法的應用范圍已包括組合最優化、圖像處理、模式識別、智能控制、神經網絡、自動程序設計、機器學習、數據挖掘、人工生命和網絡通信等許多領域。對于計算機專業的學生和計算機相關從業者而言,遺傳算法應該成為必備知識,因而不一定要在學習人工智能相關課程時,才去了解此類算法。作為一種求解函數最優化和組合最優化的十分有用和有效算法,將其引入傳統的“算法設計與分析”課程與其他算法知識一起討論,非常自然且很有必要。 隨著遺傳算法的深入研究以及與其他學科的相互融合,遺傳算法有望在智能領域占有更加重要地位。作為進化計算的主要分支,作者希望新增的遺傳算法知識能滿足計算機專業學生和計算機相關從業者了解遺傳算法,并進一步學習進化計算的需要。 作者對第13章的編寫保持了本書一貫的風格,對遺傳算法中涉及的方法,書中同樣給出了C++程序,程序代碼都有詳細注釋,已在VC++環境下編譯通過并能正確運行。 作 者 |
內容簡介:本書為普通高等教育“十一五”國家級規劃教材。 本書內容分為3部分:算法和算法分析、算法設計策略、求解困難問題。第1部分介紹問題求解方法、算法復雜度和分析、遞歸算法和遞推關系;第2部分討論常用的算法設計策略:基本搜索和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法;第3部分介紹NP完全問題、隨機算法、近似算法、遺傳算法和密碼算法,其中遺傳算法是本次修訂新增的內容。書中還介紹了兩種新的數據結構:跳表和伸展樹,以及它們特定的算法分析方法,并對現代密碼學做了簡要論述。 |
目錄:第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定理 214 10.3 一些典型的NP完全問題 217 10.3.1 最大集團 217 10.3.2 頂點覆蓋 218 10.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.2 遺傳算法的生物學基礎 257 13.3 遺傳算法的基本思想 258 13.4 基本遺傳算法 259 13.4.1 基本遺傳算法構成要素 259 13.4.2 基本遺傳算法流程圖 262 13.5 遺傳算法的特點和應用 262 13.5.1 遺傳算法的特點 262 13.5.2 遺傳算法的應用 263 13.6 基本遺傳算法實現方法 263 13.6.1 數據結構 263 13.6.2 主程序 264 13.6.3 選擇運算 264 13.6.4 交叉運算 266 13.6.5 變異運算 267 13.7 旅行商問題 268 13.7.1 排列編碼 268 13.7.2 目標函數和適應度函數 269 13.7.3 錦標賽選擇 269 13.7.4 順序交叉 269 13.7.5 交換變異 271 13.7.6 參數選擇 272 13.7.7 實例運行結果 272 本章小結 272 習題13 272 第14章 密碼算法 274 14.1 信息安全和密碼學 274 14.1.1 信息安全 274 14.1.2 什么是密碼 274 14.1.3 密碼體制 275 14.2 數論初步 276 14.3 背包密碼算法 277 14.3.1 背包算法 277 14.3.2 超遞增背包 278 14.3.3 由私人密鑰產生公開密鑰 279 14.3.4 加密方法 279 14.3.5 解密方法 279 14.3.6 背包安全性 280 14.4 RSA算法 280 14.4.1 RSA算法概述 280 14.4.2 RSA的安全性 281 14.5 散列函數和消息認證 282 14.5.1 散列函數 282 14.5.2 散列函數結構 282 14.5.3 消息認證 283 14.6 數字簽名 283 14.6.1 RSA數字簽名體制 283 14.6.2 需仲裁的數字簽名 284 本章小結 284 習題14 284 附錄A 專有名詞中英文對照表 285 附錄B C++程序設計概要 290 參考文獻 304 |
序: |