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