前言

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

根据作者所提整套丛书的内容总览，卷 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\)，如下：

\[x_0 = x \qquad x_{k+1} = f(x_k) \quad for \quad k \ge 0\]

如果\(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\)，我们有：

\[F_n \le \phi^{n-1} \tag{1}\]

称之为\(P(n)\)（以命题理解），其归纳法证明过程

• 对于\(n=1\)，那么\(F_1 = 1 = \phi^0\)

• 假设\(P(1),P(2),\cdots,P(n)\)全部为真，并且\(n > 1\)。我们得到：

  \[F_{n+1} = F{n-1} + F{n} \le \phi^{n-2} + \phi^{n-1} = \phi^{n-2}(1+\phi) \tag{2}\]

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

  \[1+\phi = \phi^2 \tag{3}\]

  式(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\)，故可以存入。