算法设计与分析

出版时间：2009-8  出版社：张德富 国防工业出版社 (2009-08出版)  作者：张德富  页数：330  
Tag标签：无  

前言

民众多好饮酒，中外概莫能外。酒馆和酿酒坊伴随饮酒客而起，人类对酒的喜爱造就了酒文化和一个庞大的产业。好酒能卖好价钱，能使文人诗兴大发，催生佳作，还能解人间百难。于是，酿天下名酒自然成为不少人的毕生追求。怎样才能酿出好酒呢？国人的看法不尽相同。崇信洋酒的人主张引进国外的生产工艺，学习洋人的生产和经营理念，而喜欢国酒的人则主张走自己的路，但不排除借鉴国外先进的科学技术和管理经验。这样的争论或许永远不会终结，但外国人重视科学酿酒，这一点是值得我们学习和借鉴的。计算机科学教育，如同酿酒工业的生产一样，科学办学迄今还只是部分学者的一种理想。与国内一样，国外的计算机科学教育并没有像他们的科学酿酒业一样，实现科学办学。也许科学办学要远比科学酿酒困难得多。譬如，怎么实现科学办学？甚至怎么推出一套科学的系列教材都是一篇大文章。这套教材的创作始于教育部面向21世纪教育与教学改革13-22项目的研究。2000年，在13-22项目研究工作即将完成之际，一些学者开始认识到面对计算机科学与技术的高速发展，我们亟需一套体现科学办学思想、反映内涵发展要求、服务教育与教学改革、参与构建学科人才培养科学体系的系列教材。强调系列教材是因为那时已经意识到计算机科学教育本质上是一项科学活动，但长期以来教师向学生传授科学技术知识的方式方法科学性不强。由于高等教育几百年来一直沿袭经验方式而非科学方式办学，大学教学的方式方法仍然还停留在古代作坊式的阶段，只不过今天使用的教学技术手段先进而已。在经验办学方式下，无论是研究型大学还是教学型大学，由于种种原因，教学活动的全过程存在着太多的漏洞和质量上的隐患。科学办学是对高等教育界传统的一个挑战，尽管在认识上，人们不难理解，科学办学是经验办学的最高形式，而经验办学应该成为科学办学的有益补充。

内容概要

　　《算法设计与分析》主要取材于算法设计与分析领域的经典内容，并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面，介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。《算法设计与分析》包括大量的问题实例，并给出了相应的设计与分析方法，书后精选了一些习题，供读者练习，以巩固所学的算法。工业应用领域的许多实际问题和疑难问题都需要有效的求解算法，《算法设计与分析》提供了设计有效算法的基础以及大量的可供选择的解决途径。　　《算法设计与分析》内容基本上涵盖了目前程序设计竞赛所要掌握的算法，并在书后精选了部分ACM国际大学生程序设计竞赛的题目，供大家练习。　　《算法设计与分析》可作为计算机科学系、数学系、软件学院等专业本科及研究生课程的教材，特别适合于有志于参加程序设计竞赛的学生学习和训练。

书籍目录

第1章 入门1.1 问题1.2 算法的概念1.3 算法的正确性1.4 算法的效率1.5 问题的下界1.6 小结习题实验题第2章 渐近符号2.1 θ符号2.2 O符号2.3 η符号2.4 渐近符号的性质2.5 常用函数的直观含义2.6 小结习题第3章 算法分析方法3.1 概率分析3.2 分摊分析3.2.1 合计方法3.2.2 记账方法3.2.3 势能方法3.3 实验分析3.4 小结习题第4章 递归4.1 算法思想4.1.1 递归算法的应用4.1.2 递归与迭代4.2 递归方程的求解4.2.1 替换方法4.2.2 递归树方法4.2.3 式：去4.3 多项式求值实验4.4 小结习题实验题第5章 分治算法5.1 算法思想5.2 合并排序5.3 快速排序5.4 大整数乘法5.5 矩阵乘法5.6 残缺棋盘游戏、5.7 快速傅里叶变换(FFT)5.8 小结习题实验题第6章 动态规划6.1 算法思想6.2 装配线调度问题6.3 矩阵链乘法问题6.4 最长公共子序列问题6.5 0／1背包问题6.6 最优二叉搜索树问题6.7 动态规划的基本性质6.8 小结习题实验题第7章 贪心算法7.1 算法思想7.2 任务选择问题7.3 背包问题7.4 哈夫曼编码问题7.5 缓存维护问题7.6 任务选择问题实验7.7 小结习题实验题第8章 图算法8.1 图的搜索问题8.1.1 宽度优先搜索8.1.2 深度优先搜索8.2 最小生成树问题8.2.1 Kruskall算法8.2.2 Prim算法8.3 最短路径问题8.3.1 单个源点的最短路径问题8.3.2 所有点对的最短路径问题8.4 小结习题实验题第9章 网络流与匹配9.1 最大流问题9.1.1 FordFulkerson方法9.1.2 最短路径增广算法9.1.3 Dinic算法9.1.4 MPM算法9.1.5 最大流问题的变形9.2 最小费用流问题9.2.1 消除回路算法9.2.2 最小费用路算法9.2.3 最小费用路算法的改进9.3 匹配问题9.3.1 二分图匹配9.3.2 一般图的匹配9.4 小结习题实验题第10章 线性规划10.1 线性规划问题10.1.1 线性规划问题的标准形式10.1.2 线性规划问题的松弛形式10.2 求解算法10.2.1 图解法10.2.2 单纯形算法10.3 对偶10.4 小结习题实验题第11章 NIP完全理论11.1 判定问题11.2 P和NP11.3 NPC11.3.1 NPC的定义11.3.2 电路可满足性问题11.4 NPC的证明11.4.1 可满足性问题11.4.2 3.CNF可满足性问题11。4.3 团问题11.4.4 顶点覆盖问题11.5 其他NP完全问题11.6 小结习题第12章 回溯12.1 算法思想12.2 装载问题12.3 0／1背包问题12.4 着色问题12.5 n皇后问题12.6 旅行商问题12.7 流水作业调度问题12.8 零件切割问题12.9 小结习题实验题第13章 分支限界第14章 启发式搜索第15章 数论第16章 计算几何参考文献

章节摘录

插图：从问题下界的描述可知，要想找出所有的算法以确定问题的下界，通常比找出有效的算法更难。1.6 小结前面我们介绍了插入排序算法的设计与分析。如果将插入排序算法用具体的程序设计语言实现，就得到了程序。因此，程序与算法是有区别的，程序是用某种程序设计语言实现的算法，而算法是抽象的，它不依赖于具体的程序设计语言和硬件，也就是说，无论算法是用c语言编写在586上运行还是用Basic语言编写在笔记本电脑上运行，算法的思想都是一样的。Turing奖获得者，Pascal语言之父Ni-klausWirth曾说过“程序=数据结构+算法”。算法是程序背后的思想，是程序的核心。从这里可以看出，程序的本质是算法，是算法的具体体现。因此描述一个算法，我们不用具体的程序，而是用伪代码，主要是因为用伪代码描述的算法非常清。

编辑推荐

《算法设计与分析》是由国防工业出版社出版的。

用户评论 (总计4条)

•   还可以，就是买了就还给图书馆了 呜呜呜
•   很好，内容很丰富，上过张国富老师的课，讲的很好，很形象！
•   学校用的教材，老师自己编的，还不错吧
•   还行，要点基本上都涉及了