Anany Levitin_算法设计与分析基础.pdf

所需积分/C币:10 2016-07-22 15:07:04 19.13MB PDF

国外经典教材·计算机科学与技术:该书作者基于教学经验,开发了一套对算法进行分类的新方法。内容包括算法效率分析基础、蛮力法、分治法、减治法、变治法、动态规划等11章。各章节均含有习题,书后给出体系提示。
出版说明 近年来。我国的高等教育特别是计算机学科教育,逛行了一系外大的调整和改革,急 需一批门类齐全、具有国际先进水平的计算机经典教材,以适应龍我国计算机科学的教 学需要。通过使用图外先进的经典教材,可以了解并吸收国际先进的教学思想和教学方法 使我国的计算机科学教育能够跟上国际计算机教育发展的步伐,从而培育出更多具有国际 水准的计算机专业人才,增强我國计算机产业的核心党予力。为此,我们从国外知名的出 版集团 Pearson引进这会“国外经典教材·计算机科学与技术”教材 作为全球最大的图书出版机构, Pearson在高等教育领域有着不凡的表现,其下属的 Prentice hal和 Addison Wesley岀版社是全球计算机髙等教育的龙头出版机构。清华大学 出版社与 Pearson出版集团长期保持着紧密友好的合作关系,这次引进的“国外经典教 材·计算机科学与技术”教材大部分出自 Prentice Hal和 Addison Wesley两家出版社。为 了组织该套教材的出版,我们在国内聘请了批細名的专家和教授,成立了个专门的教 材编审委员会。 教材编审委员会的运作从教材的选题阶段即开始启动,各位委员根据国内外商等院校 计算机科学及相关专业的现有课程体系,并结合各个专业的培养方向,从 Pearson出版的 计算系列教材中精心挑选针对性强的题材,以保证该套教材的优秀性和领先性,避兔出 现“低质重复引进”或“高质消化不良”的现象 为了保证出版质,我们为该套教材配备了一批给验丰富的编辑、排版、校对人员, 制定了更加严格的出版流程。本套教材的译者,全部来于对应专业的高校教师或拥有相 关经验的IT专家。本教材的责编在翻译伊始,就定期不间断地与该书的译者进行交流 与反偾。为了尽可能地保留与发扬教材原著的精华,在经过翻译、排版和传统的三审三校 之后,我们还请編审委员或相关的专家教授对文稿进行事读,以最大程度地弥补和修正在 前面一系列加工过程中对教材造成的误差和瑕疵。 由于时间紧迫和受全体制作人员自身能力所限,该套教材在出版过程中很可能还存在 些遗憾,欢迎广大师生来电来信批评指正。同时,也欢迎读者朋友积极向我们推荐各类 优秀的国外计算机教材,共同为我国高等院棱计算机教育事业贡献力量。 清华大学出版社 200403.20 国外经典教材·计算机科学与技术 编审委员会 主任委员: 家广 清半大学教授 副主任委员: 周立柱 清华大学教授 委员(按姓氏笔画排序 王成 天津大学教授 王册 中国人民大学教授 冯少荣 厦门大学教授 兴全源 西南交通大学教授 刘乐 华中科投大学教授 刘腾红 中南财经政法大学教授 吉枨枚 南京师范大学教授 孙吉贤 吉林大学教投 阮秋琦 北京交通大学教授 何晨 上海交通学教授 吴百锋 复∏大学教授 李彤 云南大学教授 沈钧毅 西安交通大学教授 邵志清 华东理工大学教授 陈纯 渐江大学教授 陈钟 北京大学教授 陈道譯 南京大学教授 周伯生 北京航空航大大学教投 孟祥旭 山东大学教授 姚淑珍 北京航竿航天大学教授 徐佩霞 中国科学技术大学教授 徐晓飞 昑尔滨工业大学教授 秦小麟 南京航空航天大学教授 饯培德 苏州大学教授 曹元大 北京理大学教授 龚声萃 苏州大学教授 谢希亻 屮人民解放军理上大学教授 译者序 关于这本书的意义和它的主要内容,作者在序和跋中讲得已经够多够好的了。我只想 谈谈自己在翻详过程中的一些感想。 首先,我要恭喜拿到这本书的读者,你们是幸运的。我们读书的年代,很少有大学会 教授算法课,惟一和这门课程比较相近的是数据结构。这一点我求证过很多人,只是遇到 个例外,一位毕业于西南师范大学的同事告诉我,她的母校同时开设了数据结构课程和 算法课程。遗憾的是,十年过去了,她很难回忆起这两门课程之间的显著区别。很明显, 如果算法设计课程真的像本书所描述得那么精彩的话,我们很有必要对算法设计及分析课 程绘予高度的重视。之所以这么说不是因为数据结构不重要,而是因为,算法设计与分析 的角度和商度都是不同于数据结构的: ●从考忠问题的角度来看,数据结构主要关心不同的数据结构在计算机解题屮的作 用和效率;而算法设计与分析则关心不岡的算法设计技术的适用性和效率。这使 得这两门课稞在某种程度上有所重叠,但又无法相互替代。 ●从考虑问题的高度来看,数据结构关心的是计算机解题的具体问题,所以很适合 作为计算机技术的入门课程之一;但算法投计与分析则要宽泛地多,它很适合计 算机寺业的学生学习,但又不仅限于解决计算机解题的问题。木书的作者说得好 授人纵鱼,不如授人以渔”( Learning such Lechniques is akin to learning to fish as opposed to being given a fish caught by somebody else)。当把算法设计与分析提升 为一种解决问题的通用方法时,读者·一定会有很大的收获,而且有可能终生受益 其次,我要庆率自u有机会翻译一本这么好的图书。这不仅因为在翻译的过程当中, 我为自己补上了灬-门算法设计与分析课程,而且,能够普及优秀献图书也是我的愿望,惟 的担心是自己的能小不足,所以书中无法避免会存在种种失误。读者应该及时向我指出 以便在未来的版本中不断完善。 最后,我要感谢清华大学出版社对我的信仟,以及在翻译过程屮,诸位编辑给予的帮 助。还要感谢我的家人,他们都大力支持我的作,使我能够以饱满的热情完成翻译工作。 尤其是我的太太李靓、她辅助我翻译了本书的大部分章节,并且输入了所有的公式,我很 感激她的时刻陪伴。 潘彦,2003年11月19H于上海 panyan(@dhzq.com 前言 个人接受科技教商得到的最大收获,是那些能够受用一生的一般性智能工具 George Forsythe,《计算机科学家到来以前我们做什么》,1968 九论是计算科学还是计算实或,算法都在其中扮演着重要角色。由于这一事实,这门 学科中出现了大量的教科书。它们在介绍算法的时候,基本上都选择了以下两种方案中的 种。第一种方案是按照问题的类型对算法分类。这类教科书安排了不同的章节分别讨论 排序、查找、图等笪法。这种做法的优点是,对于解决同问题的不同算法,它能够立即 七较这些算汏的效率。其缺点存于,由于过于强调问题的类型,它忽略了对算法设计技术 的讨论。 第种方案围绕着算法设计技术来组织章节。在这种结构中,即使算法来自予不同的 计算领域,如果亡们采用了相同的设计技术,就会被编成组。从各方荻得的信心(例如 LBaY95])使我相信,这种绪构对算法设计与分析的基础课程尤为适合。强调算法设计技 术有3个重要原;。第一,学生们在解决新问题时,可以运用这些技术设计出新的算法 从实用的角度看,这使学习算法设计技术成为一种很有价值的努力。第二,学生们会尝试 着拨照算法的内在设计方法,来对已知的众多法进行分类。计算机科学教育的一个主要 目的,就是使学生们通过学习,能够了解不网应用领域的算法间的共性。毕竞,每门科学 都会倾向于把它的重要主题归纳为几个甚至一个理论。第三,依我看来,算法设计技术作 为问题求解的-般性策略,在解决计算杌领域以外的问趨时,也能发挥相当大约作用 日前已纶出版了些围绕算法设讨技术进行组织的教科书(参见[B9],[HSR981 NN98])。但这些书的问题在于,它们未加批判地遵循了相同的设计技不分类法。无论是 从理论还是从教育的观点来看,这种分类法都存在一些严重的缺咯。其中最显著的缺陷就 是无法对许多重要的算法进行分类。由于这种局限性,这些书的作者不得不在按照设计拉 术进行分类的同时,另外增加一些章节,来讨论特殊的问题类型。遗憾的是,这种改变导 致课程缺乏一致性,而且很可能会使学生产生疑惑。 算法设计技术的新分类法 现有的算法设计技术分类法的缺路给我带来了困难,它激发我开发个基于设计技术 ①译注: George Forsythe认为,在这些工具当中、最重要的3项依次是自然语会、数学和计算机科学 ⅵ算法设计与分析基础 的新分类法[Lev99],该分类法就是本书的基础。以下是这个新分类法的几个主要优势 ●新分类法比恃统分类法更容易玊解它包含某些设计策略,比如蛮力法、减治 法、变治法和时空权衡,几乎从不被人们当作重要的设计范例。 新分类法很自然烛覆盖了许多传统法无法分类的经典算法(欧几里得算法、堆 排序、査找树、散列法、拓扑排序、高斯消去法、霍纳法则等,不胜枚举〉。所 以,它能够以一和连贳、一致的方式表达这些经典算法的杯准内容 新分类法很自然地包容了一些设计技术的重要变种(比如:它涵盖了碱治法的3 个变种和变治法的3个变种) ●在分析算法效率时,新分类法与分析方法结合得更好(参见附录B) 设计技术作为问题求解的一般性策略 本书中,设计技术主要应用于计算机科学中的经典问题。这里性一的创新是引入了 些数值算法的内容,这些算法也包含在相同的通用框架之中。(“计算机教音大纲2001 一种全新模式的计算机科学误程体系”[CC01中提倡包含数值算法)但我们也可以把这些 设计技术看成问题求解的一般性工具,它们的应用不仅限于传统的计算问题和数学问题。 有两个因素令这一点变得尤其重要。第一,越来越多的计算应用超越了它们传统的领域 并且有足够理由使人相信,这种趋势会愈演愈烈。第二,人们渐渐认识到,提高学生们的 问题求解能力是癌等教育的一个主要目标。为了满足这个目标,在计算机科学课程体系中 安排一门关于算法设计和分析的课程是非常合适的,因为它会告诉学生如何应用一些特定 的策略来解决问题。虽然我并不建议将算法做计和分析课程变成一门教授一般性问题求解 方法的课程,但我的确认为,我们不应错过算法投计和分析课程提供的这样一个独无二 的机会。所以,本书包含的某些应用是利谜题相关的。虽然利用谜题来教授算法课程决不 是个新的想法,但本书打算通过引进一些全新的例子来系统地实现这个思路。 如何使用本书 我的目标是写一本既不泛泛而谈,又能被学生们独立阅读的教材。为了实现这个目标, 本书做了如下努力: ●根据 George Forsythe的观点(参见引语),我试图着重强调邢些隐藏在算法设计 和分析背后的主要思想。在选择特定的算法来阐述这些思想的时傧,我并不倾向 于涉及大量的算法,而是选择那些能够揭示出…个根本的设计技术或是分析方法 的算法。宰运的是,大多数经典算法满足这个要求 第2章主要分析算法的效率,该单将分析非递归算法的方法和分析递归算法的方 法区别开来。这一章还花了些篇幅介绍算法实证分析以及算法可视化 ●书中系统地为读者安排了一些间题。其中有些河题是经过精心设计的,而且立即 前言 提供答案,目的是引起读者的注意或是疑问。其余问题的用意是防止读者走马观 花,而对本书的理解不能达到令人满意的水平。 每章结束时都会对本章最重要的概念和结论做一个总结。 本书包含大约600道习题。有些习题是用于练习;另外一些则足为了指出书中正 文部分所涉及内容的重要意义,或是为了介绍些书中没有涉及到的算法。有 些习题是从因特网上找到的,还有些习题是让读者为后面堂节将要涉及的内容做 准备的。较难的习题数量不多,会在教师用书中用-种特帐的记号标注出来(因 为有些学生可能没有勇气做那些标有难度的习题,所以本书没有对习题标注难 度〕。谜题类的习题用了一种特殊的图标做标注。 本书所有的习题都附有提示。除了编程练习,习题的详细解法都能够在教师用书 中找到,符合条件的读者可以从出版社得到教师用书(请联系 Addison- Wesley公 司的销售代表,或者发电子邮件全<Ew.cse@Daw.com)。本书的任何溪者都可以向 www:aw.com/cssuppor网站寻求支持。 读者所需的知识背景 本书假定读者已经学习了离散数学的标准课程和一门基础性的编程课程。在这样一种 知识背景下,读者应该能够掌握本书的内容而不会遇到太大的困难。尽管如此,L,4节、 附录A和附录B仍然会对基本的数裾结构、必须用到的求和公式和递推关系分别做∫复 习和回顾。只有3个小节(22节、104节和114节)会用到·一些简单的徽积分知识;如 果学生们缺少必要的微积分知识,完全可以跳过这3个包含微积分内容的小节,这样做不 会妨碍对本书其余部分的理解。 进度安排 如果打算开设-门围绕算法设计技术来讲解算法设计和分析理论的基础课程,本书乐 以作为这门课的教科书。对于=门典型的单学期课程来说,本书涵盖的内容可能过计丰富 了大体上来说,跳过第3章至第l章的部分内容不会影响读者对后面部分的理解。本 书的任何一个部分都可以安排学生自学。特别要指出的是,26节和27节分别介绍了实证 分析和算法可视化,这两小节的内容可以结合练“布置给学生。 下面提供-种针对一个学期课程的教学安排,它是按照40课时的集中授课时间设 计的。 ①译注:“练习”的原文为“ pRoject”,般应该翻译成“项耳”但闺外“般将布置在谋后完的、较大 型的、要求实际演练的习燃称为 project,国内没有相应的称呼,所以始且译为“练习” vi算法设计与分析基础 课次 主题 小节 课程简介 1.1-1.3 3、4 分析框架:O、⊙和Ω2符号 2.1,2.2 非递归算法的数学分析 6、7 递归算法的数学分析 2.4,2.5(+附录B) 蛮力算法 3.1,3.2(+3.3) 穷举查找 3.4 10-12分治法:合并排序、快速排序、折半查找 4.1-4.3 13 分治法的其他例子 44或4.5或46 14-16减一算法:插入排序、DFS和BFS、拓扑排序 5.1-53 17 减常量算法 5.5 减变量算法 5.6 19-21实例化简、预排序、高斯消去法、平衡查找树 6.1-6.3 22 改变表现:堆和堆排序 6,4 23 改变表现:霍纳法则和二进制幂 65 24 问题化简 6.6 25-27时空权衡:串匹配、散列法、B树 7.2-7.4 28-30动态规划算法 8.1-84(选3节) 31-33贪婪算法:Pim算法、 Kruskal算法、 Dijkstra算法、哈夫曼算法91-94 34 下界的参数 10.1 35 决策树 10.2 36 P、NP和NP完全问题 10.3 37 数值算法 10.4(+114) 38 回溯 11.1 分支界限 112 4 NP困难问题的近似算法 11.3 Anany Levitin anany. levitin@@villanova. edu 2002年8月 目录 算章绪论 b●pa哪罪看■■■画●晶■画晶Lh如血如·b晶山自晶■山山如■山晶暴晶■晶唱唱小晶冒山山■■■画暑国■福号督国号P■昏■■管即■ 算法的概念 d·l·■■日日■P ■亡如音自曾倡十■『"P管■十■亡十P 习题1.1 l.2算法问题求解基础 习题1.2 13重要的问题类型 ………………15 题13 14基本数据结构 习题14 ■■■■ 小结 31 第2章算法救率分析基础“r…r…….13 21分析框架 T■平P↓■■■ ………34 习题2.1……… 22渐进符号和基本效率类型…… 以趣2,2………………………………………………… 47 23非递归算法的数学分析 ………49 习题2,3…… 53 24递归算法的数学分析 55 习题24 II■十■昏■■·■一Ib■备P↓P早■+l■↓十■+■ 25例题:斐波那契数列………………………………………… 63 习题2,5 26算法的经验分析 习题26… ■亡h早q 27算法可视法 ■司■q1聊P画p即■日■日自一鲁一■■1自自冒如■自■日t 小结 77 第3章蛮力法…,…- PPP血甲唱平省中中甲卓香 3】选择排序和冒泡排序 习题3,1………… ……83 3,2顺序查找和蛮力字符串匹配……… …………名3 习趑3,2… 85 33最近对和凸包问题的蛮力算法… 习题3.3 旷■【■十矿■4■一_■■■d+·平!十I■甲■甲■晋■ 34穷举查找

...展开详情
img
Nicolas0311
  • 领英

    绑定领英第三方账户获取
  • GitHub

    绑定GitHub第三方账户获取
  • 脉脉勋章

    绑定脉脉第三方账户获得
  • 技术圈认证

    用户完成年度认证,即可获得

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐