計(jì)算機(jī)算法

第1章 緒論
1.1 算法的時(shí)間復(fù)雜性
1.2 算法的空間復(fù)雜性
1.3 兩個(gè)算法的分析實(shí)例
1.4 算法設(shè)計(jì)技術(shù)
1.4.1 分治方法
1.4.2 回溯法
1.4.3 貪心法
1.4.4 動(dòng)態(tài)規(guī)劃法
1.4.5 分支限界法
1.4.6 遞歸方程解的展開(kāi)式
習(xí)題
第2章 排序算法
2.1 插入算法
2.1.1 直接插入排序
2.1.2 折半插入排序
2.1.3 希爾排序
2.2 選擇排序
2.2.1 直接選擇排序
2.2.2 堆排序
2.3 交換排序
2.3.1 冒泡排序
2.3.2 快速排序
2.4 歸并排序
2.5 基數(shù)排序
2.6 外部排序
2.6.1 歸并排序
2.6.2 多步歸并算法
2.7 各種內(nèi)部排序方法的比較討論
習(xí)題
第3章 查找樹(shù)
3.1 二分查找樹(shù)
3.2 2—3—4樹(shù)
3.3 紅黑樹(shù)
3.4 8樹(shù)
習(xí)題
第4章 圖的算法
4.1 基本概念
4.2 圖的表示方法
4.3 圖的遍歷
4.4 所有點(diǎn)對(duì)之間的最短路徑
4.5 最小生成樹(shù)
習(xí)題
第5章 串匹配
5.1 簡(jiǎn)單的字符串匹配算法
5.2 Knuth—Morris—Pratt（KMP）字符串匹配
5.3 BM算法
5.4 RK算法
習(xí)題
第6章 分治算法
6.1 二分搜索
6.2 求最大元和最小元
6.3 大整數(shù)乘法
6.4 矩陣乘法算法
6.5 矩陣乘積的Winograd算法
習(xí)題
第7章 貪心算法
7.1 背包問(wèn)題
7.2 帶時(shí)限的作業(yè)排序
7.3 單源最短路徑問(wèn)題
7.4 最小生成樹(shù)問(wèn)題
7.5 Dijkstra各點(diǎn)之間最短路徑的優(yōu)化算法
習(xí)題
第8章 回溯法
8.1 n皇后問(wèn)題
8.2 圖的著色問(wèn)題
8.3 0—1背包問(wèn)題
8.4 哈密頓回路
8.5 子集和數(shù)
習(xí)題
第9章 動(dòng)態(tài)規(guī)劃法
9.1 最長(zhǎng)公共子序列問(wèn)題
9.2 矩陣連乘問(wèn)題
9.3 多階段決策過(guò)程最優(yōu)化問(wèn)題
9.4 0—1背包問(wèn)題
9.5 流水線調(diào)度問(wèn)題
習(xí)題
第10章 分支限界法
10.1 分支限界的策略
10.2 0－1背包問(wèn)題
習(xí)題
第11章 概率算法
11.l 隨機(jī)數(shù)
11.2 數(shù)值概率算法
11.3 蒙特卡羅算法
11.4 拉斯維加斯算法
11.5 舍伍德算法
習(xí)題
第12章 幾何問(wèn)題算法
12.1 直線相交問(wèn)題的算法
12.2 點(diǎn)是否包含在多邊形內(nèi)部
12.3 求凸包問(wèn)題
習(xí)題
第13章 NP完全問(wèn)題
13.1 不確定算法和不確定圖靈機(jī)
13.2 NP難度和NP完全問(wèn)題
13.3 COOK定理
13.4 幾個(gè)NP完全問(wèn)題
習(xí)題
第14章 密碼學(xué)算法
14.1 什么是密碼
14.2 基本數(shù)論
14.3 背包公鑰密碼
14.4 RSA算法
14.5 數(shù)字簽名
習(xí)題
第15章 近似算法
15.1 任務(wù)調(diào)度近似算法.
15.2 頂點(diǎn)覆蓋問(wèn)題近似算法
15.3 旅行商問(wèn)題的近似解
15.4 子集和數(shù)問(wèn)題的近似算法
習(xí)題
第16章 并行算法
16.1 并行計(jì)算機(jī)
16.2 并行算法的基本概念
16.3 并行算法的描述
16.4 SIMD-SM上的非線性方程求根同步并行算法
16.5 SIMD-SM上的同步并行求和算法
16.6 SIMD-CC超立方機(jī)器上的同步并行求和算法
16.7 MIMD-SM上的異步并行求和算法
習(xí)題
參考文獻(xiàn)