计算机算法

出版时间：2009-3  出版社：北京交通大学出版社  作者：胡金初 编  页数：197  字数：333000  

前言

计算机算法是计算机学科的核心课程，熟练掌握这门课程后可以很好地解决在计算机研究中遇到的疑难问题，该课程的主要目的是培养读者分析和设计算法的能力，从而为编写高效的程序和开发优秀软件奠定基础。本书主要介绍五种通用的算法设计技术，并且分析了各算法的基本原理和解题技巧。为了方便读者的理解，书中算法给出程序实现的方法和描述，读者可以用自己擅长的语言对这些算法进行上机实践以加深自己对这些算法的理解。全书共分16章，第1章介绍了算法设计和分析的基本概念，详细地对在一个表中搜索给定值和矩阵乘法两个算法进行算法分析，简单地介绍了算法的5种通用算法设计技术递归方程解的展开式；第2章介绍了几种常用的排序算法，从内部排序和外部排序两方面进行分析；第3章讨论了几种查找树的问题，包括二分查找树、2-3-4树、红黑树和B树；第4章讨论了图的算法，讲述了最短路径和最小生成树的问题；第5章介绍了串匹配问题，在该章中介绍了几种串匹配问题，如BM算法、KMP算法等；第6章介绍了五种算法设计技术之一的分治算法，解决二分搜索问题、最大最小元问题、大整数乘法问题、矩阵乘法问题；第7章介绍算法设计技术之二的贪心算法，解决背包问题、带时限的作业排序问题、单源最短路径问题、最小生成树问题、Dilkstra最短路径的优化算法；第8章介绍了算法设计技术之三的回溯法，解决n皇后问题、图的着色问题、0-1背包问题、哈密顿回路问题、子集和数问题；第9章介绍了算法设计技术之四的动态规划法应用在最长公共子序列问题、矩阵连乘问题等；第10章从0-1背包问题入手用分支限界法进行讲解；第11章简单地介绍了几种概率算法；第12章主要介绍了几何问题的实例；第13章介绍计算机算法的一个理论问题——NP问题，分析几个NP完全问题；第14章讲解了密码学算法，从背包公钥密码、RSA算法、数字签名等，对密码学作了简单的介绍；第15章介绍了近似算法；第16章重点介绍了一些数值问题的并行算法。在每章的结尾都有习题，以启发学生运用学到的知识解决实际问题。从整体上看，本书具有内容全面、取材得当、实用和指导性强等特点，是作者多年来计算机算法课程教学的经验总结，是在授课讲义基础上，参考国内外有关材料编写而成。希望所有读者能从本书中体会到计算机算法的精髓所在，能对今后的工作和学习有所帮助。在教学内容的选择上也可以根据本校教学的实际情况节选部分内容。为了方便教师的教学，本书还配备有全套的教学幻灯片，可供教师在教学中选用。本书可作为高等院校的教科书或参考书，又可以作为计算机算法领域人员的参考书，还可以作为相关领域人员了解计算机算法知识的参考材料。

内容概要

本书主要讲述、分析了各种算法的基本原理和解题技巧，以五种通用的算法设计技术为主线论述了分治策略、贪心策略、动态规划策略、分支限界法、回溯法等问题，对算法的时间和空间复杂性进行了分析。在内容的选材上注重基本理论和具体实例的结合，以便于读者理解。本书还对概率算法、近似算法、密码算法和NP问题进行了简单的介绍。    本书可作为计算机系本科学生及研究生的教材，也可作为计算机科学研究和软件开发技术人员的参考用书。

书籍目录

第1章　绪论  1.1　算法的时间复杂性  1.2　算法的空间复杂性  1.3　两个算法的分析实例  1.4　算法设计技术    1.4.1　分治方法    1.4.2　回溯法    1.4.3　贪心法    1.4.4　动态规划法    1.4.5　分支限界法    1.4.6　递归方程解的展开式  习题第2章　排序算法  2.1　插入算法    2.1.1　直接插入排序    2.1.2　折半插入排序    2.1.3　希尔排序  2.2　选择排序    2.2.1　直接选择排序    2.2.2　堆排序  2.3　交换排序    2.3.1　冒泡排序    2.3.2　快速排序  2.4　归并排序  2.5　基数排序  2.6　外部排序    2.6.1　归并排序    2.6.2　多步归并算法  2.7　各种内部排序方法的比较讨论  习题第3章　查找树  3.1　二分查找树  3.2　2—3—4树　3.3　红黑树　3.4　8树　习题第4章　图的算法　4.1　基本概念　4.2　图的表示方法　4.3　图的遍历　4.4　所有点对之间的最短路径　4.5　最小生成树　习题第5章　串匹配  5.1　简单的字符串匹配算法  5.2　Knuth—Morris—Pratt（KMP）字符串匹配  5.3　BM算法  5.4　RK算法  习题第6章　分治算法  6.1　二分搜索  6.2　求最大元和最小元  6.3　大整数乘法  6.4　矩阵乘法算法  6.5　矩阵乘积的Winograd算法  习题第7章　贪心算法　7.1　背包问题　7.2　带时限的作业排序　7.3　单源最短路径问题　7.4　最小生成树问题　7.5　Dijkstra各点之间最短路径的优化算法　习题第8章　回溯法　8.1　n皇后问题　8.2　图的着色问题　8.3　0—1背包问题　8.4　哈密顿回路　8.5　子集和数　习题第9章　动态规划法  9.1　最长公共子序列问题　9.2　矩阵连乘问题　9.3　多阶段决策过程最优化问题　9.4　0—1背包问题　9.5　流水线调度问题　习题第10章　分支限界法第11章　概率算法第12章　几何问题算法第13章　NP完全问题第14章　密码学算法第15章　近似算法第16章　并行算法参考文献

章节摘录

插图：第1章　绪论1.4　算法设计技术算法设计的基本要求是：首先是正确性（Correctness），程序中不含语法错误，程序对一切合理的输入数据都能产生满足要求的结果，程序也能对不合理的输入数据产生符合规格要求的结果。其次，算法要具有可读性（Readability），因为研究算法的目的是为了阅读和交流，可读性有助于对算法的理解，可读性有助于对算法的调试和修改。算法应具有高效率与低存储量，处理速度要快，存储容量要小，有时候处理时间和存储空间是矛盾的，实际中，往往是求得时间和空间的折中。多年来，人们提出了一些通用的算法设计技术如分治方法、贪心法、回溯法、动态规划法、分支限界法等，我们用它们解决了许多类的问题，产生有效的算法，其中贪心法、动态规划法和分支限界法大多用来解决最优化的问题。本小节简单地来介绍一下这五种设计方法，具体算法将会在第6、7、8、9、10章分别介绍。1.4.1　分治方法分治法的设计思想是将一个难以直接解决的大问题分割成一些规模较小但类型相同的问题，以便各个击破，分而治之。

用户评论 (总计4条)

•   这本书简单明了的介绍了计算机常见一些算法，实例详实，内容丰富，非常适合研究生同学阅读
•   定的书六天才到货！出现了延误！服务有待提高！
•   内容还是不错的，但是送到的书的封面却是破的，很不好
•   内容完善，比较简洁，感觉还行。