算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf

所需积分/C币:50 2019-03-31 16:03:13 164.2MB PDF
收藏 收藏 5
举报

本书由算法领域的知名专家Steven Skiena教授编写,其主要内容包括基本算法设计、算法分析、数据结构、排序与查找、图算法、动态规划以及难解问题与近似算法。 “设计”是本书的核心,作者不但以生动有趣的语言讲授了算法设计中的常用技术与思想,还着重教导我们应从已有经典设计和实现中汲取力量来完成问题求解,而这正是一个优秀算法工作者所必备的素养。为了更全面真实地展现作者的算法设计观,本书每章都给出了若干取自现实案例的精彩War Story,读者可以从中深刻体验到优秀算法设计的曲折历程。为了减轻阅读的难度,作者淡化了繁难的算法分析而仅仅给出性能结论与对比,这在同类算法书中是相当少见的。此外,本书配套
Translation from English language edition The algorithm Design manual. Second edition by Steven S Skiena Copyright c 2008. Springer Berlin Heidelberg Springer Berlin Heidelberg is a part of Springer Science+ Business Media All Rights Reserved 木书为英文版 The Algorithm Design Manual,, Second edition的简体巾文翻译版,作者 Steven s. Skiena,由 Springer出版社授权清华大学出版社出版发行。 北京市版权局著作权合同登记号图字:01-2009-3432号 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:010-6278298913701121933 图书在版编目(CIP)数据 算法设计指南(第2版)/(德)斯蒂文·斯金纳( Steven s. Skiena)著;谢勰译.一北京:清华大学 出版社,2017 (清华计算机图书译从) lSBN978-7-30245734-3 .①算…Ⅱ.①斯…②谢…Ⅲ.①算法设计一指南Ⅳ.①TP301.6-62 中国版木图书馆CIP数据核字(2016)第286940号 责任编辑:龙启铭 封面设计:傅瑞学 责任校对:梁毅 责任印制:李红英 出版发行:清华大学出版社 tiE:http://www.tup.com.cn,http://www.wgbook.com 地 址:北京清华大学学研大厦A座 编:100084 社总机:010-62770175 邮邮 购:010-62786544 投稿与读者服务:010-62776969,C-service(@tuptsinghua.edu.cn 质量反馈:010-62772015, Zhiliangaitup. tsinghua.edu.cn 课件下载:htt:/up.com.cn,010-62795954 印装者:清华大学印刷 经销:全国新华书店 开本:185mm×260mm 印张:23.75 字数:574千 版次:2017年7月第1版 印次:2G177月第1次印刷 印数:1~2000 定价:69.00元 产品编号:031141-01 中文版序 I have been gratified by the favorable reception which "The Aigorithm Design Manual"has received to, and very excited that Chinese readers will get a new exposure to it through this translation Seeing my book in translation into a distant language is always a very humbling experience: I know that I wrote it, yet realize that i will never be able to read it.I thank Xie Xie, the translators, for doing a particularly diligent job with my book I know he worked extra hard to translate the American-specific references I made throughout the book, which apparently made it more like translating a novel than a textbook I hope this book encourages greater study of algorithms in China. Indeed I hope that readers who work their way through it consider graduate study at stony brook University, where I teach. i hope you enjoy entering the world of algorithms, and find good luck with what you discover there STEVEN SKIENA Distinguished Teaching Professor Stony brook University 对于本书所获得的肯定我感到非常荣幸,而中文读者现在可以通过这部译本来 研读它,也让我非常激动 每当看到我的书被译成一种完全陌生的语言,我总是感到十分汗颜:我知道这是 我写的书,但更知道我永远没法读懂它.感谢本书的译者谢勰非常尽心尽力地去翻译 我的书.这本书用了很多面向美国本土读者的典故,我知道译者用了很多时间来诠释 它们,他为此所付出的辛勤工作更像是在翻译一本小说而不是单纯的教材. 我期望这本书能更深入地促进算法这门学科在中国的研究和发展.另外我衷心 希望那些学完本书的读者能够关注我所任教的石溪大学的研究生教育.期盼本书读 者能愉快地走进算法世界并有所收获,祝你们好运! STEVEN SKIENA 杰出教学教授 石溪大学 译者的话 名之立,旬月踟蹰 —严复 引介 算法世界中的故事由作者娓娓道来,各种设计技术非常自然地穿插其中,读者更像是在 阅读一本小说,你没看错,这就是 Steven skiena教授的名作 The Algorithm Design Manua 要是在美国亚马逊网站上输入“ Algorithms”,可以发现这本书长期排名居于前五,而且还 度是计算机算法类的最畅销书籍( Best seller).你可随手翻开一页往下读去,肯定觉得妙趣 横生不忍释卷,仿佛就像走进了 Skiena教授的课堂一样,这也许是它广受欢迎的主要原因 吧.此外, Skiena教授的主页上还提供了在线课程视频,若是身临其境更能深入体会其妙. 考虑到国内算法课程教学情况、我们认为本书的卷I(讨论“实用算法设计”)单独成书比 较适合讲授,而且携带这本“算法小说”也更为方便.为此我们征求了作者本人的同意,特将 这本书的精简版(仅包含卷1译出以飨读者.不过,阅读是一个可能随时中断的过程,而原书 中许多段落只能在课堂讲授的语境中才能理解,为此我们补充了一些起承转合的词句.此 外,作者对很多掌故信手拈来,而且经常还有弦外之音,妙则妙哉,可是对于不能一窥堂奥 的读者实为遗憾,中译本尽量对它们给出注释 说明 每章中的 War Story是本书的一大特色. War Story的原意是士兵脑海中难忘的战 争故事,而引申意则是每个人心中值得回忆的经历,一般都带着些惊险或艰难.尽管 英勇故事(取自《英汉大词典》)、艰难历程、算海拾贝、算法轶事都能在一定程度 上表达 War Story这个词,但它们都难以精确地等同于“作者 Skiena个人在算法方面 的 War story”∵.因此书中的 War Story仍按原文列出,读者可细细品味它的含义 大部分人名和书名按原文形式给出,少数历史人物和流传甚广的名著除外. 我们将" efficient algorithm”译为“高效算法”,但请注意这只是渐近意义上的“高效 第3章中“抽象数据类型”和“数据结构”这两个概念略有混淆,译文已作统一修改. 以log统一表示以2为底的对数.原书中较为混乱,有log,1g,log2等多种表示形式 ·倍数问题.例如“g(m) is a million times larger than f(mn)”,作者通常想表达的意思 是g(n)是f(n)的一百万倍,这是美国人的一种常用表述方式(尽管多有诟病 “和/或”(and/or)表述.如果我们说A和/或B,则意味着三种情况:可能是A;也可能 是B;还可能是A和B IV 译者的话 原书有许多网址已经失效,我们直接替换为最新地址但不再一一说明 读者可在http://www3.cs.stonybrookedu/-skiena/algorist/book/errata查 阅原书的最新勘误 卷中经常引用卷I的章节,精简版的译文未作删减,有兴趣的读者可查阅原书 相关内容.另外http://www3.cs.stonybrookedu/-skiena/algorist/book/中 的“ By Problem”分类亦收录了卷I中的所有问题(对应第12章到第18章) 本书由⑩X排版,书中的插图文件和原书基本一致(少量略作润色或重绘) 致谢 感谢原书作者 Steven skiena教授对中译本的大力支持,特别是他无私提供了书中所有 插图,并在百忙之中为中译本作序.此外,与 Skiena教授的多次讨论交流让我深深感受到他 的谦和、容忍和智慧.感谢 Vaughan Pratt教授对于‘ Pattern”一词的详细解释,他甚至查阅 了OED并详尽地叙述了这个词的源流感谢清华大学岀版社龙启铭编辑的不断鞭策和激励, 让我能够将这本书最终翻译完成.感谢李树钧博士在IX排版上的建议 互动 由于译者学识所限,书中必然有诸多疏漏之处,还望读者朋友们不吝赐教,您的宝贵意 见和建议可反馈至DSAD20150163.com勘误和瓷源将在https://github.com/xiexiexx/ Translations上发布.另外,我们还会在新浪微博/微信公众号“算法时空”上展开对中译本 的持续讨论与更新,敬请关注 谢 2017年1月 于古城西安 前言 我遇到的大多数专业程序员都不太愿意去解决算法设计问题.这点很遗憾,因为算法 设计已成长为计算机科学的核心实用技术之一.若想设计出正确、高效和易于实现的算法 去求解真实世界的问题,需要了解两种不同的知识体系: ·技术——优秀的算法设计师懂好几种基本算法设计技术,包括数据结构、动态规 划、深度优先搜索、回溯以及启发式方法.也许最最重要的设计技术应该就是建模 了,它能将杂乱现实世界中的应用问题提炼精化以便于用算法攻破,这可称得上是 门艺术 资源——优秀的算法设计师都站在巨人的肩膀上.他们不是每次都从一张白纸开始 费尽心思最后创造岀新算法来解决问题,他们会先弄清楚这个问题目前的研究现 状.他们不是从零开始重新实现那些广为流传的算法,他们会去寻找现有的程序实 现并以此作为起点.他们对许多经典算法问题都非常熟悉,这些问题为大多数应用 问题的建模提供了充足的素材. 本书意在作为算法设计的一本指南,从而让学生和计算机从业人员能走进组合算法技 术的殿堂.全书分为两卷:技术和资源.前者是对计算机算法设计和分析技术的一般性指引 后者则可让你进行查阅和参考,它是由多条简介构成的算法问题便览,1其中每一条都包含 了算法资料、程序实现以及大量的参考书目 致读者 自从1997年本书第1版初次面世以来,它所受到的热烈欢迎让我一直倍感欣慰.这本书 被视为一本独一无二的指南,它能教你用算法技术解决实际中的许多常见问题.不过,从本 书十年前问世至今,这个世界有了许多改变.实际上,如果我们将现代算法设计和分析的起 源定在1970年左右,那么从这本书诞生到现在的这个时间段在整个现代算法的发展历史中 占了大约30%之多 这本书有三个方面尤为受人钟爱:(1)算法问题便览,(2) War Story,(3)本书的电子 资源部分.这些特色在新版中得到了保留并有所加强: 算法问题便览——由于找出一个算法问题的现有进展可能会是一项艰巨的任务,因 此我提供了在实际中最重要的75个问题的简要介绍并汇集成“算法问题便览”.通过 查阅这份便览,学生或从业人员可以很快地确定他们的问题名称和该问题的研究现 状,以及如何利用现有工作的基础去解决它.为了帮你找到并确认问题,每条问题 简介都包含了“处理前”和“处理后”的对比示意图,2它们描述了输入和输出应符合 1译者注:在本书中,如无特殊说明,使览通常指稔I中的算法问题便览,每条简介都是一个关于算法问题的词条. 2译者注:这种示意图在算法问题便览中已经明确地标为“输入”和“输出” VI 的规格.有位颇具洞察力的评论家因为这份便览非常强大的缘故,将我的这本书称 作“算法世界搭车客手册”( The hitchhiker' Guide to algorithms) 算法问题便览是本书最重要的部分.为了在这一版中更好地改进它,我对每个问题 都向相关的世界级权威专家征求了反馈.而且新版尤为关注对每个问题的现有软件 实现讨论部分的更新 · War Story-—在实际中,算法问题不会出现在大项日的初始阶段.相反地,它们通 常会以子问题形式出现,而此时你肯定能看到如下情景:要么程序员不知道该如何 继续下去,要么目前的设计方案不足以完成该任务 为了让你更好地去观察了解算法问题在实际中究竞是如何出现的,我们在书中纳入 了一系列 War story,或者可称作“我们与真实问题交战所经历的故事”这些故事的 寓意是,算法设计和分析不仅仅是理论,它更是在你真有需要的时候可以派上用场 的一个重要工具 这一版保留了上一版中的所有 War Story(适当进行了更新),新增的 War Story覆盖 了外部排序、图算法和模拟退火以及一些其他主题. 电子资源部分——由于从事实际工作的人通常想找到一个程序而不光是算法,我们 提供了链接让你可以获取那些可靠的算法实现(只要原站点仍有效).同时我们也已 将这些实现汇集在网站(血ttp://ww.cs. sunysb.edu/-a1 gorith)上,读者可以很 方便地检索.本书初版刚问世之后没多久,我们这个站点就一直稳居 Google上的“算 法”网站排名首位. 此外,我们所提供的推荐建议能让你更容易地找出最适合于某项任务的代码.有了 这些程序实现之后,算法设计的关键问题就变成了对你的应用问题正确地建模,而 不是花时间去熟悉某个实际算法的细节.这个重要观点渗透于整本书之中 我们在本书中没有讲到的内容也同样重要.我们不强调数学形式的算法分析,所以大 多数的分析论证以较为直观的方式给出.你在这本书中找不到一个定理.如果需要了解更 多的细节,读者应该去研究本书中所提到的程序和参考文献.言以蔽之,这本指南的目标 是让你尽可能快地走上正确的方向 致教师 本书所涵盖的素材足以开设一门标准的“算法导论”课程.我们假设读者已学完相当于 中级编程的课程(通常名叫“数据结构”或“计算机科学(I”). 你可在http://www.algorist.com下载用于讲授这门课程的一整套课程幻灯片.此外, 我还基于上述幻灯片录制了在线音频和视频讲座,可供一个完整学期的算法课程使用.通 过神奇的互联网,让我来帮你教这门课! 本书强调的是设计而非分析.它既适用于传统的课堂授课,也适应于新兴的“主动式学 习方法,也就是教授不再讲课而是去引导学生分组来解决实际问题.实际上,本书的War Story就是主动式学习方法的鲜活实例 我在全书中做了很多教学法方面的改进.体现“教材导向”教学法的特征包括: 1译者注:脱胎于科幻名著《银河系搭车客指南》( The hitchhiker' s Guide to the galary) 前言 VII ●更轻松的讨论——本书卷I的讲解材料是上一版的两倍.新增部分注重对基础材料 给出更细致全面的阐述,而并不是去增加更多的专题 以错误开始——在算法教材中重要的算法通常会以既定事实的面貌出现,而这样会 掩盖其中的设计理念以及为何其他方案会失败的微妙原因. War Story通过一些应 用问题来讲解癒于解决方案背后的风起云涌,不过我还把这种讲授模式扩展到了经 典算法设计的内容中 ●停下来想想——这里会举例讲解我自己求解某个具体作业题时的思路演进——从 错误开始一直到最后解决的全过程.我把这类问题模块散布于整本教材中以提升读 者对解题活动的积极性.每个问题之后马上给出了解答 更多且更精良的课后习题——这一版的习题是前一版的两倍.那些在上一版中已 被发现不易理解或模棱两可的习题已作改进或替换.书中所有问题都标有难度等 级(从1到10) 自我激励式考试设计——在我的算法课中,我向学生保证所有的期中和期末考试题 都直接取自本书的习题.这样规定了一种“促学型考试”( student- motivated exam) 因此学生完全明白应该如何学习才能在考试中有好的表现.习题由我精心挑选而 得,可保证总数量、广度及难度都能满足这种考试的需求,此外备选问题不会过少 也不会过多. ρ所得教益——我们对这部分内容给出显著的阴影标记,以强调这是你需要从对应章 节中所汲取的大局观 编程挑战赛的相关錘接——每章的习题都包含三到五个“编程挑战赛”问题的链接, 它们来自http://www.programming-challenges.com这些链接可用于补充纸笔 算法课程所缺乏的实际编程教学环节 ·更多真代码,更少伪代码——本书中的算法更多是以代码(用C语言写成)而不是 伪代码形式出现.我认为对于较简单的算法而言,经过测试的真实程序实现不 但正确而且可靠,这可比那些形式化稍弱的表述1强多了.完整实现可于http //wwa]grist.com下载,你可以深入学习研究这些程序 ·章节注释—一卷I的每章都包含一个简短的章节注释,它们为读者指明了基本书目 和补充参考文献 致谢 十年后新书的题献会主要关注时间流逝中的世事变幻.自第1版问世后, Renee t经成 了我的妻子,然后又变成两个孩子( Bonnie和Abby)的母亲.我的父亲离开了人世,但我的母 亲和兄弟(Len与Rob)仍然与我同在,并且在我的生命中占据了非常重要的地位.我将这本 书献给我的家人,不管是新成员还是老成员,无论尚在或是离去 1译者注:指的是以伪代码或普通语言形式描述的算法 VIII 前言 我要感谢以下人士,他们为新版做出了卓越的贡献: Andrew gaun和 Betson Thomas提 供了很多方面的帮助,尤其是在构建新网站http://www.cs.sunysb.edu/-algorith的基 础架构和有关手稿准备的各类事项上. David gries热心无私地为本书提供了很有价值的反 馈. Himanshu gupta和 Bin Tang非常大胆地用这版的手稿在课堂讲授.此外,我还要感谢 我在 Springer出版社的编辑 Wayne Wheeler和 Allan Wylde. 我邀请了一批相关领域的算法大师审査了“算法世界搭车客手册”部分(即卷I〕的那些 章节,他们与我分享了聪明才智,并督促我不断进步.感谢他们 Ami Amir, Herve Bronnimann, Bernard Chazelle, Chris Chu, Scott Cotton, Yefim Dinitz, Komei Fukuda, Michael Goodrich, Lenny Heath, Cihat Imamoglu, Tao Jiang, David Karger, Giuseppe Liotta, Albert Mao, Silvano Martello. Catherine McGeoch, Kurt Mehlhorn, Scott A. Mitchell Naceur Meskini, Gene Myers, Gonzalo Navarro, Stephen North, Joe O'Rourke Mike Paterson Theo Pavlidis, Seth Pettie, Michel Pocchiola, Bart Preneel, Tomasz Radzik, Edward Reingold Frank Ruskey, Peter Sanders, Joao Setubal, Jonathan Shewchuk, Robert Skeel, Jens Stoye, Torsten Suel. Bruce Watson, and Uri Zwick 很多习题都来源于我的同事或是受到其他教材的启发.多年后要想再弄清它们来自哪 里则是一项挑战,不过每个问题的来源(我已尽全力重新搜集)都已发布在网站上 若是不感谢为本书初版做出重要贡献的人也是很无礼的. Ricky Bradley和Daro Ⅵlah建立了网站所需的坚实基础架构,不但逻辑清晰而且易于扩展. Zhong Li用xig绘制 了卷I中的大部分算法示意图. Richard Crandall. Ron Danielson, Takis metaxas,Dave Milr, Giri Narasimhan和 Joe Zachary都审查过第1版的初稿——他们的反馈都是经过深 思熟虑的,也正是这些反馈使得本书不断完善,最终呈现在读者面前 我对算法所了解的很多东西都是和我的研究生在一起学到的他们中的很多人(Yaw Ling Lin, Sundaram Gopalakrishnan, Ting Chen, Francine Evans, Harald Rau, Ricky Bradley和 Dimitris Margaritis)都是相关 War Story中的真实英雄. Estie arkin, Michael Bender, Jie gao和 Joe Mitchell是我在石溪大学的朋友和算法领域的同事,与他们共事与相 处都很开心.最后,感谢我的朋友们, Michael Brochstein以及在纽约的其他友人,在我离开 石溪造访他们时,共渡了许多美好时光 说明 作者大度地接受对任何不足之处的批评乃是一个传统.可我有所不同.本书中所出现 的任何错误、缺陷或问题都是他人的过失,不过你要指出来我会非常感激,这样我就可以 去追究相关人士的责任了 Steven s. skiena 石溪大学( Stony Brook University)计算机科学系 纽约石溪( Stony brook,NY)11794-4400 http://www.cs.sunysb.edu/-skiena 2008年4月 译者注:以前称为“纽约州立大学石溪分校”( State University of New York at Stony Brook),

...展开详情
试读 127P 算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    上传资源赚积分,得勋章
    最新推荐
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf 50积分/C币 立即下载
    1/127
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第1页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第2页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第3页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第4页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第5页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第6页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第7页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第8页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第9页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第10页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第11页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第12页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第13页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第14页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第15页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第16页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第17页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第18页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第19页
    算法设计指南(第2版).[德]Steven S. Skiena(带详细书签).pdf第20页

    试读已结束,剩余107页未读...

    50积分/C币 立即下载 >