算法设计与分析——C++语言描述(“十一五”规划教材)

书名：
作者：
ISBN号：

《现代交换原理与技术（第2版）》

《Pro/ENGINEER机械设计与制造》

《数字与模拟通信系统（第七版）（英文版）》

《应用统计学》

《芯片制造——半导体工艺制程实用教程（第五版）》

《算法设计与分析——C++语言描述(“十一五”规划教材)》

点击此处查看完整封面	著者：
	作译者：	陈慧南编著
	ISBN号：	7-121-02592-2
	出版日期：	2006-05
	丛书名：	新编计算机类本科规划教材
	字数：524.8千字		定价：￥26.80元
	页码：314		会员价：￥21.44元
	开本：16开		放入购物篮
	库存：有

内容简介

　　本书内容分为3部分：算法和算法分析，算法设计策略及求解困难问题。第1部分介绍问题求解方法、算法复杂度和分析、递归算法和递推关系；第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法；第3部分介绍NP完全问题、随机算法、近似算法和密码算法。书中还介绍了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法，并对现代密码学做了简要论述。
本书结构清晰、内容翔实、逻辑严谨、深入浅出。书中算法有完整的C++程序，程序构思精巧，且有详细注释，所有程序都已在VC++环境下编译通过并能正确运行，它们既是学习算法设计的示例，也能使复杂抽象的算法设计更易为学习者理解和掌握。书中包含大量实例和图示，并附丰富的习题，便于自学。

图书目录

第1部分  算法和算法分析
第1章  算法问题求解基础
1.1  算法概述
1.1.1  什么是算法
1.1.2  为什么学习算法
1.2  问题求解方法
1.2.1  问题和问题求解
1.2.2  问题求解过程
1.2.3  系统生命周期
1.3  算法设计与分析
1.3.1  算法问题求解过程
1.3.2  如何设计算法
1.3.3  如何表示算法
1.3.4  如何确认算法
1.3.5  如何分析算法
1.4  递归和归纳
1.4.1  递归
1.4.2  递归算法示例
1.4.3  归纳证明
本章小结
习题1
第2章  算法分析基础
2.1  算法复杂度
2.1.1  什么是好的算法
2.1.2  影响程序运行时间的因素
2.1.3  算法的时间复杂度
2.1.4  使用程序步分析算法
2.1.5  算法的空间复杂度
2.2  渐近表示法
2.2.1  大O记号
2.2.2  W记号
2.2.3  Q记号
2.2.4  小o记号
2.2.5  算法按时间复杂度分类
2.3  递推关系
2.3.1  递推方程
2.3.2  替换方法
2.3.3  迭代方法
2.3.4  主方法
2.4  分摊分析
2.4.1  聚集方法
2.4.2  会计方法
2.4.3  势能方法
本章小结
习题2
第3章  伸展树与跳表
3.1  伸展树
3.1.1  二叉搜索树
3.1.2  自调节树和伸展树
3.1.3  伸展操作
3.1.4  伸展树类
3.1.5  旋转的实现
3.1.6  插入运算的实现
3.1.7  分摊分析
3.2  跳表
3.2.1  什么是跳表
3.2.2  跳表类
3.2.3  级数分配
3.2.4  插入运算的实现
3.2.5  性能分析
本章小结
习题3
第2部分  算法设计策略
第4章  基本搜索和遍历方法
4.1  基本概念
4.2  图的搜索和遍历
4.2.1  搜索方法
4.2.2  邻接表类
4.2.3  广度优先搜索
4.2.4  深度优先搜索
4.3  双连通分量
4.3.1  基本概念
4.3.2  发现关节点
4.3.3  构造双连通图
4.4  与或图
4.4.1  问题分解
4.4.2  判断与或树是否可解
4.4.3  构建解树
本章小结
习题4
第5章  分治法
5.1  一般方法
5.1.1  分治法的基本思想
5.1.2  算法分析
5.1.3  数据结构
5.2  求最大最小元
5.2.1  分治法求解
5.2.2  时间分析
5.3  二分搜索
5.3.1  分治法求解
5.3.2  对半搜索
5.3.3  二叉判定树
5.3.4  搜索算法的时间下界
5.4  排序问题
5.4.1  合并排序
5.4.2  快速排序
5.4.3  排序算法的时间下界
5.5  选择问题
5.5.1  分治法求解
5.5.2  随机选择主元
5.5.3  线性时间选择算法
5.5.4  时间分析
5.5.5  允许重复元素的选择算法
5.6  斯特拉森矩阵乘法
5.6.1  分治法求解
5.6.2  斯特拉森分治法
本章小结
习题5
第6章  贪心法
6.1  一般方法
6.2  背包问题
6.2.1  问题描述
6.2.2  贪心法求解
6.2.3  算法正确性
6.3  带时限的作业排序
6.3.1  问题描述
6.3.2  贪心法求解
6.3.3  算法正确性
6.3.4  可行性判定
6.3.5  作业排序贪心算法
6.3.6  一种改进算法
6.4  最佳合并模式
6.4.1  问题描述
6.4.2  贪心法求解
6.4.3  算法正确性
6.5  最小代价生成树
6.5.1  问题描述
6.5.2  贪心法求解
6.5.3  普里姆算法
6.5.4  克鲁斯卡尔算法
6.5.5  算法正确性
6.6  单源最短路径
6.6.1  问题描述
6.6.2  贪心法求解
6.6.3  迪杰斯特拉算法
6.6.4  算法正确性
6.7  磁带最优存储
6.7.1  单带最优存储
6.7.2  多带最优存储
6.8   贪心法的基本要素
6.8.1  最优量度标准
6.8.2  最优子结构
本章小结
习题6
第7章  动态规划法
7.1  一般方法和基本要素
7.1.1  一般方法
7.1.2  基本要素
7.1.3  多段图问题
7.1.4  资源分配问题
7.1.5  关键路径问题
7.2  每对结点间的最短路径
7.2.1  问题描述
7.2.2  动态规划法求解
7.2.3  弗洛伊德算法
7.2.4  算法正确性
7.3  矩阵连乘
7.3.1  问题描述
7.3.2  动态规划法求解
7.3.3  矩阵连乘算法
7.3.4  备忘录方法
7.4  最长公共子序列
7.4.1  问题描述
7.4.2  动态规划法求解
7.4.3  最长公共子序列算法
7.4.4  算法的改进
7.5  最优二叉搜索树
7.5.1  问题描述
7.5.2  动态规划法求解
7.5.3  最优二叉搜索树算法
7.6  0/1背包
7.6.1  问题描述
7.6.2  动态规划法求解
7.6.3  0/1背包算法框架
7.6.4  0/1背包算法
7.6.5  性能分析
7.6.6  使用启发式方法
7.7  流水作业调度
7.7.1  问题描述
7.7.2  动态规划法求解
7.7.3  Johnson算法
本章小结
习题7
第8章  回溯法
8.1  一般方法
8.1.1  基本概念
8.1.2  剪枝函数和回溯法
8.1.3  回溯法的效率分析
8.2  n-皇后
8.2.1  问题描述
8.2.2  回溯法求解
8.2.3  n-皇后算法
8.2.4  时间分析
8.3  子集和数
8.3.1  问题描述
8.3.2  回溯法求解
8.3.3  子集和数算法
8.4  图的着色
8.4.1  问题描述
8.4.2  回溯法求解
8.4.3  图着色算法
8.4.4  时间分析
8.5  哈密顿环
8.5.1  问题描述
8.5.2  哈密顿环算法
8.6  0/1背包
8.6.1  问题描述
8.6.2  回溯法求解
8.6.3  限界函数
8.6.4  0/1背包算法
8.7  批处理作业调度
8.7.1  问题描述
8.7.2  回溯法求解
8.7.3  批处理作业调度算法
本章小结
习题8
第9章  分枝限界法
9.1  一般方法
9.1.1  分枝限界法概述
9.1.2  LC分枝限界法
9.1.3  15谜问题
9.2  求最优解的分枝限界法
9.2.1  上下界函数
9.2.2  FIFO分枝限界法
9.2.3  LC分枝限界法
9.3  带时限的作业排序
9.3.1  问题描述
9.3.2  分枝限界法求解
9.3.3  带时限作业排序算法
9.4  0/1背包
9.4.1  问题描述
9.4.2  分枝限界法求解
9.4.3  0/1背包算法
9.5  旅行商问题
9.5.1  问题描述
9.5.2  分枝限界法求解
9.6  批处理作业调度
9.6.1  问题描述
9.6.2  分枝限界法求解
9.6.3  批处理作业调度算法
本章小结
习题9
第3部分  求解困难问题
第10章  NP完全问题
10.1  基本概念
10.1.1  不确定算法和不确定机
10.1.2  可满足性问题
10.1.3  P类和NP类问题
10.1.4  NP难度和NP完全问题
10.2  Cook定理和证明
10.2.1  Cook定理
10.2.2  简化的不确定机模型
10.2.3  证明Cook定理
10.3  一些典型的NP完全问题
10.3.1  最大集团
10.3.2  顶点覆盖
10.3.3  3元CNF可满足性
10.3.4  图的着色数
10.3.5  有向哈密顿环
10.3.6  恰切覆盖
10.3.7  子集和数
10.3.8  分划问题
本章小结
习题10
第11章  随机算法
11.1  基本概念
11.1.1  随机算法概述
11.1.2  随机数发生器
11.1.3  随机算法分类
11.2  拉斯维加斯算法
11.2.1  标识重复元素算法
11.2.2  性能分析
11.3  蒙特卡罗算法
11.3.1  素数测试问题
11.3.2  伪素数测试
11.3.3  米勒-拉宾算法
11.3.4  性能分析
11.4  舍伍德算法
11.4.1  随机快速排序算法
11.4.2  舍伍德算法的其他应用
本章小结
习题11
第12章  近似算法
12.1  近似算法的性能
12.1.1  基本概念
12.1.2  绝对性能保证
12.1.3  相对性能保证
12.1.4  近似方案
12.2  绝对近似算法
12.2.1  最多程序存储问题
12.2.2  NP难度绝对近似算法
12.3  e-近似算法
12.3.1  顶点覆盖近似算法
12.3.2  旅行商问题
12.3.3  NP难度e-近似旅行商问题
12.3.4  具有三角不等式性质的旅行商问题
12.3.5  任务调度近似算法
12.4  e(n)-近似算法
12.4.1  集合覆盖问题
12.4.2  集合覆盖近似算法
12.4.3  ln(n)-近似算法
12.5  多项式时间近似方案
12.5.1  任务调度近似方案
12.5.2  多项式时间近似方案
12.6  子集和数的完全多项式时间近似方案
12.6.1  子集和数指数时间算法
12.6.2  完全多项式时间近似方案
本章小结
习题12
第13章  密码算法
13.1  信息安全和密码学
13.1.1  信息安全
13.1.2  什么是密码
13.1.3  密码体制
13.2  数论初步
13.3  背包密码算法
13.3.1  背包算法
13.3.2  超递增背包
13.3.3  由私人密钥产生公开密钥
13.3.4  加密方法
13.3.5  解密方法
13.3.6  背包安全性
13.4  RSA算法
13.4.1  RSA算法概述
13.4.2  RSA的安全性
13.5  散列函数和消息认证
13.5.1  散列函数
13.5.2  散列函数结构
13.5.3  消息认证
13.6  数字签名
13.6.1  RSA数字签名体制
13.6.2  需仲裁数字签名
本章小结
习题13
附录A  专有名词中英文对照表
附录B  C++程序设计概要
B.1  函数与参数传递
B.2  动态存储分配
B.3  类与对象
B.4  函数和运算符重载
B.5  继承性和派生类
B.6  多态性、虚函数和动态联编
B.7  纯虚函数和抽象类
B.8  模板函数和模板类
B.9  友元函数和友元类
参考文献

序言/前言

前    言
    算法设计与分析不仅是计算机科学与技术专业学生的必备知识，也是计算机应用工作者必不可少的基础知识。掌握扎实的算法设计与分析理论和方法有助于理工科学生进一步学习计算机技术，适应更广泛的职业挑战。
    计算学科教学计划2001（Computing Curricula 2001，简称CC2001）将计算机学科分成14个领域，每个领域分成若干个知识单元，每个知识单元又包括若干个主题。CC2001强调算法，重视算法设计与分析能力和程序设计能力。计算机算法的基本内容主要包含在算法与复杂性（Algorithm And Complexity，简称AL）和程序设计基础（Programming Fundamental，简称PL）等知识领域中。在CC2001建议的计算机科学与技术专业的280个核心学时中，程序设计与算法方面分配90个核心学时，约占总核心学时的32.1%。
    算法领域涉及的内容广泛，通常包括迄今为止，算法学家们所设计的许多基本和经典算法，如排序、搜索、图算法、组合问题算法、字符串算法和大量的数值算法，算法问题求解、算法分析技术和常用的算法设计策略，可计算性理论和问题复杂性的研究，如计算模型、NP完全问题和问题复杂度下界理论。近年来，算法研究在随机算法、近似算法、加密算法、分布式算法和并行算法，以及其他算法方面也都有很多新成果。
    作为“算法设计与分析”课程教材，根据我国在算法与数据结构方面课程开设的实际情况，本书不再重复属于我国传统“数据结构”课程中的基本数据结构和算法的内容，但选用快速排序等在“数据结构”课程中已学过的若干排序、搜索和图算法，它们被作为算法设计策略和算法分析的实例使用。这种做法不是内容的简单重复，而是必要的和有益的深化。以学生熟知的知识为基础，介绍新知识，可使学生更容易理解和接受新的算法知识。
    算法知识理论性较强，涉及的范围又很广，给学习和理解造成困难。为了将本书写成条理清晰、内容翔实、逻辑严谨、深入浅出的“算法设计与分析”教材，作者做了以下努力。
    首先，本书分3部分组织内容，力求做到结构清晰、内容取舍恰当。
    其次，书中算法都有完整的C++程序，程序结构清楚，构思精巧，对程序代码都做了详细注释，所有程序都已在VC++环境下编译通过并能正确运行，它们既是学习算法设计的示例，也是很好的C++程序设计示例。
    此外，本书通过大量实例和图示介绍算法，并有丰富的习题，便于自学。
    这样做的目的是在保持算法科学性的同时，加强其技术性和实用性，也降低算法学习的难度，使复杂抽象的算法设计更容易为学习者理解和掌握。这也体现了计算机学科的科学性和工程性、理论性和实践性并重的学科特点。
    全书包括3部分：算法和算法分析、算法设计策略及求解困难问题。
    第1部分介绍算法概念、算法问题分类和问题求解方法，算法复杂度、递归技术，还介绍了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法。
    第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法。对于每种算法设计策略，通常先介绍一般方法，然后使用该策略解决若干经典的算法问题。
    第3部分介绍NP完全问题、随机算法、近似算法，并对现代密码学和数论算法也做了简要论述。
    本书作者在南京邮电大学讲授“算法设计与分析”和“数据结构”课程多年。本书是在作者编写出版的多本关于算法与数据结构领域教材的基础上，参考了近年来国内外多种算法设计与分析的优秀教材编写而成的。本书的编写得到了电子工业出版社的大力支持，并得到了南京邮电大学和计算机学院领导的推荐和关心，在此表示衷心感谢。
    书中若有不妥之处，敬请读者批评指正。
    
    
    作  者  
    2006年3月

读者书评

欢迎您对我社的图书发表您的高见！