编辑推荐

  《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》源自北京大学信息科学技术学院多年的教学积淀,北京大学本科教学改革重要项目成果,是北京大学本科生和研究生的算法课程的指定的配套教学辅导用书,也是MOOC教学Coursera平台上算法课程的教学辅导用书,读者除了来自国内的学生,还有海外学生。
  《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》有配套的主教材及PPT电子教案。同时在北京大学POJ(PekingUniversityOnlineJudge)平台的基础上构建了相应的上机环境。《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》主教材第1版作为普通高等教育“十一五”国家级规划教材于2011年出版,被100余所高校选用。
  《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》是普通高等教育“十一五”国家级规划教材《算法设计与分析》(第2版)的配套辅导教材。内容包括:基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等.除了传统的算法外还介绍了随机算法、模拟退火算法、基于统计物理的消息传递算法、量子算法等。
  每章的内容提要简要地叙述本章的基本概念、重要结果、算法及常用技巧,重点突出,有助于系统掌握相关的知识,方便读者总结、复习、查阅相关内容.。
  习题丰富,有不同的难度。
  对每道题给出了详尽的解答和分析,算法用伪码给出.注重分析问题和解决问题能力的培养。
  《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》是学习算法设计与分析的优秀教学辅导教材,可以与主教材《算法设计与分析(第2版)》(ISBN:9787302424505)配套使用,也可单独使用。《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》主教材的PPT电子教案、配套的源代码,可到清华大学出版社官网下载。

内容简介

  

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

作者简介

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

  刘田,博士,北京大学信息科学技术学院副教授,中国电子学会电路与系统分会图论与系统优化专业委员会秘书长,中国计算机学会理论计算机科学专委会委员。目前主要从事算法分析和计算复杂度方面的研究和教学工作。翻译多部国外著名离散数学和计算理论教材,系国家精品课“离散数学”课程主讲教师,“算法设计与分析”课程主讲教师。《算法设计与分析习题解答与学习指导·第2版/21世纪大学本科计算机专业系列教材》的编写得到国家自然科学基金(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

前言/序言

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

其他推荐