计算机科学概论

这是《计算机科学概论（原书第13版）》的学习笔记，本文主要包括以下内容：

第一章 数据存储

• 逻辑门
• C 中的字符常量
• 二进制中的补码与余码
  • 补码记数法
  • 余码记数法

第十二章 计算理论

• 可计算性
• Bare Bones 语言
  • 复制操作
  • 交换操作
  • 分支结构
• 停机问题
• RSA

第一章 数据存储

逻辑门

这八个基础的逻辑门的符号需要记清楚。记忆的技巧也很简单，N 就是右侧加一个小圆圈，X 就是左侧加一条线。“与”和“或”的符号我总是弄混淆，后来问了一下 skyhappy，他跟我讲：

我是这么记的，看输出端 如果是与运算，就得有容乃大，所以开口得胖一点 或运算就不需要了，所以窄一点就好了

我觉得很有道理。

于是联想到了一个经典Stack Overflow 笑话——在 C# 语言中如何实现“同或 (XNOR) ”操作

C 中的字符常量

在大一下学期学习《计算机程序设计基础》这门课的时候，老师上课说有同学将一个字符串定义成 char str = '123';，虽然 他通过了编译，但这是错误的。

关注的重点在于 他通过了编译，于是我上网查找了一下“单引号内如果包含多个字符为什么会编译成功”。

在 C/C++ 中，一个 int 类型占用的空间是 32 bit，即 4 个 byte。一个 char 类型占用的空间是 8 bit，即 1 个 byte。所以 ' 内一共可以最多包含 4 个字符，它会被看做成一个 int 类型的常量。其实就是四个 char 并排组在一起就成为了一个 int。

例如，('1' << 8) + '2' 和 '12' 是一模一样的，均为 (int)12594。

如果 ' 内字符大于或等于 2 个，编译器会警告：

1warning: multi-character character constant [-Wmultichar]

如果大于或等于 5 个，编译器会警告：

1warning: character constant too long for its type

二进制中的补码与余码

补码记数法

在补码记数法中，一个 有符号整数 用一个 32 bit 二进制串来表示，其中最左侧被称为“最高位”，最右侧被称为“最低位”。最高位表示 $-2^{31}$，其余各位分别表示 $2^{30}, \cdots, 2^1, 2^0$。因此一个 32 bit 二进制串的表示范围为 $[-2^{31}, 2^{31}-1]$。

一个通过补码记数法记录的整数，通过“按位取反再加一”的方式可以得到自己的相反数。

余码记数法

在余码记数法中，“0”被定义为最高位为 1，其余位均为 0 的数。这个数在所有 32 bit 二进制串中恰好排在“差不多”中间的位置。比它大的数即为正数，比它小的数即为负数。

余码记数法和补码记数法的唯一区别是最高位的值相反。

第十二章 计算理论

可计算性

一个函数，如果依据输入，通过算法，可以确定输出值，则它被称为 可计算的。事实上，存在那么一些函数，它们过于复杂以致找不到定义明确的、有限步骤的过程来根据输入确定输出。这样的函数计算超出了任何算法系统的能力范围，它们是 不可计算的。

一个函数是否可计算是非常重要的。如果确定了一个问题（以及数学建模后对应的函数）是不可计算的，那么人们就可以不必花更多精力研究如何用计算机来解决它，而是求助于其他更有效的方法。

Bare Bones 语言

一个通用程序设计语言。

• 一种基本数据类型。

  所有的变量本质上都是二进制数。

• 三条赋值语句。

  clear name 表示把 name 清零。 incr name 表示使 name 自增 1。 decr name 表示使 name 自减 1。

• 一条控制结构语句。

  while name not 0: 在 name 不为 0 的时候，会一直做下方缩进的语句或语句序列（和 Python 类似）。

定理：Bare Bones 语言能够用来表达计算所有图灵可计算函数的算法。

复制操作、交换操作、分支结构等特性都可以使用 Bare Bones 语言实现。

复制操作

1while x not 0:
2  incr z
3while z not 0:
4  incr x
5  incr y

这样就通过辅助变量 z 完成了 y = x 的复制操作。我们将其简写为 copy x to y。

交换操作

既然能够完成复制操作，那么也一定能够完成交换操作。

分支结构

我们现在想实现类似

1if x:
2  // ... do sth1
3else:
4  // ... do sth2

的结构。

1copy x to z
2clear w
3incr w
4while z not 0:
5  // do sth1
6  clear z
7  decr w
8while w not 0:
9  // do sth 2

以上代码可以实现这样的 if-else 分支结构。

停机问题

如果程序中所有的变量都是用程序自身的编码表示（把字符全部转为二进制串）来进行初始化的，且这个程序在有限步骤后能够停止，则称这个 Bare Bones 程序是 自终止的。

停机问题指的是，是否存在一个算法，能够判断一个 Bare Bones 程序是否是自终止的。

答案是不存在。证明停机问题不可解，采取的方式是反证法。

假设有一个 Bare Bones 程序 A，它接受的输入是一段 Bare Bones 程序 test，产生的输出是 test 是否是自终止的：若是自终止的，则输出 1；若不是自终止的，则输出 0。

假设把 A 所得输出放入变量 x。考虑在 A 后添加

1// A...
2// x = output
3while x not 0:

我们称这个新的程序为 B。接下来我们要证明 B 既不是自终止的，也不是非自终止的，以此推导出矛盾。

• 若 B 是自终止的：

  将 B 作为自己的输入，则 x 为 1。此时进入 while 死循环，则 B 不是自终止的。矛盾。

• 若 B 是非自终止的：

  将 B 作为自己的输入，则 x 为 0。此时不进入 while 循环，则 B 是自终止的。矛盾。

所以，如果停机问题可解，也就是说，存在一个程序 A，使得它能判断一段 Bare Bones 程序是否是自终止的，那么我们就可以构造出一个矛盾的程序 B。因此停机问题不可解。

RSA

RSA 是一种经典的公钥加密系统，被广泛应用于加密信息传递。尤其是树洞上的信息加密。

RSA 密钥的生成与分发

$\lambda(n)$ 为 Carmichael function，是指最小的正整数 $m$，满足对于所有的与 $n$ 互质的 $a$，均有 $a^{m} \equiv 1 \pmod n$。

1. 选择两个大质数 $p, q$，记 $n = pq$。
2. 计算 $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$。
3. 选择一个 $e$ 使得 $e$ 与 $\lambda(n)$ 互质。
4. 计算 $d$ 满足 $d \equiv e^{-1} \pmod{\lambda(n)}$。

$n, e$ 作为公钥，$d$ 作为密钥。

RSA 的加密与解密

由于所有的运算都会对 $n$ 取模，所以一个很自然的要求是明文 $m$ 的长度小于 $n$。

• 加密：密文 $c \equiv m^e \pmod n$

• 解密：明文 $m \equiv m^{de} \equiv c^d \pmod n$

RSA 的正确性

只需要证明 $m \equiv m^{de} \pmod {pq}$ 即可，更简化地说，只需要证明 $m \equiv m^{de} \pmod p$ 即可，对 $q$ 同理。

由于 $de \equiv 1 \pmod {\lambda(pq)}$，而 $\lambda(pq) = (p - 1)(q - 1)$。所以不妨记 $de - 1 = h(p - 1) = k(q - 1)$。

1. 若 $m \equiv 0 \pmod p$，则 $m^{ed} \equiv 0 \equiv m \pmod p$。
2. 若 $m \not\equiv 0 \pmod p$，则由费马小定理 $m^{p-1} \equiv 1 \pmod p$。

$$m^{de} \equiv m^{1 + h(p - 1)} \equiv m \cdot (m^{p-1})^h \equiv m \cdot 1^{h} \equiv m \pmod p$$

因此命题得证。