算法导论(第2版) (Introduction to Algorithms)

4星(超过85%的资源)
所需积分/C币:30 2012-05-15 17:44:30 55.22MB PDF
39
收藏 收藏
举报

《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。   《算法导论(原书第2版)》一书内容丰富,对本科生的数据结构课程和研究生的算法课程都是很实用的教材。本书在读者的职业生涯中,也是一本案头的数学参考书或工程实践手册。   在有关算法的书中,有一些叙述非常严谨,但不够全面,另一些涉及了大量的题材,但又缺乏严谨性。《算法导论》将严谨性和全面性融为一体。   《算法导论(原书第2版)》一书深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系,可以作为独立的学习单元。算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能看懂。说明和解释力求浅显易懂,不失深度和数学严谨性。   《算法导论(原书第2版)》一书自第1版出版以来,已经成为世界范围内广泛使用的大学教材和专业人员的标准参考书。第2版增加了论述算法作用、概率分析与随机算法、线性规划等几章。同时,对第1版的几乎每一节都作了大量的修订。一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。
编程就好比练功,如果学习 net mfoνb等具体的语言和工具是外功(招式),对基础的学习就是內功只注重 招式而内功不扎实是不可能成为高于的。很多人会认为《射雕芙雄传》中马玉道长什么都没有教郭靖,马道长 教的表面看来是马步冲权实则都是内功心法,郭靖拜师洪七之后开始练习降龙十八掌凭借的就是这深厚的内 功,吞食蝮蛇宝血又加上练习了周博通传授的九阴貞经和外加功夫双手互博技之后,终于练就行走江湖的武 功,由此可见马玉道长传授给了郭靖的是最基础的,也是最重要的观念编程也妤比盖髙楼,根基没打好早晩有 天会挎掉的,而且盖得越高,损失也越惨重。这些底层知识和课本不是没有用也不是高深的不能学,而是我 们必须掌握的基础。 这些是个人的愚见,说的不是很清楚,大家可以看看这些前辈们的经验,相信看完后大家一定会有所体会 的。为了方便大家阅读,我把这些前辈们的建议的文章整理成了pdf大家在下面下载吧!希望对大家有帮助。pdf ttte:http://bbs.theithome.com/read-htm-tid-123.htm 说了这么多无非是想告诫大家要打好扎实的基础,不要只顾追求时髦的技术,打好基础再去学那些技术或是 参加些培训,对自身的发展会更好的。 基础这么重要怎样学好它呢?我觉得学好它们应该对照这些基础课程所涉及的方面,多看一些经典书籍,像算 法导论编程珠玑代码大全(具体介绍在本论坛毎本书的版块里)等这些经典书籍不仅能帮助我们打好基础,而且 对我们的程序人生也能产生莫大的影响,相信认真硏究看完这些书籍后,我们的程序之路会十分顺畅。然而这 些书籍并不好读有些甚至相当难读,国内的大学用这些书当教材的也不多,这些书又偏向理论,自己读起来难免会 有些枯燥无味。于是就想到建一个论坛,大家共同讨论学习这些书籍,就会学的更踏实更牢固更有趣这样就能 为以后的学习打下扎实的基础。 本论坛特色:bbs. theithome com 1为计算机初学者或基础不太扎实的朋友指明方向,要注重內功 2.为学习者推荐经典书籍,指明应看哪些书籍,怎样练内功 3为学习者提供一个交流的地方,更容易学好,不会那么枯燥 4对每本书分章分别讨论,更专,会学的更踏实更牢固 5讨论的都是经典书籍,每一本都会让我们受益匪浅对每本书分别讨论是很有意义的 bbs. theithome com 计算机经典书籍汇总,下载地址http://bbs.theithome.com/read-htm-tid-308.htm 9.编译原理 1.计算机科学概论 14. linux./unix编程基础 计算机科学概论 编译原理(清华第2版) 鸟哥的 Linux私房菜:基础学习篇 2.计算机数学基础 编译原理及实践 鸟哥的 Linux私房菜:服务器架设篇 高等数学 编译原理:原则,技术和工具 1inux程序设计 线性代数 现代编译原理C语言描述 UNIX环境高级编程 概率论与数理统计 高级编译器设计与实现 Unix网络编程卷1 离散数学及其应用 10.操作系统原理 NIX网络编程卷2 离散数学教程(北大版) 操作系统概念 UNIX编程艺术 现代操作系统 INIX Shell范例精解 什么是数学 具体数学:计算机科学基础 链接器和加载器 15.L.inux/unix内核源代码和驱动程序 3.C语言 程序员的自我修养:链接、装载与库 Linux内核设计与实现 谭浩强C程序设计 自己动手写操作系统 LINUX内核源代码情景分析 操作系统设计与实现 深入理解 LINUX内核 C primer plus The C programming language 11.计算机网络 Linux内核完全注释 C和指针 计算机网络(C Linux设备驱动程序 C专家教程 TCP-IP详解卷1 C陷阱与缺陷 TCP-IP详解卷2 C++编程思想2 c语言解惑 TCP-IP详解卷3 Essential c++ 标准库 用TCP/IP进行网际互联(第一卷) C 你必须知道的495个C语言间题 用TCP/TP进行网际互联第二卷 C++程序设计语言 4.算法与数据结构 用ICP/P进行网际互联第三卷 C++语言的设计和演化 数据结构(清华版) 12.软件工程和面向对象程序设计 Accelerated c++ 数据结构与算法分析—C语言描述 C+编程思想卷1 Effective C+t 编程珠巩 java编程思想 More ellective c++ 编程珠玑II 软件工程( Software. Engineering) Exceptional C+ 算法导论 软什工程:实践者的研究方法 Morc exceptional c+t 计算机程序设计艺术卷1 深入浅出面向对象分析与设计 C++设计新思维 计算机程序设计艺术卷2 head first设计模式 深度探索C++对象模型 计算机程序设计艺术卷3 道法自然:面向对象实践指南 C++沉思录 5.电子技术基础 面问对象分析与设计 C+t Templates The Complete Guide 模拟电子技术(童诗白版) 敏捷软件开发:原则、模式与实践C++FAQs 数字逻辑与数字集成电路(清华版) 设计模式:可复用面向对象软件的基础17.标准库STL使用 6.汇编语言 测试驱动开发 C++标准程序库 汇编语言(王灸版) 重构一改善既有代码的设计 Efective STl 80X86汇编语言程序设计教程 代码大全 泛型编程与STL Intel汇编语言程序设计 程序设计实践 18.STL源代码 STL源码剖析 IBM PC汇编语言程序设计(国外版) 程序员修炼之道:从小工到专家 卓有成效的程序员 19.java语言 高级汇编语言程序设计 保护方式卜的80.386及其编程 代码之美 java编程思想 人月神话 Java编程规范 Windows=环不境下32位汇编语言程序设计计算机程序的构造和解释 7.计算机硬件原理 观止-微软创建M和未来的夺命狂奔 计算机组成-结构亿方法 代码优化:有效使用内存[美]克里斯·卡巴斯基 微机原理与接口技术(陈光军版) 编程高手箴言(梁肇新 计算机体系结构(张晨曦版) 游戏之旅我的编程感悟(云风) 计算机组成与设计硬件/软件接口 13. windows编程基础 Intel微处理器结构、编程与接口 Windows操作系统原理 Inside Windows 2000 计算机体系结构(量化研究方法 编程阜越之道卷1 深人解析 Windows揀作系统 编稈卓越之道卷2 大书夜读:从汇编语言到 Windows内核编程 深入理解计算机系统 windows程序设计 编码的奥秘 WINDOWS核心编程 8.数据库系统原理 数据库系统概念 数据库系统导论 数据库系统实现 目录 出版者的话 5.4.4在线雇用问题……………………66 专家指导委员会 第二部分排序和顺序统计学 译者序 前言 引言………………………071 第6章堆排序 第一部分基础知识 6.1堆……13 引言……………………… 6.2保持堆的性质………………………74 第1章算法在计算中的作用 6.3建堆………76 1.1算法… 6.4堆排序算法 1.2作为一种技术的算法………… 6.5优先级队列 第2章算法入门 36992 第7章快速排序……………………85 2,1插入排序 7.1快速排序的描述………85 2.2算法分析 72快速排序的性能… 88 2.3算法设计…………16 7.3快速排序的随机化版本 2.3.1分治法……………………………16 7.4快速排序分析 2.3.2分治法分析…20 7.4.1最坏情况分析 91 第3章函数的增长…………………………26 7.4.2期望的运行时间 31渐近记号……………………………26 第8章线性时间排序…………………97 32标准记号和常用函数…………31 8.1排序算法时间的下界… 第4章递归式 不不……38 8.2计数排序… 98 4.1代换法……138 8.3基数排序… 100 4.2递归树方法……40 8.4桶排序……1102 43主方法…43 第9章中位数和顺序统计学………108 *4.4主定理的证明… ,,, …….459.1最小值和最大值 108 44.1取正合幂时的证明 45 9.2以期望线性时间做选择… l09 44.2上取整函数和下取整函数………48 93最坏情况线性时间的选择 112 第5章概率分析和随机算法 54 第三部分数据结构 5.1雇用问题…… 5.2指示器随机变量……56 引言 …117 5.3随机算法……… 第10章基本数据结构……………19 5.4概率分析和指示器随机变量的进一步 10,1栈和队列…………19 使用 10.2链表……………… l21 5,4,1生日悖论………………………62 10.3指针和对象的实现 124 5.4.2球与盒子………………64 10.4有根树的表示 …127 5.4.3序列……………614第11章散列表……………13 bbs. theithome com 11.1直接寻址表 132 17.3势能方法 249 11.2散列表………………………………133 7.4动态表……251 11.3散列函数………137 17.4,1表扩张…………………251 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树……26 第12章二叉查找树……………………151 18.1B树的定义…265 12.1二叉查找树…151 18.2对B树的基本操作……1267 12.2查询二叉查找树…153 18.3从B树中删除关键字…………272 12.3插入和删除………………………155第19章二项堆…………………………,277 12.4随机构造的二叉查找树… ………158 19.1二项树与二项堆…278 第13章红黑树………… 163 19.1.1二项树 13.1红黑树的性质…… 163 19.1.2二项堆 13.2旋转… 165 19.2对二项堆的操作…… 281 13.3插入 167第20章斐波那契堆… 291 13.4删除…172 20.1斐波那契堆的结构……291 第14章数据结构的扩张………………181 20.2可合并堆的操作………1293 14.1动态顺序统计 18 20.3减小一个关键字与删除一个结点…299 14.2如何扩张数据结构……………184 20.4最大度数的界…………………302 14.3区间树 ,186第21章用于不相交集合的数据 结构 第四部分高级设计和分析技术 305 21.1不相交集合上的操作…………305 导论………………………………191 21.2不相交集合的链表表示 307 第15章动态规划………………………192 21.3不相交集合森林 310 15.1装配线调度192 ……192-21.4带路径压缩的按秩合并的分析………312 15.2矩阵链乘法 197 第六部分田算法 15.3动态规划基础… 202 15.4最长公共子序列 208引言……………………21 15.5最优二叉查找树……………212第22章图的基本算法…………………322 第16章贪心算法………… 222 22.1图的表示…………………………322 16.1活动选择问题 222 22.2广度优先搜索……………324 16.2贪心策略的基本内容 ………22822.3深度优先搜素…………30 16.3赫夫曼编码……………………231 22.4拓扑排序………………………………336 16.4贪心法的理论基础…… 236 22.5强连通分支…………………………338 16.5一个任务调度问题………239第23章最小生成树……………344 第17章平摊分析……………………244 23.1最小生成树的形成………345 17.1棄集分析……244 23.2 Kruskal算法和Prim算法…………348 17.2记账方法 ……247第24章单源最短路径…………357 bbs. theithome com 24.1 Bellman-Ford算法 362第31章有关数论的算法……………522 24.2有向无回路图中的单源最短路径…364 31.1初等数论概念 522 24.3 Dijkstra算法…………………366 31,2最大公约数…………………………526 24.4差分约束与最短路径 370 31.3模运算…529 24.5最短路径性质的证明………373 31.4求解模线性方程… 533 第25章每对顶点间的最短路径………381 31.5中国余数定理 535 25.1最短路径与矩阵乘法…………382 31.6元素的幂…………… 538 25.2 Floyd-Warshal算法…386 31.7RSA公钥加密系统……………540 25.3稀疏图上的 Johnson算法…………391 *31.8素数的测试……544 第26章最大流… 396 31.9整数的因子分解………50 26.1流网络 396第32章字符串匹配……… 557 26.2 Ford-Fulkerson方法…………00 32.1朴素的字符串匹配算法 558 26.3最大二分匹配………………408 32.2 Rabin-Karp算法…560 26.4压入与重标记算法………411 32.3利用有限自动机进行字符串匹配…563 26.5重标记与前移算法………419 *32.4 Knuth Morris-Pratt算法……………568 第七部分算法研究问题选编 第33章计算几何学……………………575 33.1线段的性质… 575 引言…431 332确定任意一对线段是否相交 580 第27章排序网络………………433 33.3寻找凸包…………………………584 27.1比较网络………… 433 33.4寻找最近点对 591 27.20-1原理 436 第34章NP完全性… 597 27.3双调排序网络 …438 34.1多项式时间………600 27.4合并网络 440 34.2多项式时间的验证………605 27.5排序网络 442 34.3NP完全性与可归约性…608 第28章矩阵运算………………………446 34.4NP完全性的证明……… 615 28,1矩阵的性质 446 34.5NP完全问题…………………620 282矩阵乘法的 Strassen算法………451 34,5.1团问题………… 620 28.3求解线性方程组…455 34.5.2顶点覆盖问题…………622 28.4矩阵求逆……………………464 34.5.3哈密顿回路问题………………623 28.5对称正定矩阵与最小二乘逼近……467 34.5.4旅行商问题………………………“626 第29章线性规划………………………473 34.5.5子集和问题……………………627 29.1标准型和松弛型……….77第35章近似算法 …633 29.2将问题表达为线性规划………482 35.1顶点覆盖问题…… 634 29.3单纯形算法……11485 35.2旅行商问题 63 29.4对偶性… …495 35.2.1满足三角不等式的旅行商 29.5初始基本可行解…198 问题…166 第30章多项式与快速傅里叶变换……506 35.2.2一般旅行商问题… 63 30.1多项式的表示……… ,,、 507 35,3集合覆盖问题……640 30.2DFT与FFT…11 35.4随机化和线性规划…………….643 30.3有效的FFT实现…516 35.5子集和问题… 646 bbs. theithome com B.5.1自由树……………………………670 第八部分附录:数学基础知识 B.5.2有根树和有序树……………………671 引言…………………………………………653 B.5.3二叉树与位置树…………………672 A求和 64C计数和概率…………………………676 A.1求和公式及其性质 65 C.1计数……………………………676 A.2确定求和时间的界… 656 C.2概率………1679 B集合等离散数学结构……… 661 C.3离散随机变量…1683 B.1集合……………………………………661 C.4几何分布与二项分布……………… 686 B.2关系………1664 C.5二项分布的尾… 689 B.3函数……………………665参考文献………………………………694 B4图…………………………………….67案引………………………………………71 B、5树 670 bbs. theithome com 1作棒罗骑刻 第一部分基础知识 药彭,通 …游浪 引言 这一部分将引导读者开始思考算法的设计和分析问题,简单介绍算法的表达方法、将在本 书中用到的一些设计策略,以及算法分析中用到的许多基本思想。本书后面的内容都是建立在 这些基础知识之上的。 第1章是对算法及其在现代计算系统中地位的一个综述。本章给出了算法的定义和一些算法 的例子。它还说明了算法是一项技术,就像快速的硬件、图形用户界面、面向对象系统和网络 样 在第2章中,我们给出了书中的第一批算法,它们解决的是对n个数进行排序的问题。这些 算法是用一种伪代码形式给出的,这种伪代码尽管不能直接翻译为任何常规的程序设计语言, 但足够清晰地表达了算法的结构,以便任何一位能力比较强的程序员都能用自己选择的某种语 言将算法实现出来。我们分析的排序算法是插入排序,它采用了一种增量式的做法;另外还分析 了合并排序算法,它采用了一种递归技术,称为“分治法”。尽管这两种算法所需的运行时间都随 n的值而增长,但增长的速度是不同的。我们在第2章中分析了这两种算法的运行时间,并给出 了一种有用的表示方法来表达这些运行时间。 第3章给出了这种表示法的准确定义,称为渐近表示。在第3章的一开始,首先定义了几种 渐近记号,它们主要用于表示算法运行时间的上界和/或下界。第3章余下的部分主要给出了 些数学表示方法。这一部分的作用更多的是为了确保读者所用的记号能与本书中的记号体系相 匹配,而不主要是教授新的数学概念 第4章更深人地讨论了第2章引入的分治方法。特别地,第4章包含了解决递归式的方法 递归式主要用于描述递归算法的运行时间。“主方法”( master method)是一种功能很强的技术, 它可以用于解决分治算法中出现的递归式。第4章中的相当一部分内容都是在证明主方法的正确 性,如果跳过这一部分证明内容的话,也没有什么太大的影响。 第5章介绍了概率分析和随机化算法。概率分析一般用于确定一些算法的运行时间,在这些 算法中,由于同一规模的不同输入可能有着内在的概率分布,因而在这些不同输入之下,算法的 运行时间可能有所不同。在有些情况下,我们假定算法的输入符合某种已知的概率分布,于是, 算法的运行时间就是在所有可能的输人之下,运行时间的平均值。在其他情况下,概率分布不是 来自于输入,而是来自于算法执行过程中所做出的随机选择。如果一个算法的行为不仅由其输 入决定,还要由一个随机数生成器所生成的值来决定的话,它就是一个随机化算法( randomized agorithm)。我们可以利用随机化算法,强行使算法的输入符合某种概率分布,从而确保不会有 s. theithome com 2第一部分基础知识 某一输入会始终导致算法的性能变坏;或者,对于那些允许产生不正确结果的算法,甚至能够将 其错误率限制在某个范围之内。 附录A~附录C包含了另一些数学知识,它们对读者阅读本书可能会有所帮助。在阅读本书 之前,读者很可能已经知道了附录中给出的大部分知识(我们采用的某些符号约定与读者过去见 过的可能会有所不同),因而,可以将附录视为参考材料。另一方面,你很可能从未见过第一部 4]分中给出的内容。第一部分中的所有各章和附录都是以一种人门指南的风格来编写的。 bbs theithome com

...展开详情
试读 127P 算法导论(第2版) (Introduction to Algorithms)
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
liverandroid 还可以的资源 谢谢
2014-08-27
回复
qq_15012061 经典的入门书 好好研读
2014-08-23
回复
adai04207214 经典的入门书 好好研读
2013-12-07
回复
abing0513 不是很清晰,不过总算找到了,慢慢学习
2013-11-13
回复
_Luffy 经典的一本书,好好研读
2013-10-31
回复
一张嘲讽脸 还算清楚吧
2013-10-11
回复
cuiyanan89 很厚重的一本书,讲的很系统,下载了慢慢看,谢了
2013-09-15
回复
pugongying1214 不错的一本书,很多人都推荐,耐心研究下!
2013-08-28
回复
mooncream 扫描版,没有书签目录,清晰度一般。
2013-04-16
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
算法导论(第2版) (Introduction to Algorithms) 30积分/C币 立即下载
1/127
算法导论(第2版) (Introduction to Algorithms)第1页
算法导论(第2版) (Introduction to Algorithms)第2页
算法导论(第2版) (Introduction to Algorithms)第3页
算法导论(第2版) (Introduction to Algorithms)第4页
算法导论(第2版) (Introduction to Algorithms)第5页
算法导论(第2版) (Introduction to Algorithms)第6页
算法导论(第2版) (Introduction to Algorithms)第7页
算法导论(第2版) (Introduction to Algorithms)第8页
算法导论(第2版) (Introduction to Algorithms)第9页
算法导论(第2版) (Introduction to Algorithms)第10页
算法导论(第2版) (Introduction to Algorithms)第11页
算法导论(第2版) (Introduction to Algorithms)第12页
算法导论(第2版) (Introduction to Algorithms)第13页
算法导论(第2版) (Introduction to Algorithms)第14页
算法导论(第2版) (Introduction to Algorithms)第15页
算法导论(第2版) (Introduction to Algorithms)第16页
算法导论(第2版) (Introduction to Algorithms)第17页
算法导论(第2版) (Introduction to Algorithms)第18页
算法导论(第2版) (Introduction to Algorithms)第19页
算法导论(第2版) (Introduction to Algorithms)第20页

试读结束, 可继续阅读

30积分/C币 立即下载