这本《算法设计》教材具有以下突出的优点:
1. 以各种算法设计技术(如贪心法、分治策略、动态规划、网络流、近似算法、随机算法等)为主线来组织素材,深入分析了各种设计技术的适用条件和局限性,突出了算法设计的思想和分析的基本原则,为从事实际问题的算法设计与分析工作提供了清晰的、整体的思路和方法.
2. 本教材内容非常丰富,不但深入系统地阐述了算法设计与分析的理论,而且给出了大量的典型范例和参考文献.这些范例有的有重要的应用背景,有的与计算机科学技术的新发展密切相关.每个问题的叙述完全按照人们解决实际问题的思路进行:首先提出问题,然后考虑如何抽象出合理的数学模型,接着探讨有效的算法设计技术,给出算法的形式描述,并对算法的正确性和效率进行论证和分析,最后将有关的结果加以拓广.这不但介绍了算法设计与分析的系统方法,对如何设计正确的高效的算法有着重要指导意义,而且对如何面对实际问题从事科学研究也有着很好的启迪作用.
3. 如何确定问题的计算难度,如何处理难解的问题是计算机科学工作者经常面临的问题.本教材用相当大的篇幅(第8~12章)比较系统全面地介绍NP完全性(以及PSPACE完全性)和处理NP难问题的方法.这些材料过去多以专著形式出现,在算法教材中通常只有蜻蜓点水式的少量介绍.本教材打破了这种惯例,按照“本科生可以接受的”设计目标把这些材料纳入本科生算法教材,这是极其有益的尝试,希望能促进国内算法教学水平的提升.
4. 这本教材以算法为主线来处理算法与数据结构的关系.它先对所涉及的数据结构做了简要介绍,然后结合算法设计技术对如何选择数据结构进行了深入的分析.这种安排突出了算法设计的中心思想,避免了与数据结构课程在内容上的重复,更加适合于国内的教学计划.
5. 本教材的叙述风格和选材非常适合教学.首先,内容由浅入深,由具体到抽象,从算法设计技术与分析方法自然过渡到计算复杂性理论.教师可以根据不同的教学要求选择适当的模块进行组合.其次,算法描述采用伪码,避免了繁琐的程序设计语言等实现细节,使学生能够站在更高的抽象层次上,加深对问题本身和算法设计思想的理解.第三,对与算法有关的数学基础做了适当的铺垫和介绍,有利于学生自学.第四,选配了大量难度适当的练习,并给出求解范例.
本书适合作为计算机科学与技术专业本科高年级学生或研究生的算法设计与分析课程教材.对于在不同领域使用计算机求解实际问题的科学技术人员,它也是一本有益的参考书.
本书包含13章,前7章主要涉及算法的设计与分析技术,后6章涉及计算复杂性以及相关的难解问题的算法设计技术.前7章由屈婉玲完成,后6章及后记由张立昂完成.在翻译过程中,我们按照中文书籍的编辑习惯对原著做了一点技术处理.比如加小节编号;把定理(原著中加灰底色的部分)与命题、事实、推论等不同的成分加以区分,并按章统一编号;按照中文汉语拼音字母顺序重新改写了关键词索引.由于时间与水平所限,译文中难免存在某些问题,恳请读者批评指正.