《计算机程序设计艺术卷1》读书笔记

前言

这本“圣经”体量太大,所以笔者只记录自己想记录的或者有必要记录的。

根据作者所提整套丛书的内容总览,卷 1(基本算法)可以看成整套丛书的交集,包含了其他卷都需要用到的基本内容,不仅可以作为阅读其他各卷的参考书,还可以用作一些课程的教材,比如离散数学(1.1 节、1.2 节、1.3.3 节和 2.3.4 节),数据结构(主要是第 2 章)。

第 1 章 基本概念

算法

算法(algorithm)的五个特征:有限性、确定性、输入、输出、可行性(有效性)。

谈算法的有限性(有穷性),一个过程如果具备算法除有限性外的全部特征,那么可以称为计算方法。在实践中对各种算法在广义美学意义下判定好的,涉及到算法的执行次数、执行效率、对计算机的适应性、算法本身的优雅。面对同一问题的多种算法,判别最佳算法将我们引向算法分析(algorithmic analysis)。

算法的形式定义:本节最后会用集合论作为算法概念的坚实基础,把一种计算方法形式地定义为一个四元组$(Q,I,\Omega,f)$,四个量分别表示计算状态、输入、输出和计算规则。

  • $Q$是包含子集$I$和$\Omega$的集合
  • $f$是$Q$映射到自身的函数
  • $\Omega$应在$f$映射下点点不动

集合$I$中的每个输入$x$定义一个计算序列$x_0,x_1,x_2,\cdots$,如下:

如果$k$是使$x_k$在$\Omega$中的最小整数,就说计算序列在$k$步内中止。某些计算序列可能永远不会终止。对于$I$中的所有$x$都能在有限步骤内中止的计算方法就是算法

注意$Q$内元素可以为集合,陷入单元素想法的话不好理解书中紧接着对算法 1.1E 的形式化描述。

数学准备

本节更可取的学习方式,先略读这一节,在见过后面的大量应用过后,再返回来进行深入的学习。

数学归纳法

将数学归纳法看成一个算法式证明过程(构造证明),比如下面对任意正整数$n$,产生$P(n)$的证明。

  • I1. [证明$P(1)$.] 置$k \leftarrow 1$
  • I2. [$k=n$?] 如果$k=n$,算法终止,输出。
  • I3. [证明$P(k+1)$.] “如果$P(1),\cdots,P(k)$全部为真,那么$P(k+1)为真$的证明,并输出。
  • I4. [增加$k$.] $k$增加 1,转到步骤$I2.$.

注意,算法过程主要描述了蕴含关系的证明(这也是我们使用数学归纳法关注的地方),但若要得到推理出的证明结论,必须要证明前提,这是我们常常会忽略的地方!比如应用到了前述项$P(2)$,但是却是个伪命题。这样即便蕴含关系成立,证明也是错误的。

注意,将数学归纳法的概念同科学中常说的归纳推理区别开来。

建设归纳推理是个“猜测”的过程(构造图示理解,如果我们不能证明对于所有$n$都可以进行这种构造,就仍是一种归纳推理)。

举例,关于斐波那契数列$F$的一个性质,定义$F_0 =0$,$F_1 = 1$,$F_{n+2} = F_{n+1} + F_n$。现在我们证明,如果令$\phi = (1+\sqrt{5})/2$,那么对于所有正整数$n$,我们有:

称之为$P(n)$(以命题理解),其归纳法证明过程

  • 对于$n=1$,那么$F_1 = 1 = \phi^0$
  • 假设$P(1),P(2),\cdots,P(n)$全部为真,并且$n > 1$。我们得到:

    对于数$\phi$有一条重要性质。

    式(3)带入式(2)后我们得到$F_{n+1} \le \phi^n$,即$P(n+1)$

(对拓展欧几里得的数学归纳证明略,待补充)

其中对拓展欧几里得算法的证明,从未证明算法会终止,我们只证明了如果算法终止,那么它会给出正确的答案。

通常需要单独证明算法会终止。

习题中涉及广义归纳法,这个一般原理称为良序原理(回顾良序概念,后面再回过头来看这个题目)。

数、幂与对数

考虑对数运算,书中给出的方法,由于有限精度,必须舍入或者截断,带来的计算误差。

放几个习题吧。

1.2.2.10 证明 $\log_{10} 2$不是有理数。

Prove by contradiction 假设$\log_{10}2$是有理数,则有$\log_{10}2 = \frac{p}{q}$,则$2^q = 10^p$,显然该式矛盾,因为等式左边不被 5 整除,故$\log_{10}2$不是有理数。

1.2.2.19 如果整数$n$的十进制表示长 14 位数,$n$的值能否存入容量为 47 个二进制位和 1 个符号位的一个计算机字。

$\lg n = \log_{10} n / \log_{10} 2 = 14 \lg 10$,又因$\lg 10 \approx 3.322$(向上),$14 \times 3.33 \approx 46.62 < 47$,故可以存入。