《数据结构与算法分析》由会员分享,可在线阅读,更多相关《数据结构与算法分析(5页珍藏版)》请在金锄头文库上搜索。
1、数据结构与算法分析:C 语言描述(原书第 2 版)图 书 信 息 作 者 : ( 美 ) 维 斯 著 , 冯 舜 玺 译 出 版 社 : 机 械 工 业 出 版 社 出 版 时 间 : 2004-1-1 版 次 : 1 版 1 次 页 数 : 391 印 刷 时 间 : 2004-1-1 纸 张 : 胶 版 纸 印 次 : 1 I S B N: 9787111127482 包 装 : 平 装 内 容 简 介 书 中 详 细 介 绍 了 当 前 流 行 的 论 题 和 新 的 变 化 , 讨 论 了 算 法 设 计 技 巧 , 并在 研 究 算 法 的 性 能 、 效 率 以 及 对 运 行 时
2、 间 分 析 的 基 础 上 考 查 了 一 些 高 级 数 据结 构 , 从 历 史 的 角 度 和 近 年 的 进 展 对 数 据 结 构 的 活 跃 领 域 进 行 了 简 要 的 概 括 。由 于 本 书 选 材 新 颖 , 方 法 实 用 , 题 例 丰 富 , 取 舍 得 当 。 本 书 的 目 的 是 培 养 学生 良 好 的 程 序 设 计 技 巧 和 熟 练 的 算 法 分 析 能 力 , 使 得 他 们 能 够 开 发 出 高 效 率的 程 序 。 从 服 务 于 实 践 又 锻 炼 学 生 实 际 能 力 出 发 , 书 中 提 供 了 大 部 算 法 的C 程 序 和
3、伪 码 例 程 , 但 并 不 是 全 部 。 一 些 程 序 可 从 互 联 网 上 获 得 。 本 书 是 Data Structures and Algorithm Analysis in C 一 书 第 2版 的 简 体 中 译 本 。 原 书 曾 被 评 为 20 世 纪 顶 尖 的 30 部 计 算 机 著 作 之 一 , 作者 Mark Allen Weiss 在 数 据 结 构 和 算 法 分 析 方 面 卓 有 建 树 , 他 的 数 据 结 构和 算 法 分 析 的 著 作 尤 其 畅 销 , 并 受 到 广 泛 好 评 已 被 世 界 500 余 所 大 学 用作 教 材
4、 。 在 本 书 中 , 作 者 更 加 精 炼 并 强 化 了 他 对 算 法 和 数 据 结 构 方 面 创 新 的 处 理方 法 。 通 过 C 程 序 的 实 现 , 着 重 阐 述 了 抽 象 数 据 类 型 的 概 念 , 并 对 算 法 的 效率 、 性 能 和 运 行 时 间 进 行 了 分 析 。算法之美 2008-03-14 10:39:53 来自: etone Algorithms 的评论 5 这是本很新的书,06 年末发行,07 年才慢慢出现于人们的视野。我在 08 年初得知这本书,那会我还很奇怪:都什么年月了,怎么还有人写算法教材这么“经典”的工作,不是上个世纪就被人
5、做完了吗。读了这本 Algorithms,我才知道:这才是我心中的算法书,我等待这样一本书已经很多年了。它的确当得起这个名字。 书的三位作者:Sanjoy Dasgupta, Papadimitriou, Umesh Vazirani。 其中,Umesh 堪称计算机理论界的第二名师(第一名师是他自己的导师 Manuel Blum) ,他带过的学生们犹如一个理论计算机科学新生代的全明星队。另一个作者 Papadimitriou 可算是理论界的第二名笔(第一非 Knuth 莫属) ,他的书 Computational Complexity 和 Combinatorial optimization
6、堪称理论计算机科学最好读的专业书,他业余还写了本小说Turing。第三个作者 Dasgupta 是个算法方向的研究者,他最年轻,本身就是 Umesh 的学生,相比前面二位也没什么噱头 可他注定要因这本 Algorithms 而被载入计算机科学的史册。 在这本书之前,算法的经典教材首推 CLRS 的算法导论。算法导论让人印象深刻的,是它内容的全面翔实,还有它一千两百页的厚度。 而见到这本 Algorithms 时,你会震惊于它的薄。我从亚马逊收到这本书时,还以为拿错了包裹。 可读过之后,你就会折服于它的美。 这是一本可以给人带来巨大阅读乐趣的专业书籍。作者娓娓道来,又惜墨如金。用极精炼的语言,为
7、我们指明了一条通向那些美丽算法的线索。我要由衷地说:这本书不仅仅是一些结果的集合,更是一段美好的旅程。我对书中涉及的内容已然熟悉,但读过之后仍感收获良多,对算法这门学问又多了些认识。真的是,写书当如是。 对我来说,算法的教与学有两个困难的地方: 其一,我们学习了那些经典的算法,除了赞叹一下设计的巧思,但总难免问上一句:怎么想到的?对学生来说,这可能是最费解、也最让人窝火的地方。我们下再多的功夫去记忆书上的算法、去分析这些算法的效率,却终究不能理喻得到这些算法的过程。心理盘算着:给我一个新问题,让我设计个算法出来,我能行吗?答案是:不知道。 可这偏偏又是极重要的,无论作研究还是实际工作,一个计算
8、机专业人士最重要的能力,就是解决问题解决那些不断从理论模型、或者从实际应用中冒出来的新问题。 其二,算法作为一门学问,有两条正交的线索。一个是算法处理的对象:数、矩阵、集合、串(strings)、排列(permutations) 、图 (graphs)、表达式(formula)、分布 (distributions),等等。另一个是算法的设计思想:贪婪、分治、动态规划、线性规划、局部搜索(local search),等等。这两条线索几乎是相互独立的:同一个离散对象,例如图,稍有不同的问题,例如 single-source shortest path 和 all-pair shortest pat
9、h,就可以用到不同的设计思想,如贪婪和动态规划;而完全不同的离散对象上的问题,例如排序和整数乘法,也许就会用到相同的思想,例如分治。 两条线索交织在一起,该如何表述。对学生而言,不同离散对象的差别是直观的我们已经惯于在一章里面完全讲排序、而在另一章里面完全讲图论算法;可是对算法而言,设计思想的差别是根本的,因为这是从问题的结构来的:不同离散对象上面定义的问题,可以展现出类似的结构,而这结构特征,就是支持一类算法的根本,也是我们设计算法的依据。 坦率的说,之前还没有哪一本算法书很好的解决这两个困难,就连算法导论在这两个问题上也都做得不好。传统的算法书,大多注重内容(content)的收录,但却忽
10、视思维过程的展示(exposition),因此我们学习了经典的算法,却费解于得到算法的过程;而且算法教材对于内容的编排多是枚举式的(enumerative),这多少是受了 the art of computer programming 的影响可那是本工具书而不是教材,因此我们一提到算法课,就想起了排序、哈希、最短路径这些题目(topics),却没有一个统一的线索在心中。 这本 Algorithms,在短短的篇幅内,做到了。 三位作者可谓野心勃勃,几乎是胆大妄为。他们对传统算法教学思路的颠覆和背叛可谓前所未有。刚拿到目录的时候,我就替他们捏了一把汗,觉得这哪里像一本“正经” 的算法书。可读下来,
11、却不由得佩服算法书早该这么写了。 他们并没有要全面的收录各种各样的算法,他们做的事情是理清了一条算法这门学问的线索。因此填鸭式的内容灌输不是这本书的目的;对结构的精心安排,对问题的数学结构的剖析、从而推出一个算法的过程的讲解,都体现除了这本书真正的用心:它要让学生获得最大程度的启发,要训练学生独立解决问题的能力。 我觉得这才是教育的真正目的,也是算法课应该追求的目标。 说完了种种溢美之词,也来补充一下这本书的不足。这样一本精炼的算法书,为了它道理的清晰、为了它的美,必然会放弃一点对面面俱到的追求。如果我用这本书来教一门算法课的话,我会增加一点以下的内容: 1. 数据结构。 这本书对数据结构没有
12、单独的章节,都是在某个数据结构被一个算法用到的时候讲一下,例如priority queue 之于 Dijkstras algorithm。这种做法体现了作者的观点:这门课完全就是关于 algorithms,数据结构对于算法而言就只是个工具。如果同一个系还能开出一门很强的 data structures 课,这么做当然很好,各有侧重。但若是我来上课,肯定会提一下数据结构的一些重要思想,例如 hashing,和他们的数学背景。因为对于一些实际问题,数据结构已不再是个工具,可能就是问题本身。 2. 几个没有被此书涉及到的算法设计和分析的工具:对手论证(adversarial argument),ma
13、troid ,平摊分析(amortized analysis)。 3. 书中每个算法问题目前最好的上下界(upper bounds, lower bounds)。 对于一本书而言,让它记录这些不太现实,因为除非上下界已经紧了,也许出版的第二天就会有更好的上界或下界(其实这事已经发生了,书最结尾 historical notes 提了一句整数乘法的 fastest known algorithm,结果现在这个结果已经被刷新了) 。但老师上课的时候,应该跟学生们讲一下这个内容,让学生心里有这个“上下界”和open problem的概念,也晓得算法不是死知识,而是正在发生中的事。 4. 讲一点比贪婪
14、、动态规划等等更加“现代” 的算法设计的思想,例如 spectral analysis, metric embedding, rapid mixing of markov chain 等等。 也提一点当下的实际问题(例如 google 或豆瓣想解决的问题)面临的一些新的考虑,例如非经典的现实的计算模型:考虑内外存的 I/O 模型,面对海量数据输入的 streaming model,海量数据的 sub-linear algorithms 等等。这些现实模型上的算法需要重新设计去面对新的考量。 我理解 Algorithms 这本书没有收录这些内容的原因。越是新的东西老的越快,没有人希望自己的书很快过时。但上课不妨出一些这样的 case studies,时髦的东西学生肯定会很感兴趣,这些新东西的粗糙也可以锻炼学生实际解决问题的能力。 5. 除了这本 Algorithms 作为教材,补充读物可以在 CLRS 算法导论和 Kleinberg 和 Tardos 的算法设计(这也是本顶新的书)之间选择一本。我个人推荐后者。