算法概論

第0章 序言
0.1 書籍和算法
0.2 從Fibonacci數(shù)列開始
0.3 大O符號
習(xí)題
第1章 數(shù)字的算法
1.1 基本算術(shù)
1.1.1 加法
1.1.2 乘法和除法
1.2 模運(yùn)算
1.2.1 模的加法和乘法
1.2.2 模的指數(shù)運(yùn)算
1.2.3 Euclid的最大公因數(shù)算法
1.2.4 Euclid算法的一種擴(kuò)展
1.2.5 模的除法
1.3 素性測試
1.4 密碼學(xué)
1.4.1 密鑰機(jī)制：一次一密亂碼本和AES
1.4.2 RSA
1.5 通用散列表
1.5.1 散列表
1.5.2 散列函數(shù)族
習(xí)題
第2章 分治算法
2.1 乘法
2.2 遞推式
2.3 合并排序
2.4 尋找中項
2.5 矩陣乘法
2.6 快速Fourier變換
2.6.1 多項式的另一種表示法
2.6.2 計算步驟的分治實(shí)現(xiàn)
2.6.3 插值
2.6.4 快速Fourier變換的細(xì)節(jié)
習(xí)題
第3章 圖的分解
3.1 為什么是圖
3.2 無向圖的深度優(yōu)先搜索
3.2.1 迷宮探索
3.2.2 深度優(yōu)先搜索
3.2.3 無向圖的連通性
3.2.4 前序和后序
3.3 有向圖的深度優(yōu)先搜索
3.3.1 邊的類型
3.3.2 有向無環(huán)圖
3.4 強(qiáng)連通部件
3.4.1 定義有向圖的連通性
3.4.2 一個有效的算法
習(xí)題
第4章 圖中的路徑
4.1 距離
4.2 廣度優(yōu)先搜索
4.3 邊的長度
4.4 Dijkstra算法
4.4.1 廣度優(yōu)先搜索的一個改進(jìn)
4.4.2 另一種解釋
4.4.3 運(yùn)行時間
4.5 優(yōu)先隊列的實(shí)現(xiàn)
4.5.1 數(shù)組
4.5.2 二分堆
4.5.3 d堆
4.6 含有負(fù)邊的圖的最短路徑
4.6.1 負(fù)邊
4.6.2 負(fù)環(huán)
4.7 有向無環(huán)圖中的最短路徑
習(xí)題
第5章 貪心算法
5.1 最小生成樹
5.1.1 一個貪心方法
5.1.2 分割性質(zhì)
5.1.3 Kruskal算法
5.1.4 一種用于分離集的數(shù)據(jù)結(jié)構(gòu)
5.1.5 Prim算法
5.2 Huffman編碼
5.3 Horn公式
5.4 集合覆蓋
習(xí)題
第6章 動態(tài)規(guī)劃
6.1 重新審視有向無環(huán)圖的最短路徑問題
6.2 最長遞增子序列
6.3 編輯距離
6.4 背包問題
6.5 矩陣鏈?zhǔn)较喑?br />6.6 最短路徑問題
6.7 樹中的獨(dú)立集
習(xí)題
第7章 線性規(guī)劃與歸約
7.1 線性規(guī)劃簡介
7.1.1 示例：利潤最大化
7.1.2 示例：生產(chǎn)計劃
7.1.3 示例：最優(yōu)帶寬分配
7.1.4 線性規(guī)劃的變體
7.2 網(wǎng)絡(luò)流
7.2.1 石油運(yùn)輸
7.2.2 最大流
7.2.3 對算法的深入觀察
7.2.4 最優(yōu)性的保證
7.2.5 算法的效率
7.3 二部圖的匹配
7.4 對偶
7.5 零和博弈(游戲)
7.6 單純形算法
7.6.1 n維空間中的頂點(diǎn)和鄰居
7.6.2 算法
7.6.3 補(bǔ)遺
7.6.4 單純形法的運(yùn)行時間
7.7 后記：電路值1
習(xí)題
第8章 NP-完全問題
8.1 搜索問題
8.2 NP-完全問題
8.3 所有的歸約
習(xí)題
第9章 NP-完全問題的處理
9.1 智能窮舉搜索
9.1.1 回溯
9.1.2 分支定界
9.2 近似算法
9.2.1 頂點(diǎn)覆蓋
9.2.2 聚類
9.2.3 TSP
9.2.4 背包問題
9.2.5 逼近的層次
9.3 局部搜索中的啟發(fā)方法
9.3.1 重新審視旅行商問題
9.3.2 圖劃分
9.3.3 處理局部最優(yōu)
習(xí)題
第10章 量子算法
10.1 量子位元、疊加狀態(tài)和度量
10.2 算法設(shè)計
10.3 量子傅立葉變換
10.4 周期性
10.5 量子電路
10.5.1 基本量子門
10.5.2 量子電路的兩種基本類型
10.5.3 量子傅立葉變換電路
10.6 將因子分解問題轉(zhuǎn)化為周期求解問題
10.7 因子分解的量子算法
習(xí)題
歷史背景及深入閱讀的資