|
-- 會員 / 註冊 --
|
|
|
|
算法基礎(第5版) ( 簡體 字) |
作者:[美] 那不勒坦 ( Richard E. Neapolitan ) | 類別:1. -> 程式設計 -> 演算法 |
譯者: |
出版社:人民郵電出版社 | 3dWoo書號: 43687 詢問書籍請說出此書號!【缺書】 NT售價: 495 元 |
出版日:3/1/2016 |
頁數:398 |
光碟數:0 |
|
站長推薦: |
印刷:黑白印刷 | 語系: ( 簡體 版 ) |
|
加入購物車 │加到我的最愛 (請先登入會員) |
ISBN:9787115416575 |
作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
(簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
作者序: |
譯者序: |
前言: |
內容簡介: 本書通過大量示例介紹了算法設計、算法的復雜度分析以及計算復雜度。主要內容有:算法設計與分析、分而治之方法、動態規劃方法、貪婪方法、回溯算法、分支定界算法、計算復雜度、難解性和NP理論、遺傳算法和遺傳編程、數論算法、并行算法等。此外,本書在每章末尾都提供了大量練習,而且還提供了全面的教輔材料及答案,是教授和學習算法設計與分析的理想教材。 |
目錄:第1 章 算法:效率、分析和階 1 1.1 算法 1 1.2 開發高效算法的重要性 5 1.2.1 順序查找與二分查找的對比 6 1.2.2 斐波那契序列 7 1.3 算法分析 10 1.3.1 復雜度分析 10 1.3.2 理論應用 14 1.3.3 正確性分析 15 1.4 階 15 1.4.1 階的直觀介紹 15 1.4.2 階數的嚴謹介紹 17 1.4.3 利用極限計算階 23 1.5 本書概要 25 1.6 習題 25 第2 章 分而治之 30 2.1 二分查找 30 2.2 合并排序 33 2.3 分而治之方法 38 2.4 快速排序(分割交換排序) 38 2.5 Strassen矩陣乘法算法 42 2.6 大整數的算術運算 46 2.6.1 大整數的表示:加法和其他線性時間運算 46 2.6.2 大整數的乘法 46 2.7 確定閾值 50 2.8 不應使用分而治之方法的情況 53 2.9 習題 53 第3 章 動態規劃 58 3.1 二項式系數 58 3.2 Floyd最短路徑算法 61 3.3 動態規劃與最優化問題 66 3.4 矩陣鏈乘法 67 3.5 最優二叉查找樹 73 3.6 旅行推銷員問題 79 3.7 序列對準 84 3.8 習題 88 第4 章 貪婪方法 92 4.1 最小生成樹 94 4.1.1 Prim算法 96 4.1.2 Kruskal算法 100 4.1.3 Prim算法與Kruskal算法的比較 103 4.1.4 最終討論 103 4.2 單源最短路徑的Dijkstra算法 104 4.3 調度計劃 106 4.3.1 使系統內總時間最短 106 4.3.2 帶有最終期限的調度安排 108 4.4 霍夫曼編碼 112 4.4.1 前綴碼 113 4.4.2 霍夫曼算法 114 4.5 貪婪方法與動態規劃的比較:背包問題 116 4.5.1 0-1背包問題的一種貪婪方法 116 4.5.2 部分背包問題的貪婪方法 118 4.5.3 0-1背包問題的動態規劃方法 118 4.5.4 0-1背包問題動態規劃算法的改進 118 4.6 習題 120 第5 章 回溯 124 5.1 回溯方法 124 5.2 n皇后問題 129 5.3 用蒙特卡洛算法估計回溯算法的效率 132 5.4 “子集之和”問題 134 5.5 圖的著色 138 5.6 哈密頓回路問題 141 5.7 0-1背包問題 143 5.7.1 0-1背包問題的回溯算法 143 5.7.2 比較0-1背包問題的動態規劃算法與回溯算法 149 5.8 習題 150 第6 章 分支定界 153 6.1 用0-1背包問題說明分支定界 154 6.1.1 帶有分支定界修剪的寬度優先查找 154 6.1.2 帶有分支定界修剪的最佳優先查找 158 6.2 旅行推銷員問題 161 6.3 溯因推理(診斷) 167 6.4 習題 173 第7 章 計算復雜度介紹:排序問題 175 7.1 計算復雜度 175 7.2 插入排序和選擇排序 176 7.3 每次比較最多減少一個倒置的算法的下限 179 7.4 再談合并排序 181 7.5 再談快速排序 185 7.6 堆排序 186 7.6.1 堆和基本堆例程 186 7.6.2 堆排序的一種實現 189 7.7 合并排序、快速排序和堆排序的比較 193 7.8 僅通過鍵的比較進行排序的下限 194 7.8.1 排序算法的決策樹 194 7.8.2 最差情況下的下限 196 7.8.3 平均情況下的下限 197 7.9 分配排序(基數排序) 200 7.10 習題 203 第8 章 再談計算復雜度:查找問題 207 8.1 僅通過鍵的比較進行查找的下限 207 8.1.1 最差表現的下限 209 8.1.2 平均情況下的下限 210 8.2 插值查找 213 8.3 樹中的查找 215 8.3.1 二叉查找樹 215 8.3.2 B樹 218 8.4 散列 219 8.5 選擇問題:對手論證 222 8.5.1 找出最大鍵 222 8.5.2 同時找出最大鍵和最小鍵 223 8.5.3 找出第二大的鍵 227 8.5.4 查找第k小的鍵 230 8.5.5 選擇問題的一種概率算法 236 8.6 習題 238 第9 章 計算復雜度和難解性:NP 理論簡介 241 9.1 難解性 241 9.2 再談輸入規模 242 9.3 三類一般問題 244 9.3.1 已經找到多項式時間算法的問題 244 9.3.2 已經證明難解的問題 245 9.3.3 未被證明是難解的,但也從來沒有找到多項式時間算法的問題 245 9.4 NP理論 245 9.4.1 集合P和NP 247 9.4.2 NP完全問題 250 9.4.3 NP困難、NP容易和NP等價問題 256 9.5 處理NP困難問題 259 9.5.1 旅行推銷員問題的近似算法 259 9.5.2 裝箱問題的近似算法 263 9.6 習題 266 第10 章 遺傳算法和遺傳編程 268 10.1 遺傳知識復習 268 10.2 遺傳算法 270 10.2.1 算法 270 10.2.2 說明范例 270 10.2.3 旅行推銷員問題 272 10.3 遺傳編程 278 10.3.1 說明范例 279 10.3.2 人造螞蟻 281 10.3.3 在金融貿易中的應用 283 10.4 討論及擴展閱讀 284 10.5 習題 284 第11 章 數論算法 286 11.1 數論回顧 286 11.1.1 合數與質數 286 11.1.2 最大公約數 286 11.1.3 質因數分解 288 11.1.4 最小公倍數 289 11.2 計算最大公約數 290 11.2.1 歐氏算法 290 11.2.2 歐氏算法的擴展 292 11.3 模運算回顧 294 11.3.1 群論 294 11.3.2 關于n同余 295 11.3.3 子群 299 11.4 模線性方程的求解 302 11.5 計算模的冪 305 11.6 尋找大質數 307 11.6.1 尋找大質數 307 11.6.2 檢查一個數字是否為質數 307 11.7 RSA公鑰密碼系統 318 11.7.1 公鑰加密系統 318 11.7.2 RSA加密系統 319 11.8 習題 321 第12 章 并行算法簡介 324 12.1 并行體系結構 325 12.1.1 控制機制 326 12.1.2 地址空間的組織 326 12.1.3 互聯網絡 328 12.2 PRAM模型 330 12.2.1 為CREW PRAM模型設計算法 332 12.2.2 為CRCW PRAM模型設計算法 337 12.3 習題 339 附錄A 必備數學知識回顧 340 附錄B 求解遞歸方程:在遞歸算法分析 中的應用 363 附錄C 不交集的數據結構 388 參考文獻 395 |
序: |
|