計算機算法導引：設計與分析

第1部分基 本 算 法
第1章數學準備
1.1母函數
1.2遞推關系
1.3Fibonacci 數列
1.3.1Fibonacci 數列是典型的遞推關系
1.3.2問題的解
1.4線性常系數遞推關系舉例
1.5其他類型的遞推關系舉例
習題
第2章優(yōu)先策略與分治策略
2.1優(yōu)先策略：求最短樹的 Kruskal 算法
2.2求最短樹的 Prim 算法
2.3求最短路徑的 Dijkstra 算法
2.4文件存儲問題
2.5有期限的任務安排問題
2.6數據壓縮和 Huffman 樹
2.7分治策略與二分查找
2.8整數乘法
2.9矩陣乘積的 Strassen 算法
2.10矩陣乘積的Winograd算法
2.11布爾矩陣乘積的分段預處理方法
2.12歸并排序法
2.13快速排序法
2.14求序列中的第k個元素
習題
第3章動態(tài)規(guī)劃
3.1最短路徑問題
3.2最佳原理
3.3流動推銷員問題
3.3.1算法及例題
3.3.2復雜性估計
3.4矩陣鏈乘問題
3.5最長公共子序列
3.6圖的任意兩點間的最短距離
3.7同順序流水作業(yè)的任務安排問題
3.8可靠性問題
3.9最佳二分樹
3.9.1二分樹的一些性質
3.9.2最佳二分樹的構成
習題
第4章概率算法
4.1生日問題
4.2概率算法舉例
4.3隨機數的產生器
4.3.1線性同余式法
4.3.2離散對數法
4.3.3BBS法
4.3.4素數法
4.4素數的概率判定算法
4.4.1關于素數的若干定理
4.4.2Fermat數
4.4.3MillerRabin的素數概率測試法
4.5定理證明的數學準備
4.5.1數論的基本知識
4.5.2群論的基本知識
4.5.3中國剩余定理
4.5.4xn≡1 mod p 的解
4.6定理A的證明
4.7定理B的證明
習題
第5章并行算法
5.1并行計算機和并行算法的基本概念
5.2遞推關系的并行計算
5.3圖的并行算法舉例
5.4矩陣乘積的并行計算
5.5分布計算
5.6快速傅里葉變換
5.6.1FFT問題的背景
5.6.2預備定理
5.6.3快速算法
5.6.4傅里葉逆變換
5.6.5計算結果的重排
5.6.6復雜性估計
5.7卷積及其應用
5.7.1卷積
5.7.2多項式的一種快速乘法
5.8數論變換
5.9排序網絡
5.9.1引論
5.9.201原理
5.9.3Bn 型網絡
5.9.4Mn 歸并網絡
5.10Batcher 奇偶歸并網絡
5.11脈動陣列的并行處理
5.11.1矩陣和向量乘法的并行處理
5.11.2矩陣乘法的并行處理
5.11.3帶狀矩陣的并行乘法
習題
第6章搜索法
6.1引論
6.2DFS 搜索法
6.3無向圖的 DFS 算法
6.4有向圖的 DFS 算法
6.5互通塊問題
6.6強連通塊問題
6.7BFS 算法
6.8拓撲排序
6.9minmax 搜索法
6.10流動推銷員問題的分支定界法
6.11同順序加工任務安排問題
習題
第7章數據結構
7.1“堆”和“堆集排序法”
7.1.1堆
7.1.2堆集排序法
7.1.3優(yōu)先級隊和二進制堆
7.223樹
7.3234樹
7.4紅黑樹
7.4.1RB樹性質
7.4.2插入
7.4.3刪除
7.5B樹
7.5.1B樹性質
7.5.2B樹的插入
7.5.3B樹的刪除
7.6關于高度的均衡樹
7.6.1AVL樹--關于高度均衡的二分樹
7.6.2關于高度均衡的二分樹的插入和刪除
7.7哈希表
7.7.1什么是哈希表
7.7.2哈希函數的構造方法
7.7.3解決沖突的方法
7.7.4哈希算法的分析(線性探測法分析)
7.7.5二重哈希法
習題
第2部分若 干 專 題
第8章排序算法
8.1排序
8.2下界估計
8.3二分插入排序法
8.4下溢排序法
8.5FordJohnson 歸并插入排序法
8.5.1算法的非形式化描述
8.5.2一般情形的討論
8.5.3算法分析
8.6外存排序
8.6.1外存歸并排序法
8.6.2三條帶的外存歸并排序法
8.6.3階式歸并法
第9章計算幾何及計算數論
9.1關于線段問題
9.2凸包問題與Voronoi問題
9.2.1凸包問題
9.2.2Voronoi圖
9.2.3Voronoi圖的構造法
9.2.4Voronoi圖的應用簡介
9.2.5Voronoi圖的拓廣
9.3串匹配
9.3.1搜索法
9.3.2KMP 算法
9.3.3BM 算法
9.3.4RK 算法
9.4數論的算法問題
9.4.1求最大公因數
9.4.2因數分解之一： Pollard ρ法
9.4.3Dixon 隨機平方因數分解法
9.4.4橢圓曲線因數分解法
9.5大數模冪運算
9.5.1常規(guī)算法
9.6N mod M
9.6.1Barrett歸約
9.6.2模乘算法
9.6.3Montgomery 模冪運算
9.6.4n是偶數的情況
第10章線性規(guī)劃
10.1問題的提出
10.2線性規(guī)劃的幾何意義
10.3單純形法理論基礎
10.4單純形法及單純形表格
10.5改善的單純形法表格
10.6對偶原理
10.6.1對偶概念
10.6.2對偶問題的經濟意義
10.6.3對偶問題的性質
10.6.4對偶定理
10.6.5影子價格
10.7對偶單純形法
10.8退化情況及其他
10.8.1退化情況
10.8.2退化情況的循環(huán)不已與Bland 法則
10.9DantzigWolfe 分解算法
10.10整數規(guī)劃
10.10.1問題的提出
10.10.201 規(guī)劃和DFS 搜索法
10.10.3分支定界法
10.11Klee 與 Minty舉例
第3部分復雜性理論與智能型算法
第11章算法復雜性理論
11.1圖靈機
11.2圖靈機和算法
11.3k 條帶的圖靈機
11.4非確定型圖靈機
11.5停機問題
11.6布爾表達式
11.7布爾變量和網絡
11.8問題的轉換
11.9Cook 定理
11.10幾個 NP 完備的例子
11.11復雜度類
11.12近似解法
11.12.1任務安排的近似算法
11.12.2裝箱問題的近似算法
11.12.3流動推銷員問題的近似算法
11.12.4頂點覆蓋問題的近似算法
11.13近代密碼學簡介
11.13.1密碼概念
11.13.2背包公鑰密碼
11.13.3RSA 公鑰密碼
第12章智能型算法
12.1遺傳算法
12.2什么是遺傳算法
12.3TSP 問題
12.3.1編碼
12.3.2初始“種群”的生成
12.3.3雜交
12.3.4變異算術
12.3.5模式定理
12.4模擬退火算法簡介
習題