算法设计与分析PDF电子书下载

目录 1

第一章　计算模型和计算复杂性的 1

测度 1

§1.1 引言 1

§1.2　计算复杂性的测度 3

§1.3　随机存取模型 6

§1.3.1 RAM的构造 7

§1.3.2 RAM的指令系统 7

§1.3.3 RAM的工作方式 8

§1.3.4 RAM程序的两种解释 9

§1.4 RAM程序的计算复杂性 12

§1.5.1　直线式程序 15

§1.5 RAM模型的简化 15

§1.5.2　位向量运算 17

§1.5.3　判定树模型 17

§1.6　算法描述语言 18

练习一 21

第二章　数据结构与递归技术 23

§2.1　图和图的表示 23

§2.1.1　邻接矩阵 24

§2.1.2　邻接表和邻接向量 24

§2.1.3　关联矩阵 25

§2.2　树 26

§2.2.1　树的定义 27

§2.2.2 二叉树、完全二叉树和满二叉树 27

§2.2.3　树的遍历 29

§2.3　递归技术 30

§2.3.1　整数分划 31

§2.3.2　树的中根遍历算法 33

§2.3.3　递归过程的实现 34

§2.4　递归方程 36

§2.5　生成函数与求和 39

练习二 42

第三章　分治与平衡 45

§3.1　合并排序 45

§3.2　快速排序 47

§3.3　整数乘法和矩阵乘法 51

§3.3.1　整数乘法 51

§3.3.2　Strassen矩阵乘法 53

§3.4　马的周游路线问题 56

§3.5　顺序统计 59

§3.6　顺序统计的期望时间 61

练习三 63

第四章　排序 65

§4.1　排序的定义 65

§4.2　基数排序 66

§4.3 比较排序的时间下界 70

§4.4　堆选排序 71

§4.5　插入法 75

§4.6　二叉合并 80

练习四 85

§5.1　单源最短路问题 87

第五章 动态规划 87

§5.2　最佳折半查找树 90

§5.3　资源分配问题 95

§5.4　多机系统的可靠性设计 99

§5.5　货郎担问题 101

§5.6　流水作业车间调度 103

练习五 107

第六章　贪心法 110

§6.1 背包问题 110

§6.2　多处理机调度 113

§6.3　带时限的作业调度 115

§6.3.1　顺序选择 116

§6.3.2　最大时限选择 118

§6.3.3　快速调度法 119

§6.4　最佳合并顺序 120

§6.5　磁盘文件的最佳存贮 123

练习六 126

第七章　回溯法 129

§7.1　一般方法 129

§7.2　回溯效能估计 135

§7.3　n后问题 137

§7.4　子集和问题 139

§7.5　图的可着色性 141

§7.6　哈密顿回路 144

练习七 146

§8.1.1　两种基本搜索 149

§8.1　方法概述 149

第八章　分枝限界法 149

§8.1.2　估值函数 150

§8.1.3　LC—搜索的形式描述 153

§8.2　限界 155

§8.3　货郎担问题的另一种解法 160

§8.3.1　归约矩阵与多叉树 160

§8.3.2　分枝边与二叉树 164

§8.4　效能分析 167

练习八 168

第九章 图的算法 170

§9.1　最小代价生成树 170

§9.1.1 Kruskal算法 170

§9.1.2 Prim算法 173

§9.2 图的先深搜索 175

§9.3 图的双连通成份 177

§9.4　路径问题和传递闭包算法 182

§9.5　通路和最短路问题 186

练习九 188

第十章　NP完全问题 191

§10.1　确定型图灵机 191

§10.2　图灵机和RAM模型的相关性 196

§10.3　非确定型图灵机 199

§10.4 P和NP问题类 202

§10.5 NP完全性和COOK定理 204

§10.6 若干NP完全问题 208

练习十 212

参考文献 213