算法分析与设计

出版时间：2001-12  出版社：宋文、吴晟、 杜亚军 重庆大学出版社 (2001-12出版)  

内容概要

《算法设计与分析》介绍串行算法设计与分析。全书共分12章，主要内容包括：算法及算法的复杂性、贪婪法、递归、回溯法、动态规划、分治法、探索法、分枝-限界法、内存分类法、图的算法、NP完备理论、现代优化计算方法简介等，每章后附有习题。《算法设计与分析》可作为高等理工科院校计算机专业或相关专业本科生、研究生作为算法设计与分析的教材，也可以供从事计算机科学与应用的科技人员参考。

书籍目录

第1章 算法及算法的复杂性1.1 算法的定义1.2 算法的复杂度与评价1.3 解递归方程1.4 算法分析举例习题一第2章 贪婪法2.1 贪婪法的基本思想2.2 背包问题2.3 有限期的计算机作业调度2.4 计算机网络的最短传输时间习题二第3章 递归3.1 递归调用的内部实现原理3.2 递归程序的阅读3.3 递归转非递归3.4 递归算法的设计习题三第4章 回溯法4.1 回溯法的基本思想4.2 子集和问题4.3 皇后问题4.4 哈密顿回路问题4.5 图的着色问题习题四第5章 动态规划5.1 最优性原理5.2 一些简单例子5.3 最短路径问题5.4 最优树问题5.5 最优调度问题习题五第6章 分治法6.1 分治法的基本思想6.2 分治法算法设计的特点6.3 分治法的时间复杂度6.4 分治法的应用习题六第7章 探索法7.1 探索法的基本思想7.2 探索法的应用习题七第8章 分枝-限界法8.1 状态空间树上的检索——FIFO，LIFO，LC检索8.2 分枝-限界法解最优化问题8.3 0／1背包问题的LC分枝-限界求解的实现习题八第9章 内存分类法9.1 求第K个元素9.2 堆分类习题九第10章 图的算法10.1 图的两种遍历——DFS，BFS10.2 DFS树10.3 无向图的双连通分支10.4 有向图的强连通分支10.5 流的算法习题十第11章 NP完备理论11.1 确定型图灵机（DTM）11.2 可满足性问题11.3 非确定型图灵机11.4 Cook定理11.5 若干NP完全问题及NP难题11.6 近似计算习题十一第12章 现代优化计算方法简介12.1 模拟退火算法12.2 遗传算法12.3 人工神经网络习题十二参考文献

章节摘录

版权页：插图：如何计算算法的时空消耗？一种办法是事后分析。具体地说，对于问题P的算法A，在计算机上分别运行A对应的程序，输入适当的数据，测试程序A的开销，这一方法似乎很合理，细想一下其实不尽人意。第一，如此测试的结果与程序的运行环境有关。如计算机主频、总线和外部设备等，都会影响测试结果。第二，语言的编译系统对生成的机器代码的质量会产生很大的影响，从而影响运行的速度。第三，测试结果与选取的样本数据有关。算法的时空耗费是n的函数，它的结果应是在n足够大时才有意义。对于不同的n个数据，运行的结果是不一样的。欲要获得真实可靠的结果，必须科学地选取样本数据，而要做到这一点，并不是一件简单的事情。总之，这种事后分析是面向机器，面向程序员，面向语言的。从理论上讲，只有在标准环境下进行算法测试，得到的资源耗费才是可信的。这些因素与问题P的两种算法的差异无关。为了公平起见，同一问题的两种算法所对应的两个程序，应该在同样的条件下用同一个编译器编译，在同一台机器上运行，并且两次编程时所花费的精力也应尽可能地相等，使算法的实现“等效”。如果做到这几点，上面提到的那些因素就不会对结果产生影响，因为它对于每一个算法都是公平的。但是，仅凭实验来比较算法，很有可能因为一个程序比另一个程序“写得好”，而使算法的真正质量没有得到很好的体现。再者，可能两种算法，通过艰苦的编程，测试后都超过了预算的耗费，那么只有重新设计适合预算耗费的新算法。

编辑推荐

《算法设计与分析》为21世纪高等学校本科系列教材•计算机科学与技术专业之一。