数学魔术——评《具体数学》

Hui Zheng May 18, 2013 book-review math  computer-science  programmer  learning 

数学魔术

人民邮电出版社出版的《具体数学——计算机科学基础》译自经典名著 《Concrete Mathematics: A Foundation for Computer Science》。 简单地称赞这是一本好书,虽毫无风险性,却也毫无信息量。 那么《具体数学》(以下简称《具》)具体好在何处呢? 简言之两个词:一曰充分,二曰实在。

充分

此所谓充分,系指一本书在深度、广度、高度、细度、角度等各维度上的充分。

深度

在不过分为难目标读者的前提下,足够的深度始终是专业书籍的核心价值所在,否则“专业”二字只是枉谈。 哪怕是入门书籍,也不应轻易地点到为止。好书如严师,严师方能出高徒。让人一直轻松的书,通常 也会轻松地被人遗忘。

《具》书之深,似乎无庸赘述。充斥全书的数学符号,足令大多数非数学专业者望而却步。 此书基于Donald Knuth(第二作者)在斯坦福大学的讲义而成,便是这所全球顶级大学的学生 也倍感不易。虽然不少人推荐该书为The Art of Computer Programming(TAOCP) 的预备书籍,但若仔细比较二者,前者甚至在一些专题上的深入度比后者犹有过之。 好在书中虽不乏抽象的数学理论,但均适可而止,且最终皆为实际问题服务。 这在降低难度的同时,也增加了实用性和亲和力。

其实,深度并不一定意味着复杂、玄妙或高深,更非概念、理论、公式、数据或代码等单纯的堆砌。 关键是作者能否拨开笼罩在知识周围的迷雾和光晕,引领读者渐入深境,让他们获得头脑 与知识内在的硬核产生正面撞击的机会(这大概是人们恍然大悟时喜欢摸后脑勺的原因吧?)。

《具》书的主线是从递归问题到求和问题,再到二项式系数,接着从特殊的数列到一般的生成函数, 内容环环相扣并逐步加深。书中屡见不鲜的情形是:某一问题看似已挖掘至极限,但随着更深刻的 理论或更强大的工具的推出,原问题有了更妙的解法或更强的结论。

广度

深度可反映一本书对知识的纵向开采程度,广度则反映它对知识的横向拓展程度。 坦率地说,《具》书的广度不如其深度突出。作为计算机科学基础的数学教材,它未涵盖的内容还有不少, 如图论、自动机理论、博弈论、信息论、可计算性理论等,也没有更基础的集合论或数学逻辑。 另外,数论与离散概率虽有涉及,但篇幅较少。

当然,这与作者明确的目的有关。正如书中前言所说,“具体”数学是针对“抽象”数学而设的名称。 纯粹数学工作者大都有个通病:醉心理论的抽象而不屑实际的应用。本书试图证明, 兼顾具体性与抽象性、实用性与通用性的数学,同样可以很高级、很优美。 因此它并不打算覆盖全部的离散数学,而是提供一套系统的、有关离散运算的工具和方法。 故仅就其所重视的主线而言,该书的广度也是可观的。

高度

一本书应通过深度由表及里,通过广度由此及彼,把局部孤立的知识点编织成整体联系的知识面。 进一步地,它还应上升到一定的高度,让知识图案变得立体而丰满。

具体数学另有一个双关的解释:连续与离散数学的混合(CONtinuous与disCRETE混合 成CONCRETE)。虽说计算机科学主要建立于离散数学之上,而本书又特别强调具体性和实用性, 但仍不可避免地涉及到更具抽象性和理论性的连续数学。原因无他,后者的层次更高。

人们都有这个体会:一个难解的观点或问题往往在“更上一层楼”之后,立刻一目了然。 以数学为例,在引入代数方程后,算术应用题变得轻而易举;借助高等数学,许多初等数学中的难题 迎刃而解。

《具》书中这类例子不胜枚举。如:用L’Hospital法则求极限、用导数或积分求和, 用Taylor级数展开生成函数(generating function)、估算近似值,等等。 令人印象最深的是,该书5.2节提出了8个级数问题,一道比一道难,读时目不转睛、屏气凝神,唯恐迷失。 直到后来提升到更一般的超几何级数(hypergeometric series),这才恍然大悟:原来 那些问题不过是些特例罢了。同样有启发性的是9.5节,在证明欧拉求和公式前,提供了一个非正式但 高层次的(high-level)推理。此外,出于严谨,在谈到为何书中经常忽略无穷级数的收敛性 时,用到了域(field)的概念。从抽象代数的高度来解释,自然言简意赅。

细度

除了宏观的深度、广度和高度外,微观的细度也是衡量书籍的一个标准。 一本书不应也不可能事无巨细,面面俱到,但一定要有足够的细节,以填补大多数读者的思维盲点。 令人稍感意外的是,《具》书的细度毫不逊色于深度。

细首先体现在思虑周到、推理严谨。书中不断地在考察:分母是否为零?如何定义退化情形下的函数值? 数列的负下标是否有意义?级数的收敛性如何?等等。程序员若有这份细致,就不会常犯逻辑混乱、 考虑欠周、忽略边界检查等编程错误了。如果说这些只是对数学专业书籍的基本要求,那么 在求得答案后还经常不厌其烦地用特殊值验证就不是那么常见了。这倒不是说数学工作者不如程序员 那么重视测试,而是他们通常不会将此过程写入书中。

在分析和讲解问题时,本书可谓细致入微。许多细腻的数学小技巧是其他书中鲜有提及的,比如: 如何从特殊情形入手,逐步过渡到一般情形;如何猜测答案,又如何不通过猜测而获取答案; 如何调整级数的下标以利计算;如何通过变换逐步降低求和的难度,等等。不时还夹杂一些 忠告,如:计算效率不等于理解效率(efficiency of computation is not the same as efficiency of understanding)(译本中将efficiency译为“有效性”似有不妥,易被认为“效果”effectivity之效), 这对那些为微小改进效率而牺牲代码可读性的程序员同样有警示作用。

最能体现本书之细的是关于数学符号的选取和解释。例如,用k而非常见的i做数列下标,以避免 与虚数i混淆;解释用< >代表欧拉数(Eulerian number)、用上下横杠分别代表上下阶乘幂的合理性; 不吝用4个自然段来说明O记号中的等号;为追求表达式的合理性,不惜采用非标准的记法,如 从编程语言APL中引入[]记号、用\代替|作为整除符号、用表示互素、用倒置而非前置的! (即¡)表示子阶乘(subfactorial,译本干脆译为倒阶乘)、采用简化的超几何函数符号、采用象形 的立方体、硬币、骰子、铺砖符号等。

有人或会对本书如此讲究符号不以为然,那他一定低估了简洁直观、自然优美的符号对于数学的重大意义。 数学家兼哲学家怀特海(Whitehead)在《数学导论》中曾说:良好的数学符号能解除大脑多余的工作, 使之集中于更高级的问题,从而有效地提高了心智的力量。本书的作者之一Knuth显然赞同此点,这 从其所著的《Mathematical Writing》中便可看出。无论所编程语言的发明者还是使用者, 均应从中获得启示:良好的语法设计和变量命名有助于提高代码的可读性和编程的效率。

本书在字体设计上也颇费心思,真正做到了从內在到外表处处展现数学之美。 考虑到Knuth是排版软件TeX的设计者,这也不足为奇。

角度

从不同的角度看待同一问题,通常会有不同解释方式和解决方式。一本时常切换角度的书,对读者 融会概念、贯通方法大有裨益。

例如:《具》书对平方项求和问题,先后共计采用8种方法。在数学书中一题多解并不少见,少见的 是多处一题多解。作者常常在介绍一种新技巧后,并不急于解决新问题,而是用它回头更加漂亮地 解决前面早已解决的老问题,不经意地展现数学的和谐与自洽。宛如一个魔术师,不停地用熟练的、 令人眼花缭乱的手法,变换不同的视角,采用不同的形式,展现同样令人称绝的效果。

实在

以上从多个维度分析了《具》书的精彩之处,然其价值远不止此。最理想的专业教材, 应当既能呈现静态的知识体系和结构,又能重现动态的知识形成和发展。

传统数学教材(尤其国内教材)大都按序遵循如下套路:引入概念和定义,提出定理并证明, 列举推论并证明,展示若干例题,布置一堆习题,转入下一章节循环以上过程。 难怪在很多人眼里,数学不过是由一些怪癖的天才们发明的一套冰冷干枯、机械无趣的逻辑系统。

《具》书最可贵之处在于,它不仅显示数学的当前形态,而且反映其产生和发展的历史过程, 以便让读者感知鲜活真实的知识、掌握切实可行的方法。

起源

数学的最终表现通常是高度抽象化和形式化的,但其最初往往起源于具体的实际问题。 本书经常通过一些有趣而实用的问题让数学接上“地气”,既减少了数学的神秘感,也真实 反映了数学的起源。

过程

在提出问题后,本书一般并不直截了当地给出解法,而是针对不同问题采用不同策略: 或通过有针对性的变换逐步化繁为简;或从特殊情形入手,通过猜测和归纳来证明一般性结论; 或通过类比从已知结论中获得启示;或通过引进强大的工具解决问题; 或通过反复迭代逐步优化结论(如9.4节中介绍的bootstrapping技巧)。 如同名师做示范表演,既有连贯动作,又有分解动作,各种招式和套路都 交代得一清二楚。

积累

本书尤其强调数学知识库的积累和演进。如5.2节8道基本练习题难度递增,但由于读者在拾级而上 的过程中慢慢积累了经验和技巧,故而显得难度曲线并不那么陡峭。 书中一再从简单情形开始,逐步得出越来越强的结论,并尽可能泛化推广,再应用于特殊情形获得 新的结果,由此建立越来越完备的定理仓库和公式列表(类似软件工程中的迭代增量式开发)。 跟随此书一路学来,你会感到心中慢慢堆起了一座数学小山。

试错

在实际的数学发现中,单有直觉和洞察力是不够的,更多时候还得靠硬性的计算和反复的试错排除。 可惜绝大多数的教材都是“洁本”——抹去所有的失败痕迹,不见试错的过程或探索的途径,总是每击必中。 《具》书则不然,诸如wrong、fail、embarrassing、impass、lose、loss、mistake、error、deflating等 负面词汇比比皆是,毫不讳言失败,不仅真实再现了数学的探索过程,也告诉读者:不必耻于失败, 也不必因屡次碰壁而怀疑自己。很多时候,失败只是成功路上的一个必要的弯路。 比如,2.5节采用“扰动法”时,从起初的失败中运用类比推理获得正确的解法。 在5.2节的问题6中,作者甚至故卖破绽,给出了一个通过简单验证却仍错误的解法。

系统性

本书宗旨是培养读者的实际数学运算能力,因此虽不乏令人眼花缭乱的技巧(trick), 但更着力的却是传授系统成套的技术(technique)(这从书中高频出现“系统”二字便可看出)。 例如:生成函数法、超几何级数法、Gosper算法、Zeilberger算法,等等。 这些方法不复杂难懂(intricate),不倚重人的洞察力(clairvoyance)或灵光一现 (sudden flash of inspiration),不靠聪明和运气(cleverness and luck)或猜测(guesswork)。 它们是系统的(systematic)和有指导性的(instructive),甚至是机械的 (mechanical)、算法的(algorithmical),乃至可用计算机代劳的。

搞数学的喜欢聪明的方法,写程序的喜欢聪明的代码,但这种聪明往往缺少可靠性、 可理解性、可重复性和可推广性。有时需抑制这类聪明,谨记大巧若拙。

无人会低估数学智慧和灵感的作用,那是所有数学知识的来源。 只是智慧多源自先天,灵感也可遇不可求,故本书着重后天通过训练可获得的系统性技术。

不定性

《具》书还原真实数学的另一表现是,让读者充分意识到数学发现的开放性和不定性。 传统的数学教材中往往证明题居多,而实际的数学研究会面对更多的不确定性。 比如,证明或否证一个结论比单纯的证明更困难,因为需要考虑两种不同的可能; 化简表达式也比证明一个等式更费劲,因为方向和目标均不确定。 更为棘手的问题是,找出使某一断言成立的充要条件。 最可怕也最接近真实数学研究的问题则是:给定一个集合,找出其元素所具有的有趣的性质。 按本书3.2节的标准,这属于最高级(第5级)数学问题,因为其最开放、不定性最大。

练习

《具》书中精彩绝妙的数学技巧层出不穷,令人叹为观止。但它显然不满足于让读者成为 数学魔术的欣赏者,更希望他们成为数学魔术的表演者。 因此,除了充满知识性和启发性的正文外,本书习题之丰富、解答之详尽也是罕见的。 从相对简单的热身题和基础题,到困难的作业题和考试题,乃至超难的附加题和研究题, 如同逐渐升温的熔炉,为读者淬炼越来越锋利的数学兵器。

结语

综上所述,对数学或计算机理论感兴趣者阅读《具》书,如入宝山而不至空返。 至于程序员,他们中的绝大多数在工作中并不涉及高深的数学知识,本书未必会对其编程有直接的帮助。 然而,只考虑工作需求而无自我追求的程序员绝不是好程序员。 研读此书不仅能增长数学知识,更能提高数学修养。要知道,一名程序员最大的价值, 不在于他对某些编程语言和工具的熟练运用,而在于拥有一个 冷静而清晰、 严谨而灵活、抽象而深刻的头脑。

说到本书的翻译,虽非尽善尽美,但总体忠实原文,甚少生硬之处。 尤为难得的是,译者连原书中最难译的(有些还是德语、法语、拉丁语等非英语文字)非技术 性的幽默双关都给出了恰当的翻译和解释,其认真程度可见一斑。 故此,尽管提倡技术人员多看原版书籍,但至少读此译本是无伤大雅的。

一直以来,人们只看到数学枯燥无味、艰深晦涩的一面(世上哪门学问又何尝不如此呢?)。 《具》书则揭示了数学生动有趣的另一面,同时也表明:数学不是少数天才们的专属游戏,只要 经过适当的训练,数学魔术人人皆会变。

(此文发表于《程序员》2013年7月刊,发表时有删节)