算法设计与分析习题解答与学习指导（第2版）_屈婉玲、刘田、张立昂、王捍贫_9787302429555

本教材为普通高等教育“十一五”国家级规划教材《算法设计与分析（第2版）》（主教材）的辅助教材. 主教材的主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等. 本书对主教材所阐述的算法设计技术和分析方法进行了总结，并对其中200多道习题给出了详尽的解答和分析. 本书适合作为大学计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生的辅助教学用书，也可以作为从事实际问题求解的算法设计与分析工作的参考书.

　作为问题求解和程序设计的重要基础，算法设计与分析在计算机科学与技术专业的课程体系中是一门重要的必修课.通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，而且对培养学生分析与解决问题的能力及计算思维有着不可替代的作用.ACMIEEEComputingCurricula2004与我国教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范2005》都把该课程列入本专业的核心课程之一.

　　本书是国家高等教育“十一五”规划教材《算法设计与分析》(清华大学出版社出版，屈婉玲等编著)的辅助教材.主教材包括算法设计、算法分析、计算复杂性理论等重要内容.结合各种典型应用，主教材首先深入分析了各种算法设计技术的适用范围、设计步骤、正确性证明与复杂度的分析方法、改进算法的途径、局限性等，为从事实际问题求解的算法设计与分析工作在理论上提供清晰的、整体的思路和方法，并在此基础上介绍了问题难度的分析方法和计算复杂性理论的基本框架和一些重要的结果.

　　算法具有广泛的应用背景，习题量大，方法灵活.针对给定算法问题，在建模、设计技术选择、效率分析、改进途径等方面，初学者往往不知道如何着手.本书在多年算法教学的基础上精选了100多道典型的习题，给出了详尽的解答和分析，以期对初学者有所帮助.

　　与主教材配套，本书也分为10章.第1章是基础知识；第2～5章分别阐述分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术；第6章介绍算法分析和问题的计算复杂度；第7章是NP完全性理论；第8章是近似算法；第9章是随机算法；第10章介绍处理难解问题的策略.每章首先对所涉及的重要知识点和方法进行总结，然后给出习题和解答.

　　本书前4章由屈婉玲编写，第5～6章由王捍贫编写，第7～8章由张立昂编写，第9～10章由刘田编写.

　　为了提高本书的质量，欢迎广大读者的批评和指正！

　　作者

　　2014年3月于北京大学

　　屈婉玲，北京大学信息科学技术学院教授，博士生导师。长期从事离散数学、算法分析与计算复杂性等方向的教学和研究工作，参与完成多项国家研究课题，撰写多部教材与译著，其中包含国家规划教材、教育部高等教育精品教材、北京市精品教材等。获得北京市教学成果奖一等奖，被评为北京大学十佳教师，并获得北京市优秀教师称号，系国家精品课“离散数学”课程主持人，“算法设计与分析”课程主讲教师。

　　刘田，博士，北京大学信息科学技术学院副教授，中国电子学会电路与系统分会图论与系统优化专业委员会秘书长，中国计算机学会理论计算机科学专委会委员。目前主要从事算法分析和计算复杂度方面的研究和教学工作。翻译多部国外著名离散数学和计算理论教材，系国家精品课“离散数学”课程主讲教师，“算法设计与分析”课程主讲教师。本书的编写得到国家自然科学基金（61370052）的资助。

　　张立昂，北京大学信息科学技术学院教授，博士生导师。一直从事数学和理论计算机科学的教学与研究工作，主要研究方向是计算复杂性理论和算法设计与分析。撰写多部教材、教学参考书与译著，其中包括国家规划教材、北京市精品教材、教育部高等教育精品教材等，曾获得北京市教学成果奖一等奖和教育部课程成果二等奖。

　　王捍贫，博士，北京大学信息科学技术学院教授，博士生导师，软件研究所副所长，中国人工智能学会离散智能计算专委会主任。长期从事离散数学、形式化方法及算法设计与分析的教学和研究工作。主持完成多项国家研究课题，撰写和翻译多部离散数学和计算机理论教材，曾获得北京市教学成果奖一等奖，系国家精品课“离散数学”课程主讲教师，国家精品资源共享课“离散数学”课程主持人，“算法设计与分析”课程主讲教师。

我要评论