enter image description here

文 / 郑晖

作者简介:郑晖,男,年方不惑。1986年入武汉大学数学系学习,1993年毕业后到高校教书三年。1996年赴美攻读数学博士学位,1998年开始选修计算机课程。2000年获计算机硕士学位,随后到华尔街一家IT公司就职。2004年底回国,先在广州一所IT外企工作,后出任一家软件公司的技术总监。从2008年4月起,在网上发表连载博文《冒号课堂》(原名《冒号和他的学生们》)。

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

充分

一本书的内容是否充分,通常体现在深度、广度、高度、细度和角度上。

深度。在不过分为难目标读者的前提下,足够的深度是专业书籍的核心价值所在,否则“专业”二字只是枉谈。本书是基于Donald Knuth(第二作者)在美国斯坦福大学的讲义编写而成,内容上即便是这所全球顶级大学的学生也倍感不易。虽然不少人推荐该书为《The Art of Computer Programming》的预备图书,但若仔细比较二者就会发现,前者甚至在一些专题上的深入度比后者犹有过之。好在书中虽不乏抽象的数学理论,但均适可而止,且最终皆为实际问题服务。在降低难度的同时,增加了实用性和亲和力。

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

广度。坦率地说,这本书的广度不如其深度突出。作为计算机科学基础的数学教材,它未涵盖的内容还有不少,比如图论、自动机理论、博弈论、信息论、可计算性理论,也没有更基础的集合论或数学逻辑等。另外,数论与离散概率虽有涉及,但篇幅较少。

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

高度。具体数学另有一个“双关”的解释:连续与离散数学的混合(Continuous与Discrete混合成Concrete)。虽说计算机科学主要建立于离散数学之上,而本书又特别强调具体性和实用性,但仍不可避免地涉及到更具抽象性和理论性的连续数学。原因无他,后者的层次更高。人们都有这个体会:一个难解的观点或问题往往在“更上一层楼”之后,立刻一目了然。

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

最能体现本书之细的是数学符号的选取和解释。例如用“k”而非常见的“i”做数列下标,避免与虚数“i”混淆;解释用“< >”代表欧拉数(Eulerian Number),用上、下横杠分别代表上、下阶乘幂的合理性,不吝用4个自然段来说明“O”记号中的等号等。或许有人会对本书如此讲究符号不以为然,那他一定低估了简洁直观、自然优美的符号对于数学的重大意义。数学家兼哲学家Whitehead在《数学导论》中曾说:“良好的数学符号能解除大脑多余的工作,使之集中于更高级的问题,从而有效提高心智的力量。”

角度。从不同的角度看待同一问题,通常会有不同的解释方式和解决方式。一本时常切换角度的书,对读者融会概念、贯通方法大有裨益。例如本书对平方项求和问题先后共计采用8种方法。在数学书中,一题多解并不少见,少见的是多处一题多解。作者常常在介绍一种新技巧后,并不急于解决新问题,而是用它更加漂亮地解决前面早已解决的老问题,不经意地展现数学的和谐与自洽。宛如一个魔术师,不停地用熟练的、令人眼花缭乱的手法,变换不同的视角,采用不同的形式展现同样令人称绝的效果。

实在

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

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

过程。在提出问题后,本书一般并不直截了当地给出解法,而是针对不同问题采用不同策略:或通过有针对性的变换逐步化繁为简;或从特殊情形入手,通过猜测和归纳来证明一般性结论;或通过类比从已知结论中获得启示;或通过引进强大的工具解决问题;或通过反复迭代逐步优化结论(如9.4节中介绍的BootStrapping技巧)。

积累。本书尤其强调数学知识库的积累和演进。书中一再从简单情形开始,逐步得出越来越强的结论,并尽可能泛化推广,再应用于特殊情形获得新的结果,由此建立起越来越完备的定理仓库和公式列表(类似软件工程中的迭代增量式开发)。

试错。在实际的数学发现中,单有直觉和洞察力是不够的,更多时候还得靠硬性的计算和反复的试错排除。可惜绝大多数的教材都是“洁本”——抹去所有的失败痕迹,不见试错的过程或探索的途径,总是每击必中。本书则不然,诸如Wrong、Fail、Embarrassing、Impass、Lose、Loss、Mistake、Deflating等负面词汇比比皆是,毫不讳言失败,不仅真实再现了数学的探索过程,也告诉读者,不必耻于失败,也不必因屡次碰壁而怀疑自己。很多时候,失败只是成功路上的一个必要的弯路。

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

不定性。本书还原真实数学的另一表现是,让读者充分意识到数学发现的开放性和不定性。传统的数学教材中往往证明题居多,而实际的数学研究会面对更多的不确定性。比如证明或否证一个结论比单纯的证明更困难,因为需要考虑两种不同的可能;化简表达式也比证明一个等式更费劲,因为方向和目标均不确定。更为棘手的问题是,找出使某一断言成立的充要条件。

最可怕也最接近真实数学研究的问题则是,给定一个集合,找出其元素所具有的“有趣”的性质。按本书3.2节的标准,这属于最高级(第5级)的数学问题,因为其最开放、不定性最大。

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

结语

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

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

一直以来,人们只看到数学枯燥无味、艰深晦涩的一面。本书则揭示了数学生动有趣的另一面,同时也表明,数学不是少数天才们的专属游戏,只要经过适当的训练,数学魔术人人皆会变。

(此文发表于《程序员杂志》2013年7月刊)豆瓣有作者未删减版:数学魔术

程序员应读的四本数学书:

enter image description here