《计算机程序设计艺术》初读感

传奇

在计算机领域里，有这么一本神作：作者从 20 多岁还在读博士时就开始写，一直写到 80 多岁，写到现在这本书还没完结；为了排版这本书而顺便开发的排版系统推动了整个西文印刷行业的变革；比尔盖茨说：“如果你能够看懂这本书的所有内容，那么欢迎给我发来简历”；《美国科学家》杂志列为 20 世纪最重要的 12 本物理科学类专著之一……或许关于这本书的赞誉就能写一本书。

这本书就是《计算机程序设计艺术》，作者是高德纳（Donald Ervin Knuth)。高德纳本身就是一个传奇，他获得的著名奖项如下：

ACM 授予：

1. 图灵奖（计算机科学界最负盛名的奖项，被誉为计算机界的诺贝尔奖）
2. 软件系统奖（授予对技术概念、商业接受度方面产生了持久影响的软件系统的开发者或者机构）
3. 格蕾丝·默里·霍波奖（授予取得独立的、意义非凡的或服务贡献的年轻专业研究人员）

美国前总统卡特授予：

• 全国科学奖章

IEEE 授予：

1. McDowell 奖(1980)
2. 计算机先驱奖(1982)

（以上奖项只是选出了一些较为知名的奖项，如果把所有奖项都列出来，恐怕这篇文章都写不完）
高德纳一生获奖无数，但他十分淡泊名利，有传闻说图灵奖的奖杯（如图）被高德纳拿来放水果

而《计算机程序设计艺术》则是他这传奇的一生中最璀璨的篇章，按照高德纳本人最开始的计划，这本书的主要内容分为 5 卷，每卷包含两章，分别为

• 卷 1. 基本算法
  • 第 1 章：基本概念
  • 第 2 章：信息结构
• 卷 2. 半数值算法
  • 第 3 章：随机数
  • 第 4 章：算术
• 卷 3. 排序与查找
  • 第 5 章：排序
  • 第 6 章：查找
• 卷 4. 组合算法
  • 第 7 章：组合查找
  • 第 8 章：递归
• 卷 5. 语法算法
  • 第 9 章：语法扫描
  • 第 10 章：语法分析

其中第 4 卷设计的范围很大，实际上包含三本书（卷 4A、4B 和 4C）。

目前最新一部应该是卷 4A，至少网上能买到的最新一部就是它。作者自己预计还要用 20 年才能写完整套书。

个人初读感受

本人有幸从学校图书馆中借到了本书中文版的第一卷（人民邮电出版社 2016 年出版），准备细细品读一下。

翻开这本书，第一页是高德纳专门为中国读者写的序，里面写到了高德纳这个名字是他 1977 年访问中国前夕姚期智的夫人姚储枫给他起的中文名。他也希望中国读者能记住他的这个中文名。最后还写了一段激励读者钻研计算机程序设计的话。这个序言一下子就拉近让我感受到高德纳的人格魅力，尽管拥有数不清的荣誉，但他依然如此平易近人，实在是难能可贵。

本书还有一个非常有特色的地方，就是专门用一页内容写了阅读本套书的步骤，还在旁边列出了相对应的流程图，在增加趣味性的同时也在不知不觉中培养起了读者的算法思维。继续读下去会发现之后书中的很多内容都在潜移默化地培养读者的算法思维。

另外，本书中所有习题都给出了难度等级，让读者可以根据自己的能力选择适合自己的题目练习。而且这个难度等级分的非常细也非常有意思。从 0 到 50 每个整数都是一个难度等级，难度依次增长。而等级编号除以 5 得到的余数表示完成这道习题的具体工作，比如求解一道等级为 24 的习题比求解一道等级为 25 的习题可能花更长的时间，不过做后一种习题需要更多的创造性。而所有等级为 46 及以上的习题都是开放式问题，有待于进一步研究。

继续阅读下去，感觉这本书的文字叙述也相当优美，而且往往是以第一人称“我们”来描述，就像是作者和读者以朋友的身份一起在探讨问题，拉近了作者和读者的距离。此外，得力于 TeX 排版系统（后文后详细叙述），本书的印刷排版也十分优美，特别是对数学公式的排版，简直就像艺术品一般。

当然，一本书最重要的还是它能不能把问题讲明白。在这点上，这本书依然相当优秀。比如书中提到的第一个算法：欧几里得算法，这是一个用于求两个正整数最大公因数的算法。书中对这个描述如下：

算法 E （ 欧几里得算法 ）. 给定两个正整数m和n，求它们的最大公因数，即同时整除m和n的最大正整数.
E1. [ 求余数. ] 用 n 除 m ，令 r 为余数. （ 我们将有 $0\leqslant r< n$. ）
E2. [ 余数为 0？] 如果 r=0 ，算法终止. n 是答案.
E3. [ 减少. ] 置 m\gets n， n\gets r，然后返回步骤 E1.

5 行文字将这个算法解释的清清楚楚，就算只有小学数学水平都能理解。对比一下某度百科词条对欧几里得算法的描述：

欧几里德算法又称辗转相除法，是指用于计算两个正整数 a，b 的最大公约数。应用领域有数学和计算机两个方面。计算公式 gcd(a,b) = gcd(b,a mod b)

说实话，我第一眼看到 gcd 都懵了，gcd 是啥，我只知道 gkd 啊（哈哈，开个玩笑）。后来一查才知道 gcd 就是最大公因数。而且这句话语法都有问题，“是指用于计算两个正整数 a，b 的最大公约数”这是个病句啊，要么在最后加上“的算法”，要么去掉开头的“是指”。两者一对比，高下立判。

另外，在每章的开头和结尾都有和章节内容相关的名著选段和名人名言，起到了锦上添花的作用。

\TeX

前文说过为了排版这本书而顺便开发的排版系统推动了整个西文印刷行业的变革，这个排版系统的名字叫做\TeX。最初是因为出版商将这本书中的数学公式排版做的非常难看，所以高德纳就自己写了一套排版系统，特别专注于数学公式的美观性，这就是\TeX。

\TeX目前广泛应用于科研机构及出版行业中，很多专业领域的杂志都要求以\TeX格式提交论文。各种基于\TeX的宏包极大地丰富了\TeX的生态。而\TeX的数学公式表示方法则基本上成为了目前在网上输入数学公式的标准，被众多文本编辑器使用，包括本博客的编辑器。\TeX这三个字母的这种格式（E 稍微下沉）是官方认定的表示方法，如果使用的文本工具不支持这种格式，则写成 TeX，e 必须小写。