|
關(guān)于我們
 書單推薦 新書推薦 |
算法設(shè)計與分析 ——基于計算教學(xué)論的解析 
定 價：89 元
9 7 4 8 4 7 0 1 5 2 1 1 9 讀者對象:本書可用作高等學(xué)校計算機專業(yè)本科生的教材，也可作為計算機及相關(guān)專業(yè)研究生和科研、工程或技術(shù)人員自學(xué)算法的參考書。 
本教材是基于作者所創(chuàng)立的計算教學(xué)論編寫的，是為實現(xiàn)教學(xué)效率顯著提升而對計算教學(xué)論提出的思想、 方法和工具的深廣應(yīng)用。 本教材共 12 章。第 1 章由 Euclid GCD 算法引出算法的定義，并介紹基于可視化的算法學(xué)習(xí)方法，第 2～5 章分別介紹算法的窮舉設(shè)計方法、算法復(fù)雜度分析、算法的遞歸設(shè)計方法和基于比較的排序算法，第 6～10 章 分別介紹分治、動態(tài)規(guī)劃、貪心、回溯和分支限界等經(jīng)典的算法設(shè)計方法，第 11 章介紹 RSA 算法，第 12 章介 紹 NP 理論。 本教材可作為高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)算法設(shè)計與分析課程的教材，也可作為計算機及相關(guān)專業(yè)研 究生和科研、工程或技術(shù)人員自學(xué)算法設(shè)計與分析的參考書。
段會川 教授，長期致力于以計算改進(jìn)教和學(xué)的效率，并創(chuàng)立了計算教學(xué)論學(xué)說。該學(xué)說以計算的本質(zhì)能力即算法化的知識表達(dá)和解析改進(jìn)教與學(xué)的效率，在《算法設(shè)計與分析》和《計算機網(wǎng)絡(luò)原理》課程中取得了很好的效果。
目 錄
第 1 章 算法及其可視化教學(xué)支持系統(tǒng) ............ 1 初識算法：Euclid GCD 算法 .............. 1 1.1.1 GCD 及因子分解方法 .............. 1 1.1.2 Euclid GCD 算法 ....................... 3 算法的定義 .......................................... 3 1.2.1 算法是一種求解問題的 科學(xué)方法 ................................... 4 1.2.2 算法的克努特定義.................... 5 1.2.3 算法的圖靈機定義.................... 6 算法的描述方法 .................................. 8 1.3.1 算法的自然語言描述方法 ........ 8 1.3.2 算法的流程圖描述方法 ............ 8 1.3.3 算法的偽代碼描述方法 ............ 9 1.3.4 算法的現(xiàn)代版 C++描述方法 ... 10 1.3.5 設(shè)計算法求解問題的 基本過程 ................................. 10 可視化算法學(xué)習(xí)的支持工具............. 12 1.4.1 CAAIS 的基本界面及其 功能 ......................................... 12 1.4.2 算法 CD-AV 演示的基本 操作 ......................................... 13 使用現(xiàn)代版 C++進(jìn)行算法實驗 ........ 15 1.5.1 現(xiàn)代版 C++的算法實驗 環(huán)境建議 ................................. 15 1.5.2 算法的現(xiàn)代版 C++實現(xiàn) 方式——以 Euclid GCD 算法為例 ................................. 16 算法國粹——《九章算術(shù)》中的 二進(jìn)制 GCD 算法 .............................. 17 1.6.1 《九章算術(shù)》中的更相減 損術(shù)——最早的二進(jìn)制 GCD 算法 ................................ 17 1.6.2 現(xiàn)代版的二進(jìn)制 GCD 算法 .... 18 習(xí)題 ............................................................ 19 參考文獻(xiàn) ..................................................... 20 第 2 章 算法的窮舉設(shè)計方法 .......................... 22 窮舉算法設(shè)計基礎(chǔ) ............................ 22 窮舉算法設(shè)計示例 ............................ 23 2.2.1 百錢買百雞問題算法設(shè)計 ..... 23 2.2.2 素性測試的試除算法設(shè)計 ..... 26 2.2.3 順序搜索算法設(shè)計及 CD-AV 演示 ......................................... 28 2.2.4 洗牌算法設(shè)計及 CD-AV 演示 29 偽隨機數(shù)發(fā)生器及其在算法實驗 中的應(yīng)用 ............................................ 31 2.3.1 生成偽隨機數(shù)的線性同余法 ... 31 2.3.2 傳統(tǒng) C 語言標(biāo)準(zhǔn)庫中的 偽隨機函數(shù)及其應(yīng)用 ............. 32 2.3.3 現(xiàn)代版 C++標(biāo)準(zhǔn)庫中的 偽隨機函數(shù)及其應(yīng)用 ............. 33 2.4 算法國粹——圖靈獎獲得者姚期智 院士的偽隨機數(shù)理論 ........................ 34 2.4.1 姚期智院士密碼學(xué)安全的 偽隨機數(shù)理論 ......................... 35 2.4.2 LCG 不是密碼學(xué)安全的 ........ 35 2.4.3 Java JDK 提供的密碼學(xué) 安全的偽隨機數(shù)發(fā)生器 ......... 37 習(xí)題 ........................................................... 39 參考文獻(xiàn) ..................................................... 40 第 3 章 算法復(fù)雜度分析 .................................. 42 算法復(fù)雜度分析基礎(chǔ) ........................ 42 3.1.1 算法的輸入規(guī)模及復(fù)雜度 計量 ......................................... 42 3.1.2 算法的最好、最壞和平均 情況復(fù)雜度 ............................. 43 算法復(fù)雜度的漸近分析方法 ............ 45 3.2.1 算法的漸近復(fù)雜度及其記法 . 46 3.2.2 常見的算法復(fù)雜度階及其 關(guān)系 ......................................... 51 算法設(shè)計與分析——基于計算教學(xué)論的解析 - VIII - 3.2.3 算法復(fù)雜度漸近分析的 基本范型 ................................. 53 大整數(shù)算術(shù)運算的復(fù)雜度 ................ 55 3.3.1 二進(jìn)制數(shù)的豎式算術(shù)運算的 復(fù)雜度 ..................................... 55 3.3.2 大整數(shù)的多精度表示 .............. 57 3.3.3 多精度整數(shù)算術(shù)運算的 復(fù)雜度 ..................................... 57 Euclid GCD 算法的復(fù)雜度分析 ........ 59 3.4.1 Fibonacci 數(shù)列及其通項的 閉式解 ..................................... 59 3.4.2 Euclid GCD 算法復(fù)雜度的 詳細(xì)分析 ................................. 62 算法復(fù)雜度的平攤分析方法............. 64 3.5.1 平攤分析方法概述.................. 64 3.5.2 Fibonacci 堆的基本操作及其 復(fù)雜度的平攤分析.................. 66 算法復(fù)雜度的實驗分析法 ................ 70 3.6.1 算法復(fù)雜度實驗分析的 必要性和基本過程.................. 70 3.6.2 算法復(fù)雜度的實驗分析法 示例 ......................................... 72 問題的復(fù)雜度 .................................... 73 3.7.1 問題的復(fù)雜度概述.................. 73 3.7.2 基于比較的排序問題的 復(fù)雜度 ..................................... 74 算法國粹——姚期智院士的通信 復(fù)雜性理論 ........................................ 76 3.8.1 通信復(fù)雜性的問題定義 .......... 76 3.8.2 通信復(fù)雜性理論的基本成果.... 77 習(xí)題 ............................................................ 80 參考文獻(xiàn) ..................................................... 81 第 4 章 算法的遞歸設(shè)計方法 .......................... 84 遞歸算法的普適性及其理論內(nèi)涵 ..... 84 4.1.1 遞歸算法的基本特性及實例 .... 84 4.1.2 遞歸是一種普適的算法表達(dá) 方法 ......................................... 86 子集遍歷問題的遞歸窮舉算法 ......... 88 4.2.1 子集遍歷問題及其遞歸窮舉 算法設(shè)計 ................................. 88 4.2.2 現(xiàn)代版 C++實現(xiàn)與 CD-AV 演示設(shè)計 ................................. 90 全排列遍歷問題的遞歸窮舉算法 .... 93 4.3.1 全排列遍歷問題及其遞歸 窮舉算法設(shè)計 ......................... 93 4.3.2 現(xiàn)代版 C++實現(xiàn)與 CD-AV 演示設(shè)計 ................................. 96 0-1 背包問題及其遞歸窮舉算法 ...... 98 4.4.1 0-1 背包問題的定義及 解空間分析 ............................. 99 4.4.2 0-1 背包問題的遞歸窮舉 算法 ....................................... 100 TSP 問題及其遞歸窮舉算法 .......... 101 4.5.1 TSP 問題的定義及解空間 分析 ....................................... 101 4.5.2 TSP 問題的遞歸窮舉算法 ... 103 �？蚣芗皩⑦f歸算法轉(zhuǎn)換為迭代 算法的方法 ...................................... 105 4.6.1 函數(shù)調(diào)用的�？蚣� ............... 105 4.6.2 將遞歸算法轉(zhuǎn)換為迭代 算法的方法 ........................... 107 算法國粹——管梅谷教授的 中國郵遞員問題 ............................... 111 4.7.1 CPP 與歐拉回路 .................... 111 4.7.2 CPP 的求解思路與算法 ........ 112 習(xí)題 .......................................................... 114 參考文獻(xiàn) .................................................... 116 第 5 章 基于比較的排序算法 ......................... 118 冒泡排序算法 ................................... 118 5.1.1 基本思想、偽代碼與復(fù)雜度 分析 ........................................ 118 5.1.2 現(xiàn)代版 C++實現(xiàn) ................... 120 5.1.3 CD-AV 演示設(shè)計 .................. 121 插入排序算法 .................................. 122 5.2.1 基本思想、偽代碼與復(fù)雜度 分析 ....................................... 123 5.2.2 現(xiàn)代版 C++實現(xiàn) ................... 125 5.2.3 CD-AV 演示設(shè)計 .................. 125 堆排序算法 ...................................... 126 5.3.1 二叉堆的理論及相關(guān)算法 ... 127 目錄 - IX - 5.3.2 基本思想、偽代碼與復(fù)雜度 分析 ....................................... 131 5.3.3 現(xiàn)代版 C++實現(xiàn) ................... 133 5.3.4 CD-AV 演示設(shè)計 .................. 133 5.3.5 優(yōu)先隊列簡介 ....................... 136 算法國粹——π 值計算方法 ............ 137 5.4.1 劉徽關(guān)于 π 值的“割圓術(shù)” 計算方法 ............................... 137 5.4.2 祖沖之的 π 值計算成果 ........ 138 5.4.3 π 值的近現(xiàn)代計算方法和 計算成果 ............................... 138 習(xí)題 .......................................................... 139 參考文獻(xiàn) ................................................... 140 第 6 章 算法的分治設(shè)計方法 ........................ 141 分治法基礎(chǔ) ...................................... 141 6.1.1 分治法概述 ........................... 141 6.1.2 二分搜索算法 ....................... 142 Karatsuba 乘法算法 ......................... 144 6.2.1 大整數(shù)乘法的樸素分治 算法 ....................................... 144 6.2.2 大整數(shù)乘法的 Karatsuba 算法 ....................................... 145 歸并排序算法 .................................. 147 6.3.1 基本思想、偽代碼與復(fù)雜度 分析 ....................................... 147 6.3.2 現(xiàn)代版 C++實現(xiàn)與 CD-AV 演示設(shè)計 ............................... 150 快速排序算法 .................................. 152 6.4.1 基本思想、偽代碼與復(fù)雜度 分析 ....................................... 152 6.4.2 現(xiàn)代版 C++實現(xiàn)與 CD-AV 演示設(shè)計 ............................... 155 大師定理及其應(yīng)用 .......................... 156 6.5.1 大師定理簡介 ....................... 157 6.5.2 大師定理的應(yīng)用 ................... 157 算法國粹——賈憲的增乘開平 方法 .................................................. 158 6.6.1 增乘開平方法詳解................ 158 6.6.2 近代開平方法——牛頓 迭代法 ................................... 160 習(xí)題 ......................................................... 161 參考文獻(xiàn) ................................................... 163 第 7 章 算法的動態(tài)規(guī)劃設(shè)計方法 ................ 164 DP 方法概述 .................................... 164 7.1.1 Fibonacci 數(shù)的 DP 計算 ....... 164 7.1.2 DP 方法的基本思想及其所 求解問題的兩個重要特征 ... 166 7.1.3 DP 算法設(shè)計的基本步驟 ..... 167 兩個字符串間的編輯距離問題的 DP 算法 ........................................... 168 7.2.1 DP 方程及算法設(shè)計 ............. 168 7.2.2 現(xiàn)代版 C++實現(xiàn)與復(fù)雜度 分析 ....................................... 172 7.2.3 CD-AV 演示設(shè)計 .................. 174 矩陣鏈相乘問題的 DP 算法 ........... 176 7.3.1 DP 方程及算法設(shè)計 ............. 176 7.3.2 現(xiàn)代版 C++實現(xiàn)與復(fù)雜度 分析 ....................................... 179 7.3.3 CD-AV 演示設(shè)計 .................. 181 0-1 背包問題的 DP 算法 ................. 184 7.4.1 DP 方程及算法設(shè)計 ............. 184 7.4.2 現(xiàn)代版 C++實現(xiàn)與復(fù)雜度 分析 ....................................... 187 7.4.3 CD-AV 演示設(shè)計 .................. 189 TSP 問題的 DP 算法 ....................... 191 7.5.1 DP 方程及算法設(shè)計 ............. 191 7.5.2 現(xiàn)代版 C++實現(xiàn)與復(fù)雜度 分析 ....................................... 196 7.5.3 CD-AV 演示設(shè)計 .................. 200 算法國粹——秦九韶的正負(fù)開方術(shù) 與最優(yōu)多項式計算算法 .................. 202 7.6.1 秦九韶的正負(fù)開方術(shù) ........... 202 7.6.2 秦九韶的最優(yōu)多項式計算 算法 ....................................... 205 習(xí)題 ......................................................... 206 參考文獻(xiàn) ................................................... 207 第 8 章 算法的貪心設(shè)計方法 ........................ 209 貪心法概述 ...................................... 209 算法設(shè)計與分析——基于計算教學(xué)論的解析 - X - 8.1.1 找零錢問題、局部最優(yōu)與 全局最優(yōu) ............................... 209 8.1.2 貪心法的基本特征................ 211 圖中單源最短路徑的 Dijkstra 算法 .................................................. 213 8.2.1 最短路徑的最優(yōu)子結(jié)構(gòu) 性質(zhì) ....................................... 213 8.2.2 Dijkstra 算法的基本思想與 貪心選擇策略 ....................... 214 8.2.3 現(xiàn)代版 C++實現(xiàn)與復(fù)雜度 分析 ....................................... 215 8.2.4 CD-AV 演示設(shè)計 .................. 219 圖的最小生成樹的 Prim 算法 ......... 222 8.3.1 最小生成樹的最優(yōu)子 結(jié)構(gòu)性質(zhì) ............................... 222 8.3.2 Prim 算法的基本思想與 貪心選擇策略 ....................... 223 8.3.3 現(xiàn)代版 C++實現(xiàn)與 CD-AV 演示設(shè)計 ............................... 224 圖的最小生成樹的 Kruskal 算法 .... 225 8.4.1 Kruskal 算法的基本思想與 貪心選擇策略 ....................... 225 8.4.2 不相交集合及其 Union 與 Find 操作 ............................... 227 8.4.3 現(xiàn)代版 C++實現(xiàn)與復(fù)雜度 分析 ....................................... 228 8.4.4 CD-AV 演示設(shè)計 .................. 231 Huffman 編碼算法 ........................... 233 8.5.1 變長編碼、前綴編碼及其 滿二叉樹表示 ....................... 233 8.5.2 Huffman 編碼算法的基本 思想與復(fù)雜度分析................ 235 8.5.3 最優(yōu)前綴編碼的最優(yōu)子結(jié)構(gòu) 性質(zhì)與 Huffman 編碼算法的 貪心選擇策略 ....................... 236 8.5.4 現(xiàn)代版 C++實現(xiàn) ................... 238 8.5.5 CD-AV 演示設(shè)計 .................. 240 算法國粹——姚期智院士的 最小生成樹算法 .............................. 242 8.6.1 算法描述 ............................... 242 8.6.2 復(fù)雜度分析 ........................... 244 習(xí)題 ......................................................... 244 參考文獻(xiàn) ................................................... 245 第 9 章 算法的回溯設(shè)計方法 ........................ 247 圖的 DFS 算法 ................................. 247 9.1.1 圖及其表示 ........................... 247 9.1.2 圖的 DFS 算法、DFS 樹及 拓?fù)渑判?............................... 248 9.1.3 現(xiàn)代版 C++實現(xiàn) ................... 251 9.1.4 CD-AV 演示設(shè)計 .................. 252 回溯法概述 ...................................... 254 9.2.1 回溯法基礎(chǔ) ........................... 254 9.2.2 問題解的形態(tài)與回溯 算法的基本流程及相 關(guān)的節(jié)點狀態(tài) ....................... 257 0-1 背包問題的回溯算法 ................ 258 9.3.1 約束條件和限界條件設(shè)計 ... 259 9.3.2 0-1 背包問題回溯算法的 偽代碼及運行實例 ............... 260 N-皇后問題的回溯算法 .................. 263 9.4.1 N-皇后問題的定義、解空間 分析及約束條件設(shè)計 ........... 263 9.4.2 現(xiàn)代版 C++實現(xiàn) ................... 265 9.4.3 CD-AV 演示設(shè)計 .................. 266 K-著色問題的回溯算法 .................. 268 9.5.1 圖著色問題的定義與分析 ... 268 9.5.2 K-著色問題的回溯算法 設(shè)計 ....................................... 270 9.5.3 現(xiàn)代版 C++實現(xiàn) ................... 270 9.5.4 CD-AV 演示設(shè)計 .................. 272 算法國粹——線性方程組的 消元求解法 ...................................... 274 9.6.1 中國古代數(shù)學(xué)家對線性 方程組消元求解法的探索 ... 274 9.6.2 線性方程組求解的高斯 消元法 ................................... 276 習(xí)題 ......................................................... 277 參考文獻(xiàn) ................................................... 278 第 10 章 算法的分支限界設(shè)計方法 .............. 280 目錄 - XI - 圖的廣度優(yōu)先搜索 ........................ 280 10.1.1 圖的 BFS 算法 .................... 280 10.1.2 現(xiàn)代版 C++實現(xiàn) ................. 282 10.1.3 CD-AV 演示設(shè)計 ................ 282 分支限界法概述 ............................ 283 10.2.1 分支限界算法設(shè)計的 基本要領(lǐng) ............................. 283 10.2.2 兩類分支限界法 ................. 284 0-1 背包問題的分支限界算法 ...... 286 10.3.1 約束條件和限界函數(shù)設(shè)計.... 286 10.3.2 現(xiàn)代版 C++實現(xiàn) ................. 287 10.3.3 CD-AV 演示設(shè)計 ................ 289 TSP 問題的分支限界算法 ............. 292 10.4.1 TSP 問題與哈密爾頓回路 ... 292 10.4.2 費用矩陣及其歸約矩陣上的 哈密爾頓回路 ..................... 293 10.4.3 基于費用矩陣歸約的 TSP 問題的分支限界條件設(shè)計... 295 10.4.4 現(xiàn)代版 C++實現(xiàn) ................. 299 10.4.5 CD-AV 演示設(shè)計 ................ 303 算法國粹——內(nèi)插法與招差術(shù) ..... 306 10.5.1 中國古代數(shù)學(xué)家對內(nèi)插法與 招差術(shù)的探索 ..................... 306 10.5.2 現(xiàn)代插值法 ......................... 309 習(xí)題 .......................................................... 311 參考文獻(xiàn) ................................................... 312 第 11 章 RSA 算法 ......................................... 313 公鑰密碼學(xué)基礎(chǔ) ............................ 313 11.1.1 凱撒加密 .............................. 313 11.1.2 對稱密鑰體制 ...................... 314 11.1.3 公鑰密碼學(xué)簡介 .................. 315 模冪運算的反復(fù)平方算法 ............. 317 11.2.1 模運算基礎(chǔ) .......................... 317 11.2.2 模冪運算的反復(fù)平方表示與 算法 ..................................... 318 模同余、模的乘法逆元及擴展 Euclid GCD 算法 ........................... 320 11.3.1 模同余的定義及其 運算性質(zhì) ............................. 320 11.3.2 模的乘法逆元及 擴展 Euclid GCD 算法 ....... 322 Miller-Rabin 素性測試算法 .......... 324 11.4.1 關(guān)于素數(shù)的定理 ................. 324 11.4.2 費馬小定理及相關(guān)的素性 測試算法 ............................. 326 11.4.3 Miller-Rabin 素性測試算法 詳解 ..................................... 328 RSA 算法的基本原理與實現(xiàn) ........ 331 11.5.1 RSA 算法的基本原理 ......... 331 11.5.2 現(xiàn)代版 C++實現(xiàn) ................. 333 11.5.3 CD-AV 演示設(shè)計 ................ 335 算法國粹——中國余數(shù)算法 ......... 339 11.6.1 《孫子算經(jīng)》中的中國 余數(shù)算法 ............................. 339 11.6.2 秦九韶關(guān)于中國余數(shù)算法的 普適設(shè)計 ............................. 340 11.6.3 中國余數(shù)算法的現(xiàn)代版 C++ 實現(xiàn)及 CD-AV 演示設(shè)計 ... 341 11.6.4 中國余數(shù)算法在加快 RSA 解密運算中的應(yīng)用 ............. 343 習(xí)題 ......................................................... 345 參考文獻(xiàn) ................................................... 346 第 12 章 NP 理論............................................ 348 算法不可解的問題 ........................ 348 12.1.1 停機問題的不可計算性 ..... 348 12.1.2 希爾伯特第十問題的 不可計算性 ......................... 349 易解問題與難解問題、NP 理論 基礎(chǔ) ................................................ 350 12.2.1 易解問題與難解問題 ......... 350 12.2.2 NP 理論基礎(chǔ) ....................... 351 NP 完全性理論 .............................. 356 12.3.1 判定性問題的多項式 時間歸約 ............................. 356 12.3.2 通過定義證明的 NP 完全問題 ............................. 357 12.3.3 通過多項式歸約證明的 NP 完全問題 ....................... 360 算法設(shè)計與分析——基于計算教學(xué)論的解析 - XII - 12.3.4 問題復(fù)雜性類間的關(guān)系 ...... 365 算法國粹——姚期智院士的百萬富翁 問題 ................................................ 366 12.4.1 多方安全計算簡介 .............. 367 12.4.2 百萬富翁問題及其 求解協(xié)議 ............................. 368 習(xí)題 .......................................................... 369 參考文獻(xiàn) ................................................... 370 附錄：教材算法的現(xiàn)代版 C++實現(xiàn)及 計算教學(xué)論簡介 .................................... 372 附錄 1-1 Euclid GCD 算法 .................... 372 附錄 2-1 洗牌算法 ................................. 373 附錄 2-2 順序搜索算法 ......................... 374 附錄 4-1 子集遍歷問題的遞歸窮舉 算法 ......................................... 374 附錄 4-2 全排列遍歷問題的遞歸窮舉 算法 ......................................... 376 附錄 5-1 冒泡排序算法 ......................... 376 附錄 5-2 插入排序算法 ......................... 377 附錄 5-3 堆排序算法 ............................. 378 附錄 6-1 歸并排序算法 ......................... 379 附錄 6-2 快速排序算法 ......................... 380 附錄 7-1 Levenshtein 編輯距離問題的 DP 算法 .................................. 381 附錄 7-2 矩陣鏈相乘問題的 DP 算法 .... 384 附錄 7-3 0-1 背包問題的 DP 算法 ....... 387 附錄 7-4 TSP 問題的 DP 算法 .............. 389 附錄 8-1 Dijkstra 最短路徑算法 ........... 392 附錄 8-2 Prim 算法 ................................ 396 附錄 8-3 Kruskal 算法 ........................... 399 附錄 8-4 Huffman 編碼算法 ................. 404 附錄 9-1 圖遍歷的 DFS 算法 ............... 408 附錄 9-2 N-皇后問題的回溯算法 ......... 410 附錄 9-3 K-著色問題的回溯算法 .......... 411 附錄 10-1 圖的 BFS 算法 ...................... 414 附錄 10-2 0-1 背包問題的分支限界 算法 ....................................... 415 附錄 10-3 TSP 問題的分支限界算法 .... 420 附錄 11-1 RSA 算法 .............................. 426 附錄 11-2 中國余數(shù)算法 ....................... 429 附錄 12 計算教學(xué)論簡介 ...................... 431
你還可能感興趣
我要評論
|
