計(jì)算機(jī)算法導(dǎo)引：設(shè)計(jì)與分析

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