📚 Pre-U AQA Computer Science: Formula and Theorem Quick Reference Handbook | Pre-U AQA 计算机：公式定理速查手册
This quick reference handbook distils the essential formulas, theorems, and rule sets required for the AQA Pre-U Computer Science specification. Use it as a last-minute revision aid or as a systematic checklist to ensure you have memorised every critical expression before the examination. Each section presents key relationships in both English and Chinese, supplemented by tables and bullet lists for clarity.
这本速查手册提炼了AQA Pre-U计算机科学考试所需的基本公式、定理和规则集合。你可以将它作为考前最后复习的利器，也可以当作系统检查清单，确保自己已经记住了每一个关键的表达式。每个小节都以中英双语呈现核心关系，并配以表格和项目符号，让内容一目了然。
1. Number Systems & Data Representation | 数制与数据表示
Understanding number representation is fundamental. For an n-bit unsigned binary integer, the representable range is from 0 to 2n – 1. When using two’s complement for signed integers, the range becomes -2n-1 to 2n-1 – 1. Conversion between binary and hexadecimal relies on grouping 4 bits per hex digit.
理解数制表示是基础。对于n位无符号二进制整数，可表示的范围是从0到2n – 1。使用二进制补码表示有符号整数时，范围变为-2n-1到2n-1 – 1。二进制与十六进制之间的转换依赖于每4个比特位对应一个十六进制数字。
For floating-point representation, a number is expressed as mantissa x baseexponent. In a standardised binary floating-point format with a normalised mantissa M and exponent E, the decimal value is M x 2E, where the mantissa is typically a signed fraction. The precision and range are determined by the bit widths allocated.
对于浮点表示，一个数被表示为尾数 x 基数指数。在标准化的二进制浮点格式中，规范化尾数M和指数E对应的十进制值为M x 2E，其中尾数通常是一个带符号的小数。精度和范围取决于分配的位宽。
| Representation | Formula / Range |
|---|---|
| Unsigned n-bit | 0 to 2n – 1 |
| Signed two’s complement n-bit | -2n-1 to 2n-1 – 1 |
| Binary to Hex | Group 4 bits from right, 10102 = A16 |
| Floating-point value | (-1)sign x (1.mantissa) x 2exponent – bias |
中文：数制与表示速查：无符号整数范围 0 到 2n-1；补码范围 -2n-1 到 2n-1-1；IEEE风格浮点数值 = (-1)符号位 x (1.尾数) x 2指数-偏置。
2. Boolean Algebra Laws & Logic Simplification | 布尔代数定律与逻辑简化
Boolean algebra is the backbone of digital circuit design. The following laws enable expression simplification. Note that we use ‘+’ for OR, ‘·’ for AND (often omitted), and ‘ (prime) for NOT. Every law has a dual obtained by swapping + and ·, and swapping 0 and 1.
布尔代数是数字电路设计的基础。以下定律可用于简化表达式。注意，我们用’+’表示或，’·’表示与（常常省略），用’表示非。每条定律都有一个对偶形式，可通过交换+和·、交换0和1得到。
- Identity: A + 0 = A, A · 1 = A / 同一律：A + 0 = A，A · 1 = A
- Complement: A + A’ = 1, A · A’ = 0 / 互补律：A + A’ = 1，A · A’ = 0
- Idempotent: A + A = A, A · A = A / 幂等律：A + A = A，A · A = A
- Domination: A + 1 = 1, A · 0 = 0 / 支配律：A + 1 = 1，A · 0 = 0
- Double Negation: (A’)’ = A / 双重否定律：(A’)’ = A
- Commutative: A + B = B + A, A · B = B · A / 交换律：A + B = B + A，A · B = B · A
- Associative: A + (B + C) = (A + B) + C, A · (B · C) = (A · B) · C / 结合律：略
- Distributive: A · (B + C) = A · B + A · C, A + (B · C) = (A + B) · (A + C) / 分配律：与·对+分配，+对·分配
- Absorption: A + A · B = A, A · (A + B) = A / 吸收律：A + A·B = A，A·(A+B) = A
- De Morgan’s Theorem: (A · B)’ = A’ + B’, (A + B)’ = A’ · B’ / 德摩根定理：(A·B)’ = A’ + B’，(A+B)’ = A’·B’
The consensus theorem is also valuable: A·B + A’·C + B·C = A·B + A’·C. Its dual: (A+B)·(A’+C)·(B+C) = (A+B)·(A’+C).
一致定理同样有用：A·B + A’·C + B·C = A·B + A’·C。其对偶形式：(A+B)·(A’+C)·(B+C) = (A+B)·(A’+C)。
3. Karnaugh Maps & Minimisation | 卡诺图与最小化
A Karnaugh map (K-map) provides a visual method for minimising Boolean expressions. An n-variable function yields a grid of 2n cells. Adjacent cells differ by exactly one variable. The aim is to cover all 1s (for Sum of Products, SOP) with the fewest largest possible groups of size 2k. The simplified expression is obtained by identifying variables that remain constant within each group.
卡诺图为布尔表达式最小化提供了一种可视化方法。一个n变量函数对应一个含有2n个单元的网格。相邻单元之间仅有一个变量不同。目标是使用尽可能少、尽可能大的2k大小的圈覆盖所有的1（针对与或式SOP）。简化后的表达式是通过找出每个圈中保持不变的变量得到的。
For Product of Sums (POS) minimisation, group the 0s and write the expression as a product of maxterms. The relationship between SOP and POS is: POS = complement of SOP of the complement function.
对于或与式（POS）最小化，圈0并以最大项之积的形式写出表达式。SOP与POS的关系为：POS等于原函数之补的SOP再取补。
f(A,B,C) = Σ m(0,1,2,5,6) → f = A’B’ + B C’ + A C’ (SOP example)
中文：卡诺图规则：圈1得SOP，圈0得POS；每个圈必须为矩形，大小为1,2,4,8…；圈可以重叠、环绕边界。最终表达式为各圈对应乘积项之和。
4. Algorithmic Complexity & Big O Notation | 算法复杂度与大O表示法
Big O notation describes the upper bound of an algorithm’s time or space complexity as the input size n grows. Common orders, from best to worst, are: O(1) – constant, O(log n) – logarithmic, O(n) – linear, O(n log n) – linearithmic, O(n²) – quadratic, O(2ⁿ) – exponential.
大O表示法描述了随着输入规模n的增长，算法的时间或空间复杂度的上界。常见的增长阶（从优到劣）有：O(1) 常数级、O(log n) 对数级、O(n) 线性级、O(n log n) 线性对数级、O(n²) 平方级、O(2ⁿ) 指数级。
The Master Theorem gives asymptotics for recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1. Let d = log_b a.
主定理用于求解形如T(n) = aT(n/b) + f(n)的递推式，其中a ≥ 1, b > 1。令d = log_b a。
- If f(n) = O(nd-ε) for ε > 0, then T(n) = Θ(nd). / 若f(n) = O(nd-ε)，则T(n) = Θ(nd)。
- If f(n) = Θ(nd), then T(n) = Θ(nd log n). / 若f(n) = Θ(nd)，则T(n) = Θ(nd log n)。
- If f(n) = Ω(nd+ε) and a f(n/b) ≤ c f(n) for c < 1, then T(n) = Θ(f(n)). / 若f(n) = Ω(nd+ε)且满足正则条件，则T(n) = Θ(f(n))。
Example: T(n) = 2T(n/2) + n → a=2, b=2, d=1 → case 2, T(n) = Θ(n log n).
示例：T(n) = 2T(n/2) + n，a=2, b=2, d=1 → 情况2，T(n) = Θ(n log n)。
5. Sorting & Searching Algorithms | 排序与搜索算法
AQA Pre-U expects familiarity with classic sorting and searching algorithms along with their worst-case and average time complexities. The table below summarises the most frequently examined ones.
AQA Pre-U要求熟悉经典排序和搜索算法及其最坏、平均时间复杂度。下表总结了最常考的算法。
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
Binary search works on a sorted array by repeatedly dividing the search interval in half. Its recurrence is T(n) = T(n/2) + O(1), giving O(log n).
二分搜索通过在有序数组中反复将搜索区间减半来工作。其递推式为T(n) = T(n/2) + O(1)，得到O(log n)。
Merge sort recurrence: T(n) = 2T(n/2) + O(n), yielding linearithmic time. Quick sort’s worst case occurs with unbalanced partitions, degrading to O(n²).
归并排序递推式：T(n) = 2T(n/2) + O(n)，产生线性对数时间。快速排序的最坏情况出现在划分不均衡时，退化为O(n²)。
6. Networking Formulas & Performance | 网络公式与性能
Network performance metrics are quantitative. Transmission delay (also serialisation delay) is the time to push all bits onto the link: Ttrans = Packet size (bits) / Bandwidth (bps). Propagation delay depends on distance and signal speed: Tprop = Distance / Propagation speed (approx. 2×10⁸ m/s in copper).
网络性能指标是可量化的。传输时延（也称串行化时延）是将所有比特推上链路的时间：Ttrans = 数据包大小(比特) / 带宽(bps)。传播时延取决于距离和信号速度：Tprop = 距离 / 传播速度（铜缆中约2×10⁸ m/s）。
Round Trip Time (RTT) is the time for a signal to go to the destination and back. Throughput is often limited by the smaller of the bottleneck link rate or the sliding window size / RTT. With a sliding window protocol, the maximum throughput in ideal conditions is: Throughput ≤ Window size / RTT.
往返时间(RTT)是信号到达目的地并返回的时间。吞吐量通常受限于瓶颈链路速率与滑动窗口大小/RTT两者中的较小值。在理想的滑动窗口协议中，最大吞吐量为：吞吐量 ≤ 窗口大小 / RTT。
For subnetting: the number of subnets created by borrowing n bits is 2n; the number of usable host addresses per subnet is 2h – 2, where h is the remaining host bits.
子网划分：借用n位创建的子网数为2n；每子网可用主机地址数为2h – 2，其中h为剩余的主机位数。
7. Data Compression & Entropy | 数据压缩与熵
Lossless compression reduces the number of bits needed to represent data without losing information. The compression ratio is defined as: Compression Ratio = Size of original data / Size of compressed data. A value > 1 indicates compression. Entropy H measures the theoretical minimum average bits per symbol: H = – Σ pi log2 pi, where pi is the probability of symbol i.
无损压缩在减少表示数据所需比特数的同时不丢失信息。压缩比定义为：压缩比 = 原始数据大小 / 压缩后数据大小。大于1的值表示压缩有效。熵 H衡量每个符号的理论最小平均比特数：H = – Σ pi log2 pi，其中pi是符号i出现的概率。
Huffman coding constructs an optimal prefix code. The average code length L satisfies H ≤ L < H+1. Run-length encoding (RLE) is effective for data with long runs; the required bits for a run of length k may follow a predefined threshold.
哈夫曼编码构造最优前缀码。平均码长L满足 H ≤ L < H+1。游程编码（RLE）对于含有长游程的数据有效；长度为k的游程所需比特可能遵循预设的阈值。
For example, given symbols A(0.5), B(0.25), C(0.25), entropy H = -(0.5 log₂ 0.5 + 2×0.25 log₂ 0.25) = 1.5 bits/symbol. A Huffman tree can assign codes A=0, B=10, C=11, giving average length 1.5 bits.
例如，给定符号A(0.5), B(0.25), C(0.25)，熵 H = 1.5 比特/符号。哈夫曼树可分配编码A=0, B=10, C=11，平均长度1.5比特。
8. Error Detection & Correction | 错误检测与纠正
The Hamming distance between two code words is the number of bit positions where they differ. The minimum Hamming distance dmin of a code determines its error-handling capability: to detect up to s errors, dmin ≥ s+1; to correct up to t errors, dmin ≥ 2t+1. For simultaneous detection of s errors and correction of t errors (s ≥ t), dmin ≥ s+t+1.
两个码字之间的汉明距离是它们比特不同的位置数。码的最小汉明距离dmin决定了它的错误处理能力：检测最多s个错误需要 dmin ≥ s+1；纠正最多t个错误需要 dmin ≥ 2t+1。在同时检测s个错误并纠正t个错误时（s ≥ t），需要 dmin ≥ s+t+1。
A parity bit can detect a single-bit error (dmin=2), but cannot correct it. CRC (Cyclic Redundancy Check) uses polynomial division modulo 2. Given a generator polynomial G(x) of degree r, the CRC remainder is the remainder of xrM(x) divided by G(x). The transmitted frame is appended with the CRC bits; the receiver divides the whole frame by G(x) and checks for a zero remainder.
奇偶校验位可检测单个比特错误（dmin=2），但不能纠正。CRC（循环冗余校验）使用模2多项式除法。给定一个度为r的生成多项式G(x)，CRC余数是xrM(x)除以G(x)的余数。发送帧附加CRC比特；接收端将整个帧除以G(x)并检查余数是否为零。
Hamming codes are single-error-correcting codes. For data bits k, the number of parity bits r must satisfy 2r ≥ k + r + 1. Position the parity bits at powers of two; each parity bit checks specific data bits such that the overall syndrome indicates the erroneous bit.
汉明码是单错纠正码。对于k个数据位，所需的校验位数r必须满足2r ≥ k + r + 1。校验位放置在2的幂次位置；每个校验位负责检查特定的数据位，使得综合出的症状码能够指示出错比特的位置。
9. Encryption & Cryptography |
Published by TutorHao | Pre-U Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导