算法设计与分析 - 中国高校教材图书网
|
书名： |
算法设计与分析
|
| ISBN： | 7-5606-1492-2 |
责任编辑： | |
| 作者： |
霍红卫
相关图书
|
装订： | 平装 |
| 印次： | 1-1 |
开本： | 16开 |
| 定价： |
￥15.00
折扣价：￥14.25
折扣：0.95
节省了0.75元
|
字数： |
310千字
|
| 出版社： |
西安电子科技大学出版社 |
页数： |
|
| 出版日期： |
2005-02-01 |
每包册数： |
|
| 国家规划教材： |
|
省部级规划教材： |
|
| 入选重点出版项目： |
|
获奖信息： |
|
|
|
| 内容简介： |
本书系统地介绍了算法设计与分析的基本内容，并对讨论的算法进行了详尽分析。全书共7章，内容包括算法基础、基本算法设计和分析技术(递归和分治法、动态规划、贪心法、回溯法和分枝限界法)，以及NP完全性理论。书中以类高级程序设计语言对算法所做的简明描述，使得稍微具有程序设计语言知识的人即可读懂。此外，书中以大量图例说明每个算法的工作过程，使得算法更加易于理解和掌握。
本书可作为高等院校与计算机相关的各专业“算法设计”课程的教材，也可作为计算机领域的相关科研人员的参考书。此外，本书也可供参加ACM程序设计大赛的算法爱好者参考。
|
| 作者简介： |
|
|
| 章节目录： |
第1章 算法基础 1
1.1 算法 1
1.1.1 冒泡排序 1
1.1.2 循环不变式和冒泡排序算法的正确性 2
1.1.3 伪代码使用约定 3
1.2 算法分析 4
1.2.1 冒泡排序算法分析 5
1.2.2 最坏情况和平均情况分析 6
1.2.3 增长的数量级 6
1.3 算法的运行时间 7
1.3.1 函数增长 7
1.3.2 渐近表示 8
习题 10
第2章 分治法 13
2.1 递归与递归方程 13
2.1.1 递归的概念 13
2.1.2 替换方法 16
2.1.3 递归树方法 17
2.1.4 主方法 18
2.2 分治法 20
2.2.1 分治法的基本思想 20
2.2.2 二叉查找算法 21
2.3 分治法应用实例 24
2.3.1 找最大值与最小值 24
2.3.2 Strassen矩阵乘法 26
2.3.3 整数相乘 27
2.3.4 归并排序 28
2.3.5 快速排序 33
2.3.6 线性时间选择 38
2.3.7 最近点对问题 42
习题 44
第3章 动态规划 49
3.1 用表代替递归 49
3.2 01背包问题 52
3.3 矩阵链乘问题 54
3.4 动态规划的基本元素 60
3.5 备忘录方法 64
3.6 装配线调度问题 70
3.7 最长公共子序列 73
3.8 最优二分检索树 77
3.9 凸多边形最优三角剖分 84
习题 88
第4章 贪心法 98
4.1 背包问题 98
4.2 活动选择问题 101
4.3 贪心算法的基本元素 105
4.4 哈夫曼编码 107
4.5 最小生成树算法 113
4.5.1 最小生成树的基本原理 114
4.5.2 Kruskal算法 117
4.5.3 Prim算法 121
4.5.4 Boruvka算法 125
4.5.5 比较与改进 127
4.6 Dijkstra单源点最短路径算法 127
4.7 贪心算法的理论基础 133
4.8 作业调度问题 136
习题 138
第5章 回溯法 144
5.1 回溯法的基本原理 144
5.2 n皇后问题 148
5.3 子集和数问题 151
5.4 01背包问题 154
5.5 着色问题 157
习题 160
第6章 分枝限界法 163
6.1 分枝限界法的基本思想 163
6.2 01背包问题 167
6.3 作业调度问题 175
习题 178
第7章 NP完全性 180
7.1 P类问题与NP类问题 180
7.1.1 复杂类P和复杂类NP 181
7.1.2 NP中的有趣问题 183
7.2 NP完全性 185
7.2.1 多项式时间归约和NP难度 185
7.2.2 Cook定理 186
7.3 典型的NP完全问题 187
7.3.1 CNF3SAT问题和3SAT问题 189
7.3.2 顶点覆盖问题 191
7.3.3 团问题和集合覆盖问题 193
7.3.4 子集和数问题与背包问题 194
7.3.5 哈密尔顿回路问题和TSP问题 196
习题 199
索引 201
参考文献 206
|
| 精彩片段： |
|
|
| 书 评： |
算法研究是计算机科学研究的核心领域之一。在过去的半个世纪中，算法研究领域取得了大量重要的突破。这些突破引起了人们对算法研究的浓厚兴趣。同时，也使算法的应用领域不断扩大。从天体物理学中的N体问题的模拟到分子生物学中的序列分析，从排版系统到数据压缩，从数据库系统到Internet搜索引擎，算法在其中起着至关重要的作用，已经成为现代软件系统重要的组成部分。
全书分为三大部分： 算法基础(第1章)、基本算法设计和分析技术(第2~6章)，以及NP完全性理论(第7章)。书中较全面地阐述了算法设计与分析方面的诸多理论和实践。本书内容安排如下：
· 第一部分介绍算法的基本概念和渐近表示，函数增长的数量级，证明算法正确性的循环不变式。
· 第二部分讨论递归和分治法、动态规划、贪心法、回溯法和分枝限界法。在分治法中，阐述了递归、递归方程和分治算法的关系，讨论了求解一般递归方程的三种方法。所给出的分治法应用实例包括经典问题(找最大值和最小值、矩阵相乘及整数相乘)、排序问题(归并排序、快速排序)、选择问题和最近点对问题。在动态规划算法中，分别介绍了自顶向下与自底向上的动态规划方法，深入地分析了设计一个动态规划算法时，问题自身所应具有的最优子结构和重叠子问题的性质，给出了动态规划算法的应用实例。在贪心算法中，分析了贪心算法所具有的基本元素，讨论了贪心算法在调度问题、文本压缩和网络算法中的应用。在回溯法和分枝限界法中，讨论了算法的设计思想及其在典型问题中的应用。
· 第三部分以深入浅出的方式，介绍了NP完全性理论，引入了P类问题和NP类问题的定义。通过网络路由器最优配置问题、网络服务器带宽优化问题和Internet网站多次抽签拍卖问题这些现实中的具体问题，来说明我们为什么要研究NP完全问题。同时，还给出了许多重要的NP完全问题的实例。
本书以类高级程序设计语言对算法进行简明描述，使得稍微具有程序设计语言知识的人即可读懂。另外，本书还以大量图例说明每个算法的工作过程，使得算法更加易于理解和掌握。
本书适合作为高等院校与计算机相关的各专业“算法设计”课程的教材，同时也可作为计算机领域的相关科研人员的参考书。此外，本书也可供参加ACM程序设计大赛的算法爱好者参考。
感谢西安电子科技大学出版社对于本书的出版给予的支持。
由于时间仓促及作者水平有限，书中难免有错误及不妥之处，希望读者批评指正。
|
| 其 它： |
|
|
|
中国大学出版社协会 |
首页 |
宏观指导 |
出版社天地 |
图书代办站 |
教材图书信息 |
教材图书评论 |
在线订购 |
教材征订
