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

第1部分基 本 算 法
第1章數(shù)學準備
1.1母函數(shù)
1.2遞推關(guān)系
1.3Fibonacci 數(shù)列
1.3.1Fibonacci 數(shù)列是典型的遞推關(guān)系
1.3.2問題的解
1.4線性常系數(shù)遞推關(guān)系舉例
1.5其他類型的遞推關(guān)系舉例
習題
第2章優(yōu)先策略與分治策略
2.1優(yōu)先策略：求最短樹的 Kruskal 算法
2.2求最短樹的 Prim 算法
2.3求最短路徑的 Dijkstra 算法
2.4文件存儲問題
2.5有期限的任務安排問題
2.6數(shù)據(jù)壓縮和 Huffman 樹
2.7分治策略與二分查找
2.8整數(shù)乘法
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二分樹的一些性質(zhì)
3.9.2最佳二分樹的構(gòu)成
習題
第4章概率算法
4.1生日問題
4.2概率算法舉例
4.3隨機數(shù)的產(chǎn)生器
4.3.1線性同余式法
4.3.2離散對數(shù)法
4.3.3BBS法
4.3.4素數(shù)法
4.4素數(shù)的概率判定算法
4.4.1關(guān)于素數(shù)的若干定理
4.4.2Fermat數(shù)
4.4.3MillerRabin的素數(shù)概率測試法
4.5定理證明的數(shù)學準備
4.5.1數(shù)論的基本知識
4.5.2群論的基本知識
4.5.3中國剩余定理
4.5.4xn≡1 mod p 的解
4.6定理A的證明
4.7定理B的證明
習題
第5章并行算法
5.1并行計算機和并行算法的基本概念
5.2遞推關(guān)系的并行計算
5.3圖的并行算法舉例
5.4矩陣乘積的并行計算
5.5分布計算
5.6快速傅里葉變換
5.6.1FFT問題的背景
5.6.2預備定理
5.6.3快速算法
5.6.4傅里葉逆變換
5.6.5計算結(jié)果的重排
5.6.6復雜性估計
5.7卷積及其應用
5.7.1卷積
5.7.2多項式的一種快速乘法
5.8數(shù)論變換
5.9排序網(wǎng)絡
5.9.1引論
5.9.201原理
5.9.3Bn 型網(wǎng)絡
5.9.4Mn 歸并網(wǎng)絡
5.10Batcher 奇偶歸并網(wǎng)絡
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章數(shù)據(jù)結(jié)構(gòu)
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樹性質(zhì)
7.4.2插入
7.4.3刪除
7.5B樹
7.5.1B樹性質(zhì)
7.5.2B樹的插入
7.5.3B樹的刪除
7.6關(guān)于高度的均衡樹
7.6.1AVL樹--關(guān)于高度均衡的二分樹
7.6.2關(guān)于高度均衡的二分樹的插入和刪除
7.7哈希表
7.7.1什么是哈希表
7.7.2哈希函數(shù)的構(gòu)造方法
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章計算幾何及計算數(shù)論
9.1關(guān)于線段問題
9.2凸包問題與Voronoi問題
9.2.1凸包問題
9.2.2Voronoi圖
9.2.3Voronoi圖的構(gòu)造法
9.2.4Voronoi圖的應用簡介
9.2.5Voronoi圖的拓廣
9.3串匹配
9.3.1搜索法
9.3.2KMP 算法
9.3.3BM 算法
9.3.4RK 算法
9.4數(shù)論的算法問題
9.4.1求最大公因數(shù)
9.4.2因數(shù)分解之一： Pollard ρ法
9.4.3Dixon 隨機平方因數(shù)分解法
9.4.4橢圓曲線因數(shù)分解法
9.5大數(shù)模冪運算
9.5.1常規(guī)算法
9.6N mod M
9.6.1Barrett歸約
9.6.2模乘算法
9.6.3Montgomery 模冪運算
9.6.4n是偶數(shù)的情況
第10章線性規(guī)劃
10.1問題的提出
10.2線性規(guī)劃的幾何意義
10.3單純形法理論基礎
10.4單純形法及單純形表格
10.5改善的單純形法表格
10.6對偶原理
10.6.1對偶概念
10.6.2對偶問題的經(jīng)濟意義
10.6.3對偶問題的性質(zhì)
10.6.4對偶定理
10.6.5影子價格
10.7對偶單純形法
10.8退化情況及其他
10.8.1退化情況
10.8.2退化情況的循環(huán)不已與Bland 法則
10.9DantzigWolfe 分解算法
10.10整數(shù)規(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布爾變量和網(wǎng)絡
11.8問題的轉(zhuǎn)換
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變異算術(shù)
12.3.5模式定理
12.4模擬退火算法簡介
習題