《算法设计与分析》求取 ⇩

目录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