计算机科学导论：速成包

数制

位权

二进制 2^k，八进制 8^k，十六进制 16^k

转为十进制

Σ d_k·b^k

从十进制转换

除以基数，余数从下往上读

十六进制 ↔ 二进制

一位十六进制数 = 4 位二进制

二进制补码

按位取反后加 1

命题逻辑与证明

真值表的行数

2ⁿ

蕴涵

p → q ≡ ¬p ∨ q ≡ ¬q → ¬p

蕴涵的否定

¬(p → q) ≡ p ∧ ¬q

双条件

p ↔ q ≡ (p → q) ∧ (q → p)

德摩根律

¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q

分配律

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

量词的否定

¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)

肯定前件，否定后件

p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

方法

1. 数一数不同变量的个数：真值表有 2ⁿ 行，从全为 1 的一行开始。
2. 给每个子公式单独一列，由内向外逐列填写。
3. 按各联结词的规则计算：→ 只有在 1 → 0 时为 0，↔ 在两边相同时为 1。
4. 判断等价时，逐行比较最后一列；判断论证时，只看所有前提都为 1 的那些行。
5. 否定带量词的命题时，把 ¬ 移到内部，交换 ∀ 和 ∃，并否定内部的公式。

数字逻辑：门电路、卡诺图与触发器

基本逻辑门

A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B

布尔规则

X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X

德摩根律

(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′

卡诺图的顺序

00, 01, 11, 10 (Gray code)

由 2ᵏ 个格子组成的圈

消去 k 个变量

4 选 1 多路选择器

F = A′B′I₀ + A′BI₁ + AB′I₂ + ABI₃

触发器

D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q

计数器

n 位：2ⁿ 个状态； 模 N：满足 2ⁿ ≥ N 的最小 n； f_out = f_clk/N

行波计数器

f_max = 1/(n·t_pd)

环形计数器与约翰逊计数器

n 个和 2n 个状态

方法

1. 对于电路，从输入到输出一个门一个门地分析，并在每根线上写出值；或者写出它的表达式并填写真值表。
2. 化简时，把 1（以及标为 X 的无关项）填入行列按格雷码 00, 01, 11, 10 排列的卡诺图。
3. 用尽可能少而大的圈（由 1、2、4、8 或 16 个格子组成）覆盖所有 1，可以绕过边界；每个圈对应一个乘积项，由保持不变的变量构成。求 POS 形式时圈 0。
4. 对于触发器和计数器，在每个有效时钟边沿读取输入，写出每个边沿之后的状态，并记住 n 位计数器在 2ⁿ 个状态之后回绕。

数论与模运算

带余除法

a = q·n + r, 0 ≤ r < n

欧几里得

gcd(a, b) = gcd(b, a mod b)

最小公倍数

lcm(a, b) = a·b/gcd(a, b)

逆矩阵

a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1

线性同余方程

a·x ≡ b → x ≡ a⁻¹·b (mod n)

欧拉函数

φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹

费马

aᵖ⁻¹ ≡ 1 (mod p)

RSA

n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

方法

1. 先把每个数对 n 取模；余数在 0 到 n − 1 之间。
2. 求最大公约数时，用欧几里得算法反复做除法；最后一个非零余数就是最大公约数。
3. 求逆元时，运行扩展算法并保留 a 的系数；若为负数则加上 n。
4. 解 a·x ≡ b 时，两边乘以 a⁻¹；合并两个同余式时，写成 x = r₁ + m₁k。
5. 求幂时，把指数写成二进制并反复平方；在 RSA 中，d = e⁻¹ mod φ(n)，其中 φ(n) = (p − 1)(q − 1)。

图论

握手引理

Σ deg(v) = 2|E|

完全图

|E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n

正则图

|E| = n·k/2

树与森林

|E| = n − 1, |E| = n − c

树的叶子

L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3

欧拉

回路：所有顶点度数为偶数； 通路：恰有 2 个奇度顶点

K_n 中的哈密顿回路

(n − 1)!/2

迪杰斯特拉更新

d(v) = min(d(v), d(u) + w(u, v))

长度为 L 的途径

(Mᴸ)_ij

方法

1. 写出每个顶点的度数；所有度数之和等于边数的两倍。
2. 对于欧拉问题，先检查图是否连通，再数一数奇度顶点的个数。
3. 对于树，利用 n − 1 条边和握手引理。
4. 对于迪杰斯特拉算法，保留一张暂定距离表，每一轮确定未确定顶点中距离最小的那个。
5. 对于最小生成树，把边按权重排序，跳过每条会形成圈的边（克鲁斯卡尔算法），或者从一个起点出发扩展一棵树（普里姆算法）。

IPv4 子网划分

每个子网的主机数

2^{(32 − prefix)} − 2 (/31: 2, /32: 1)

块大小

256 − (mask octet)

网络地址

IP AND 掩码

广播地址

IP OR (NOT 掩码)：主机位全部置 1

借用 n 位得到的子网数

2ⁿ