算法概论.pdf

所需积分/C币:48 2016-08-27 22:37:51 54.45MB PDF
74
收藏 收藏
举报

序言 Preface 方框目录 0Prologue(序论) 0.1Booksandalgorithms(书和算法) 0.2EnterFibonacci(斐波那契数列) 0.3Big-Onotation(大O记号) Exercises(习题) 1Algorithmswithnumbers(数的算法) 1.1Basicarithmetic(基本算术) 1.2Modulararithmetic(模运算) 1.3Primalitytesting(素性测试) 1.4Cryptography(密码学) 1.5Universalhashing(全域散列) Exercises(习题) Randomizedalgorithms:avirtualchapter(虚拟章:随机化算法) 2Divide-and-conqueralgorithms(分而治之算法) 2.1Multiplication(乘法) 2.2Recurrencerelations(递归关系) 2.3Mergesort(合并排序) 2.4Medians(中位数) 2.5Matrixmultiplication(矩阵乘法) 2.6ThefastFouriertransform(快速傅里叶变换) Exercises(习题) 3Decompositionsofgraphs(图的分解) 3.1Whygraphs?(图论) 3.2Depth-firstsearchinundirectedgraphs(无向图中的深度优先搜索) 3.3Depth-firstsearchindirectedgraphs(有向图中的深度优先搜索) 3.4Stronglyconnectedcomponents(强连通分量) Exercises(习题)—— 4Pathsingraphs(图的路径) 4.1Distances(距离) 4.2Breadth-firstsearch(广度优先搜索) 4.3Lengthsonedges(边的长度) 4.4Dijkstra’salgorithm(Dijkstra算法) 4.5Priorityqueueimplementations(实现优先队列) 4.6Shortestpathsinthepresenceofnegativeedges(带负权的边的图中的最短路径) 4.7Shortestpathsindags(有向无环图中的最短路径) Exercises(习题) 5Greedyalgorithms(贪婪算法) 5.1Minimumspanningtrees(最小生成树) 5.2Huffmanencoding(赫夫曼编码) 5.3Hornformulas(Horn公式) 5.4Setcover(集合覆盖) Exercises(习题) 6Dynamicprogramming(动态规划) 6.1Shortestpathsindags,revisited(回顾:有向无环图中的最短路径) 6.2Longestincreasingsubsequences(最长 递增子序列) 6.3Editdistance(编辑距离) 6.4Knapsack(背包问题) 6.5Chainmatrixmultiplication(链式矩阵乘法) 6.6Shortestpaths(最短路径) 6.7Independentsetsintrees(树中的独立集) Exercises(习题) 7Linearprogrammingandreductions(线性规划与归约) 7.1Anintroductiontolinearprogramming(线性规划入门) 7.2Flowsinnetworks(网络流) 7.3Bipartitematching(二部图匹配) 7.4Duality(对偶性) 7.5Zero-sumgames(零和游戏) 7.6Thesimplexalgorithm(单纯形算法) 7.7Postscript:circuitevaluation(附录:电路求值) Exercises(习题) 8NP-completeproblems(NP完全问题) 8.1Searchproblems(搜索问题) 8.2NP-completeproblems(NP完全问题) 8.3Thereductions(归约) Exercises(习题) 9CopingwithNP-completeness(处理NP完全问题) 9.1Intelligentexhaustivesearch(智能穷举搜索) 9.2Approximationalgorithms(近似算法) 9.3Localsearchheuristics(局部启发式搜索) Exercises(习题) 10Quantumalgorithms(量子算法) 10.1Qubits,
出版说明 近年来,我国的高等教育特别是计算机学科教育,进行了一系列大的调整和改革, 亟需一批门类齐全、具有国际先进水平的计算机经典教材,以适应我国当前计算机科学 的教学需要。通过使用国外优秀的计算机科学经典教材,可以了解并吸收国际先进的教 学思想和教学方法,使我国的计算机科学教育能够跟上国际计算机教育发展的步伐,从 而培养出更多具有国际水准的计算机专业人才,增强我国计算机产业的核心竞争力。为 此,我们从国外多家知名的出版机构 Pearson、 McGraw- Hill, John Wiley&Sons、 Springer、 Thomson等精选、引进了这套“国外计算机科学经典教材” 作为世界级的图书出版机构, Pearson、 Mcgraw- Hill, John Wiley&Sons、 Springer Thomson通过与世界级的计算机教育大师携手,每年都为全球的计算机高等教育奉献大 量的优秀教材。清华大学出版社和这些世界知名的出版机构长期保持着紧密友好的合作 关系,这次引进的“国外计算机科学经典教材”便全是出自上述这些出版机构。同时, 为了组织该套教材的出版,我们在国内聘请了一批知名的专家和教授,成立了专门的教 材编审委员会。 教材编审委员会的运作从教材的选题阶段即开始启动,各位委员根据国内外高等院 校计算机科学及相关专业的现有课程体系,并结合各个专业的培养方向,从上述这些出 版机构出版的计算机系列教材中精心挑选针对性强的题材,以保证该套教材的优秀性和 领先性,避免出现“低质重复引进”或“高质消化不良”的现象。 为了保证出版质量,我们为该套教材配备了一批经验丰富的编辑、排版、校对人员, 制定了更加严格的出版流程。本套教材的译者,全部由对应专业的高校教师或拥有相关 经验的专家担任。每本教材的责编在翻译伊始,就定期不间断地与该书的译者进行交 流与反馈。为了尽可能地保留与发扬教材原著的精华,在经过翻译、排版和传统的三审 三校之后,我们还请编审委员或相关的专家教授对文稿进行审读,以最大程度地弥补和 修正在前面一系列加工过程中对教材造成的误差和瑕疵。 由于时间紧迫和受全体制作人员自身能力所限,该套教材在出版过程中很可能还存 在一些遗憾,欢迎广大师生来电来信批评指正。同时,也欢迎读者朋友积极向我们推荐 各类优秀的国外计算机教材,共同为我国高等院校计算机教育事业贡献力量。 清华大学出版社 国外计算机科学经典教材 编审委员会 主任委员: 孙家广 清华大学教授 副主任委员: 周立柱 清华大学教授 委员(按姓氏笔画排序): 王成山 天津大学教授 王珊中国人民大学教授 冯少荣 厦门大学教授 冯全源 西南交通大学教授 刘乐善 华中科技大学教授 刘腾红中南财经政法大学教授 吉根林 南京师范大学教授 孙吉贵 吉林大学教授 阢秋琦 北京交通大学教授 何晨 上海交通大学教授 吴百锋 复旦大学教授 李彤 云南大学教授 沈钧毅 西安交通大学教授 邵志清 华东理工大学教授 陈纯 浙江大学教授 陈钟北京大学教授 陈道蓄 南京大学教授 周伯生北京航空航天大学教授 孟祥旭 山东大学教授 姚淑珍 北京航空航天大学教授 徐佩霞 中国科学技术大学教授徐晓飞哈尔滨工业大学教授 秦小麟 南京航空航天大学教授钱培德 苏州大学教授 曹元大 北京理工大学教授 龚声蓉苏州大学教授 谢希仁 中国人民解放军理工大学教授 求 国大姆是函据法 不式,。A的再平为一曲许 干长的 对,汗本量 译 己 者序 与:平因,原,管进不是女,量 算法是当代信息技术的重要基石,同时也是计算科学研究的一项永恒主题 早在许多世纪以前,算法研究就已经从数学,特别是算术研究中崭露头角。在 人类近代和当代文明的发展过程中,即使是在计算机这一自动化的电子工具诞生之 前,算法已经成为了数学研究的一个重要分支。然而,当代计算机硬件体系架构的 确立和以 Moore定律为指引的硬件水平的飞速发展,真正使算法技术成为了现代信 息科学的支柱之 作为一本介绍算法技术和思想的书籍,本书不仅可以面向信息学科大学生作为 基本的教材或参考书),更是将任何具有初等数学基础的人引入算法应用与研究殿 堂的一块引路石。本书循序渐进、深入浅出,展示了算法研究与应用中,从模型分 析、算法构造到复杂性分析和算法优化的方方面面。涉及的内容从古老的算术算法、 排序算法、简单图论到近现代出现的计算图论、贪心算法、分治算法、线性规划、 动态规划、随机算法以及NP复杂性理论,甚至是尚未完全显现全貌的量子计算, 覆盖了经典、现代和未来算法发展的众多代表性工作。套用作者自己的话,“不求把 本书编成一本算法百科全书,但它却涵盖了大多数传统算法书籍未曾强调或忽略的 主题”。虽然说仅凭这样一本书恐怕不能展现出当代算法技术的全貌,但它无疑能对 所有初窥算法技术的人获得一个较为全景和完整的认识,对引导算法设计的“门外 汉”成为算法技术的受益者甚至探索者提供非常有力的帮助。 本书的几位作者都是从事算法理论和技术研究的专业人员,同时具备该领域多 年的教学经验。因此,本书的一大特点,就是在介绍算法设计思想时,突出了讲述 的“故事情节”,强调对读者的启发和引导,从始至终体现了一种“学以致用”的精 神。其中一个亮点是每章正文之后的习题,其中不仅仅提供了章节内容的练习,更 强调了对相关研究和应用的引介。这里有一个简单的统计数据,在本书原稿正文的 300多页中,仅习题所占篇幅就达到了其中的约30%,涉及的应用领域包括经济、 社会、生物、科学等的许多方面。可以相信,对于任何有志于算法研究与应用的读 者,在浏览章节内容的基础上,籍此进行更进一步的思考,都将会使自身对算法思 v算法概论 想的领悟和视野的拓展获得极大的提升 翻译的过程对于每位译者也是一次学习和再思的历程。作为译者,我们不敢妄 称精通算法分析与设计领域,通过对本书的翻译,更使我们深深感到算法领域的博 大精深,及其在计算机科学技术中的核心地位。从初稿的形成,到交叉阅稿,最终 审定,过程虽然不短暂,却无过多艰辛之感,原因无外乎自己已在这次“工作”中 得到了很好的熏陶和锻炼。 最后,限于译者自身的水平及经验,错漏和不足在所难免。恳请读者批评指正。 :共中不虽保从屋与资面,当早 里具工游自一量书,中原氯式文类人 果其些,面文个2007年9月25日,於湖南长沙 的升面建五真,贫扩的平钟的状第式90M则立到 大学息卧向面不本,激的味乐量本一 已人人说指闭音具回你显更,(年幻)道基 公望测从,中福工示,出人,平本,一的量 古从容内的买,面面司闻径录量章, 默到因,箭,图卡要出面险图单简,建 常的全圆品全未尚县的题夏,以默 不一当时1头众致算来外照,工 的如题计管讲景大1法,计全百取本一湖针本 区,全木进升些出报不许本一年法录贝是主 快“好量转一,周片的量全长建个一速人的不封质序面 带的非虽至基益木好区点 业的寶福好事从显游并验具本 工出,长写最混,点人一本,积,学的 的”置学“原全 变,区的容内分不,圆区信文章展京个一中其,每 的文五部水的单个里,面流形关世距 国萨的的一的中其下古泡圆区,中0C 原量日封会是 要行器,上毫容的章, 阳国甲一)水收毒:回润弹政 回因回,当单少性面喜)欧(的璃 全:的国固恢工个暗四的录许本 补简 只,白?。圆图量全是,当某年量 前言 强兴需回不的学乘)资的计全动工长。随个三下舍本 本书是在加州大学 Berkeley分校和 San Diego分校本科生算法课程讲义的基础 上,历经十年,逐渐整理、日益完善而成的。我们教授此门课程的方法在过去几年 间经历了巨大变革,它一方面照顾到了学生的背景(学生们除编程之外并不具备正式 而完善的应用技巧),一方面反映了算法领域总体上走向成熟的趋势,正如过去数十 年我们已经见证了的。随着当初的教学讲义被逐渐提炼成娓娓道来的文字,我们也 逐渐调整着课程的结构,以突岀教学材料编排中蕴含的“故事情节”。因此,本书的 内容经过伃细选择后才得以结集成篇。我们不求把此书编成一本算法百科全书,这 使我们可以自由地把大多数传统算法书籍未曾强调或忽略的主题包含进来 u我们根据学生的特点(这些特点也是当今计算机科学专业的大多数本科生所共 有的),提炼出能使每个算法运转下去的简洁数学思想,而不是沉湎于正式而冗长的 理论证明。换言之,我们在活力和刻板之间,更强调前者。我们发现,学生更能接 受这种形式带来的数学的生命力。正是在这些简洁有力的数学思想的推动下,我们 才得以展开我们的阐述。 旦按照这种方式来理解算法,那么从它的历史本源开始研究就显得很有意 义,并且,对于今天的我们来说,一方面,历史的主题看似那样的熟悉,另一方面, 其与今天的对比却又是那样的显著:数论、素性测试和因子分解。这就是本书第 部分的主题,此外它还包括RSA密码系统、整数乘法的分治算法、排序与寻找中项 以及快速 Fourier变换。本书还包含其他三个部分:其中第二部分堪称本书内容最传 统的章节,主要围绕数据结构和图论展开。这一部分中,错综复杂的问题结构和用 于解决问题的简洁明快的伪代码形成了鲜明对比。如果希望以传统的方式进行讲授, 可以直接从本书的第二部分开始,这部分自成体系(在序言之后),如有需要,可再 跳回第一部分。在本书的第一和第二部分,我们介绍了某些用于解决特定问题的技 术(例如贪心算法和分治技术):第三部分介绍一些强有力的算法设计技术,它们被 Ⅷ算法概论 广泛地用于解决实际问题:如动态规划技术(一种新颖的可用于清除学生的传统学习 障碍的方法)和线性规划技术(一种简洁而直观地处理单纯形法、对偶问题以及原问 题的简化问题的技术)。本书最后的第四部分介绍了对付困难问题的方法:NP完全 性、各种启发式算法以及量子算法,后者或许是当今最前沿的课题。碰巧的是,我 们关于算法的讲述在本书的末尾又回到了最初讨论的问题:针对因子分解问题的 Shor量子算法。 本书包含了三个附加的脉络。为了保持全书的可读性(兼顾学生的不同需求和兴趣) 和逻辑的完整性,它们以三组自成系列的“灰色方框”形式出现,分别对应于些算 法技术的历史背景、对所介绍算法如何在实际中应用(突出了互联网应用)的描述,以 及对相关数学知识的简要阐释。背的1原面一,革大T出 1我们的很多同事为此书的出版做出了重要贡献。在此对 Dimitris Achlioptas、 Dorit Aharonov、 Mike Clancy、 Jim Demmel、 Monika Henzinger、 Mike jordan、 Milena hail、 Gene Myers、 Dana randall.、 Satish rao、 Tim Roughgarden, Jonathan Shewchuk、 Martha Sideri、 Alistair Sinclair,以及 David Wagner表示由衷的感谢,他们均对本书 提出了宝贵意见,并对本书的初稿作了校对。 Satish rao、 Leonard schulman和 Vijay Vazirani对本书几个核心章节的内容给出了重要建议。 Gene Myers、 Satish rao、Luca Trevisan. Vijay vazirani和 Lofti zadeh提供了本书的习题。最后,向加州大学 Berkeley 分校和 San diego分校的同学们表示感谢,是他们推动了本书的出版工作,并参与 审阅本书的手稿。(确国米发用变 国界干导下 原计显形油什本的从点,来左式发旦 房王的史,面一,来的天平饭且并,文 发:显县又联出区天己 中已,合的 密A2代, 计景容内本海中 其舍时五本、变100 时染带 需(高言等 开合暗一重的计本从游直 的圆,买黑干某 件一本。一回源 的方,分的平 心三:(朱代出小)朱 三代章S留 目 录 中 括乘2.C 处10iu0为.0. 一民的 .5 第0章序言 0.1书籍和算法 02从 Fibonacci数列开始 ti音f出t出“量当“量出音量面面量出击删音量出音量出出由出量番量普量唐出出当出f音栅通 03大O符号 ………………………………6 习题… 照闻回章E 第1章数字的算法………………………………………………13 1.1基本算术…………………………13 1.1.1加法……… 备和新垂和国 13 1.1.2乘法和除法 1.2模运算 删番吾干普密吾吾普鲁要鲁平 18 0OI 1.2.1模的加法和乘法…………21 1.2.2模的指数运算………………21 123 Euclid的最大公因数算法… 和面面面出面套鲁要 …23 124 Euclid算法的一种扩展 24 1.2.5模的除法…7 1.3素性测试…………………………………"……………………28 14密码学 35 14.1密钥机制:一次一密乱码本和AES…16 14.2RSA…… …………138 5通用散列表 ““,,………………………… 151散列表………… 41 152散列函数族… …141 习题…………4 X算法概论 第2章分治算法 …53 2.1乘法 ………… ………………53 22递推式 ………57 23合并排序… 59 24寻找中项 …62 2.5矩阵乘法 ···,百:中由面面面 “………………,,,, 66 26快速 Fourier变换 ………………………………………67 26.1多项式的另一种表示法 ……………68 26.2计算步骤的分治实现 哪单……“……………… 71 2.6.3插值 75 26,4快速 Fourier变换的细节 DUBS ¨………………………………78 习题 83 第3章图的分解 ···,下田看出,国 93 31为什么是图… ¨………………93 32无向图的深度优先搜索 96 32.1迷宫探索 …………………………………96 322深度优先搜索………1 99 BE- 323无向图的连通性 …100 324前序和后序……… ·:*“·…····中日“甲·中日 100 3有向图的深度优先搜索 ······型日道日日·平福a==a 101 331边的类型 ¨……¨……………………101 332有向无环图 …"……103 3.4强连通部件……… … 105 34.1定义有向图的连通性 ……………105 342一个有效的算法……… ………"………………106 E习题… ¨…“…………………………110 A名.上 第4章图中的路径… "· …119 4.1距离 …119 1.4.2广度优先搜索… ………"……120 4.3边的长度 ……………122

...展开详情
试读 127P 算法概论.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享王者

关注 私信
上传资源赚钱or赚积分
最新推荐
算法概论.pdf 48积分/C币 立即下载
1/127
算法概论.pdf第1页
算法概论.pdf第2页
算法概论.pdf第3页
算法概论.pdf第4页
算法概论.pdf第5页
算法概论.pdf第6页
算法概论.pdf第7页
算法概论.pdf第8页
算法概论.pdf第9页
算法概论.pdf第10页
算法概论.pdf第11页
算法概论.pdf第12页
算法概论.pdf第13页
算法概论.pdf第14页
算法概论.pdf第15页
算法概论.pdf第16页
算法概论.pdf第17页
算法概论.pdf第18页
算法概论.pdf第19页
算法概论.pdf第20页

试读结束, 可继续阅读

48积分/C币 立即下载