📚 Cambridge A-Level Computer Science Formula & Theorem Quick Reference Handbook | 剑桥A-Level计算机科学公式定理速查手册
This quick reference handbook gathers the essential formulas, theorems, and key relationships required for the Year 12 Cambridge Computer Science syllabus. Use it to reinforce your understanding of data representation, Boolean algebra, processor performance, networking, algorithm complexity, and more. All symbols follow the standard notation used in examinations, with Unicode characters for readability.
本速查手册汇总了 Year 12 剑桥计算机科学课程所必需的核心公式、定理和关键关系。用它来巩固你对数据表示、布尔代数、处理器性能、网络、算法复杂度等内容的理解。所有符号均采用考试中使用的标准记法，并使用 Unicode 字符以提高可读性。
1. Number Systems & Data Representation | 数制与数据表示
Decimal value of a binary integer: dn-1×2n-1 + … + d1×21 + d0×20, where each dk is 0 or 1.
二进制整数转十进制：dn-1×2n-1 + … + d1×21 + d0×20，其中每个 dk 为 0 或 1。
For fractional binary, bits after the point have negative powers: b-1×2-1 + b-2×2-2 + … .
对于二进制小数，小数点后的位使用负指数：b-1×2-1 + b-2×2-2 + … 。
Hexadecimal to binary: replace each hex digit with its 4-bit binary equivalent; groups of 4 bits are separated for readability.
十六进制转二进制：将每个十六进制数字替换为其等价的 4 位二进制数；通常以 4 位一组分隔以增强可读性。
N10 = Σ dk × 2k (binary) | Hex A–F → 10–15
2. Binary Arithmetic & Integer Ranges | 二进制运算与整数范围
Two’s complement negation: invert all bits and add 1 to the least significant bit. Positive numbers remain unchanged.
二进制补码求负：将所有位取反，然后在最低位加 1。正数保持不变。
Range for n-bit two’s complement: –2n-1 to 2n-1 – 1. For example, 8 bits give –128 to +127.
n 位补码整数的范围：–2n-1 至 2n-1 – 1。例如，8 位表示范围是 –128 到 +127。
Overflow occurs when the result of an addition or subtraction exceeds the representable range; detected when carry into sign bit differs from carry out.
当加法或减法的结果超出可表示范围时发生溢出；当进入符号位的进位与输出进位不同时即可检测到溢出。
–x = NOT(x) + 1 | Range: [–2n-1, 2n-1–1]
3. Floating-Point Representation | 浮点数表示
IEEE 754 single precision format: 1 sign bit, 8 exponent bits (biased by 127), 23 mantissa bits with an implicit leading 1 (normalised).
IEEE 754 单精度格式：1 位符号，8 位阶码（偏置 127），23 位尾数，隐含前导 1（规格化形式）。
Value = (–1)s × 1.m × 2e–127, where s is sign, m is fractional mantissa, and e is stored exponent.
数值 = (–1)s × 1.m × 2e–127，其中 s 为符号，m 为尾数的小数部分，e 为存储的阶码。
Precision is about 7 decimal digits; special patterns represent zero, infinity, and NaN.
精度约为 7 位十进制有效数字；特殊模式用来表示零、无穷大和非数（NaN）。
V = (–1)s × (1 + m/223) × 2e–127
4. Logic Gates & Boolean Algebra Theorems | 逻辑门与布尔代数定理
Basic identities: A+0 = A, A·1 = A, A+A’ = 1, A·A’ = 0, A+A = A, A·A = A.
基本恒等式：A+0 = A, A·1 = A, A+A’ = 1, A·A’ = 0, A+A = A, A·A = A。
Commutative: A+B = B+A, A·B = B·A. Associative: (A+B)+C = A+(B+C). Distributive: A·(B+C) = A·B + A·C, A+(B·C) = (A+B)·(A+C).
交换律：A+B = B+A, A·B = B·A。结合律：(A+B)+C = A+(B+C)。分配律：A·(B+C) = A·B + A·C, A+(B·C) = (A+B)·(A+C)。
De Morgan’s theorems: (A+B)’ = A’·B’, (A·B)’ = A’+B’.
德摩根定理：(A+B)’ = A’·B’, (A·B)’ = A’+B’。
Absorption: A + A·B = A, A·(A+B) = A. Useful simplifications: A + A’·B = A+B.
吸收律：A + A·B = A, A·(A+B) = A。常用简化：A + A’·B = A+B。
De Morgan: (A+B)’ = A’·B’ | (A·B)’ = A’+B’
5. Karnaugh Maps & Simplification Rules | 卡诺图与化简规则
A K-map is a 2D table of minterms; adjacent cells differ by exactly one variable. Groups of 1, 2, 4, 8 … adjacent 1s form terms that are powers of two in size.
卡诺图是最小项的二维表格；相邻单元之间只有一个变量不同。将 1、2、4、8……个相邻的 1 圈为一组，每组大小必须是 2 的幂。
Groups must be rectangular and can wrap around edges. Each group eliminates the variables that change within it, giving a simplified product term.
圈组必须为矩形，可以跨越边界（环绕）。每组消去其中发生变化的变量，得到一个简化的乘积项。
The minimal SOP expression is obtained by covering all 1s with the fewest, largest possible groups. Don’t-care conditions (X) may be treated as 0 or 1 to help grouping.
最小的与或表达式是通过用最少、最大的圈覆盖所有 1 得到的。无关项（X）可视为 0 或 1 以帮助圈组。
Minimal SOP = Σ (essential prime implicants)
6. Processor Performance Equations | 处理器性能公式
CPU execution time for a program: T = IC × CPI × Tc, where IC = instruction count, CPI = average clock cycles per instruction, and Tc = clock cycle time.
程序的 CPU 执行时间：T = IC × CPI × Tc，其中 IC 为指令数量，CPI 为每条指令的平均时钟周期数，Tc 为时钟周期时间。
Clock rate f = 1 / Tc. Thus T = (IC × CPI) / f. Performance improves with higher f or lower CPI.
时钟频率 f = 1 / Tc。因此 T = (IC × CPI) / f。提高频率或降低 CPI 均可提升性能。
MIPS rate = IC / (T × 106). Be careful: MIPS depends on the instruction mix and does not directly compare machines with different ISAs.
MIPS 速率 = IC / (T × 106)。注意：MIPS 依赖于指令混合，无法直接比较不同指令集架构的机器。
T = (IC × CPI) / f | Speedup = Told / Tnew
7. Memory Hierarchy & Access Time | 存储层次与访问时间
Average memory access time: AMAT = Hit time + Miss rate × Miss penalty. This applies to cache and virtual memory.
平均存储器访问时间：AMAT = 命中时间 + 缺失率 × 缺失代价。该公式适用于高速缓存和虚拟存储器。
Hit time is the time to access the faster level (e.g., L1 cache). Miss rate is the fraction of accesses not found. Miss penalty is the additional time to fetch from the slower level.
命中时间指访问较快层次（如 L1 缓存）的时间。缺失率是未命中的访问比例。缺失代价是从较慢层次读取所需的额外时间。
Cache capacity C = number of blocks × block size. Effective access time decreases with higher hit rate.
缓存容量 C = 块数 × 块大小。命中率越高，有效访问时间越低。
AMAT = HitTime + MissRate × MissPenalty
8. Network Data Transmission Formulas | 网络数据传输公式
Transmission delay (serialisation delay): Ttrans = L / R, where L is packet length in bits and R is bandwidth in bps.
传输时延（串行化时延）：Ttrans = L / R，其中 L 为数据分组长度（比特），R 为带宽（bps）。
Propagation delay: Tprop = d / s, where d is physical distance and s is signal propagation speed (~2×10⁸ m/s in copper).
传播时延：Tprop = d / s，其中 d 为物理距离，s 为信号传播速度（铜缆中约 2×10⁸ m/s）。
Total nodal delay = Tproc + Tqueue + Ttrans + Tprop. Round-trip time RTT ≈ 2 × Tprop (ignoring other delays).
节点总时延 = 处理时延 + 排队时延 + 传输时延 + 传播时延。往返时间 RTT ≈ 2 × Tprop（忽略其他时延）。
Throughput = min(Rsender, Rpath) under ideal conditions; effective throughput is often lower due to protocol overhead.
吞吐量 = min(R发送方, R路径)（理想条件下）；由于协议开销，有效吞吐量通常更低。
Ttrans = L / R | Tprop = d / s
9. Error Detection & Correction Principles | 差错检测与纠正原理
Parity bit: an extra bit added so that the total number of 1s is even (even parity) or odd (odd parity). Detects single-bit errors only.
奇偶校验位：额外添加一个比特，使整个数据中 1 的个数为偶数（偶校验）或奇数（奇校验）。仅能检测单比特错误。
Checksum: sum of data words is appended; receiver verifies the sum. Simple but not fully reliable.
校验和：将数据字累加，把和附加在数据后；接收方验证累加和。简单但并非完全可靠。
Hamming distance: the number of bit positions in which two codewords differ. To detect d errors, minimum distance ≥ d+1; to correct t errors, distance ≥ 2t+1.
汉明距离：两个码字之间不同的比特位数。要检测 d 个错误，最小距离需 ≥ d+1；要纠正 t 个错误，距离需 ≥ 2t+1。
CRC uses polynomial division; it can detect burst errors efficiently and is widely used in networking.
循环冗余校验（CRC）使用多项式除法；能高效检测突发错误，广泛用于网络通信。
Min distance ≥ 2t+1 for correction | CRC-32 polynomial: x³²+…+1
10. Data Compression & Encryption Basics | 数据压缩与加密基础
Compression ratio = Suncompressed / Scompressed. A ratio >1 indicates size reduction; for example, ratio 4:1 means the compressed file is a quarter of the original.
压缩比 = 未压缩大小 / 压缩后大小。比值 >1 表示尺寸减小；例如 4:1 表示压缩文件只有原始大小的四分之一。
Entropy H = – Σ pi log2 pi, where pi is the probability of symbol i. H gives the theoretical limit for lossless compression.
熵 H = – Σ pi log2 pi，其中 pi 是符号 i 出现的概率。H 给出了无损压缩的理论极限。
RSA encryption: public key (e, n), private key (d, n). n = p × q (large primes). φ(n) = (p–1)(q–1). Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. Compute d as the modular inverse: e·d ≡ 1 (mod φ(n)).
RSA 加密：公钥 (e, n)，私钥 (d, n)。n = p × q（大素数）。φ(n) = (p–1)(q–1)。选择 e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。计算 d 为模反元素：e·d ≡ 1 (mod φ(n))。
Ciphertext c = me mod n, plaintext m = cd mod n. Security relies on the difficulty of factoring n.
密文 c = me mod n，明文 m = cd mod n。安全性依赖于对 n 进行因数分解的难度。
Comp Ratio = Uncompressed/Compressed | c = me mod n, m = cd mod n
11. Algorithmic Complexity & Big-O Notation | 算法复杂度与大O记号
Big-O definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. It describes an upper bound on growth rate.
大O定义：若存在正常数 c 和 n₀，使得对所有 n ≥ n₀ 均有 0 ≤ f(n) ≤ c·g(n)，则 f(n) = O(g(n))。它描述了增长速率的上界。
Common complexities: O(1) constant, O(log n) logarithmic (e.g., binary search), O(n) linear, O(n log n) linearithmic (efficient sorts), O(n²) quadratic, O(2ⁿ) exponential.
常见复杂度：O(1) 常数，O(log n) 对数（如二分查找），O(n) 线性，O(n log n) 线性对数（高效排序），O(n²) 平方，O(2ⁿ) 指数。
For sorting: Bubble and Insertion sort are O(n²) average; Merge sort and Heap sort are O(n log n). Space complexity also matters.
排序算法：冒泡排序和插入排序平均为 O(n²)；归并排序和堆排序为 O(n log n)。空间复杂度同样重要。
f(n) = O(g(n)) | O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
12. Finite State Machines & Regular Expressions | 有限状态机与正则表达式
A deterministic FSM (DFSM) is defined by a 5-tuple (Q, Σ, δ, q₀, F) where Q is a finite set of states, Σ is the input alphabet, δ: Q×Σ → Q is the transition function, q₀ is the start state, and F is the set of accept states.
确定性有限状态机（DFSM）由一个五元组 (Q, Σ, δ, q₀, F) 定义，其中 Q 是有限状态集，Σ 是输入字母表，δ: Q×Σ → Q 为转移函数，q₀ 为起始状态，F 为接受状态集。
A language is regular if it can be described by a regular expression or recognised by a finite state machine. Regular expressions use operators: concatenation, union (|), and Kleene star (*).
若一个语言可用正则表达式描述或被有限状态机识别，则该语言是正则的。正则表达式使用以下运算符：连接、并（|）和克林闭包（*）。
Example: a(b|c)* matches strings starting with a followed by any sequence of b and c, including the empty sequence.
示例：a(b|c)* 匹配以 a 开头后跟任意个 b 和 c（包括空串）的字符串。
DFSM: δ(q, a) = q’ | RE: a(b|c)*
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导