算法設(shè)計與分析

1 引論
1.1 什么是算法
1.2 分析算法的準(zhǔn)則
1.3 描述算法的語言和基本的數(shù)據(jù)結(jié)構(gòu)
思考題與習(xí)題
2 分治與遞歸
2.1 折半查找
2.2 搜索二叉排序樹
2.2.1 二叉排序樹的定義
2.2.2 搜索二叉排序樹
2.2.3 向二叉排序樹中插入新結(jié)點
2.2.4 從二叉排序樹中刪除一個結(jié)點
2.2.5 平衡的二叉排序樹
2.3 快速排序
2.4 歸并排序
2.5 大整數(shù)乘法
2.6 矩陣乘積的Strassen算法
思考題與習(xí)題
3 貪心算法
3.1 最小生成樹
3.2 單源最短路徑
3.3 旅行商問題
思考題與習(xí)題
4 動態(tài)規(guī)劃
4.1 動態(tài)規(guī)劃在最短路徑中的應(yīng)用
4.2 矩陣連乘積問題
4.3 求最長公共子序列
4.4 凸多邊形的最優(yōu)三角形剖分
4.5 旅行商問題
思考題與習(xí)題
5 回溯法
5.1 樹的深度優(yōu)先遍歷
5.2 數(shù)的全排列
5.3 八皇后問題
5.4 0-1背包問題
5.5 旅行商問題
思考題與習(xí)題
6 分支限界法
6.1 最小耗費搜索
6.2 背包問題
6.3 旅行商問題
思考題與習(xí)題
7 字符串
7.1 串概念及簡單串匹配算法
7.1.1 字符串的概念
7.1.2 串的匹配
7.1.3 簡單串模式匹配算法
7.2 Knuth-Morris-Pratt（KMP）算法
7.2.1 KMP算法
7.2.2 改進的KMP算法
7.3 Boyer.Moore算法
7.3.1 Boyer-Moore算法
7.4 Karp-Rabin串匹配隨機算法
思考題與習(xí)題
8 NP完全問題與近似算法
8.1 確定型圖靈機
8.2 非確定型圖靈機
8.3 Cook定理和NP完全理論
8.3.1 NP完全理論
8.3.2 Cook定理
8.3.3 若干NP完全問題
8.4 。NP完全問題的近似算法
8.4.1 0-1背包問題
8.4.2 旅行商問題
思考題與習(xí)題
9 概率算法
9.1 隨機抽樣
9.2 判定素數(shù)的概率算法
9.2.1 Fermat素數(shù)測試法
9.2.2 MiLler-Rabin素數(shù)判定概率算法
思考題與習(xí)題
10 數(shù)據(jù)壓縮算法
10.1.ASCII碼壓縮算法
10.2 哈夫曼編碼
10.3 字典法
10.4 LZ算法
10.4.1 LZ77算法
10.4.2 LZ78算法
10.4.3 LZW算法
思考題與習(xí)題
11 公鑰密碼學(xué)基礎(chǔ)
11.1 公鑰密碼體制的應(yīng)用與基本思想
11.2 背包公鑰密碼
11.3 RSA公鑰密碼體制
10.4 數(shù)字簽名和Hash算法
思考題與習(xí)題
參考文獻