算法设计与分析（第二版）

图书标准信息

• 作者 霍红卫 著
• 出版社 西安电子科技大学出版社
• 出版时间 2010-08
• 版次 2
• ISBN 9787560624594
• 定价 21.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 232页
• 字数 353千字

【内容简介】

《算法设计与分析（第2版）》系统地介绍了算法设计与分析的基本内容，并对讨论的算法进行了详尽分析。全书共8章，内容包括算法基础、基本算法设计和分析技术（分治法、动态规划、贪心法、回溯法和分枝限界法）、图算法以及NP完全性理论。书中以类高级程序设计语言对算法所作的简明描述，使得稍微具有程序设计语言知识的人即可读懂。此外，书中以大量图例说明每个算法的工作过程，使得算法更加易于理解和掌握。
《算法设计与分析（第2版）》可作为高等院校与计算机相关的各专业“算法设计”课程的教材，也可作为计算机领域的相关科研人员的参考书。此外，本书还可供参加ACM程序设计大赛的算法爱好者参考。

【目录】

第1章算法基础
1.1算法
1.1.1冒泡排序
1.1.2循环不变式和冒泡排序算法的正确性
1.1.3伪代码使用约定
1.2算法分析
1.2.1冒泡排序算法分析
1.2.2最坏情况和平均情况分析
1.2.3增长的数量级
1.3算法的运行时间
1.3.1函数增长
1.3.2渐近表示
习题
第2章分治法
2.1递归与递归方程
2.1.1递归的概念
2.1.2替换方法
2.1.3递归树方法
2.1.4主方法
2.2分治法
2.2.1分治法的基本思想
2.2.2二叉查找算法
2.3分治法应用实例
2.3.1找最大值与最小值
2.3.2Strassen矩阵乘法
2.3.3整数相乘
2.3.4归并排序
2.3.5快速排序
2.3.6线性时间选择
2.3.7最近点对问题
习题
第3章动态规划
3.1用表代替递归
3.2－1背包问题
3.3矩阵链乘问题
3.4动态规划的基本元素
3.5备忘录方法
3.6装配线调度问题
3.7最长公共子序列
3.8最优二分检索树
3.9凸多边形最优三角剖分
习题
第4章贪心法
4.1背包问题
4.2活动选择问题
4.3贪心算法的基本元素
4.4哈夫曼编码
4.5最小生成树算法
4.5.1最小生成树的基本原理
4.5.2Kruskal算法
4.5.3Prim算法
4.5.4Boruvka算法
4.5.5比较与改进
4.6贪心算法的理论基础
4.7作业调度问题
习题
第5章回溯法
5.1回溯法的基本原理
5.2n-皇后问题
5.3子集和数问题
5.4－1背包问题
5.5着色问题
习题
第6章分枝限界法
6.1分枝限界法的基本思想
6.2－1背包问题
6.3作业调度问题
习题
第7章图算法
7.1图的表示
7.2广度优先搜索
7.3Dijkstra算法
7.4BellmanFord算法
7.5FloydWarshall算法
习题
第8章NP完全性
8.1P类问题和NP类问题
8.1.1复杂类P和复杂类NP
8.1.2NP中的有趣问题
8.2NP完全性
8.2.1多项式时间归约和NP难度
8.2.2Cook定理
8.3典型的NP完全问题
8.3.1CNF3SAT问题和3SAT问题
8.3.2顶点覆盖问题
8.3.3团问题和集合覆盖问题
8.3.4子集和数问题与背包问题
8.3.5哈密尔顿回路问题和TSP问题
习题
附录A习题选解
附录B索引
参考文献