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

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