《算法分析导论》评介

2006-08-08苏运霖

计算机教育 2006年7期

苏运霖

本文对由两位著名计算机科学家罗伯特·基德格维克（Robert Sedgewick）和菲律比·弗拉约列特（Philippe Flajolet）合著的《算法分析导论》一书进行介绍和评论，既指出它的突出特点和优点，也指出其中美中不足处。

由于种种原因，我很晚才获知关于《算法分析导论》一书在大洋彼岸出版的消息。但得知它在我国翻译和影印出版，则相对地较早些，而且很荣幸，得到华章图文信息有限公司的盛情邀请，要我写一篇书评。这是一件很有意义的事情。因此我欣然命笔。

首先，要说一说本书的两位作者。第一作者罗伯特·基德格维克是著名计算机科学家唐纳德·欧·克努特的博士生，可以说是克努特的一位得意门生。在获得博士学位之后，他继承克努特的衣钵，从事计算机算法设计和分析的研究，而且成绩斐然。除已发表了许多颇有建树的有关算法的论文外，还发表了《算法》(Algorithms) 、《C语言下的算法》(Algorithms in C)等多部著作。基德格维克现在在美国长青藤大学之一的普林斯顿大学计算机科学系任教，也就是同世界首位荣获计算机界最高奖的姚期智教授同在一个学校一个系内，并且还是美国著名的Adobe System公司的董事。基德格维克还曾是另一家著名公司Xerox PARC的研究人员，她也是姚期智教授的夫人，著名计算机科学家姚储枫教授长期任职的公司。基德格维克还曾就职于美国国防部防御分析研究所及INRIA等。而菲律比·弗拉约列特也非等闲之辈，他的多项成果被克努特在《计算机程序设计艺术》一书中所引用。作为法国科学院的院士，他现在是INRIA的高级研究主任，也在普林斯顿大学和Ecole Polytechnique任教，并且在斯坦福大学、智利大学和弗吉尼亚理工学院都拥有客座教授的席位。因此，克努特为本书所写的序言中，指出两位作者都是这一领域的世界级领军人物，也是阐述问题的能手，并非只是赞美吹捧之词。而由他们两位来写这么一本书，乃是适得其所的。

其次，本书确实具有里程碑式的意义。把它看做算法分析这样一个崭新领域的头一本经典著作，是丝毫不过分的。正如克努特在序言中所说，在30多年的发展之后，算法分析已经相当成熟，可以单独作为标准的计算机科学课程之一。而两位作者来写此书，正是当仁不让地承担起为这一课程提供一本经典教材的使命。轻易不愿为他人的书作序的克努特，却破例为本书写序言，而且对它给予极高评价，正是本书价值的佐证。

当然，更雄厚的证据，还在于此书的内容本身。作为本领域的领军人物，本书的相当一部分内容是两位作者本人的创新性成果，也包括了迄今为止许多本领域的杰出科学家们的最新成果，而首先就是对于算法分析的工具或子领域的界定。在这方面，他们的见解肯定是权威性的。他们把它划分成为递归式关系、生成函数、渐近近似式、树形、排列、串和检索结构以及字和图等。这种分划是极其重要的。因为由此开始，在算法分析这一领域，研究的范畴就将包括这些方面。如同人工智能这一领域，也是当年由人工智能的先驱者们界定出包括：游戏、自动推理、搜索、定理自动证明、神经网络、模糊逻辑、非单调推理、自动决策和规划、学习、记忆、语言产生和理解、语言识别、模式识别、机器人等。因此人工智能的发展就沿着这样一些方向继续下来。同时，它也说明，在算法分析中所使用的工具大体上属于这一范畴。当然，同人工智能领域一样，界定范畴并不妨碍今后的发展，可能会随着时间的推移而出现新的领域，或采用别的更新的工具。

更具体地来看作者们的创新点，如在关于递归式关系的介绍中，他们把递归式归纳为：

1)一阶递归式；

2)非线性一阶递归式；

3)高阶递归式；

4)二进制的分而治之递归式；

5)一般的分而治之递归式。

并把求解递归式的方法分为四个：

1)改变变量法；

2)各种技能法；

3)自举法；

4)振动法。

这些都是作者们在总结别人和他们自己的工作的基础上所作出的新贡献。在这当中，不乏精彩的论述和巧妙的构思。