算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材

图书标准信息

• 作者 屈婉玲、刘田、张立昂、王捍贫 著
• 出版社 清华大学出版社
• 出版时间 2000-01
• 版次 2
• ISBN 9787302429555
• 定价 29.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 丛书 21世纪大学本科计算机专业系列教材

【内容简介】

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

【作者简介】

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

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

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

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

【目录】

第1章基础知识1
1.1内容提要1
1.2习题3
1.3习题解答与分析7
第2章分治策略12
2.1内容提要12
2.2习题13
2.3习题解答与分析17
第3章动态规划32
3.1内容提要32
3.2习题35
3.3习题解答与分析38
第4章贪心法52
4.1内容提要52
4.2习题55
4.3习题解答与分析58
第5章回溯与分支限界73
5.1内容提要73
5.2习题75
5.3习题解答与分析76
第6章线性规划81
6.1内容提要81 基础知识第 1 章算法设计与分析习题解答与学习指导（第2版）6.2习题83
6.3习题解答与分析88
第7章网络流算法109
7.1内容提要109
7.2习题111
7.3习题解答与分析115
第8章算法分析与问题的计算复杂度133
8.1内容提要133
8.2习题134
8.3习题解答与分析135
第9章NP完全性141
9.1内容提要141
9.2习题142
9.3习题解答与分析144
第10章近似算法150
10.1内容提要150
10.2习题151
10.3习题解答与分析152
第11章随机算法155
11.1内容提要155
11.2习题156
11.3习题解答与分析156
第12章处理难解问题的策略162
12.1内容提要162
12.2习题163
12.3习题解答与分析163
参考文献179