📚 Year 13 AQA Computer Science: Formula & Theorem Quick Reference Handbook | AQA Year 13 计算机科学公式定理速查手册
This concise handbook collates the essential formulas, theorems, and key relationships prescribed in the AQA A‑Level Computer Science (7517) specification for Year 13. It is intended as a rapid revision companion, helping students locate and apply critical mathematical and logical constructs without searching through the full syllabus. Each entry is presented in a paired English‑Chinese format to reinforce understanding and accuracy.
这本简明手册整理了 AQA A‑Level 计算机科学（7517）Year 13 考试大纲中的核心公式、定理和关键关系。它旨在作为快速复习伴侣，帮助学生定位和应用重要的数学及逻辑构思，无需翻阅完整的课程大纲。每个条目均以中英配对形式呈现，以加深理解和准确性。
1. Boolean Algebra Laws & De Morgan’s Theorem | 布尔代数定律与德摩根定理
Boolean algebra operates on binary variables with logical operations AND (·), OR (+), and NOT (‘). The following laws are fundamental for simplifying logic circuits.
布尔代数对二进制变量执行逻辑与（·）、或（+）、非（’）运算。下列定律是化简逻辑电路的基础。
Identity Law: A + 0 = A and A · 1 = A.
恒等律：A + 0 = A，A · 1 = A。
Null Law: A + 1 = 1 and A · 0 = 0.
零一律：A + 1 = 1，A · 0 = 0。
Idempotent Law: A + A = A and A · A = A.
幂等律：A + A = A，A · A = A。
Complement Law: A + A’ = 1 and A · A’ = 0.
互补律：A + A’ = 1，A · A’ = 0。
Involution Law: (A’)’ = A.
双重否定律：(A’)’ = A。
Commutative Law: A + B = B + A and A · B = B · A.
交换律：A + B = B + A，A · B = B · A。
Associative Law: A + (B + C) = (A + B) + C and A · (B · C) = (A · B) · C.
结合律：A + (B + C) = (A + B) + C，A · (B · C) = (A · B) · C。
Distributive Law: A · (B + C) = A·B + A·C and A + B·C = (A+B) · (A+C).
分配律：A · (B + C) = A·B + A·C，A + B·C = (A+B) · (A+C)。
Absorption Law: A + A·B = A and A · (A+B) = A.
吸收律：A + A·B = A，A · (A+B) = A。
De Morgan’s Theorem: (A · B)’ = A’ + B’ and (A + B)’ = A’ · B’.
德摩根定理：(A · B)’ = A’ + B’ 以及 (A + B)’ = A’ · B’。
2. Karnaugh Maps & Minimisation | 卡诺图与最小化
A Karnaugh map (K‑map) provides a visual method for minimising Boolean expressions up to four variables. Each cell represents a minterm; adjacent cells differ by one variable.
卡诺图（K‑map）为最多四个变量的布尔表达式极小化提供了可视化方法。每个单元格代表一个最小项；相邻单元格之间只有一个变量不同。
Grouping rule: enclose exactly 2ⁿ adjacent 1s (or don’t‑cares) using the largest possible groups. Overlapping is allowed, and groups may wrap around map edges.
圈组规则：圈出恰好 2ⁿ 个相邻的 1（或无关项），并尽可能使用最大的圈组。允许重叠，且圈组可以环绕地图边界。
A prime implicant is a group that cannot be expanded further. The minimal sum‑of‑products expression uses the fewest prime implicants to cover all 1s.
质蕴含项是指无法再进一步扩大的圈组。最简积之和表达式使用最少数量的质蕴含项覆盖所有的 1。
For don’t‑care conditions (marked ‘X’), they may be included as 1s if they enlarge a group, otherwise treated as 0s.
对于无关项（标记为 ‘X’），如果将其视为 1 可以扩大圈组，则可包含在内；否则视为 0。
3. Data Representation: Two’s Complement & Floating Point | 数据表示：二进制补码与浮点数
Two’s complement is the standard method for representing signed integers in binary. For an n‑bit pattern aₙ₋₁ aₙ₋₂ … a₀, the decimal value is:
二进制补码是表示有符号整数的标准方法。对于 n 位二进制数 aₙ₋₁ aₙ₋₂ … a₀，其十进制值为：
Value = -aₙ₋₁ × 2^(n-1) + Σ (aᵢ × 2ⁱ) for i=0 to n-2
To negate a number: invert all bits and add 1 to the least significant bit, i.e., -X = (~X) + 1.
求负数的方法：将所有位取反并在最低位加 1，即 -X = (~X) + 1。
IEEE 754 single‑precision floating‑point uses 1 sign bit (S), 8 exponent bits (E) with bias 127, and 23 mantissa bits (M) representing a normalised fraction. The value is:
IEEE 754 单精度浮点数使用 1 位符号 (S)、8 位阶码 (E)（偏置 127）和 23 位尾数 (M) 表示规格化小数。其值为：
Value = (-1)^S × (1.M)₂ × 2^(E-127)
Denormalised numbers occur when E = 0; then the leading 1 is omitted and the exponent is treated as -126.
当 E = 0 时出现非规格化数；此时省略前导 1，且指数视为 -126。
4. Tree & Graph Properties | 树与图的性质
A tree with n vertices has exactly n-1 edges. Adding any edge creates a cycle; removing any edge disconnects the graph.
具有 n 个顶点的树恰好有 n-1 条边。增加任意边会形成环；删除任意边会使图不连通。
In a full binary tree of height h (root at level 1), the maximum number of nodes is 2^h – 1, and the maximum number of leaves is 2^(h-1).
在一棵高度为 h（根为第 1 层）的满二叉树中，最大节点数为 2^h – 1，最大叶节点数为 2^(h-1)。
The Handshaking Lemma for an undirected graph states that the sum of the degrees of all vertices equals twice the number of edges:
对于无向图，握手引理指出所有顶点的度数之和等于边数的两倍：
Σ deg(v) = 2|E|
For a directed graph, the sum of in‑degrees equals the sum of out‑degrees, and both equal the total number of edges.
对于有向图，入度之和等于出度之和，且两者均等于边的总数。
5. Algorithmic Complexity & Big-O | 算法复杂度与大O记号
Big‑O notation describes the upper bound of an algorithm’s time or space requirements as the input size n grows. f(n) = O(g(n)) if there exist constants c and n₀ such that f(n) ≤ c·g(n) for all n > n₀.
大O记号描述了随着输入规模 n 的增长，算法时间或空间需求的上界。若存在常数 c 和 n₀，使得对所有 n > n₀ 有 f(n) ≤ c·g(n)，则 f(n) = O(g(n))。
Common complexity classes and typical examples:
常见复杂度类别及典型示例：
| Complexity | Example |
|---|---|
| O(1) | Array index access |
| O(log n) | Binary search |
| O(n) | Linear search |
| O(n log n) | Merge sort, quicksort (average) |
| O(n²) | Bubble sort, insertion sort |
| O(2ⁿ) | Recursive Fibonacci |
Table: Complexity classes and representative algorithms | 表：复杂度类别与代表性算法
Constant factors and lower‑order terms are ignored in Big‑O. The complexity of a sequential composition adds (sum rule), while nested loops multiply complexities (product rule).
大O记号中忽略常数因子和低阶项。顺序组合的复杂度相加（和法则），而嵌套循环则将复杂度相乘（积法则）。
6. Shortest Path Algorithms: Dijkstra & A* | 最短路径算法：Dijkstra 与 A*
Dijkstra’s algorithm iteratively updates the shortest distance to each vertex from the source. The relaxation step:
Dijkstra 算法迭代更新从源点到每个顶点的最短距离。松弛步骤为：
if d[u] + w(u, v) < d[v] then d[v] = d[u] + w(u, v)
It uses a priority queue and works for graphs with non‑negative edge weights.
它使用优先队列，适用于边权非负的图。
A* search extends Dijkstra by employing an evaluation function f(n) = g(n) + h(n), where g(n) is the cost from the start to node n, and h(n) is a heuristic estimate of the cost from n to the goal.
A* 搜索通过使用估价函数 f(n) = g(n) + h(n) 来扩展 Dijkstra，其中 g(n) 为从起点到节点 n 的实际代价，h(n) 为从 n 到目标代价的启发式估计。
For optimality, the heuristic h(n) must be admissible – it must never overestimate the true cost. A consistent (monotonic) heuristic further guarantees that each node is expanded at most once.
为保证最优性，启发式 h(n) 必须是可接受的——绝不能高估真实代价。一致的（单调的）启发式还能保证每个节点最多被扩展一次。
7. Relational Databases & Normalisation | 关系数据库与规范化
Normalisation reduces data redundancy and prevents update anomalies. It is based on the concept of functional dependency: attribute Y is functionally dependent on X (written X → Y) if each value of X determines exactly one value of Y.
规范化减少数据冗余并防止更新异常。它建立在函数依赖的概念之上：若属性 X 的每个值唯一确定属性 Y 的一个值，则称 Y 函数依赖于 X（记作 X → Y）。
First Normal Form (1NF): All attributes must contain atomic (indivisible) values; there must be no repeating groups.
第一范式（1NF）：所有属性必须包含原子（不可再分）的值；不得出现重复组。
Second Normal Form (2NF): 1NF plus every non‑key attribute is fully functionally dependent on the whole candidate key (no partial dependencies).
第二范式（2NF）：满足 1NF 且每个非主属性完全函数依赖于整个候选键（无部分依赖）。
Third Normal Form (3NF): 2NF plus no non‑key attribute is transitively dependent on a candidate key (no non‑key attribute determines another non‑key attribute).
第三范式（3NF）：满足 2NF 且不存在非主属性传递依赖于候选键（无一个非主属性决定另一个非主属性）。
Armstrong’s axioms capture inference rules for functional dependencies: reflexivity (if Y ⊆ X then X → Y), augmentation (if X → Y then XZ → YZ), and transitivity (if X → Y and Y → Z then X → Z).
阿姆斯特朗公理刻画了函数依赖的推导规则：自反律（若 Y ⊆ X 则 X → Y）、增广律（若 X → Y 则 XZ → YZ）和传递律（若 X → Y 且 Y → Z 则 X → Z）。
8. Error Detection & Correction | 错误检测与纠正
A parity bit is added to a data unit to make the total number of 1s even (even parity) or odd (odd parity). It can detect single‑bit errors but cannot correct them.
奇偶校验位被添加到数据单元中，使 1 的总数为偶数（偶校验）或奇数（奇校验）。它能检测一位错误，但无法纠正。
Hamming code uses multiple parity bits to locate and correct single‑bit errors. For m data bits and r check bits, the relation is: 2^r ≥ m + r + 1.
汉明码使用多个校验位来定位和纠正单个位错误。对于 m 个数据位和 r 个校验位，满足关系：2^r ≥ m + r + 1。
Cyclic Redundancy Check (CRC) treats the bit string as a polynomial and computes a remainder by dividing with a generator polynomial using modulo‑2 division. The remainder is appended as the checksum. The process catches burst errors and ensures high detection reliability.
循环冗余校验（CRC）将位串视为多项式，通过模二除法除以生成多项式得到余数。该余数作为校验和附加。此过程能捕获突发错误并提供高检测可靠性。
9. Processor Performance Formulas | 处理器性能公式
The execution time of a program can be expressed as the product of instruction count, cycles per instruction, and clock cycle time:
程序的执行时间可表示为指令数、每指令周期数和时钟周期时间的乘积：
CPU Time = Instruction Count × CPI × T_clock
Alternatively, using clock rate f = 1/T_clock, execution time = (Instruction Count × CPI) / f.
另外，使用时钟频率 f = 1/T_clock，则执行时间 = (指令数 × CPI) / f。
MIPS (Millions of Instructions Per Second) = Instruction Count / (Execution Time × 10⁶). This metric alone can be misleading because it ignores CPI and the instruction set.
MIPS（每秒百万指令数）= 指令数 / (执行时间 × 10⁶)。仅凭该指标可能产生误导，因为它忽略了 CPI 和指令集。
For an ideal pipelined processor with k stages, the maximum speedup over a non‑pipelined machine is approximately k, assuming balanced stages and no hazards.
对于具有 k 个阶段的理想流水线处理器，与非流水线机器相比的最大加速比约为 k，前提是各阶段平衡且无冲突。
10. Finite State Machines & Regular Expressions | 有限状态机与正则表达式
A deterministic
Published by TutorHao | Year 13 Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导