算法导论(第二版)

所需积分/C币:9 2018-06-20 20:27:23 19.26MB PDF
38
收藏 收藏
举报

第一部分 基础知识 第二部分 排序和顺序统计学 第三部分 数据结构 第四部分 高级设计和分析技术 第五部分 高级数据结构 第六部分 图算法 第七部分 算法研究问题选编 第八部分 附录:数学基础知识
编程就好比练功,如果学习.net,mfcνb等具体的语言和工具是外功(招式),对基础的学习就是内功,只注重 招式而內功不扎实是不可能成为高手的。很多人会认为《射雕英雄传》中马玉道长什么都没有教郭靖,马道长 教的表面看来是马步冲权实则都是内功υ心法,郭靖拜师淇七之后开始练习降龙十八掌凭借的就是这深厚的內 功,吞食蝮蛇宝血又加上练习了周愽博通传授的九阴真经和外加功夫双手互博技之后,终于练就行走江湖的武 功,由此可見马玉道长传授给了郭靖的是最基础的,也是最重要的观念编程好比盖高楼,根基没打好早晩有 天会挎掉的,而且盖得越高,损失也越参重。这些底层知识和课本不是没有用也不是高深的不能学,而是我 们必须掌握的基础。 这些是个人的愚见,说的不是很清楚,大家可以看看这些前翚们的经验,相信看完后大家一定会有所体会 的。为了方便大家阅读,我把这些前辈们的建议的文章整理成了pdf大家在下面下载吧希望对大家有帮助。pdt #eTle:http://bbs.theithome.com/read-htm-tid-123.html 说了这么多无非是想告诫大家要打好扎实的基础;不要只顾追求时髦的技术,打好基础再去学那些技术或是 参加些培训,对自身的发展会更好的。 基础这么重要怎样学好它呢?我觉得学好它们应该对照这些基础课程所涉及的方面多看一些经典书籍,像算 法导论编程珠玑代码大全(具体介绍在本论坛每本书的版块里)等这些经典书籍不仅能帮助我们打好基础,而且 对我们的程序人生也能产生莫大的影响,相信认真硏究看完这些书籍后,我们的程序之路会十分顺畅。然而这 些书籍并不好读有些甚至相当难读,国內的大学用这些书当教材的也不多,这些书又偏向理论,自己读起来难免会 有些枯燥无味。于是就想到建一个论坛,大家共同讨论学习这些书籍,就会学的更踏实更牢固更有趣这样就能 为以后的学习打下扎实的基础。 本论坛特色 bbs theithome com 1为计算机初学者或基础不太扎实的朋友指明方向,要注重内功 2.为学习者推荐经些书籍,指岄明应看哪些书籍,怎样练内功 3为学习者提供一个交流的地方,更容易学好,不会那么枯燥 4对每本书分章分别讨论,更专,会学的更踏实更牢固 5讨论的都是经典书籍,每一本都会让我们受益匪浅对每本书分别讨论是很有意义的。 bbs theithome. com 目录 出版者的话 544在线庖用问题+s 专京指导委员会 第二部分排序和顺序统计学 译者序 前言 引百…"…,9 第6章堆排序 73 算一部分甚础虹识 6.1堆+111 引言 中中自自◆口日P日画日目 5,E保持堆的性质 第1章算法在计算中的作用 53逛堆 76 口n口 .1算甚 .4掉序算法4+…k 中■P十加十自⑦?■■宁■■■P■口■■ 12作为一种技术的算法 55优先级队列………………"!B0 算2章算法入门T 算7章快遽排序…………………8 2.1插人排序* 71秋速#序的述……"……………B5 2.2算法分析……………………………1 22快排序的性能……-………………88 2.3算法设计·*… 73快速俳序的随执化版本 2.31分治法* 7,4快速排序升析 上1 z。32分治法分析“…艹20 7.4.1最坏情况分析…………" 第3章函数的增长…4m;,26 7.4.2期的运行时间 +92 31渐近记号→ 目日日日P日目■日■P日 …“第8章找性时间排序……49 a.2标准记号和常用函数… 3 B.1排序算法时间的下界 9 筹生章递归式…… 3 8.z计数排序,+……+… 4.1代换法………:--1---3 B3茹数排序""◆n…,POf 4-2递归树方轄+ 4桶排序…………"…P2 4.3主方法4+4………*分 第9章中位数和顺序统计学 4.4主烂琿的证明……………"…-…… 9.1最小值和最大值………+……g 4.4】取正合暴时的证明4* 92期望性时间做选择……………!09 4.4.2上取整丽致和下郁函数… 9,最坏情况统性时问拍选择………!2 第5章概卑分析和随机算法 第三部分数据结构 5.履用问题 52抬器险机变量 EFq目P中□t 引…………………………………卩7 5.3随机算法 日日··LPF4q↓mh■■士 第10章水数据结构 1P卜+u上19 t54概辜分析和指示器隘机变量的进一步 10.1栈和队列………*…P9 键用“*………”6 】0.2链丧 I2i 5,4.1生日博论…………”+"+,52 l,3指针和对的实现………“…24 542球与盒于 6 10.4有根的我乐 727 43序列 +TD■■■ …么…64 算11章散列卷…-………→*-…灬32 bbs theithome. com 11.1直接寻址表…4…“*…**扌32 1?3势能方摆艹"*”249 1!.2散列北◆·……*……◆」 17.动布表 血血…"25】 ],3散列酒 17.4,1丧扩张……………………,…25 11.31除法散列洁……138 17.4.2表扩张和收婚艹如"253 1].32乘法胜列法“*…+……13 第五部分高級数据结构 ]]3,3全域列………………139 11.4开寻址法… ■■L■■ ■一■■函司司LL司■司司 〗42 祝述 ■■■■■■■■■■■q■■?■■■■■■■■二■■ .5完全散列……………………146第1R章B树… ■■重■■■■ 63 鎳12章二叉查找树………… 5 18.1B树的定义……"MAM"E65 12.1二叉充找树……s15 B.2对B树的撼本操作…”+….*"267 12.2查询二叉查找树…………153 1民.3从日树屮剧除关键字… l2.3橘入和剧除…………………15第19章二项堆……***277 k12,4机构遣的二叉查找树 "158 9.1二项树与二听唯4 第13章红惡树… I好3 19.1.1二项树…*,?8 3.】红黑骨的性质∵r a【币3 1.1.2二项雄 日』卩■4b 229 13.2恢转 s…卫65 19.2对二项堆的搡作4………………281 13.3人………167第20章斐波那契堆 …E9 13+尉除 十十订·十■上d■L士十是人日上L-rl i7宫 忍1那唾的结构“………21 第14章数据结构的扩张……18 202可合并嶕的操怍·…*………293 t,I动态序施计+-,k-I8 203减小一个关轄字与耐除冖↑皆点z99 t4.2如何扩张数据构… 84 4曼大度数的界…,…302 43区闻树 21章用于不相尧集合的教据 结构-………………35 第四部分高级设计和分析技术 2L]不相交集合上的操作……………05 导论 山目日日4目目◆中,日.司 21.2不相交梨合的链表表示 307 算15章动恋规翘………………………扌92 21.3不粗交集仓森林+:rnm"30 15,L装配线调度…*;,…**…………I92 214带路垫压精的糕合并的分析+…32 15,2矩阵乘法………44*…………19? 第六部分图算法 5.3动菇规划莘础 202 15.4最长公共子序列…………………20a引盲 中山亏中日P中中m中4日wm日日.日日日日品日.心果 155敢忧二貝觐树 ……212第22章图的基本算法…,h…t 第16章贪心算法……………………222 221赶的表示 ■■P■■■■■■■■■■■■■■日品■■EL■司■ 322 16.l活动选择问·m"灬4*!22 22.2广度优先键实………-……94 16.2负心策的基本内容…""E8 22.3濚度优先搜新Hr+r330 63光曼编码………… 22.4拓扑排岸 336 164货心法的理论基础 22.5强连通分支……………………*338 h16.5一个任务谢度问题…… 15 算23章最小生崴树… 344 第1?章平摊分析…t… 24f 23,1最小生成树的形吡 245 17,1尞集分析山…B4·244 23,2 Krusk算法和Prm算法………3g 17,2记账方壮+……… 247第24章单源歌炬路径………57 bbs theithome. com 24.1Bman-Furd算法…1362第31章有关数论射算法……tt22 242有向无问路图屮的单最短惭径…34 3⊥]初等数论怃念 522 243Dr了法+…… 不66 31,2是大公约 中■自b中加血t 24.4分约束与最短路径-……3℃ 31,3模运算 ■■■d■十十十十q■P+子P↓,■山■■十+h+■ 52 24.5最短路径性质的证明… 3z3 31,4求解换线性方捏……………-………533 第25章每对顶点问的最短路径…3.】 315中国余数妃理 ■d■山dhm+d■mm■■T■口T 25.1最监径与矩阵乘法4+4H4+382 3】6元的幕…………"538 25,2 FloydWarshall算法,……6 317RSA公钥加密系540 25.3稀疏图上的 Johnson算法4…39 3L8亲数的测试+………54 第26章最大流…+…: 39 3L9薹数的因子分解……550 2流网辂………………*… 96第32章字符郜¢配……+44444.557 26.2FDr} Fulkerson方沾……… 40 32,朴旗的宇符邮匹配算法+*r558 2.3量大二分匹配 P↓↓ 32,2 Rabin-karp算法+…560 2.4压入与重标记算法…*"sr…4H 323利用有限自动机进行字符申匹配…53 26.5重标记与前移算法++H+4……49 432.4 Knuth- Morris-Prat算法…………",568 第七部分算法耐究问题选编 第33章汁算几何学… 331线段的性质………+5 引直…-- ■■■■■■ 332定任意一对线段足否相坐………580 第27章排序网络 433 33.3寻我凸包+……………*…"*584 27.]比网 其33 33.4寻找最近点对……… 59 2?,2-1 原 436 笫34章NP完全性……… 273双训排序网络“………438 34.1多项式时闰…*……… 274合并网络…………*40 34.2多项式时网的证……05 27.5排序网蛴………"*…*-42 3NP完全性与可归射性…*+4+608 第28章炬阵运算 +!b包下“中M山至46 34.4NP完全性的证明 6T5 284矩阵的性质…………………446 3.5NP完全问题………………*!60 E,2矩阵法的Sn算活 SI 34,号.1团问题………… E品.3求解线性方型组 ……+455 34.5.2顶点益问… 622 284矩求逆……*……灬…"………454 34.53哈阻回路间4… 622 2B.5称正定矩阵与最小二乘近 467 34.5.4旅行商间趣“*…626 寡29章线性规划+…,,2,,,473 34.3.5子集和问恧……………………”687 29.」柝准型和松弛遭 ……477第35章近似算法 29,2将问医亵达为线性规划…………482 351顶煎盖问题 293单施形算法“… 352旅行商岡題 ……rr636 p9.4对性…--+* 乎95 35.2.1满足三角不等式的旅行商 29.5初始基本可行解…………………:498 问题…*……………*536 算30章多项式与快逮傅里叶变换…506 .22一般旅行商问题 3 3.多项式的表示 上T口宁T■■■ 5.3桌合曩盐问题……r… 64 30.2DFT与FT·4◆卜51 35.4阳机化和鲵性规划…;+… 43 3.3有的HH实…56 355于和向题 a"6d6 bbs theithome. com 巧 B5.1闩由树艹…………r…*…67 第八部分附录:数学基础知识 B5,2有根树帮有序树+*4…,"…*…67l 引言 B.5.3二叉树与佗置树 672 A求和………………… …,5C计数和概…………+…*………676 A.】求和公式及其性质………*4*………+…654 C1计数*1-…*+4,+,,676 A2确定求和时间酌羿 C.2概…+4…*…*…6?9 B集合等离散数学结构……*·*……舴6 C.3高散随机变量… …〔3 1棠合…*………*…-………66 C.4几何分布与二项分布……“686 旦2美系M…,…"………………"………664 C.5二项分布的尼……*…M…艹69 B.了函敷………………………………65参考文献………………………………694 R4图……-…………………………667宗引 ■■■T重■■ FIr B.5树 …,……670 bbs theithome. com :;第炸烈寧辦 第一部分基础知识*犒 专,5 增你前“即彭…善 游 这一部分将引导读者开始思考算法的设计和分析问题,简单介绍算法的表达方法、将在本 书中用到的一些设计策略,以及算法分析中用到的许多基车思想。本书后面的内容都是建立在 这些基础知识之上的。 第1章是对算法及其在现代计算系统中地位的一个综述。本章给出了算法的定义和一些算法 的例子。它还说明了算法是一项技术,就像快速的硬件、图形用户界面、面向对象系统和网络 样 在第2章中,我们给出了书中的第一批算法,它们解决的是对n个数进行排序的问题。这些 算法是用→种伪代码形式给出的;这种伪代码尽管不能育接翻谇为任何常规的程序设计语言, 但足够清晰地表达了算法的结构,以便任何一位能力比较强的程序员都能用白已选择的某种语 言将算法实现出来。我们分析的排序算法是插入排序,它釆用了一种增量式的做法}另外还分析 了合并排序算法,它采用了一种递归技术,称为“分治法”。尽管这两种算法所需的运行时间都随 的值而增长,但增长的速度是不同的。我们在第2章中分析了这两种算法的运行时间,并给出 了一种有用的表示方法来表达这些运行时间。 第3章给出了这种表示法的准确定义,称为渐近表示。在第3章的一→开始,首先定义了几种 渐近记号,它们主要用于表示算法运行时间的上界和/或下界。第3章余下的部分主要给出了 些数学表示方法.这一部分的作用更多的是为了确保读者所用的记号能与本书中的记号体系相 E配:前不主要是教授新的数学概念 第4更深人地讨论了第2章引入的分治方法。特别地,第4章包含了解决递归式的方法 递归式主要用于摧述递归算法的运行时间。“主方法”( master method)是一种功能很强的技术, 它可以用于解决分冶算法中出现的递归式。第4中的相当一部分内容都是在证明主方法正确 性,如果跳过这一部分证明内容的话,也没有什么太大的影响。 第5章介绍了概率分析和随机化算法。概率分析一般用于确定一些算法的运行时间,在这些 算法中,由于同一规模的不同输入可能有着内在的概率分布,因而在这些不同输入之下,算法的 运行时间可能有所不同。在有些情况下,我们假定算法的输人符合某种已知的概率分布,于是, 箅法的运行时间就足在所有可能的输入之下,运行时间的平均值。狂其他情况下,概率分布不是 来自于输入,而是来自于算法执行过程中所做出的随机选择。如果一个算法的行为不仅由其输 入决定,还要由一个随机数生成器所生成的值来决定的话,它就是一个随机化算法( randomized algorithm)。我们可以利用随机化算法,强行使算法的输入符合某种概率分布,从而确保不会有 bbs. theithome, com 2第一部分基础知识 某一输入会始终导致算法的性能变坏;或者,对于那些允许产生不正确结果的算法,甚至能够将 其错误率限制在某个范围之内。 附录A~附录C包含了另一些数学知识,它们对读者阅读本书可能会有所帮助。在阅读本书 之前,读者很可能已经知道了附录中给出的大部分知识(我们采用的某些符号约定与读者过去见 过的可能会有所不同),因而,可以将附录视为参考材料。另一方面,你很可能从未见过第一部 〖41分中给出的内容。第一部分中的所有各章和附录都是以一种人门指南的风格来编写的。 bbs. theithome, com 第1章算法在计算中的作用 什么是算法?为什么要对算法进行研究?相对于计算机中使用的其他技术来说,算法的作用 是什么?在本章中,我们就要来回答这些问题。 1.1算法 简单来说,所谓算法( algorithm)就是定义良好的计算过程,它取一个或一组值作为输入,并 产生出一个或一组值作为输出。亦即,算法就是一系列的计算步骤,用来将输入数据转换成输出 绪果。 我们还可以将算法看作是一种工具,用米解决一个具有良奷规格说明的计算问题。有关该 问题的表述可以用通用的语言,来規定所霱的输人/输出关系。与之对应的算法则描述了一一个特 定的计算过程,用予实现这一输入/输出关系。 例妞,假设霱要将一列数按非降顺序进行排序。在实践中,这一问题经常出现。它为我们弓 人许多标准的算法设计技术和分析工具提供了丰富的问题场景。下面是有关该排序问题的形式 化定义 输入:由n个数构成的一个序列a1,a2,…,an〉。 输出:对输人序列的一个排列(重排)a1,a2,…,an),使得al≤a2≤san。 例如,给定一个输人序列31,41,59,26,41,58),一个排序算法返回的輪出序列是(26, 31,41,41,58,59〉。这样的一个输人序列称为该排序问题的一个实例〔 instance)。一般来说 某一个间题的实例包含了求解该问题所需的输人(它满足有关该问题的表述中所给出的任何限 制) 在计算机科学中,排序是一种基本的操作(很多程序都将它用作一种中间步骤),因此,迄今[5 为止、科研人员提出了多种菲常好的排序算法。对于一项特定的应用来说,奶何选择最佳的排序 算法要考虑多方面的因素,其中最主要的是考虑待排序的数据项数、这些数据项已排好序的程 度、对数据项取值的可能限制、打算采用的存儲设备的类型(内存、磁盘、磁带〕等 如果一个算法对其每一个输人实例,都能输出正确的结果并停止,则称它是正确的。我们说 个正确的算法解决了给定的计算间题。不正确的算法对于某些输入来说,可能根本不会停止, 或者停止时给出的不是预期的结果。然而,与人们对不正确算法的看法相反,如果这些算法的错 误率可以得到控制的话,它们有时也是有用的。关于这一点,在第31章中研究用于寻找大质数 的算法时介绍了一个例子。但是,一般而言,我们还是仅关注正确的算法 箅法可以用英活、以计算机程序或甚至是硬件设计等形式来表达。不论采用哪种形式,唯 的要求就是算法的规格说明必须提供关于待执行的计算过程的精确描述。 算法可以解决哪些类型的问题? 研究人员并不仅仅是针对排序这一计算问题设计了大量的算法(读者在看到本书的厚度时可 能也会这么猜想的)。算法的实际应用面很广,例如 人类基因项目的且标是找出人类DNA中的所有10000种基因,确定构成类DNA的 30亿种化学基对的各种序列,将这些信息存储在数据库中,并开发出用于进行这方面数 据分析的工具。这些步骤中的每一个都需要复杂的算法。该项所涉及的各个问题的解 bbs. theithome, com

...展开详情
试读 127P 算法导论(第二版)
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
算法导论(第二版) 9积分/C币 立即下载
1/127
算法导论(第二版)第1页
算法导论(第二版)第2页
算法导论(第二版)第3页
算法导论(第二版)第4页
算法导论(第二版)第5页
算法导论(第二版)第6页
算法导论(第二版)第7页
算法导论(第二版)第8页
算法导论(第二版)第9页
算法导论(第二版)第10页
算法导论(第二版)第11页
算法导论(第二版)第12页
算法导论(第二版)第13页
算法导论(第二版)第14页
算法导论(第二版)第15页
算法导论(第二版)第16页
算法导论(第二版)第17页
算法导论(第二版)第18页
算法导论(第二版)第19页
算法导论(第二版)第20页

试读结束, 可继续阅读

9积分/C币 立即下载