算法设计技巧与分析

出版时间：2010-10  出版社：电子工业  作者：阿苏外耶  页数：318  
Tag标签：无  

前言

算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课，越来越受到重视。本书系统地介绍了一些常用的、经典的算法设计技术，并给出了详细的复杂性分析。全书分七部分19章，内容含有递归技术、分治、动态规划、贪心算法、图的遍历等，同时也包括了近年来发展迅速的近似算法、概率算法和几何算法，对于NP完全问题等复杂性理论的基础内容，也做了基本的、清楚的描述。本书结构合理，选材适度，陈述简明易读，每章附有适量的各种类型练习，没有过难或研讨性题目，适合于教学和自学。出版后已被许多大学选做本科和研究生的教材及参考书。作者M.H.Alsuwaiyel在沙特阿拉伯的King Fahd University of Petroleum & Minerals（KFUPM，皇家法哈德石油矿业大学）完成大学学业，在南加州（USC）大学获得计算机科学硕士和博士学位。作者曾任KFUPM的计算机科学系主任、工程与计算机学院院长。他在沙特阿拉伯有广泛的学术影响，是政府（包括内务部和国防部在内）的高级顾问。本书的翻译工作是在朱洪教授的主持下进行的，全书主要由吴伟昶、方世昌翻译，朱洪审校。对于发现的原书中的错误，在翻译时已做了纠正，主要的错误已给予说明。上海应用技术学院计算机系的教师徐克奇、蔡旖旎、吴晓伟参与了部分翻译工作。复旦大学计算机系研究生李夷磊、葛启、谢之易、李镇坚、王海涛、马俊、田世俊、张涌、张华、李镇坚、李夷磊、谢之易等阅读了本书的大部分译稿，并提出了许多宝贵的意见。对于他们的帮助表示最衷心的感谢。由于译者本身的水平，翻译中难免有错误，恳请读者批评指正。

内容概要

本书是国际著名算法专家李德财教授主编的系列丛书Lecture Notes Series on Computing中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习题，有利于读者对书中内容的理解和应用。    本书结构简明，内容丰富，适合于作为计算机学科及相关学科算法课程的教材和参考书，尤其适宜于学过数据结构和离散数学课程之后的算法课程教材。同时也可作为从事算法研究的一本好的入门书。

作者简介

作者：（沙特）阿苏外耶（M.H.Alsuwaiyel） 译者：吴伟昶 方世昌 等 注释 解说词：朱洪

书籍目录

第一部分　基本概念和算法导引第1章　算法分析基本概念　1.1　引言　1.2　历史背景　1.3　二分搜索　1.4　合并两个已排序的表　1.5　选择排序　1.6　插入排序　1.7　自底向上合并排序　1.8　时间复杂性　1.9　空间复杂性　1.10　最优算法　1.11　如何估计算法运行时间　1.12　最坏情况和平均情况的分析　1.13　平摊分析　1.14　输入大小和问题实例　1.15　练习　1.16　参考注释第2章　数学预备知识　2.1　集合、关系和函数　2.2　证明方法　2.3　对数　2.4　底函数和顶函数　2.5　阶乘和二项式系数　2.6　鸽巢原理　2.7　和式　2.8　递推关系　2.9　练习第3章　数据结构　3.1　引言　3.2　链表　3.3　图　3.4　树　3.5　根树　3.6　二叉树　3.7　练习　3.8　参考注释第4章　堆和不相交集数据结构　4.1　引言　4.2　堆　4.3　不相交集数据结构　4.4　练习　4.5　参考注释第二部分　基于递归的技术第5章　归纳法　5.1　引言　5.2　两个简单的例子　5.3　基数排序　5.4　整数幂　5.5　多项式求值（Horner规则）　5.6　生成排列　5.7　寻找多数元素　5.8　练习　5.9　参考注释第6章　分治　6.1　引言　6.2　二分搜索　6.3　合并排序　6.4　分治范式　6.5　寻找中项和第k小元素　6.6　快速排序　6.7　大整数乘法　6.8　矩阵乘法　6.9　最近点对问题　6.10　练习　6.11　参考注释第7章　动态规划　7.1　引言　7.2　最长公共子序列问题　7.3　矩阵链相乘　7.4　动态规划范式　7.5　所有点对的最短路径问题　7.6　背包问题　7.7　练习　7.8　参考注释第三部分　最先割技术第8章　贪心算法　8.1　引言　8.2　最短路径问题　8.3　最小耗费生成树（Kruskal算法）　8.4　最小耗费生成树（Prim算法）　8.5　文件压缩　8.6　练习　8.7　参考注释第9章　图的遍历　9.1　引言　9.2　深度优先搜索　9.3　深度优先搜索的应用　9.4　广度优先搜索　9.5　广度优先搜索的应用　9.6　练习　9.7　参考注释第四部分问题的复杂性第10章　NP完全问题　10.1　引言　10.2　P类　10.3　NP类　10.4　NP完全问题　10.5　co-NP类　10.6　NPI类　10.7　四种类之间的关系　10.8　练习　10.9　参考注释第11章　计算复杂性引论　11.1　引言　11.2　计算模型：图灵机　11.3　k带图灵机和时间复杂性　11.4　离线图灵机和空间复杂性　11.5　带压缩和线性增速　11.6　复杂性类之间的关系　11.7　归约　11.8　完全性　11.9　多项式时间层次　11.10　练习　11.11　参考注释第12章　下界　12.1　引言　12.2　平凡下界　12.3　决策树模型　12.4　代数决策树模型　12.5　线性时间归约　12.6　练习　12.7　参考注释第五部分克服困难性第13章　回溯法　13.1　引言　13.2　3着色问题　13.3　8皇后问题　13.4　一般回溯方法　13.5　分支限界法　13.6　练习　13.7　参考注释第14章　随机算法　14.1　引言　14.2　Las　Vegas和Monte　Carlo算法　14.3　随机化快速排序　14.4　随机化的选择算法　14.5　测试串的相等性　14.6　模式匹配　14.7　随机取样　14.8　素数性测试　14.9　练习　14.10　参考注释第15章　近似算法　15.1　引言　15.2　基本定义　15.3　差界　15.4　相对性能界　15.5　多项式近似方案　15.6　完全多项式近似方案　15.7　练习　15.8　参考注释第六部分域指定问题的迭代改进第16章　网络流　16.1　引言　16.2　预备知识　16.3　Ford-Fulkerson方法　16.4　最大容量增值　16.5　最短路径增值　16.6　Dinic算法　16.7　MPM算法　16.8　练习　16.9　参考注释第17章　匹配　17.1　引言　17.2　预备知识　17.3　网络流方法　17.4　二分图的匈牙利树方法　17.5　一般图中的最大匹配　17.6　二分图的On2.5算法　17.7　练习　17.8　参考注释第七部分计算几何技术第18　章几何扫描　18.1　引言　18.2　几何预备知识　18.3　计算线段的交点　18.4　凸包问题　18.5　计算点集的直径　18.6　练习　18.7　参考注释第19章　Voronoi图解　19.1　引言　19.2　最近点Voronoi图解　19.3　Voronoi图解的应用　19.4　最远点Voronoi图解　19.5　最远点Voronoi图解的应用　19.6　练习　19.7　参考注释参考文献

章节摘录

插图：1.1引言最一般的直觉意义上的算法①就是一个由有限的指令集组成的过程。从可能的输人集中给这个过程一个输入，如果系统地执行该指令集，那么对于这个特定的输人，当输出存在时，就能得到输出；当没有输出时，就什么结果也得不到。可能的输入集是指能让该算法给出一个输出的所有输入。如果对于一个特定的输入有一个输出，那么就说该算法能用于这一输入，执行该算法能够得到相应的输出。我们要求算法对于每一个输入能停下来，这意味着每一条指令只需要有限的时间，同时每一个输入的长度是有限的。我们还要求对于一个合法输人所对应的输出是惟一的。也就是说当算法从一个特定的输入开始，多次执行同一指令集时，结果总是相同，从这个意义上讲算法是确定的。第14章研究随机算法时将放宽这一条件。在计算机科学领域，算法设计与分析是十分重要的。正如Donald E.Knuth所说，“计算机科学就是算法的研究”。这没什么可惊讶的，因为计算机科学的每个领域都高度依赖于有效算法的设计。举个简单例子，编译程序和操作系统不外乎就是具有特定目标的算法的直接实现。本章的目的有两个：首先介绍一些简单的算法，特别是与搜索和排序相关的那一类；其次讲述用于算法设计和分析的基本概念。由于算法的“运行时间”这一概念对于设计有效算法是至关重要的，我们将对它进行深入讨论。总之，时间是衡量算法有效性的最好测度。我们也会讨论其他重要资源的测度，比如一个算法所需要的空间等。本章给出的算法虽然简单，但它们是解释一些算法概念的许多例子的基础。从简单有用的、在更复杂的算法中被用做构件模块的算法开始，是非常有益的。1.2 历史背景20世纪早期，尤其在30年代，能否用一种有效的过程（即相当于现在所说的算法）来求解问题受到广泛关注。在那时，人们的注意力是放在问题的可解或不可解的分类上，即是否存在有效过程来求解问题。为此，产生了对计算模型的需要。如果应用这个模型能够建立一个算法来求解这个问题，那么这个问题就被归人可解的问题类。其中的一些模型是哥德尔（del）的递归函数、丘奇（Church）的入演算、波斯特（Post）的波斯特机和图灵（luring）的图灵机。RAM计算模型是作为实际的计算机的理论上的补充被引人的。根据丘奇的论断，所有这些模型是等效的，即意味着如果一个问题在其中的一个模型上是可解的，那么对于所有其他的模型，该问题都是可解的。

编辑推荐

《算法设计技巧与分析》是国外计算机科学教材系列

用户评论 (总计67条)

•   在国内翻译外文著作中还好的了，书的内容适合对算法有一定基础的，拔高的书籍，很不错的书
•   这本书介绍了一些一般算法书不常提到的算法,值得好好读读.
•   这本书对我学编程帮助挺大的，里面对算法的分类很不错，挺好的一本算法书！
•   恩，不错，算是算法导论的精简版，看不了那么大部头的书可以看这个
•   考研考博必备专业书，值得推荐的算法类教材
•   有关算法的很多练习，对于算法的理解帮助很大
•   知识点很多，很多算法让人耳目一新。
•   这本书还是挺好的，结构挺好，讲的还算比较清楚
•   是上交的计算机专业教材，够专业够难
•   买了两本，速度很快，一天就到了，正版啊~~~就是书里面的知识太难，呜呜。。
•   请网站及时更行书本的相关信息，我看到的是蓝色的书，买的是红色的，好在内容一样
•   收到书花了4天。书翻译的差强人意，不过这本书还是挺不错的，质量也很好。
•   非常好的书，十分好
•   其实是教辅资料了，书摸上去质感也挺好的，看着很舒服，但有股臭臭的味道，，，不知道是油墨还是什么
•   书编的挺好的，可以当做课本用~
•   上课的教材，交大的老师说这书不错，翻译的也不错
•   要上课的书，是想要的那本
•   但是到手上略有点褶皱 破损 我很喜欢书 所以很心疼
•   书不错翻译质量也还可以
•   书质量还行，就是翻译差点
•   书的品质好，送货也快
•   稍微看了看，不知道是翻译有误还是原版如此，有些地方表达不通顺
•   内容解释较全面，值得一读
•   纸张还行，物流非常给力，隔天就收到了，内容还没看，现在看来总体不错
•   内容比严蔚敏奶奶的要多，还没看完继续看
•   实用，但是难度较高，偏重于数学。
•   很好 讲得详细
•   感觉不错，看目录从浅入深，应该适合初学者
•   读书时不努力，现在蛋疼
•   不错,送货及时
•   上课要用的 学校都没有了 来的很及时
•   还没读呢.
•   经典之作，很是受益
•   有C语言的基础就能够看懂!
•   价格比较便宜 书是新的 和同学一起订了的 感觉不错 会常来看哦
•   好使用！！！
•   速度很快 质量超好 不错的
•   通常翻译的书都不怎么样，所以就不评价翻译了。
  书的内容还可以，涉及的算法的面很广，算法讲的简明但是完整，每部分其实可以算是对相关问题的一个引子。可以快速入门。然后如果对相关问题还敢兴趣的话，可以查阅算法导论去看算法的详细的分析
•   学校要求要订的书，讲到一些算法思想，对优化编程有一些帮助。
•   算法的入门级参考书吧
•   好难好难
  不过例子超多
•   今天刚刚收到书，可能下雨天的关系吧，边角有点皱，不过整体挺好的。。。
•   书的包装不错，内容还没看，只是这次速度很慢！
•   还没开始读。真不知道是什么原因，这本书有股怪味，，我周围同学买的也是有。。。
•   还没有看，似乎是高校教材，纸张一般吧
•   教材，没什么可以说的
•   应该算不错吧 但可能不太适合我
•   以前在当当买过多次书，都没什么问题。这次就没查看，现在当我打开书时书的20-33页就有7页印刷有问题，即是字双重错开，看不清楚。其他部分暂时还没有发现问题。希望下次能够对其旗下书籍严格把关。
•   内容还算丰富，但是感觉部分内容说的太简单抽象了……
•   书里面的内容没的说，不错。老师推荐的教材。但是卓越的服务态度太差了。到手后书脊全部坏掉了。胶裂了两处，害得我用胶带粘起来凑合用。
•   算法设计的经典书籍，
•   封面好像是红色的 建议你们吧图片换掉成和实物一致
•   老师指定的参考书，看完它了，真心不错，比算法导论简单易懂
•   很不错的一本算法图书
•   这本算法分析的书讲得比较好，用得伪代码，零基础的同学都可以看懂！赞一个！
•   感觉书本不错的，只是我不是很看得懂
•   买了好几本书，就这本质量最好了
•   之前学校订教材，自己没有买……还行吧，算法分析本来就一门比较难的课，这书写的相对比较简略
•   觉得应该是一本好书。
•   总体挺不错的，就是读着有点枯燥
•   除了算法导论，个人觉得最不错的介绍算法的书了，适合教学。
•   发货很快，，书是正版，，，学习算法的教材书哦！！
•   书很不错，值得购买，评价一下
•   内容不错 ，适合学习
•   一本将算法的书
•   很不错 ，很喜欢很不错 ，很喜欢
•   算法书中的经典