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