计算机算法设计与分析

出版时间：2009-6  出版社：中国铁道出版社  作者：郑丽英　等编著  

前言

算法设计与分析是计算机科学的一个主要研究领域。本课程是计算机、管理信息系统、系统工程、应用数学和计算数学等专业高年级学生和研究生的一门重要专业课程。它的主要目的是讲授在计算机应用中常常遇到的实际问题的有效解法，讲授设计和分析各种算法的基本原理、方法和技术，以培养读者在选择或设计一个算法时，思考下列问题：这个算法是否有效？这个算法有多好？是否还有更好的算法？用什么方法和技巧去获得更好的算法？从而使得所设计算法的时空复杂性最优，进而为编写高效的程序、开发优秀软件奠定基础。本书旨在全面介绍计算机算法设计与分析的內容。力争做到取材先进、內容实用、重点突出、少而精，便于自学；并注意收录一些典型问题的最新研究成果。期望读者通过本课程的学习，接受算法设计基础研究的初步训练，了解算法设计的最新应用领域，培养独立开展科研工作的能力和创新意识。本书可作为计算机科学及相关专业高年级学生和研究生课程的教材；也可供其他从事计算机研究与应用的人员参考。全书共分十三章。第一章介绍算法分析的基本概念和基本理论，介绍设计算法的基本技术和分析算法复杂性的基本方法；第二章介绍递归技术，重点讲述了递归方程的解法；第三章介绍分治策略，它是设计有效算法最常用的策略，也是必须掌握的方法；第四章介绍动态规划算法，以具体实例详述动态规划算法的设计思想以及算法的设计要点；第五章介绍贪心算法，它是一种重要的算法设计策略，按其设计出的许多算法能导致最优解；第六章和第七章分别介绍了回溯法和分支限界法，这两章所介绍的算法适合于处理难解问题，其解题的思想各有特色，值得学习和掌握；第八章介绍了NP完全问题及近似算法，重点剖析一些典型、能启迪人们思维的算法设计思想；第九章介绍了字符串精确匹配和近似匹配技术，也重点剖析一些典型、能启迪人们思维的算法设计思想；第十章介绍了网络路由算法，这是当前计算机网络应用研究中受到广泛关注的研究內容。

内容概要

计算机算法是计算机科学和计算机应用的核心。无论是计算机系统、系统软件的设计，还是为解决计算机的各种应用课题做的设计都可归结为算法的设计。    本书以计算机算法设计策略为知识单元，围绕算法设计的基本方法，对计算机应用领域中许多常用的非数值算法做了系统的描述，并分析了这些算法所需的时间和空间。全书共分十三章，前七章介绍了递归技术、分治策略、动态规划、贪心法、回溯法及分支限界法等基本设计方法，第八到十三章介绍NP完全理论和NP难题、近似算法、字符串匹配、随机算法、概率算法的相关知识，并对近年来广泛受到关注的网络路由算法及生物信息算法的基本设计方法作了介绍。书中既涉及传统算法的实例分析，更有算法领域热点研究课题追踪，具有较高的实用价值。    本书可作为高等院校计算机及相关专业本科生及研究生的教学用书，也可作为从事计算机科学、工程和应用的工作人员的自学教材和参考书。

书籍目录

第一章　导论　第一节　算法与程序  第二节　算法的描述  第三节　算法的评价与优化  第四节　算法的复杂度  习题第二章　递归技术  第一节　递归过程  第二节　递归技术  第三节　递归过程的实现  第四节　递归函数  第五节　递归方程  第六节　递归方程求解  第七节　递归消除  习题第三章　分治策略  第一节　分治法的基本思想  第二节　二分搜索技术  第三节　大整数的乘法  第四节　Strassen矩阵乘法  第五节　棋盘覆盖  第六节　合并排序  第七节　快速排序  第八节　找最大和最小元素  习题第四章　动态规划  第一节　一般方法  第二节　矩阵连乘问题　第三节　动态规划算法的基本要素　第四节　最长公共子序列　第五节　最大子段和　第六节　电路布线　第七节　流水作业调度　第八节　0-1背包问题　第九节　整数规划问题　第十节　流动推销员（或旅行商）问题　习题第五章　贪心法　第一节  引言　第二节　背包问题　第三节　最小生成树　第四节　单源最短路径问题　第五节　文件存储问题　第六节　有期限的任务安排问题　习题第六章　回溯法　第一节　回溯法的一般方法　第二节　n皇后问题　第三节　图的着色问题　第四节　流水作业车间调度　第五节　装载问题　第六节　0-1背包问题　第七节　马的遍历问题　习题第七章　分支限界法　第一节　分支限界法的基本思想　第二节　旅行推销员问题　第三节　单源最短路径问题　第四节　布线问题　第五节　0-1背包问题　第六节　装载问题　习题第八章　P、NP和NP完全问题第九章　字符串匹配第十章　网络路由算法第十一章　随机地第十二章　概率算法·数论算法·计算几何第十三章　生物信息处理算法参考文献

章节摘录

插图：第一章 导论计算机算法是计算机科学和计算机应用的核心，无论是计算机系统、系统软件和解决计算机的各种应用课题都可归结为算法的设计。通常，给了一个问题，我们关心三件事：1．怎样找到解决此问题的有效算法？2．如何比较解决同一问题的不同算法？3．如何判断一个算法的优点？简单地说，解决这三个问题就是应该掌握常规的或经典的算法设计方法，掌握算法分析的基本手段。第一节 算法与程序一、算法的概念及特性对于计算机科学来说，算法(Algorithm)的概念是至关重要的。例如在一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法，且满足下述几条性质：1．输入：有零个或多个由外部提供的量作为算法的输入。2．输出：算法产生至少一个量作为输出。3．确定性：组成算法的每条指令是清晰的、无歧义的。4．可行性：算法中有待实现的运算都相当基本（都是基本运算），每种运算至少在原理上能由人用纸和笔在有限的时间内完成。整数算术运算是可行性运算的一个例子，而实数算术运算则不是可行的，因为某些实数值只能由无限长的十进制数展开式来表示，像这样的两个数相加就违背可行性这一特性。

编辑推荐

《计算机算法设计与分析》由中国铁道出版社出版。

用户评论 (总计1条)

•   这本书还好，算法介绍的很全，内容丰富。