第3版前言


FOREWORD本书是《算法设计与分析（第3版）》的辅助教材. 作为普通高等教育“十一五”国家级规划教材，《算法设计与分析（第2版）》已经出版6年了. 在这6年里，计算机科学与技术又有了新的发展，各种新的技术和算法层出不穷. 然而万变不离其宗，各种新的算法依然是建立在各种经典算法技术的基础上的，最新的算法技术往往是对各种已有算法技术的组合和改进. 掌握了本书所介绍的各种经典算法技术之后，在学习理解新的算法技术，或学习掌握各领域内的专门算法时，往往可以事半功倍. 
本次修订对第2版的内容未做大的改动，除了个别字句的改动和订正一些错误，以及对文字做进一步的精细加工之外，主要是在主教材第11章随机算法中新增最后一节，介绍姚的极小极大原理，并补充了相应的习题. 姚的极小极大原理是证明随机算法复杂度下界的主要工具，在各种随机算法模型下都有广泛应用. 与主教材配套，本书也进行了同步更新，在第11章中补充了新的习题和解答.
 本次修订主要由刘田完成. 对广大读者提出的宝贵建议和意见，以及清华大学出版社的支持，我们一如既往地表示衷心的感谢！


作者2022年6月于北京大学第2版前言FOREWORD本书是《算法设计与分析（第2版）》的辅助教材. 作为普通高等教育“十一五”国家级规划教材，《算法设计与分析》出版已经5年了. 在这5年的时间里，大数据、云计算、“互联网+”等新领域、新问题、新应用层出不穷，许多问题求解都离不开问题的建模和算法的设计与分析. 这次关于主教材的修订保持了原书的基本结构、主要内容与写作特色. 考虑到线性规划与网络流问题在实践中有广泛应用，本次修订增加了这两章内容，并在第9章增添了整数线性规划的NP完全性证明. 此外，补充了部分习题，并对第1版书中的某些疏漏之处进行了更新. 
与主教材配套，本书也进行了同步更新，增加了第6章线性规划、第7章网络流算法，并对补充习题给出了详细的分析和解答.
本书第1章至第4章由屈婉玲编写，第5章和第8章由王捍贫编写，第6章、第7章、第9章和第10章由张立昂编写，第11章和第12章由刘田编写. 
欢迎广大读者批评指正！

 作者
2015年11月于北京大学第1版前言FOREWORD作为问题求解和程序设计的重要基础，“算法设计与分析”在计算机科学与技术专业的课程体系中是一门重要的必修课. 通过该课程的学习，不但为学习其他专业课程奠定扎实的基础，而且对培养学生分析与解决问题的能力及计算思维具有不可替代的作用. ACM IEEE Computing Curricula 2004以及我国教育部高等学校计算机科学与技术教学指导委员会制订的《计算机科学与技术专业规范2005》都把该课程列入相关专业的核心课程之一.
本书是普通高等教育“十一五”国家级规划教材《算法设计与分析》(清华大学出版社出版，屈婉玲等编著)的辅助教材. 主教材包括算法设计、算法分析、计算复杂性理论等重要内容. 结合各种典型应用，主教材首先深入分析了各种算法设计技术的适用范围、设计步骤、正确性证明与复杂度的分析方法、算法改进的途径、局限性等，为从事实际问题求解的算法设计与分析工作在理论上提供清晰的、整体的思路和方法，并在此基础上介绍了问题难度的分析方法和计算复杂性理论的基本框架和一些重要的结果. 
算法具有广泛的应用背景，习题量大，方法灵活. 针对给定算法问题，在模型建立、设计技术选择、效率分析、途径改进等方面，初学者往往不知道如何着手. 本书在多年算法教学的基础上精选了100多道典型的习题，给出了详尽的解答和分析，以期对初学者有所帮助. 
与主教材配套，本书也分10章. 第1章是基础知识，第2章至第5章分别阐述分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术，第6章介绍算法分析与问题的计算复杂度，第7章是NP完全性理论，第8章是近似算法，第9章是随机算法，第10章介绍处理难解问题的策略. 每章首先对所涉及的重要知识点和方法进行总结，然后给出习题和解答.
本书前4章由屈婉玲编写，第5章和第6章由王捍贫编写，第7章和第8章由张立昂编写，第9章和第10章由刘田编写. 
为了提高本书的质量，欢迎广大读者批评和指正！

作者
2014年3月于北京大学