算法引论

出版时间：2010-1  出版社：电子工业出版社  作者：[美]乌迪·曼博(Udi Manber)  页数：334  
Tag标签：无  

前言

编写本书的动机来源于我在教学实践中常常无法为给定算法给出清晰解析的困惑。与许多教师一样，我发现对一些学生来说，要他们亲自动手解决一些简单问题有困难，而让他们理解给定问题的解决方案同样有困难。我相信，事物的两个方面——创造和解释——是相关而不可分离的。为了完全了解一个问题，考察最后的答案远远不够，我们必须了解问题的求解过程。 本书强调了算法设计的创造性方面，其主要目的是要告诉读者如何去设计一个新的算法。本书描述算法的顺序不是“问题X、算法A、算法A'、程序P、程序P'”，而是像（但并不总是）“问题X、直接明了的问题求解算法、缺点、改进这些缺点的困难、（可能包含一些错误的）好的算法、进一步的改进、分析以及其他方法和算法的关系”。本书的目标不是给出一个容易转换为程序代码的算法，而是希望读者理解算法的原理。算法因此被解释为创造过程而不是最终产品。我们讲授算法的目标不仅是说明如何求解特定的问题，还包括传授如何求解未来将产生或遇到的新问题的技术。可以说，讲授算法设计的思维过程与讲授问题求解细节是同样重要的。

内容概要

本书是国际算法大师乌迪·曼博（Udi Manber）博士撰写的一本享有盛誉的著作。全书共分12章：第1章到第4章为介绍性内容，涉及数学归纳法、算法分析、数据结构等内容；第5章提出了与归纳证明进行类比的算法设计思想；第6章到第9章分别给出了4个领域的算法，如序列和集合的算法、图算法、几何算法、代数和数值算法；第10章涉及归约，也是第11章的序幕，而后者涉及NP完全问题；第12章则介绍了并行算法；最后是部分习题的答案及参考文献。本书的特色有二，旨在提高读者的问题求解能力，使读者能够理解算法设计的过程和思想：一是强调算法设计的创造性过程，注重算法设计背后的创造性思想，而不拘泥于某个具体算法的详细讨论；二是将算法设计类比于定理归纳证明，揭示了算法设计的基本思想和本质。    本书的组织结构清晰且易于理解，强调了创造性，具有浓郁特色，时至今日仍有其巨大的价值，并且适合作为计算机及相关专业算法和高级算法课程的教材。

作者简介

曼博（Udi Manber）美国著名的计算机科学家，国际公认的算法大师，在线信息搜索引擎的先驱。1982年于华盛顿大学获得计算机科学博士学位，曾是美国亚利桑那大学计算机专业教授。离开学校后在雅虎公司担任执行官，闫前是亚马逊（Amazon.com）的副总裁和首席算法师（CAO），也是亚马逊旗下搜索网站A9.corn的首席执行官。他提出的UDI测试已经成为衡量搜索引擎质量的评估标准。

书籍目录

第1章  引论第2章　数学归纳法　2.1  引言　2.2　三个简单的例子　2.3　平面内区域的计数　2.4　简单的着色问题　2.5　复杂一些的加法题　2.6　一个简单的不等式　2.7　欧拉公式　2.8　图论中的一个问题　2.9　格雷码　2.10　在图上寻找无重边的路　2.11　数学平均数和几何平均数定理　2.12　循环不变量：将十进制数转换为二进制数　2.13　常见的错误　2.14　小结第3章　算法分析　3.1　引言　3.2　符号O　3.3　时间与空间复杂度　3.4　习之和　3.5　递推关系　　3.5.1　巧妙地猜测　　3.5.2　分治关系　　3.5.3　涉及全部历史的递推关系　3.6　一些有用的证明论据　3.7　小结第4章　数据结构简介　4.1  引言　4.2　基本数据结构　　4.2.1　元素　　4.2.2　数组　　4.2.3　记录　　4.2.4　链表　4.3　树　　4.3.1  树的表示　　4.3.2　堆　　4.3.3　二叉搜索树　　4.3.4　AVL树　4.4　散列　4.5　合并碴找问题　4.6  图　4.7　小结第5章　基于归纳的算法设计　5.1  引言　5.2　多项式求值　5.3　最大导出子图　5.4　寻找一对一映射　5.5　社会名流问题　5.6　分治算法：轮廓问题　5.7　在二叉树中计算平衡因子　5.8　寻找最大连续子序列　5.9　增强归纳假设　5.10　动态规划：背包问题　5.11　常见的错误　5.12　小结第6章　序列和集合的算法　6.1  引言　6.2　二叉搜索的几种形式　　6.2.1  纯二叉搜索　　6.2.2　循环序列的二叉搜索　　6.2.3　二叉搜索特殊下标　　6.2.4　二叉搜索长度未知的序列　　6.2.5　重叠子序列问题　　6.2.6　解方程　6.3  内插搜索　6.4　排序　　6.4.1　桶排序和基数排序　　6.4.2　插入排序和选择排序　　6.4.3　归并排序　　6.4.4　快速排序　　6.4.5　堆排序　　……第7章　图算法第8章　几何算法第9章　代数和数值算法第10章　归约第11章　NP完全问题第12章　并行算法部分习题答案参考文献

章节摘录

插图：在《韦氏大学词典（第九版）》中，算法的解释是“求解数学问题（如寻找最大公约数）的一个过程，该过程步骤有限，通常还涉及重复的操作；广义地说，算法是按部就班解决一个问题或完成某个目标的过程。本书取广义的算法来定义。算法设计是一个古老的研究领域。自古以来，人们总是对发现更好的目标求解方法充满兴趣，不论是取火、建造金字塔还是对邮件进行排序。而计算机算法的研究当然是一个新的领域。一些计算机算法采用的方法早在计算机发明之前就存在，但大多数计算机算法的设计需要新的方法和技术。首先，告诉计算机诸如“察看小山，如果发现敌情就拉响警报”是不够的。一台计算机必须了解“察看”的确切含义，知道如何识别敌情，懂得如何拉响警报（基于技术原因，拉响警报是最容易的）。一台计算机可接受的指令应当是定义明确、长度有限的基本操作序列。将通常的命令转换为计算机可以理解的指令是一个困难的过程，而该过程就是编程，目前有成百万的程序员正在不同层次上进行编程。计算机上的编程，所需要的不仅仅是将那些为人所理解的命令转换为计算机可以理解的语言。在大多数情况下，程序员必须设计出完全崭新的算法来求解问题。只学习与计算机交谈所用的怪异语言会使编程变得困难，因为只有计算机才知道你说了什么。计算机不仅能以极快的速度执行先前由人完成的操作，它还可以做得更多。计算机能处理数十亿、数万亿比特单位的信息，能在一秒内完成数百万条基本指令。在这个数量级上进行算法设计是一种崭新的实践，有很多方面会与我们的直觉相反，因为我们通常只对自己能感知的事物进行思考。遗憾的是，一些能很好解决小问题的程序在处理大问题时就变得很糟。因此当进行大规模计算时不要忽视算法的复杂度和有效性。

编辑推荐

《算法引论:一种创造性方法》是国际算法大师乌迪·曼博（UdiManber）博士撰写的一本享有盛誉的著作，强调了算法设计的创造性方面，通过算法开发步骤来描述算法设计过程。此外，《算法引论:一种创造性方法》创造性地将算法设计过程同定理归纳证明过程进行类比，揭示了算法设计的基本思想和本质，旨在提高读者的问题求解以及理解算法设计的过程和思想的能力。《算法引论:一种创造性方法》特点：包括经典算法以及流行算法算法设计技巧及其综合应用并行算法设计犬多数算法的伪代码表示500多道习题，其中四分之一给出了答案将算法实现细节和算法思想尽可能分离

用户评论 (总计45条)

•   Amazon的原首席技术官所作。应该属于最好的算法书之一。本书的特色是强调了证明与演绎的过程，让人知其然并知其所以然，这一点是强过《算法导论》（the CLRS book）的地方。本书更适合有一定编程基础，想从全新角度学习算法的人士。如果是零基础的纯入门，也许CLRS更好，应为更详细（相应的，废话会更多）。
•   对比经典的塞奇伟克的《算法I-IV》,开创算法学科传奇的《计算机程序设计艺术》...等等，这本少了学院式的推导和工具书查阅的实用，但是，却多了一份至关重要的：怎么样思考，用算法的思想来思考，从而更具有在实践中自行得到适合解决方案的能力！
•   算法的设计不仅要熟悉一些经典算法，还要知其所以然，这样才能在解决具体问题中来设计出有效的算法。这本书用归纳法的来分析了很多算法的设计，让思维过程更加连贯，继续学习中
•   本书可以告诉我们算法从哪里来。正如本书副标题的一种创造性方法，当我们掌握了这种方法以后，我们就有一种不同一般的观点。再读其它算法方面的书时，我们会有一种不过如此的感觉。这是一本二十年前的九阴真经。
•   循序渐进的讲解了算法的各种知识。
•   没有《算法导论》细，但题目更多。
•   作者在算法界是个神般的人物，里面有他多年从事算法研究的心得，是独家的，其他人其他书都没有的，受益匪浅。
•   这本书有些高级，建议先学些初级的数据结构。
•   内容新颖，适合用作教材
•   这本书相当不错，感觉正是我急需的
•   原来就想买这本书，然而缺货，现在终于买到了，是新版本的
•   网上高手推荐的此书~买来拜读解惑~
  快递速度超快~这次两天就到货~包装质量也都无问题~可惜的是书体有点脏~
•   让人知其然跟知其所以然，知道what，更知道why
•   工科生的书，我不懂啊。。。看他一直都在看，应该挺不错的
•   算法之为何？抽象到具体，算法之精要深入骨髓。唯有创造性算法，才算成就！
•   这本书主要是分类讲解各种算法的理论知识，建议喜欢读伪代码学算法的同志买别的书~
•   相比《算法导论》，《引论》别具风格。以前在图书馆看到，觉得不错
•   书不错,在算法方面介绍得比较全面，主要精神是教你如何分治
•   书虽然不厚，但内容非常详实，讲解的很不错，不过要是有配套的书（代码实现、习题答案）就更好了。
  习题很难，1/4的有答案，但剩下的3/4就算做了也不知道对不对。
•   这本书出版日期是2011年的。印刷质量貌似不过关，好像还有味道。
•   很好，值得慢慢深读！
•   感觉送货速度挺快的
•   本书创造性地将算法设计过程同定理归纳证明过程进行类比，揭示了算法设计的基本思想和本质
•   上课用书，主要是数学归纳法，还行吧
•   濂戒功
•   [...]算法引论：一种创造性方法2009年02月26日 17:04这是一本可以给人带来巨大阅读乐趣的专业书籍。作者娓娓道来，又惜墨如金。用极精炼的语言，为我们指明了一条通向那些美丽算法的线索。我要由衷地说：这本书不仅仅是一些结果的集合，更是一段美好的旅程。我对书中涉及的内容已然熟悉，但读过之后仍感收获良多，对算法这门学问又多了些认识。真的是，写书当如是。　　　　　　对我来说，算法的教与学有两个困难的地方：　　　　其一，我们学习了那些经典的算法，除了赞叹一下设计的巧思，但总难免问上一句：怎么想到的？对学生来说，这可能是最费解、也最让人窝火的地方。我们下再多的功夫去记忆书上的算法、去分析这些算法的效率，却终究不能理喻得到这些算法的过程。心理盘算着：给我一个新问题，让我设计个算法出来，我能行吗？答案是：不知道。　　　　可这偏偏又是极重要的，无论作研究还是实际工作，一个计算机专业人士最重要的能力，就是解决问题——解决那些不断从理论模型、或者从实际应用中冒出来的新问题。　　　　其二，算法作为一门学问，有两条正交的线索。一个是算法处理的对象：数、矩阵、集合、串(strings)、排列(permutations)、图(graph...s)、表达式(formula)、分布(distributions)，等等。一个是算法的设计思想：贪婪、分治、动态规划、线性规划、局部搜索(local search)，等等。这两条线索几乎是相互独立的：同一个离散对象，例如图，稍有不同的问题，例如single-source shortest path和all-pair shortest path，就可以用到不同的设计思想，如贪婪和动态规划；而完全不同的离散对象上的问题，例如排序和整数乘法，也许就会用到相同的思想，例如分治。　　　　两条线索交织在一起，该如何表述。对学生而言，不同离散对象的差别是直观的——我们已经惯于在一章里面完全讲排序、而在另一章里面完全讲图论算法；可是对算法而言，设计思想的差别是根本的，因为这是从问题的结构来的：不同离散对象上面定义的问题，可以展现出类似的结构，而这结构特征，就是支持一类算法的根本，也是我们设计算法的依据。　　　　　　 阅读更多 ›
•   Udi Manner确实是算法大师，很多国内的书对算法的描述都是描述其最终形式，本书描述的是得到最终算法形式的过程，对于我们设计新算法非常有帮助，很多算法看了其他书再看这本书，会有豁然开朗的感觉！强烈推荐。作者用词非常严谨，思路很严密，用语也精练，看这本书的时候大脑比较累，不过也很锻炼人！看此书时候的相当于是数学书，我看了此书后再去参加各种算法机试、笔试、面试的时候容易多了！
•   卓越发货速度快，书的质量也很好。看了不少算法书，都是翻了几页就看不下去。而这本却是充满了往下看的兴趣。
•   内容不错，讲得挺好，循序渐进的讲，值得一看。
•   我是程序员，我推荐此书
•   帮朋友买的, 他说还不错.
•   推荐IT人士读，对提升算法很有帮助
•   耐心看完会有很大的收获，尤其是在思维方法上
•   有别于其他经典算法图书主要针对具体算法的详细讨论，重点在于锻炼算法设计能力而不是算法应用能力。
•   速度很快啊！书也很好，谢谢！
•   听说是好书，买了一本，看了很吃力。所以又买了本零基础学算法，先补补基础。
•   书是好书，可惜发现的太晚了
•   翻译的不够好, 这要是大多数译书的问题.原书太贵了, 而且中国没得卖, 英文版亚马逊价格竟然是90美元, 实在是望书兴叹
•   上课要用的书,内容不错.
•   本书是一位博士写的, 未免有点pedantic, 中文翻译, 感觉技术有限, 读起来发涩. 如果有原版的话, 我是一定不会买这个中文版的, 翻译的程度, 确实是, 相当有限. 只能这么说, 如果是这本的话, 还是推荐各位看原版的书.
•   有别于一般的算法书
•   很不错的书，内容很好，我很喜欢。
•   算法首选书
•   帮别人买的，号称很不错
•   好书！！！学习中！！！！