算法导论 (Introduction to Algorithms中文版)

所需积分/C币:32 2012-07-06 21:33:46 54.23MB PDF
收藏 收藏 6
举报

《算法导论》是由潘金贵、顾铁成等人翻译的。它的原版《Introduction to Algorithms》是最经典的算法教程之一。很多名校,比如MIT都用这本书作为算法课的教程,网上也有相关的公开课视频。
目录 出版者的话 5.4.4在线雇用问题111166 专家指导委员会 第二部分排序和顺序统计学 译者序 前言 引言………..1 第6章堆排序 和+·+中,中,t都日B,E 第一部分基础知识 6.1堆*…:::…13 引言 想守十曹自围日国日日百品日.品和4+++ 62保持堆的性质…………………*…474 第1章算法在计算中的作用1 6.3建堆……16 1,1算法 64堆排序算法…+ …+78 1.2作为一种技术的算法……………………6 65优先级队列…80 第2章算法入门 第7章快速排序…185 2,1插人排序…………… 7.1快速排序的描述 +t·,度主 85 2.2算法分析……………………12 7.2快速排序的性能 2,3算法设计…:416 7.3快速排序的随机化版本…190 2.3.1分治法…,,…………………16 7,4快速排序分析*…91 2。3,2分治法分析 7.4.1最坏情况分析· 團■La品画 第3章函数的增长……….26 7.4.2期望的运行时间……………………92 31渐近记号……,26 第8章线性时间排序…………97 3.2标准记号和常用函数……31 8.1排序算法时间的下界 97 第4章递归式………………38 8.2计数排序…419 4.1代换法…………………………38 8.3基数排序,:00 4.2递归树方法 8.4桶排序…*1102 4.3主方法 43 第9章中位数和顺序统计学 P08 44主定理的证明… 91最小值和最大值……………108 4.4.1取正合幕时的证明…45 9.2以期望线性时间做选择…………109 4.4.2上取整函数和下取整函数 48 9.3最坏情况线性时间的选择………12 第5章概率分析和随机算法……………,.54 第三部分数据结构 51雇用问题·…154 52指示器随机变量63言………17 53随机算法 第10章基本数据结构……………119 t5.4概率分析和指示器随机变量的进一步 10,1栈和队列… n9 使用…62 10.2链表 2 54,1生日悖论…………“…,,462 10,3指针和对象的实现……124 5.4.2球与盒子………64 10.4有根树的表示………………………27 54.3序列…64第11章散列表…1 11.1直接寻址表……*…*…*…,132 17.3势能方法 249 11.2散列表………-…133 17.4动态表……251 11,3散列函数·1437 17.4,1表扩张…1251 11.3.1除法散列法……………138 17.4.2表扩张和收缩*…+……,…253 11.3.2乘法散列法……*,,:,138 第五部分高级数据结构 11,3,3全域散列………………………:139 11,4开放寻址法…42概述……………………………………261 11,5完全散列………146第18章B树 ……2:63 第12章二叉查找树…………151 18,1B树的定义……………………265 12.1二叉查找树1151 18.2对B树的基本操怍…… 12.2查询二叉查找树:1tt153 18.3从B树中删除关键字,272 12.3插A和删除…………15第19章二項堆 277 12,4随机构遣的二叉查找树…………158 19.1二项树与二项堆…278 第13章红黑树……………………………163 19.1.1二项树…*…278 13.1红黑树的性质·…… …163 19.1.2二项堆 和中日和斗白日中中·中 13.2旋转:… 165 19.2对二项堆的操作…… 281 13,3插人…… 中·“*““·“·中 167第20章斐波那契堆…… 13.4删除…………“…+…*…*172 20.1斐被那契堆的结构 曹「国售曹售_售围里m车留 291 第14章数据结构的扩张……………181 20.2可合并堆的操作……1293 14.1动态顺序统计………181 20.3减小一个关键字与剽除一个结点…299 14.2如何扩张数据结构::84 20.4最大度数的界……,:302 14.3区间树 186第21章用于不相交集合的数据 结构 第四部分高级设计和分析技术 3 21.1不相交集合上的操作…- 305 导论…………………………191 21.2不相交集合的链表表示 307 第15章动态规划………………………192 21.3不相交集合森林+mn3I0 15.1装配线调度………1192 ………192*21.4带路径压缩的按秩合并的分析……12 15,2矩阵链乘法… 197 第六部分图算法 15.3动态规划基础…………………202 15.4最长公共子序列…209引言 +H日日由团士度:t:t:度道翻面目面者道自L国1围日画面画翻 32 15。5最优二叉查找树…4212 第22章图的基本算法… 322 第16章贪心算法…… 222 22.1图的表示……………1322 16.I活动选择问题………222 22.2广度优先搜索……………………324 16.2贪心策略的基本内容…………………22822.3深度优先搜索…+………………330 16.3赫夫曼编码1231 22.4拓扑排序1136 *16.4贪心法的理论基础…………1236 22.5强连通分支…………………38 16.5一个任务调度问题…………………239第23章最小生成树………………344 第17章平摊分析………244 231最小生成树的形成……345 17。1聚集分析4244 23.2 Kruskal算法和Prim算法…………348 17.2记账方法……4*4247第24章单源最短路径 357 24.1 Bellman-Ford算法……62第31章有关数论的算法……………522 24.2有向无回路图中的单源最短路径…364 31.1初等数论概念……14522 24.3 Dijkstra算法………,……366 31,2最大公约数 24,4差分约束与最短路径…………370 31,3模运算……529 24.5最短路径性质的证明………373 31,4求解模线性方程 533 第25章每对顶点间的最短路径………38 31.5中国余数定理·535 25.1最短路径与矩阵乘法“4:4382 31.6元素的幂…………………++538 25。2 Floyd-Warshall算法……**……386 31.7RSA公钥加密系统“:t540 25.3稀疏图上的 Johnson算法·391 *31.8素数的测试…:544 第26章最大流…………96419整数的因子分解……5 26,1流网络………… …396第32章字符串匹配……4…,,147 26.2 Ford-Fulkerson方法…………:+00 32.1朴素的字符串匹配算法 558 26.3最大二分匹配… 40 2.2 Rabin-Karp算法 和+++市,t建 26.4压人与重标记算法… 411 2.3利用有限自动机进行字符申匹配…563 26.5重标记与前移算法·419 *32.4 Knuth- Morris-Pratt算法4568 第七部分算法研究问题选编 第33章计算几何学 575 33.1线段的性质……………:575 引言-431 33.2确定任意一对线段是否相交………580 第27章排序网络………………433 33.3寻找凸包…………………“……584 27.1比较网络4“tttt…!33 33.4寻找最近点对………591 27.20-1原理+436 第34章NP完全性 273双调排序网络………*…438 34,1多项式时间…… 疆 27.4合井网络……………………40 34.2多项式时间的验证……465 27.5排序网络 ■国日目L;和和和吾研+=担度tt 442 34.3NP完全性与可归约性4*“"*.60g 第28章矩阵运算…….46 34.4NP完全性的证明…615 281矩阵的性质…·…………446 34.5NP完全问题 282矩阵乘法的Sasn算法………45 345.1团问题…………………………620 28.3求解线性方程组……………455 34.5.2顶点覆盖间题…*41622 28.4矩阵求逆………………44 34.5.3哈密馥回路问题… 623 28.5对称正定矩阵与最小二乘近……467 34.5.4旅行商问题·626 第29章线性规划………473 34.5.5子集和问题…1627 291标准型和松弛型……………477第35章近似算法, 633 29.2将问题表达为线性规划……482 35.1顶点盖问题 63 29.3单纯形算法·……485 35,2旅行商问题 29.4对偶性………:…495 35.2,1满足三角不等式的旅行商 29.5初始基本可行解…148 间题 636 第30章多项式与快速傅里叶变换……506 35.2.2一般旅行商问题……………638 30.1多项式的表示…+……507 35,3集合覆盖问题… 日干日 nHrr dE 640 30.2DFT与FFT……!511 35.4随机化和线性规划 643 30.3有效的FFT实现+“…516 35.5子集和问题…… 646 第八部分附录:数学基础知识 B.5.1自由树…t1:670 B.5.2有根树和有序树 671 引言 53 B.5.3二叉树与位置树……………………672 A求和…654C计数和概舉…………………………676 A.1求和公式及其性质………,*,…*,654 C.1计数…,………1,::,::676 A.2确定求和时间的界……*11656 C.2概率………………… B集合等离散数学结构……………………661 C.3离散随机变量·… 683 B.1集合………………………………661 C.4几何分布与二项分布………4686 B2关系…………………………………664 C.5二项分布的尾44689 B.3函数…………………………"665参考文献 694 B.4图…………………………67案引……………………… 711 B.5树……1670 棒率持 第一部分基础知识的A 强P热…读 弓 这一部分将引导读者开始思考算法的设计和分析问题,简单介绍算法的表达方法、将在本 书中用到的一些设计策略,以及算法分析中用到的许多基本思想。本书后面的内容都是建立在 这些基础知识之上的。 第1章是对算法及其在现代计算系统中地位的一个综述。本章给出了算法的定义和一些算法 的例子。它还说明了算法是一项技术,就像快速的硬件、图形用户界面、面向对象系统和网络 一样 在第2章中,我们给出了书中的第一批算法,它们解决的是对n个数进行排序的问题。这些 算法是用一种伪代码形式给出的,这种伪代码尽管不能直接翻译为任何常规的程序设计语言, 但足够清晰地表达了算法的结构,以便任何一位能力比较强的程序员都能用自己选择的某种语 言将算法实现出来。我们分析的排序算法是插人排序,它采用了一种增量式的做法;另外还分析 了合并排序算法,它采用了一种递归技术,称为“分治法”。尽管这两种算法所需的运行时间都随 n的值而增长,但增长的速度是不同的。我们在第2章中分析了这两种算法的运行时间,并给出 了一种有用的表示方法来表达这些运行时间。 第3章给出了这种表示法的准确定义,称为渐近表示。在第3章的一开始,首先定义了几种 渐近记号,它们主要用于表示算法运行时间的上界和/或下界。第3章余下的部分主要给出了 些数学表示方法。这一部分的作用更多的是为了确保读者所用的记号能与本书中的记号体系相 匹配,而不主要是教授新的数学概念。 第4章更深人地讨论了第2章引入的分治方法。特别地,第4章包含了解决递归式的方法 递归式主要用于描述递归算法的运行时间。“主方法”( master method)是一种功能很强的技术, 它可以用于解决分治算法中出现的递归式。第4章中的相当一部分内容都是在证明主方法的正确 性,如果跳过这一部分证明内容的话,也没有什么太大的影响。 第5章介绍了概率分析和随机化算法。概率分析一般用于确定一些算法的运行时间,在这些 算法中,由于同一规模的不同输入可能有着内在的概率分布,因而在这些不同输入之下,算法的 运行时间可能有所不同。在有些情况下,我们假定算法的输入符合某种已知的概率分布,于是, 算法的运行时间就是在所有可能的输入之下,运行时间的平均值。在其他情况下,概率分布不是 来自于输人,而是来自于算法执行过程中所做出的随机选择。如果一个算法的行为不仅由其输 人决定,还要由一个随机数生成器所生成的值来决定的话,它就是一个随机化算法( randomized algorithm)。我们可以利用随机化算法,强行使算法的输入符合某种概率分布,从而确保不会有 2第一部分基础知识 某一输入会始终导致算法的性能变坏;或者,对于那些允许产生不正确结果的算法,甚至能够将 其错误率限制在某个范围之内。 附录A~附录C包含了另一些数学知识,它们对读者阅读本书可能会有所帮助。在阅读本书 之前,读者很可能已经知道了附录中给出的大部分知识(我们采用的某些符号约定与读者过去见 过的可能会有所不同),因而,可以将附录视为参考材料。另一方面,你很可能从未见过第一部 4]分中给出的内容。第一部分中的所有各章和附录都是以一种人门指南的风格来编写的。 第1章算法在计算中的作用 什么是算法?为什么要对算法进行研究?相对于计算机中使用的其他技术来说,算法的作用 是什么?在本章中,我们就要来回答这些问题。 1.1算法 简单来说,所谓算法( algorithm)就是定义良好的计算过程,它取一个或一组值作为输入,并 产生出一个或一组值作为输出。亦即,算法就是一系列的计算步骤,用来将输入数据转换成输出 结果。 我们还可以将算法看作是一种工具,用来解决一个具有良好规格说明的计算问题。有关该 问题的表述可以用通用的语言,来规定所需的输入/输出关系。与之对应的算法则描述了一个特 定的计算过程,用于实现这一输入/输出关系。 例如,假设需要将一列数按非降顺序进行排序。在实践中,这一问题经常出现。它为我们引 人许多标准的算法设计技术和分析工具提供了丰富的问题场景。下面是有关该排序问题的形式 化定义: 输入:由n个数构成的一个序列a1,a2,…,an)。 翰出:对输入序列的一个排列(重排)(a1,a2,…,an),使得a1≤a2≤…≤an 例如,给定一个输人序列(31,41,59,26,41,58),一个排序算法返回的输出序列是(26, 31,41,41,58,59)。这样的一个输人序列称为该排序问题的一个实例( instance)。一般来说, 某一个问题的实例包含了求解该问题所需的输入(它满足有关该问题的表述中所给出的任何限 制 在计算机科学中,排序是一种基本的操作(很多程序都将它用作一种中间步骤),因此,迄今5 为止,科研人员提出了多种非常好的排序算法。对于一项特定的应用来说,如何选择最佳的排序 算法要考虑多方面的因素,其中最主要的是考虑待排序的数据项数、这些数据项已排好序的程 度、对数据项取值的可能限制、打算采用的存储设备的类型(内存、磁盘、磁带)等。 如果一个算法对其每一个输入实例,都能输出正确的结果并停止,则称它是正确的。我们说 个正确的算法解决了给定的计算问题。不正确的算法对于某些输入来说,可能根本不会停止, 或者停止时给出的不是预期的结果。然而,与人们对不正确算法的看法相反,如果这些算法的错 误率可以得到控制的话,它们有时也是有用的。关于这一点,在第31章中研究用于寻找大质数 的算法时介绍了一个例子。但是,一般而言,我们还是仅关注正确的算法。 算法可以用英语、以计算机程序或甚至是硬件设计等形式来表达。不论采用哪种形式,唯一 的要求就是算法的规格说明必须提供关于待执行的计算过程的精确描述 算法可以解决聊些类型的问题? 研究人员并不仅仅是针对排序这一计算问题设计了大量的算法(读者在看到本书的厚度时可 能也会这么猜想的)。算法的实际应用面很广,例如: 人类基因项目的目标是找出人类DNA中的所有100000种基因,确定构成人类DNA的 30亿种化学基对的各种序列,将这些信息存储在数据库中,并开发出用于进行这方面数 据分析的工具。这些步骤中的每一个都需要复杂的算法。该项目所涉及的各个问题的解

...展开详情
试读 127P 算法导论 (Introduction to Algorithms中文版)
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    一个资源只可评论一次,评论内容不能少于5个字
    jianh2008 挺好的,够用了。
    2020-03-16
    回复
    hzbulesea 打不开 评论完才给下载
    2017-10-06
    回复
    fxingw1 扫描版, 不是很清晰
    2016-09-14
    回复
    smxcyp2 不错,楼主辛苦了。
    2016-03-21
    回复
    rongningrong 发现下不了,不知道为啥
    2016-01-06
    回复
    chenlei825 不错,虽然不是最清晰的,但也够了
    2015-09-03
    回复
    pasta_kirby 不差,但缺目錄,有點可惜
    2014-09-30
    回复
    zyyxhcll 就是我要的那个资源 MIT出的那个,对照英文的看学的很快
    2014-09-07
    回复
    Lemon_Labs 能用,是掃描版的,主要是拿來對照英文版來看很好用
    2014-04-14
    回复
    j883988 教材很詳細,謝謝分享。
    2013-10-30
    回复
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    算法导论 (Introduction to Algorithms中文版) 32积分/C币 立即下载
    1/127
    算法导论 (Introduction to Algorithms中文版)第1页
    算法导论 (Introduction to Algorithms中文版)第2页
    算法导论 (Introduction to Algorithms中文版)第3页
    算法导论 (Introduction to Algorithms中文版)第4页
    算法导论 (Introduction to Algorithms中文版)第5页
    算法导论 (Introduction to Algorithms中文版)第6页
    算法导论 (Introduction to Algorithms中文版)第7页
    算法导论 (Introduction to Algorithms中文版)第8页
    算法导论 (Introduction to Algorithms中文版)第9页
    算法导论 (Introduction to Algorithms中文版)第10页
    算法导论 (Introduction to Algorithms中文版)第11页
    算法导论 (Introduction to Algorithms中文版)第12页
    算法导论 (Introduction to Algorithms中文版)第13页
    算法导论 (Introduction to Algorithms中文版)第14页
    算法导论 (Introduction to Algorithms中文版)第15页
    算法导论 (Introduction to Algorithms中文版)第16页
    算法导论 (Introduction to Algorithms中文版)第17页
    算法导论 (Introduction to Algorithms中文版)第18页
    算法导论 (Introduction to Algorithms中文版)第19页
    算法导论 (Introduction to Algorithms中文版)第20页

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

    32积分/C币 立即下载 >