算法引論：一種創(chuàng)造性方法 a creative approach

第1章 引論
第2章 數(shù)學歸納法
2.1 引言
2.2 三個簡單的例子
2.3 平面內(nèi)區(qū)域的計數(shù)
2.4 簡單的著色問題
2.5 復雜一些的加法題
2.6 一個簡單的不等式
2.7 歐拉公式
2.8 圖論中的一個問題
2.9 格雷碼
2.10 在圖上尋找無重邊的路
2.11 數(shù)學平均數(shù)和幾何平均數(shù)定理
2.12 循環(huán)不變量：將十進制數(shù)轉(zhuǎn)換為二進制數(shù)
2.13 常見的錯誤
2.14 小結(jié)
第3章 算法分析
3.1 引言
3.2 符號D
3.3 時間與空間復雜度
3.4 求和
3.5 遞推關(guān)系
3.5.1 巧妙地猜測
3.5.2 分治關(guān)系
3.5.3 涉及全部歷史的遞推關(guān)系
3.6 一些有用的證明論據(jù)
3.7 小結(jié)
第4章 數(shù)據(jù)結(jié)構(gòu)簡介
4.1 引言
4.2 基本數(shù)據(jù)結(jié)構(gòu)
4.2.1 元素
4.2.2 數(shù)組
4.2.3 記錄
4.2.4 鏈表
4.3 樹
4.3.1 樹的表示
4.3.2 堆
4.3.3 二叉搜索樹
4.3.4 AVL樹
4.4 散列
4.5 合并—查找問題
4.6 圖
4.7 小結(jié)
第5章 基于歸納的算法設(shè)計
5.1 引言
5.2 多項式求值
5.3 最大導出子圖
5.4 尋找一對一映射
5.5 社會名流問題
5.6 分治算法：輪廓問題
5.7 在二叉樹中計算平衡因子
5.8 尋找最大連續(xù)子序列
5.9 增強歸納假設(shè)
5.10 動態(tài)規(guī)劃：背包問題
5.11 常見的錯誤
5.12 小結(jié)
第6章 序列和集合的算法
6.1 引言
6.2 二叉搜索的幾種形式
6.2.1 純二叉搜索
6.2.2 循環(huán)序列的二叉搜索
6.2.3 二叉搜索特殊下標
6.2.4 二叉搜索長度未知的序列·
6.2.5 重疊子序列問題
6.2.6 解方程
6.3 內(nèi)插搜索
6.4 排序
6.4.1 桶排序和基數(shù)排序
6.4.2 插入排序和選擇排序
6.4.3 歸并排序
6.4.4 快速排序
6.4.5 堆排序
6.4.6 排序問題的下界
6.5 順序統(tǒng)計
6.5.1 最大數(shù)和最小數(shù)
6.5.2 查找第足小的數(shù)
6.6 數(shù)據(jù)壓縮
6.7 串匹配
6.8 序列比較
6.9 概率算法
6.9.1 隨機數(shù)
6.9.2 著色問題
6.9.3 將拉斯維加斯算法變換成確定性算法
6.10 查找眾數(shù)
6.11 三個展現(xiàn)有趣證明方法的問題
6.11.1 最長遞增序列
6.11.2 查找集合中兩個最大的元素
6.11.3 計算多重集合的模
6.12 小結(jié)
第7章 圖算法
7.1 引言
7.2 歐拉圖
7.3 圖的遍歷
7.3.1 深度優(yōu)先搜索
7.3.2 廣度優(yōu)先搜索
7.4 拓撲排序
7.5 單源最短路徑
7.6 最小代價生成樹
7.7 全部最短路徑
7.8 傳遞閉包
7.9 圖的分解
7.9.1 雙連通分支
7.9.2 強連通分支
7.9.3 利用圖分解的例子
7.10 配
7.10.1 非常稠密圖中的完美匹配
7.10.2 偶圖匹配
7.11 網(wǎng)絡(luò)流量
7.12 哈密爾頓旅行
7.12.1 反向歸納
7.12.2 在非常稠密圖中找哈密爾頓回路
7.13 小結(jié)
第8章 幾何算法
8.1 引言
8.2 判定點是否在多邊形內(nèi)部
8.3 構(gòu)造簡單多邊形
8.4 凸包
8.4.1 直接方法
8.4.2 禮品包裹算法
8.4.3 Graham掃描算法
8.5 最近點對
8.6 水平線段和豎直線段的交點
8.7 小結(jié)
第9章 代數(shù)和數(shù)值算法
9.1 引言
9.2 求冪運算
9.3 歐幾里得算法
9.4 多項式乘法
9.5 矩陣乘法
9.5.1 Winograd算法
9.5.2 Strassen算法
9.5.3 布爾矩陣
9.6 快速傅里葉變換
9.7 小結(jié)
第10章 歸約
10.1 引言
10.2 歸約的例子
10.2.1 簡單字符串匹配問題
10.2.2 特殊代表集
10.2.3 關(guān)于序列比較的歸約
10.2.4 在無向圖中尋找三角形
10.3 有關(guān)線性規(guī)劃的歸約
10.3.1 概述與定義
10.3.2 歸約到線性規(guī)劃的例子
10.4 下界的歸約
10.4.1 尋找簡單多邊形算法復雜度的下界
10.4.2 關(guān)于矩陣的簡單歸約
10.5 常見的錯誤
10.6 小結(jié)
第11章 NP完全問題
11.1 引言
11.2 多項式時間歸約
11.3 非確定性和Cook定理
11.4 NP完全性的證明例子
11.4.1 頂點覆蓋問題
11.4.2 支配集問題
11.4.3 3SAT問題
11.4.4 團問題
11.4.5 3著色問題
11.4.6 一般經(jīng)驗
11.4.7 更多的NP完全問題
11.5 處理NP完全問題的技術(shù)
11.5.1 回溯法和分枝限界法
11.5.2 確保性能的近似算法
11.6 小結(jié)
第12章 并行算法
12.1 引言
12.2 并行計算模型
12.3 共享存儲器算法
12.3.1 并行加
12.3.2 尋找最大數(shù)的算法
12.3.3 并行前綴問題
12.3.4 在鏈表中查尋秩
12.3.5 歐拉遍歷技術(shù)
12.4 連網(wǎng)絡(luò)上的算法
12.4.1 陣列上的排序
12.4.2 排序網(wǎng)絡(luò)
12.4.3 在樹中查找第k個最小元素
12.4.4 網(wǎng)孔上的矩陣乘法
12.4.5 超立方體中的路由
12.5 脈動計算
12.5.1 矩陣與向量相乘
12.5.2 卷積問題
12.5.3 序列的比較
12.6 小結(jié)
部分習題答案
參考文獻