計(jì)算機(jī)算法引論：設(shè)計(jì)與分析技術(shù)

1  緒論                  
 1. 1  交通信號(hào)燈問(wèn)題                  
 1. 1. 1  問(wèn)題                  
 1. 1. 2  實(shí)例                  
 1. 1. 3  圖著色問(wèn)題                  
 1. 1. 4  算法設(shè)計(jì)討論                  
 1. 1. 5  討論                  
 1. 2  什么是算法                  
 1. 2. 1  算法                  
 1. 2. 2  算法與問(wèn)題                  
 1. 2. 3  算法與程序                  
 1. 3  算法的評(píng)估                  
 1. 3. 1  正確性                  
 1. 3. 2  時(shí)間代價(jià)                  
 1. 3. 3  空間代價(jià)                  
 1. 3. 4  最優(yōu)性                  
 1. 4  算法理論的基本概念                  
 1. 4. 1  摹本操作                  
 1. 4. 2  問(wèn)題實(shí)例長(zhǎng)度                  
 1. 4. 3  復(fù)雜度的漸進(jìn)性質(zhì)                  
 1. 4. 4  最壞情形和最好情形                  
 1. 4. 5  平均情形和算法的期望復(fù)雜度                  
 1. 4. 6  復(fù)雜度函數(shù)的表示                  
 * 1. 5  算法的研究與Moore定律                  
 * 1. 6  MAXMIN問(wèn)題                  
 1. 6. 1  平凡算法                  
 1. 6. 2  改進(jìn)一                  
 1. 6. 3  改進(jìn)二                  
 1. 6. 4  改進(jìn)三                  
 1. 6. 5  討論                  
 習(xí)題1                  
 2  排序算法與算法的分析技術(shù)                  
 2. 1  排序問(wèn)題                  
 2. 2  O(n )階的排序算法                  
 2. 2. 1  選擇排序                  
 2. 2. 2  插入排序                  
 2. 2. 3  起泡排序                  
 2. 3  基于相鄰元比較的排序算法和希爾排序                  
 2. 3. 1  插入排序的最優(yōu)性                  
 2. 3. 2  希爾排序                  
 2. 4  O(nlogn)階的排序算法                  
 2. 4. 1  快速排序算法                  
 2. 4. 2  合并排序算法                  
 2. 4. 3  堆排序算法                  
 2. 5  比較排序算法的時(shí)間復(fù)雜度下界                  
 2. 5. 1  判定樹(shù)模型                  
 2. 5. 2  最壞情形                  
 2. 5. 3  平均情形                  
 2. 6  排序算法的有關(guān)研究                  
 習(xí)題2                  
 3  分治技術(shù)                  
 3. 1  分治策略的思想                  
 3. 2  大整數(shù)乘法                  
 3. 3  矩陣相乘的Strassen算法                  
 3. 3. 1  問(wèn)題                  
 3. 3. 2  分治                  
 3. 3. 3  Strassen的分治方法                  
 3. 3. 4  Strassen算法的描述                  
 3. 3. 5  討論                  
 3. 4  選擇問(wèn)題的線性算法                  
 3. 4. 1  問(wèn)題                  
 3. 4. 2  簡(jiǎn)單算法                  
 3. 4. 3  O(n)階選擇算法的思路                  
 3. 4. 4  選擇算法                  
 3. 4. 5  選擇算法Select的分析                  
 3. 4. 6  討論                  
 習(xí)題3                  
 4  數(shù)據(jù)集合上的搜索算法                  
 4. 1  動(dòng)態(tài)數(shù)據(jù)集與抽象數(shù)據(jù)類(lèi)型                  
 4. 2  二叉搜索樹(shù)                  
 4. 2. 1  二叉搜索樹(shù)                  
 4. 2. 2  查詢(xún)的實(shí)現(xiàn)                  
 4. 2. 3  插入與刪除操作                  
 4. 3  隨機(jī)二叉搜索樹(shù)                  
 4. 4  紅黑樹(shù)                  
 4. 4. 1  紅黑樹(shù)的性質(zhì)                  
 4. 4. 2  RB樹(shù)的插入與刪除算法                  
 4. 4. 3  關(guān)于RB樹(shù)的幾點(diǎn)討論                  
 4. 5  2—3—4樹(shù)                  
 4. 5. 1  2—3—4樹(shù)及其實(shí)例                  
 4. 5. 2  2—3—4樹(shù)上的查詢(xún)操作算法                  
 4. 5. 3  2—3—4樹(shù)的構(gòu)造過(guò)程                  
 4. 5. 4  2—3—4樹(shù)的性能分析                  
 4. 5. 5  有關(guān)2—3—4樹(shù)的幾點(diǎn)討論                  
 4. 6  Hash技術(shù)                  
 4. 6. 1  Hash算法的基本思想與一般模型                  
 4. 6, 2  Hash函數(shù)的設(shè)計(jì)                  
 4. 6. 3  解決沖突的策略                  
 4. 6. 4  Hash算法的優(yōu)劣分析                  
 4. 6. 5  Hash技術(shù)的幾種新發(fā)展                  
 習(xí)題4                  
 5  貪心技術(shù)                  
 5. 1  貪心策略的思想                  
 5. 1. 1  付款問(wèn)題                  
 5. 1. 2  鋪磚問(wèn)題                  
 5. 1. 3  貪心算法的基本思想                  
 5. 2  背包問(wèn)題                  
 5. 3  Huffman編碼                  
 5. 4  多機(jī)調(diào)度問(wèn)題的近似解法                  
 5. 5  單源最短路徑的Dijkstra算法                  
 習(xí)題5                  
 6  字符串匹配                  
 6. 1  字符串匹配問(wèn)題                  
 6. 2  KMP算法                  
 6. 2. 1  KMP算法的思路                  
 6. 2. 2  KMP算法                  
 6. 2. 3  KMP算法的正確性                  
 6. 2. 4  KMP算法的分析                  
 6. 2. 5  有關(guān)KMP算法的討論                  
 6. 3  BM算法                  
 6. 3. 1  BM算法的兩種處理思路                  
 6. 3. 2  BM算法的時(shí)間復(fù)雜度分析                  
 6. 3. 3  對(duì)BM算法的進(jìn)一步討論                  
 6. 4  RK算法                  
 6. 4. 1  RK算法的思路                  
 6. 4. 2  RK算法的描述                  
 6. 4. 3  RK算法的分析與討論                  
 習(xí)題6                  
 7  動(dòng)態(tài)規(guī)劃                  
 7. 1  動(dòng)態(tài)規(guī)劃的基本原理                  
 7. 1. 1  Fibonacci數(shù)的計(jì)算                  
 7. 1. 2  矩陣連乘的順序問(wèn)題                  
 7. 1. 3  動(dòng)態(tài)規(guī)劃算法的基本條件                  
 7. 2  最優(yōu)二分搜索樹(shù)                  
 7. 2. 1  最優(yōu)二分搜索樹(shù)問(wèn)題                  
 7. 2. 2  動(dòng)態(tài)規(guī)劃算法的思路                  
 7. 2. 3  OBST算法                  
 7. 2. 4  OBST算法的復(fù)雜度分析                  
 7. 2. 5  討論                  
 7. 3  近似串匹配問(wèn)題                  
 7. 3. 1  近似串匹配問(wèn)題的描述                  
 7. 3. 2  動(dòng)態(tài)規(guī)劃算法的思路                  
 7. 3. 3  動(dòng)態(tài)規(guī)劃算法                  
 7. 3. 4  算法的復(fù)雜度分析與實(shí)例                  
 7. 3. 5  討論                  
 習(xí)題7                  
 8  回溯與分枝限界技術(shù)                  
 8. 1  回溯和分枝限界的基本思想                  
 8. 1. 1  八皇后問(wèn)題                  
 8. 1. 2  子集合問(wèn)題                  
 8. 1. 3  回溯與分枝限界算法的基本思路                  
 8. 2  0—1背包問(wèn)題的回溯算法                  
 8. 2. 1  0—1背包問(wèn)題                  
 8. 2. 2  回溯策略的解題思路                  
 8. 2. 3  0—1背包問(wèn)題的回溯算法                  
 8. 2. 4  算法的復(fù)雜度分析                  
 8. 2. 5  一個(gè)運(yùn)行實(shí)例                  
 8. 3  無(wú)向圖的團(tuán)集問(wèn)題                  
 8. 3. 1  團(tuán)集問(wèn)題                  
 8. 3. 2  解題思路                  
 8. 3. 3  團(tuán)集問(wèn)題的回溯算法                  
 8. 3. 4  算法Max Clique()的分析與討論                  
 8. 4  旅行商問(wèn)題的回溯算法                  
 8. 4. 1  旅行商問(wèn)題                  
 8. 4. 2  旅行商問(wèn)題的回溯算法                  
 8. 5  分枝限界算法思路的特征                  
 8. 5. 1  0—1背包問(wèn)題的分枝限界策略                  
 8. 5. 2  分枝限界算法的優(yōu)點(diǎn)和缺點(diǎn)                  
 8. 5. 3  用分枝限界算法解旅行商問(wèn)題的一個(gè)實(shí)例                  
 習(xí)題8                  
 9  計(jì)算機(jī)難解問(wèn)題與NP—完全性問(wèn)題                  
 9. 1  一些難解問(wèn)題                  
 9. 1. 1  圖著色問(wèn)題                  
 9. 1. 2  0—1背包問(wèn)題                  
 9. 1. 3  子集合問(wèn)題                  
 9. 1. 4  裝箱問(wèn)題                  
 9. 1. 5  作業(yè)調(diào)度問(wèn)題                  
 9. 1. 6  可滿(mǎn)足性問(wèn)題                  
 9. 1. 7  圖的團(tuán)集問(wèn)題                  
 9. 1. 8  Hamiltonian回路問(wèn)題與Hamiltonian路徑問(wèn)題                  
 9. 1. 9  旅行商問(wèn)題                  
 9. 2  多項(xiàng)式界與P類(lèi)問(wèn)題                  
 9. 2. 1  多項(xiàng)式(時(shí)間)界                  
 9. 2. 2  問(wèn)題求解與判定問(wèn)題                  
 9. 2. 3  P類(lèi)                  
 9. 3  不確定算法與NP類(lèi)                  
 9. 3. 1  問(wèn)題求解與驗(yàn)證                  
 9. 3. 2  非確定算法與NP類(lèi)                  
 9. 4  問(wèn)題的多項(xiàng)式歸約和NP—完全性                  
 9. 4. 1  多項(xiàng)式歸約                  
 9. 4. 2  NP—完全性                  
 9. 4. 3  Cook定理                  
 9. 5  與NP—完全問(wèn)題相關(guān)的理論問(wèn)題與實(shí)際問(wèn)題                  
 9. 5. 1  理論可計(jì)算性與實(shí)際可計(jì)算性                  
 9. 5. 2  “P=NP”問(wèn)題                  
 9. 5. 3  NP—完全問(wèn)題的計(jì)算處理                  
 習(xí)題9                  
 10  近似算法                  
 10. 1  近似算法的思想與基本概念                  
 10. 1. 1  頂點(diǎn)覆蓋問(wèn)題的近似算法                  
 10. 1. 2  頂點(diǎn)覆蓋問(wèn)題的近似算法a VertexCover()                  
 10. 1. 3  近似算法a VertexCover()的復(fù)雜度分析                  
 10. 1. 4  算法a VertexCover()的近似度分析                  
 10. 2  裝箱問(wèn)題的近似算法                  
 10. 2. 1  裝箱問(wèn)題                  
 10. 2. 2  裝箱問(wèn)題的近似策略的討論                  
 10. 2. 3  裝箱問(wèn)題的FF策略近似算法                  
 10. 2. 4  bpFFD算法的復(fù)雜度                  
 10. 2. 5  近似算法bqFFD()解的最優(yōu)性分析                  
 10. 2. 6  討論                  
 10. 3  旅行商問(wèn)題的近似算法                  
 10. 3. 1  最近鄰點(diǎn)策略                  
 10. 3. 2  最短鏈接策略                  
 10. 3. 3  滿(mǎn)足三角不等式的旅行商問(wèn)題                  
 10. 3. 4  幾點(diǎn)討論                  
 習(xí)題10                  
 11  數(shù)論算法及其在計(jì)算機(jī)安全系統(tǒng)中的應(yīng)用                  
 11. 1  RSA公鑰密碼系統(tǒng)                  
 11. 1. 1  數(shù)據(jù)加密的歷史及現(xiàn)狀                  
 11. 1. 2  公鑰密碼系統(tǒng)                  
 11. 1. 3  RSA公鑰密碼系統(tǒng)                  
 11. 1. 4  公鑰密碼系統(tǒng)的數(shù)字簽名功能                  
 11. 1. 5  公鑰密碼系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)安全                  
 11. 1. 6  RSA公鑰密碼系統(tǒng)的主要技術(shù)問(wèn)題                  
 11. 2  判素問(wèn)題的概率算法                  
 11. 2. 1  判素問(wèn)題                  
 11. 2. 2  輸入長(zhǎng)度和算術(shù)計(jì)算的時(shí)間代價(jià)                  
 11. 2. 3  基于數(shù)論的素?cái)?shù)判別概率算法                  
 11. 3  大素?cái)?shù)的獲得和Miller—Rabin算法的應(yīng)用                  
 11. 3. 1  素?cái)?shù)的稠密性                  
 11. 3. 2  Miller-Rabin測(cè)試算法的時(shí)間代價(jià)                  
 11. 3. 3  Miller-Rabin算法判定素?cái)?shù)的正確性                  
 11. 4  加密解密算法                  
 11. 5  大整數(shù)分解與RSA系統(tǒng)的安全性                  
 11. 5. 1  整數(shù)的因子分解問(wèn)題                  
 11. 5. 2  Pollard的rho啟發(fā)式算法                  
 習(xí)題11                  
 附錄A  遞歸方程(遞歸不等式)的求解判定方法                  
 附錄B  實(shí)際性能最佳的排序算法的設(shè)計(jì)                  
 附錄C  計(jì)算模型                  
 附錄D  Cook定理                  
 附錄E  若干數(shù)論知識(shí)                  
 附錄F  算法索引                  
 主要參考文獻(xiàn)