书籍详情
算法分析与设计
作者：邓向阳、万婷婷
出版社：冶金工业出版社
出版时间：2006-07-01
ISBN：9787502440138
定价：¥30.00
购买这本书可以去
内容简介
本书是根据普通高等教育“十一五”国家级规划教材的指导精神而编写的。算法分析与设计是一门理论性与实践性兼顾的课程，是计算机科学与技术应用的核心，本书主要介绍算法设计的基本方法、基本理论，突出了计算机科学领域中的非数值算法和算法分析的基本知识。本书共分十三章，第一、二章介绍基本概念，第三至十一章介绍分别讨论各类方法。如：树及其操作、集合操作、排序、查找、图、动态规划、贪心法、分治法等。最后讨论了傅氏变换和NP完全问题。为进一步研究算法奠定了基础。本书可作为计算机软件专业本科类和研究生教材，也可供其他从事计算机研究与应用人员参考。
作者简介
暂缺《算法分析与设计》作者简介
目录
第1章 绪论 1
1.1 引论 1
1.2 从问题到程序 3
1.3 抽象数据类型 7
1.4 算法的分析 13
1.4.1 算法设计 13
1.4.2 算法的复杂性测度 14
1.5 算法描述及语句简介 16
1.5.1 C中的标准数据类型 17
1.5.2 C中的运算符 18
1.5.3 C中的语句简介 19
小结 22
练习一 22
一、填空题 22
二、选择题 23
三、简答题 24
第2章 递归技术 25
2.1 递归过程 25
2.2 递归技术 26
2.3 递归过程的实现 29
2.4 递归函数 29
2.5 递归方程 33
2.6 递归方程求解 35
2.6.1 迭代法 36
2.6.2 套用差分方程法 37
2.6.3 套用公式法 38
2.6.4 生成函数与求和 39
2.7 递归消除 42
2.7.1 简单递归消除 42
2.7.2 基于栈的递归消除 44
小结 46
练习二 46
一、填空题 46
二、选择题 46
三、简答题 47
第3章 树 48
3.1 树的结构定义及基本操作 48
3.2 二叉树 51
3.2.1 定义及基本操作 51
3.2.2 二叉树性质 52
3.2.3 二叉树存储结构 54
3.3 遍历二叉树和线索二叉树 57
3.3.1 遍历二叉树 58
3.3.2 线索二叉树 60
3.4 树和森林 64
3.4.1 树的存储结构 64
3.4.2 树和森林的遍历 67
3.4.3 森林与二叉树的转换 68
3.5 树的计数 73
3.6 哈夫曼树 74
小结 77
练习三 78
一、填空题 78
二、选择题 78
三、简答题 79
第4章 图及有向图的应用 81
4.1 基本定义与术语 81
4.2 图的存储结构 84
4.2.1 图的邻接矩阵表示法 84
4.2.2 邻接表表示法 86
4.3 图的遍历 88
4.3.1 深度优先搜索 89
4.3.2 广度优先搜索 91
4.4 单源最短路径问题 93
4.5 顶点对之间最短路径 95
4.6 拓扑排序 97
4.7 关键路径 101
小结 104
练习四 104
一、填空题 104
二、选择题 105
三、简答题 106
第5章 无向图 108
5.1 最小生成树 108
5.1.1 最小生成树性质 109
5.1.2 Prim算法 109
5.1.3 Kruskal算法 111
5.2 无向图遍历 113
5.3 迷宫问题 114
5.4 最短路径 117
小结 120
练习五 120
一、填空题 120
二、选择题 120
三、简答题 121
第6章 查找 123
6.1 基本概念 123
6.2 顺序表查找 124
6.2.1 顺序查找 125
6.2.2 折半查找 126
6.3 分块查找 128
6.4 树表 130
6.5 散列表的查找 141
6.5.1 散列表的概念 142
6.5.2 散列函数的构造 142
6.5.3 处理冲突的方法 144
6.5.4 散列表分析 145
小结 146
练习六 146
一、填空题 146
二、选择题 147
三、简答题 149
第7章 排序 150
7.1 排序的定义 150
7.2 交换排序 151
7.2.1 冒泡法排序 151
7.2.2 快速排序 153
7.3 插入法排序 156
7.3.1 直接插入排序 156
7.3.2 希尔排序 157
7.4 选择排序 158
7.4.1 简单选择排序 158
7.4.2 堆排序 159
7.5 归并排序 161
7.5.1 排序文件的合并 162
7.5.2 二路归并排序 162
7.6 基数排序 163
7.7 各种内部排序方法的比较和选择 165
小结 166
练习七 166
一、填空题 166
二、选择题 167
三、简答题 168
第8章 集合操作 170
8.1 集合的基本概念 170
8.1.1 集合的概念 170
8.1.2 集合的表示法 170
8.1.3 常见的一些集合 171
8.1.4 集合间的关系 171
8.1.5 集合例题 171
8.2 集合的基本运算 172
8.2.1 集合的运算 172
8.2.2 文氏图 173
8.2.3 集合运算律 174
8.2.4 集合论进一步研究 175
8.3 链表结构与顺序搜索 176
8.3.1 链表结构 176
8.3.2 链表的运算 179
小结 181
练习八 181
一、填空题 181
二、选择题 181
三、简答题 182
第9章 动态规划 183
9.1 动态规划法的概念 183
9.1.1 动态规划模型的基本要素 184
9.1.2 动态规划的基本定理和基本方程 184
9.1.3 动态规划法的基本步骤 186
9.1.4 动态规划与其他算法的比较 186
9.2 计算二项式系数 187
9.3 最佳折半查找树 188
9.3.1 查找树的期望深度 189
9.3.2 最佳折半查找树的动态规划算法 190
9.4 资源分配问题 191
9.5 多机系统的可靠性设计 193
9.6 背包问题 195
9.7 货郎担问题 196
小结 198
练习九 198
一、填空题 198
二、选择题 199
三、简答题 199
第10章 贪心法 201
10.1 贪心算法 201
10.2 背包问题 202
10.3 多处理机调度 205
10.4 单源最短路径 210
10.5 最佳合并顺序 212
小结 213
练习十 214
一、填空题 214
二、选择题 214
三、简答题 214
第11章 回溯法 215
11.1 一般方法 215
11.2 效能统计 218
11.3 哈密尔顿回路 220
11.4 图的可着色性 223
11.5 子集和问题 224
小结 225
练习十一 225
一、填空题 225
二、选择题 225
三、简答题 225
第12章 分治与平衡 227
12.1 分治算法 227
12.2 合并排序 230
12.3 快速排序 231
12.4 整数乘法和矩阵乘法 237
12.4.1 整数乘法 237
12.4.2 strassen矩阵乘法 239
12.5 马的周游路线问题 241
小结 243
练习十二 244
一、填空题 244
二、选择题 244
三、简答题 244
第13章 NP完全问题 245
13.1 确定图灵机 245
13.2 不确定图灵机 249
13.3 P和NP类 251
13.4 NP完全性和COOK定理 254
13.5 若干NP完全问题 258
小结 260
练习十三 261
一、填空题 261
二、选择题 261
三、简答题 261
参考文献 262
1.1 引论 1
1.2 从问题到程序 3
1.3 抽象数据类型 7
1.4 算法的分析 13
1.4.1 算法设计 13
1.4.2 算法的复杂性测度 14
1.5 算法描述及语句简介 16
1.5.1 C中的标准数据类型 17
1.5.2 C中的运算符 18
1.5.3 C中的语句简介 19
小结 22
练习一 22
一、填空题 22
二、选择题 23
三、简答题 24
第2章 递归技术 25
2.1 递归过程 25
2.2 递归技术 26
2.3 递归过程的实现 29
2.4 递归函数 29
2.5 递归方程 33
2.6 递归方程求解 35
2.6.1 迭代法 36
2.6.2 套用差分方程法 37
2.6.3 套用公式法 38
2.6.4 生成函数与求和 39
2.7 递归消除 42
2.7.1 简单递归消除 42
2.7.2 基于栈的递归消除 44
小结 46
练习二 46
一、填空题 46
二、选择题 46
三、简答题 47
第3章 树 48
3.1 树的结构定义及基本操作 48
3.2 二叉树 51
3.2.1 定义及基本操作 51
3.2.2 二叉树性质 52
3.2.3 二叉树存储结构 54
3.3 遍历二叉树和线索二叉树 57
3.3.1 遍历二叉树 58
3.3.2 线索二叉树 60
3.4 树和森林 64
3.4.1 树的存储结构 64
3.4.2 树和森林的遍历 67
3.4.3 森林与二叉树的转换 68
3.5 树的计数 73
3.6 哈夫曼树 74
小结 77
练习三 78
一、填空题 78
二、选择题 78
三、简答题 79
第4章 图及有向图的应用 81
4.1 基本定义与术语 81
4.2 图的存储结构 84
4.2.1 图的邻接矩阵表示法 84
4.2.2 邻接表表示法 86
4.3 图的遍历 88
4.3.1 深度优先搜索 89
4.3.2 广度优先搜索 91
4.4 单源最短路径问题 93
4.5 顶点对之间最短路径 95
4.6 拓扑排序 97
4.7 关键路径 101
小结 104
练习四 104
一、填空题 104
二、选择题 105
三、简答题 106
第5章 无向图 108
5.1 最小生成树 108
5.1.1 最小生成树性质 109
5.1.2 Prim算法 109
5.1.3 Kruskal算法 111
5.2 无向图遍历 113
5.3 迷宫问题 114
5.4 最短路径 117
小结 120
练习五 120
一、填空题 120
二、选择题 120
三、简答题 121
第6章 查找 123
6.1 基本概念 123
6.2 顺序表查找 124
6.2.1 顺序查找 125
6.2.2 折半查找 126
6.3 分块查找 128
6.4 树表 130
6.5 散列表的查找 141
6.5.1 散列表的概念 142
6.5.2 散列函数的构造 142
6.5.3 处理冲突的方法 144
6.5.4 散列表分析 145
小结 146
练习六 146
一、填空题 146
二、选择题 147
三、简答题 149
第7章 排序 150
7.1 排序的定义 150
7.2 交换排序 151
7.2.1 冒泡法排序 151
7.2.2 快速排序 153
7.3 插入法排序 156
7.3.1 直接插入排序 156
7.3.2 希尔排序 157
7.4 选择排序 158
7.4.1 简单选择排序 158
7.4.2 堆排序 159
7.5 归并排序 161
7.5.1 排序文件的合并 162
7.5.2 二路归并排序 162
7.6 基数排序 163
7.7 各种内部排序方法的比较和选择 165
小结 166
练习七 166
一、填空题 166
二、选择题 167
三、简答题 168
第8章 集合操作 170
8.1 集合的基本概念 170
8.1.1 集合的概念 170
8.1.2 集合的表示法 170
8.1.3 常见的一些集合 171
8.1.4 集合间的关系 171
8.1.5 集合例题 171
8.2 集合的基本运算 172
8.2.1 集合的运算 172
8.2.2 文氏图 173
8.2.3 集合运算律 174
8.2.4 集合论进一步研究 175
8.3 链表结构与顺序搜索 176
8.3.1 链表结构 176
8.3.2 链表的运算 179
小结 181
练习八 181
一、填空题 181
二、选择题 181
三、简答题 182
第9章 动态规划 183
9.1 动态规划法的概念 183
9.1.1 动态规划模型的基本要素 184
9.1.2 动态规划的基本定理和基本方程 184
9.1.3 动态规划法的基本步骤 186
9.1.4 动态规划与其他算法的比较 186
9.2 计算二项式系数 187
9.3 最佳折半查找树 188
9.3.1 查找树的期望深度 189
9.3.2 最佳折半查找树的动态规划算法 190
9.4 资源分配问题 191
9.5 多机系统的可靠性设计 193
9.6 背包问题 195
9.7 货郎担问题 196
小结 198
练习九 198
一、填空题 198
二、选择题 199
三、简答题 199
第10章 贪心法 201
10.1 贪心算法 201
10.2 背包问题 202
10.3 多处理机调度 205
10.4 单源最短路径 210
10.5 最佳合并顺序 212
小结 213
练习十 214
一、填空题 214
二、选择题 214
三、简答题 214
第11章 回溯法 215
11.1 一般方法 215
11.2 效能统计 218
11.3 哈密尔顿回路 220
11.4 图的可着色性 223
11.5 子集和问题 224
小结 225
练习十一 225
一、填空题 225
二、选择题 225
三、简答题 225
第12章 分治与平衡 227
12.1 分治算法 227
12.2 合并排序 230
12.3 快速排序 231
12.4 整数乘法和矩阵乘法 237
12.4.1 整数乘法 237
12.4.2 strassen矩阵乘法 239
12.5 马的周游路线问题 241
小结 243
练习十二 244
一、填空题 244
二、选择题 244
三、简答题 244
第13章 NP完全问题 245
13.1 确定图灵机 245
13.2 不确定图灵机 249
13.3 P和NP类 251
13.4 NP完全性和COOK定理 254
13.5 若干NP完全问题 258
小结 260
练习十三 261
一、填空题 261
二、选择题 261
三、简答题 261
参考文献 262
猜您喜欢
