算法设计与分析

出版时间：2011-5  出版社：清华大学  作者：屈婉玲,刘田,张立昂,王捍贫  页数：218  
Tag标签：无  

内容概要

　　本教材为计算机科学技术专业核心课程“算法设计与分析”教材.全书以算法设计技术和分析方法为主线来组织各知识单元，主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等。书中突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术。
　　本书有配套的学习指导与习题解析用书以及PPT电子教案。
　　本书可作为大学计算机科学与技术、软件工程、信息安全、信息与计算机科学等专业本科生和研究生教学用书，也可以作为从事实际问题求解的算法设计与分析工作的参考书。

作者简介

屈婉玲，北京大学信息科学技术学院教授，博士生导师。长期从事离散数学、算法分析与计算复杂性等方向的教学和研究工作。参与完成多项国家研究课题，撰写多部教材、教学参考书与译著，其中包括国家级规划教材、北京市精品教材、教育部高等教育精品教材等。曾获得北京市教学成果奖一等奖，被评为北京大学十佳教师和北京市优秀教师，系国家精品课“离散数学”课程主持人，“算法设计与分析”课程主持人。刘田博士，北京大学信息科学技术学院副教授，中国电子学会电路与系统分会图论与系统优化专业委员会秘书长，中国电子学会和中国计算机学会高级会员。目前主要从事算法分析和计算复杂度方面的研究和教学工作。翻译多部国外著名离散数学和计算理论教材，系国家精品课“离散数学”课程主讲教师，“算法设计与分析”课程主讲教师。张立昂，北京大学信息科学技术学院教授，博士生导师。一直从事数学和理论计算机科学的教学与研究工作，主要研究方向是计算复杂性理论和算法设计与分析。撰写多部教材、教学参考书与译著，其中包括国家级规划教材、北京市精品教材、教育部高等教育精品教材等。曾获得北京市教学成果奖一等奖和教育部科技进步二等奖。王捍贫博士，北京大学信息科学技术学院教授，博士生导师，软件研究所副所长，人工智能学会离散数学专委会副主任。长期从事离散数学、形式化方法及算法设计与分析的教学和研究工作。主持完成多项国家研究课题，撰写和翻译多部离散数学和计算理论教材，曾获得北京市教学成果奖一等奖，系国家精品课“离散数学”课程主讲教师，“算法设计与分析”课程主讲教师。

书籍目录

第1章　基础知识
　1.1　有关算法的基本概念
　1.2　算法的伪码描述
　1.3　算法的数学基础
　　1.3.1　函数的渐近的界
　　1.3.2　求和的方法
　　1.3.3　递推方程求解方法
　习题1
第2章　分治策略
　2.1　分治策略的基本思想
　　2.1.1　两个熟悉的例子
　　2.1.2　分治算法的一般性描述
　2.2　分治算法的分析技术
　2.3　改进分治算法的途径
　　2.3.1　通过代数变换减少子问题个数
　　2.3.2　利用预处理减少递归内部的计算量
　2.4　典型实例
　　2.4.1　快速排序算法
　　2.4.2　选择问题
　　2.4.3　n -1次多项式在全体2 n 次方根上的求值
　习题2
第3章　动态规划
　3.1　动态规划的设计思想
　　3.1.1　多起点、多终点的最短路径问题
　　3.1.2　使用动态规划技术的必要条件
　3.2　动态规划算法的设计要素
　　3.2.1　子问题的划分和递推方程
　　3.2.2　动态规划算法的递归实现
　　3.2.3　动态规划算法的迭代实现
　　3.2.4　一个简单实例的计算过程
　3.3　动态规划算法的典型应用
　　3.3.1　投资问题
　　3.3.2　背包问题
　　3.3.3　最长公共子序列LCS
　　3.3.4　图像压缩
　　3.3.5　最大子段和
　　3.3.6　最优二分检索树
　　3.3.7　生物信息学中的动态规划算法
　习题3
第4章　贪心法
　4.1　贪心法的设计思想
　4.2　关于贪心法的正确性证明
　4.3　对贪心法得不到最优解情况的处理
　4.4　贪心法的典型应用
　　4.4.1　最优前缀码
　　4.4.2　最小生成树
　　4.4.3　单源最短路径
　习题4
第5章　回溯与分支限界
第6章　算法分析与问题的计算复杂度
第7章　NP完全性
第8章　近似算法
第9章　随机算法
第10章　处理难解问题的策略
参考文献

章节摘录

版权页：插图：

编辑推荐

《算法设计与分析》以算法设计技术为主线组织素材，以伪码描述算法，深入分析了各种设计技术的适用范围、设计步骤、算法正确性证明与时间复杂度估计方法，以及改进算法的途径、局限性等，为实际问题的建模与算法设计在理论上提供清晰的整体思路。从对具体算法的设计与分析，自然过渡到对问题难度的分析和界定，系统地介绍了一些关于问题复杂度的分析方法。力求用清晰易懂的语言介绍NP完全性理论的核心内容和难解问题的处理策略，希望为求解实际中的复杂问题提供帮助。除了传统的算法外，《算法设计与分析》还介绍了随机算法、模拟退火算法、基于统计物理的消息传递算法、量子算法等，给有兴趣的读者提供进一步学习和研究的入门知识。《算法设计与分析》的主要素材来自多年的教学积淀，也有一些研究的心得。既注意理论上的严谨性，又精选了大量实例，并配有难度适当的练习，适合教学使用。根据教育部“高等学校计算机科学与技术专业规范”组织编写。与美国ACM和lEEE CS Computing Curricula最新进展同步。

用户评论 (总计26条)

•   书很好，也很划算，里面的算法思想非常好。是计算机专业的必备，应该人手人本。
•   是算法课的教材，就是屈老师编的，感觉写的非常通俗易懂，包含很多例题，超赞~~~
•   国内不错的算法书
•   教材，还行，屈奶奶基本都是按书上讲的，不错
•   上课老师编写的教材，页数虽然不多，但是很精辟，推荐！
•   课程要求的标配教科书一本
•   内容完善，举例也比较好
•   该书通俗易懂 内容翔实
•   书籍内容很好 收益很大
•   这本屈婉玲写的书很好，思路清晰，只是当当网到现在还没有2013年印刷版，因为那是最新的一版
•   屈老师的书绝对有质量保证
•   北大导师写的书
  讲的很不错
•   屈前辈的书一向是很严谨的，值得推荐。
•   东西还不错但是快递不知道是快春节了5天才送来，有点失望
•   很好非常好，特特别别好
•   算法设计与分析讲的很详细，很不错，对我的学习很有帮助。
•   内容比较基础，算法从本书开始！
•   书不错。没什么质量问题。速度快
•   作为教材的书籍，内容覆盖较广，实例较多，但总结较少
•   Very very very good!
•   书皮前面和后面都花了，感觉不像全新的一样，不过打开里面还好，希望当当下次发货，能把好关
•   请问你们给我发的书有一本少了4页的内容，这是怎么回事？请问能换吗
•   货到付款挺好
•   内容丰富有介绍的很清楚的一本书
•   深入学习算法的好书
•   12年看的最认真的书，没有之一