计算机算法设计与分析
点此进入淘宝搜索页搜索分类: 图书,计算机/网络,计算机理论,
作者： 郑丽英等编著
出 版 社： 中国铁道出版社
出版时间： 2009-6-1字数：版次： 1页数： 302印刷时间：开本： 16开印次：纸张：I S B N ： 9787113096298包装： 平装内容简介
计算机算法是计算机科学和计算机应用的核心。无论是计算机系统、系统软件的设计，还是为解决计算机的各种应用课题做的设计都可归结为算法的设计。
本书以计算机算法设计策略为知识单元，围绕算法设计的基本方法，对计算机应用领域中许多常用的非数值算法做了系统的描述，并分析了这些算法所需的时间和空间。全书共分十三章，前七章介绍了递归技术、分治策略、动态规划、贪心法、回溯法及分支限界法等基本设计方法，第八到十三章介绍NP完全理论和NP难题、近似算法、字符串匹配、随机算法、概率算法的相关知识，并对近年来广泛受到关注的网络路由算法及生物信息算法的基本设计方法作了介绍。书中既涉及传统算法的实例分析，更有算法领域热点研究课题追踪，具有较高的实用价值。
本书可作为高等院校计算机及相关专业本科生及研究生的教学用书，也可作为从事计算机科学、工程和应用的工作人员的自学教材和参考书。
目录
第一章导论
第一节算法与程序
第二节算法的描述
第三节算法的评价与优化
第四节算法的复杂度
习题
第二章递归技术
第一节递归过程
第二节递归技术
第三节递归过程的实现
第四节递归函数
第五节递归方程
第六节递归方程求解
第七节递归消除
习题
第三章分治策略
第一节分治法的基本思想
第二节二分搜索技术
第三节大整数的乘法
第四节Strassen矩阵乘法
第五节棋盘覆盖
第六节合并排序
第七节快速排序
第八节找最大和最小元素
习题
第四章动态规划
第一节一般方法
第二节矩阵连乘问题
第三节动态规划算法的基本要素
第四节最长公共子序列
第五节最大子段和
第六节电路布线
第七节流水作业调度
第八节0-1背包问题
第九节整数规划问题
第十节流动推销员（或旅行商）问题
习题
第五章贪心法
第一节 引言
第二节背包问题
第三节最小生成树
第四节单源最短路径问题
第五节文件存储问题
第六节有期限的任务安排问题
习题
第六章回溯法
第一节回溯法的一般方法
第二节n皇后问题
第三节图的着色问题
第四节流水作业车间调度
第五节装载问题
第六节0-1背包问题
第七节马的遍历问题
习题
第七章分支限界法
第一节分支限界法的基本思想
第二节旅行推销员问题
第三节单源最短路径问题
第四节布线问题
第五节0-1背包问题
第六节装载问题
习题
第八章P、NP和NP完全问题
第九章字符串匹配
第十章网络路由算法
第十一章随机地
第十二章概率算法数论算法计算几何
第十三章生物信息处理算法
参考文献
书摘插图
第一章导论
计算机算法是计算机科学和计算机应用的核心，无论是计算机系统、系统软件和解决计算机的各种应用课题都可归结为算法的设计。通常，给了一个问题，我们关心三件事：
1．怎样找到解决此问题的有效算法？
2．如何比较解决同一问题的不同算法？
3．如何判断一个算法的优点？
简单地说，解决这三个问题就是应该掌握常规的或经典的算法设计方法，掌握算法分析的基本手段。
第一节 算法与程序
一、算法的概念及特性
对于计算机科学来说，算法(Algorithm)的概念是至关重要的。例如在一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。
通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法，且满足下述几条性质：
1．输入：有零个或多个由外部提供的量作为算法的输入。
2．输出：算法产生至少一个量作为输出。
3．确定性：组成算法的每条指令是清晰的、无歧义的。
4．可行性：算法中有待实现的运算都相当基本（都是基本运算），每种运算至少在原理上能由人用纸和笔在有限的时间内完成。整数算术运算是可行性运算的一个例子，而实数算术运算则不是可行的，因为某些实数值只能由无限长的十进制数展开式来表示，像这样的两个数相加就违背可行性这一特性。
……
