SICP笔记(1)

这是SICP纸质笔记的整理。

你可以在这里下载到重新排版过的英文原版或者直接在线阅读。点击这里购买中文纸质版(右侧)。

这里是我第一章的习题。

第一章 构造过程抽象

1. (P9) 1.1， 强有力语言提供的三种机制：

   • 基本表达形式
   • 组合的方法
   • 抽象的方法

2. (P10-P11) 1.1.3，两种求值顺序：

   • 正则序求值：完全展开后规约

     1 2 3 4 5

     (square (square (+ (square 5) (square 6)))) ;; 这里因为遇到了(square 5)，所以先求值，得到25 ;; => (square (square (+ 25 (square 6))) ;; => (square (square (+ 25 36))) ;; 只在必要时求值

     是非严格求值(Non-strict Evalutaion)，只在必要时才进行求值。

   • 应用序求值：先求值参数后应用：

     1 2 3 4

     (square (square (+ (square 5) (square 6)))) ;; 这里(+)需要两个参数才能应用，所以立即对这两个参数进行求值 ;; => (square (square (+ 25 36))) ;; 应用前就求值完毕

     是严格求值(Strict Evalutaion)，应用前就求职完毕

   拓展阅读：维基百科

3. (P18-P19) 1.1.8，局部变量：

   • 约束变量：一个过程的定义约束了所有变量，与名字无关，以这个过程的体为它们的作用域
   • 自由变量：非约束变量，一般可以被子作用于捕获。

4. (补充内容) 1.1.8，作用域：

   • 动态作用域 (Dynamic Scope)：Lisp采用。全局绑定栈，当我们在局部过程定义一个变量时，它的绑定会被推入全局栈，离开时栈顶弹栈，无论何时使用该变量时我们总是使用栈顶绑定。
   • 词法作用域 (Lexical Scope)：Scheme采用。局部环境，即无论何时定义一个变量，我们总在局部环境绑定中操作，使用时也在局部环境寻找。

   拓展阅读：维基百科

5. (P23) 1.2.1，计算过程(Process)与过程(Procedure)：

   • 过程：语法上的形式。如递归过程：在定义中直接或间接调用自己的过程。

     例：

     1 2 3 4

     (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (+ (fib (- n 2)))))))

     这一过程直接调用了自己，是一个递归过程(Recursive procedure)。

   • 计算过程：这一过程的进展形式。例如迭代计算过程：可能是以递归为形式，但是进展上是一种迭代的方式。

     例：

     1 2 3 4 5 6

     (define (fib n) (define (iter count a b) (if (= count n) b (iter (+ count 1) b (+ a b)))) (iter 0 1 0))

     这一过程虽然是一个递归过程，但是在进展上，是迭代的进展方式，所以这是一个迭代计算过程(Iterate process)。

   辨析：过程指的是语法本身的含义，而计算过程指的是所描述的计算过程。

6. (P23) 1.2.1，尾递归：

   尾递归可以在$O(1)$空间内执行迭代计算过程，即使这一计算使用的是递归过程描述的。

7. (Ex 1.13) 证明$Fib(n)$为最接近$\frac{\phi^n}{\sqrt{5}}$的整数，其中$\phi=\frac{1+\sqrt{5}}{2}$。

   证：若要证明$Fib(n)$为最接近$\frac{\phi^n}{\sqrt{5}}$的整数，可以证明$|Fib(n)-\frac{\phi^n}{\sqrt{5}}|<\frac{1}{2}$

   若证上式，可证$Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}$，其中$\psi=\frac{1-\sqrt{5}}{2}$。

   使用归纳法证明上式：$Fib(0)=\frac{\phi^0-\psi^0}{\sqrt{5}}=0$，成立；$Fib(1)=\frac{\phi^1-\psi^1}{\sqrt{5}}=\frac{\sqrt{5}}{\sqrt{5}}=1$，成立。

   假设$Fib(n-1)=\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}$与$Fib(n-2)=\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt{5}}$成立，

   由定义，

   $$ \begin{aligned} Fib(n) &= Fib(n-1)+Fib(n-2) \\&= \frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}+\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt{5}} \\&= \frac{\phi^n(\phi^{-2}+\phi^{-1})+\psi^n(\psi^{-2}+\psi^{-1})}{\sqrt{5}} \end{aligned} $$

   由于$\phi^{-2}+\phi^{-1}=\frac{3-\sqrt{5}}{2}+\frac{\sqrt{5}-1}{2}=1$，$\psi^{-2}+\psi^{-1}=\frac{3+\sqrt{5}}{2}-\frac{\sqrt{5}+1}{2}=1$，

   立即可得$Fib(n)=\frac{\phi^n+\psi^n}{\sqrt{5}}$，得证。

   那么立即有$Fib(n)-\frac{\phi^n}{\sqrt{5}}=-\frac{\psi^n}{\sqrt{5}}$。

   又由$|\frac{1}{\sqrt{5}}|<1, |\psi^n|<\frac{1}{2}$，可得$|\frac{\psi^n}{\sqrt{5}}|<\frac{1}{2}$，也就是$|Fib(n)-\frac{\phi^n}{\sqrt{5}}|<\frac{1}{2}$，$\mathtt{Q.E.D.}$

8. (P28) 1.2.3，增长阶（渐进紧确界）：

   令$n$为可度量问题规模的参数，$R(n)$为计算$n$规模问题时所需的资源，我们称$R(n)$具有$\Theta(f(n))$的增长阶，记为$R(n)=\Theta(f(n))$，满足： $$ \forall n, \exists k_1,k_2\in\mathbb{Z}, k_1f(n)\le R(n)\le k_2(f(n)) $$ 其中$k_1,k_2$为与$n$无关的参量。

   拓展阅读：算法复杂度的记号表示法，《算法导论》。

   增长阶计算练习：

   1. Ex 1.14，把$n$元换成$k$枚硬币：

      首先考虑(cc n 1)的情况，在这种情况下，每一个$n$都会带来以下两种展开：(cc (- n 1) 1)和(cc n 0)，也就是说，这样情况下总共会有$2n+1$个节点，时间复杂度自然为$O(n)$。由于$n$每增长$1$，这棵树的层数就增加$1$，所以空间复杂度为$O(n)$。

      接下来考虑(cc n 2)，这样的情况会展开为(cc (- n 5) 2)和(cc n 1)，根据上述讨论得知(cc n 1)复杂度为$O(n)$，而这棵树一共有$\frac{n}{5}$棵这样的子树，所以总共复杂度为$O(n^2)$。空间复杂度不变，仍然是$n$每增长$1$多一层调用。

      那么根据如上考虑，(cc n k)总计的时间复杂度就为$O(n^k)$，空间复杂度为$O(n)$。

   2. Ex 1.15，计算三角恒等式复杂度。

      计算的核心代码为：(p (sine (/ angle 3.0)))，也就是说，对于每一个数，求得答案时，假如p调用了$n$次，那么一定满足$a\le 0.1\cdot 3^n$，对两边取对数，有$\log{a}\le \log{0.1}+n\log{3}$，也就是说，$n$和$\log{a}$正相关。那么算法的时间复杂度和空间复杂度都为$O(\log{a})$。

9. (P35) 概率算法：

   在满足条件的情况下，有一定概率能保证解的正确性的算法，如费马素数检测。

10. (P35-P36) Ex 1.22~1.24，算法复杂度的讨论：

    算法复杂度是用于衡量增长率的工具，而不是描述实际增长率的工具。

    运算时间一般受以下因子影响：

    • 运算环境：如瞬时I/O速度，CPU调度等
    • 常数因子，如$O(kn)=O(n)$，此时$k$为常数因子，那么$O(2n)=O(n)=O(3n)$的两个算法速度并不一样。

    等等。

    我们使用算法复杂度来衡量增长速度，尤其是数据量比较大的情况下。

11. (P37) Ex 1.28，Miller-Rabin算法：

    实现参照：1.28.scm

    理论依据：费马小定理，若$n$为质数，那么$\forall a<n,a\in \mathbb{N}, a^{n-1}\equiv1\pmod n$，取$a$检查即可。

    Miller-Rabin算法中会遇上$1$取模$n$的非平凡平方根，即：$\exists b\in\mathbb{N}, 1<b<n-1, b^2\mod n=1$。这样的数表示$n$不为素数。证明也很简单，考虑： $$ (x^2-1)\mod n=0\implies(x+1)(x-1)\mod n =0 $$

    也就是说，假如$x$为非$2$的质数，上面的式子一定不成立（因为此时只会有$\pm1$两个解）。

    在Miller-Rabin算法运行过程中，我们大概有$50%$的几率遇上这样的数，所以测试总计$\frac{n}{2}$次可以保证准确性。在实际使用中，一般取8次即可，大约$\frac{1}{2}^8\approx0.3%$的几率会遇到例外。

12. (P37) 1.3，高阶过程：以过程为参数，或者以过程为返回值的过程。

13. (P37) 1.3.1，求和记法：$\sum^b_{n=a}f(n)=f(a)+\cdots+f(b)$。

14. (P45-P46) 1.3.3，不动点：若$x$满足$f(x)=x$，则称$x$为$f(x)$的不动点。

    用途：求方程$x=f(x)$的解，如可利用不动点求平方根：$y=x^2\implies x=y/x$，也就是求$f(x)=y/x$的不动点。

15. (P51) 1.3.4，第一级过程(First-class procedure)：

    第一级过程有如下特点：

    • 可以用变量命名
    • 可以由过程作为结果返回
    • 可以提供给过程作为参数
    • 可以包含在数据结构中

    等等。这一要求给实现增加了难度。

    一般的第一级对象有：字面量，变量等。

16. (P51) Ex 1.41：分析过程(((double (double double)) inc) 5)。

    上述过程返回值为21。

    重点在于分析(double (double double))部分。首先分析内部的(double double)，得到(double (double f))，也就是$4$次调用f。接下来我们对这个过程取别名，例如(define (g f) ((double double) f))，那么上述过程可以重写为(double g)，这里展开即得到(g (g f))，那么内部首先是调用$4$次f，外部再对这个新的函数调用$4$次，总计调用了$4\times4=16$次。

    上述过程即$5+16=21$。