AQA Year 12 Computer Science: Formula & Theorem Quick Reference | AQA Year 12 计算机：公式定理速查手册

📚 AQA Year 12 Computer Science: Formula & Theorem Quick Reference | AQA Year 12 计算机：公式定理速查手册

This quick reference collects the essential formulas and theorems from the AQA Year 12 Computer Science specification. It covers binary arithmetic, Boolean algebra, algorithm complexity, network latency, error detection and finite state machines. Each section is presented in a compact, exam‑friendly format to help you revise key concepts and calculations efficiently.

本速查手册汇集了 AQA Year 12 计算机科学课程中的核心公式和定理，涵盖二进制运算、布尔代数、算法复杂度、网络延迟、错误检测和有限状态机等内容。每个小节都以简洁、适合考试复习的形式呈现，帮助你高效掌握关键概念和计算方法。

---

1. Number Base Conversion | 数制转换

To convert a positive decimal integer to binary, repeatedly divide by 2 and record the remainders. The binary number is the sequence of remainders read from bottom to top.

将十进制正整数转换为二进制时，反复除以 2 并记录余数。从下往上读取余数序列，即为对应的二进制数。

For fractional decimal to binary, multiply the fraction by 2 repeatedly; the integer part (0 or 1) of each product forms the binary fraction bits in order.

将十进制小数转换为二进制时，反复乘以 2，每次乘积的整数部分（0 或 1）依次构成二进制小数位。

Hexadecimal and binary conversion: each hex digit corresponds to a 4‑bit nibble. Group binary digits in sets of four from the right, then replace each group with its hex equivalent.

十六进制与二进制的转换：每位十六进制数字对应一个 4 位的半字节。从右边开始将二进制数字每四位分组，再将每组替换为相应的十六进制字符。

---

2. Two's Complement Representation | 二进制补码表示

For an n‑bit two's complement signed integer, the range of representable values is −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.

对于 n 位二进制补码有符号整数，可表示的数值范围为 −2ⁿ⁻¹ 到 2ⁿ⁻¹ − 1。

To negate a binary number in two's complement, invert all bits (one's complement) and add 1 to the least significant bit. Overflow occurs if the carry into the sign bit is different from the carry out of the sign bit.

对补码表示的数取反（求负数）时，先对所有位取反（反码），然后在最低位加 1。若进入符号位的进位与出符号位的进位不同，则发生溢出。

Two's complement addition follows ordinary binary addition rules, discarding any carry beyond the most significant bit. The result is correct if no overflow has occurred.

补码加法遵循普通二进制加法规则，丢弃超出最高位的进位。若无溢出，结果就是正确的。

---

3. Floating‑Point Essentials | 浮点数基本公式

In simplified IEEE 754 single precision, a floating‑point number is represented as (−1)^s × 1.m × 2^e−127, where s is the sign bit, e is the 8‑bit biased exponent, and m is the 23‑bit mantissa (fraction).

在简化的 IEEE 754 单精度格式中，一个浮点数表示为 (−1)ˢ × 1.m × 2ᵉ⁻¹²⁷，其中 s 是符号位，e 是 8 位偏置指数，m 是 23 位尾数（小数部分）。

The exponent is stored with a bias of 127 (or 1023 for double precision). To obtain the true exponent, subtract the bias from the stored exponent value. Normalised numbers have an implied leading 1 before the mantissa.

指数以偏置 127（双精度为 1023）存储。真实指数等于存储的指数值减去偏置。规范化数的尾数前隐含一个前导 1。

When adding or subtracting floating‑point numbers, first align the exponents by shifting the mantissa of the smaller number, then perform integer addition on the mantissas, and finally renormalise the result.

浮点数加减时，首先通过移动较小数的尾数使指数对齐，然后对尾数进行整数加减，最后重新规范化结果。

---

4. Boolean Algebra Theorems | 布尔代数定理

A · B = B · A. Associative laws: (A + B) + C = A + (B + C) and (A · B) · C = A · (B · C).

交换律：A + B = B + A，A · B = B · A。结合律：(A + B) + C = A + (B + C)，(A · B) · C = A · (B · C)。

Distributive laws: 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)。

Identity and complement: A + 0 = A, A · 1 = A, A + Ā = 1, A · Ā = 0. Double negation: A̿ = A.

恒等与互补：A + 0 = A，A · 1 = A，A + Ā = 1，A · Ā = 0。双重否定：A̿ = A。

Absorption laws: A + A · B = A and A · (A + B) = A. Also A + Ā · B = A + B.

吸收律：A + A · B = A，A · (A + B) = A。此外 A + Ā · B = A + B。

De Morgan’s laws: ¬(A · B) = ¬A + ¬B and ¬(A + B) = ¬A · ¬B. These are fundamental for simplifying digital circuits.

德摩根定律：¬(A · B) = ¬A + ¬B，¬(A + B) = ¬A · ¬B。这是简化数字电路的基础。

---

5. Karnaugh Map Simplification | 卡诺图化简

A Karnaugh map (K‑ two variables, it is a 2×2 grid; for three variables a 2×4; for four variables a 4×4 grid.

卡诺图 (K‑map) 是一种用于最小化布尔表达式的可视化工具。二变量为 2×2 网格；三变量为 2×4；四变量为 4×4 网格。

Cells are arranged such that adjacent cells differ in only one variable (Gray code ordering). Groups of 1s must be rectangular and contain 2^k cells (1, 2, 4, 8, ...). Each group is represented by a product term where variables that change within the group are eliminated.

单元格的排列使得相邻单元格仅在一个变量上不同（格雷码顺序）。圈出的 1 必须为矩形，且包含 2ᵏ 个单元格 (1, 2, 4, 8, ...)。每个圈对应于一个乘积项，在圈内发生变化的变量将被消去。

The simplified SOP (Sum of Products) expression is the OR of the product terms for all essential prime implicants that cover every 1 in the map.

简化的与或式 (SOP) 是覆盖了图中所有 1 的各个质蕴含项（必须项）的乘积项相或。

---

6. Logic Gate Truth Tables & Expressions | 逻辑门真值表与表达式

Gate / 门	Symbol / 符号	Boolean Expression / 布尔表达式
AND	· , ∧	Q = A · B
OR	+ , ∨	Q = A + B
NOT	¯ , ¬	Q = ¬A
NAND	↑	Q = ¬(A · B)
NOR	↓	Q = ¬(A + B)
XOR	⊕	Q = A ⊕ B = A·¬B + ¬A·B

NAND and NOR gates are called universal gates because any Boolean function can be implemented using only NAND gates or only NOR gates.

与非门和或非门被称为通用门，因为仅使用与非门或仅使用或非门就可以实现任何布尔函数。

XOR gate output is 1 when an odd number of inputs are 1. Its complement is XNOR, output 1 when an even number of inputs are 1.

异或门在输入中有奇数个 1 时输出为 1。其互补门为同或门 (XNOR)，当输入中有偶数个 1 时输出 1。

---

广告 / Sponsored

7. Algorithm Complexity & Big O Notation | 算法复杂度与大 O 记法

Big O notation describes the worst‑case time complexity of an algorithm as the input size n grows. Constant factors and lower‑order terms are ignored.

大 O 记法描述了算法在输入规模 n 增长时的最坏情况时间复杂度。常数因子和低阶项均被忽略。

O(1) – constant time, independent of n (e.g. array access). O(log n) – logarithmic time (e.g. binary search). O(n) – linear time (e.g. linear search). O(n log n) – linearithmic time (e.g. merge sort). O(n²) – quadratic time (e.g. bubble sort, insertion sort).

O(1) – 常数时间，与 n 无关（如数组访问）。O(log n) – 对数时间（如二分搜索）。O(n) – 线性时间（如线性搜索）。O(n log n) – 线性对数时间（如归并排序）。O(n²) – 平方时间（如冒泡排序、插入排序）。

Space complexity follows similar notation and indicates how much extra memory an algorithm requires relative to the input size.

空间复杂度使用类似的记号，表示算法相对于输入大小需要的额外内存量。

---

8. Searching Algorithm Comparisons | 搜索算法比较

Linear search checks each element sequentially. Worst‑case comparisons = n, average ≈ n/2. Works on unsorted lists.

线性搜索逐个检查元素。最坏情况比较次数 = n，平均 ≈ n/2。适用于未排序列表。

uires a sorted array. It repeatedly divides the search interval in half. Max comparisons = ⌈log₂(n+1)⌉. Time complexity O(log n).

二分搜索要求数组已排序。它反复将搜索区间折半。最大比较次数 = ⌈log₂(n+1)⌉。时间复杂度 O(log n)。

For small n the overhead of binary search may make linear search faster, but for large n the logarithmic growth of binary search makes it far superior.

对于较小的 n，二分搜索的额外开销可能使线性搜索更快，但对于大 n，二分搜索的对数增长特性使其远优于线性搜索。

---

9. Sorting Algorithm Comparisons | 排序算法比较

adjacent items and swaps them if they are in the wrong order. Worst case comparisons = n(n‑1)/2 ≈ O(n²).

冒泡排序反复遍历列表，比较相邻元素并在顺序错误时交换它们。最坏情况比较次数 = n(n‑1)/2 ≈ O(n²)。

at a time, inserting new elements into the correct position. Worst case comparisons ≈ n(n‑1)/2, best case n‑1 (O(n) for nearly sorted data).

插入排序逐项构建最终有序列表，将新元素插入到正确位置。最坏情况比较次数 ≈ n(n‑1)/2，最好情况 n‑1（对接近有序的数据为 O(n)）。

Merge sort uses a divide‑and‑ risons ≈ n log₂ n. Time complexity O(n log n) in all cases, but requires O(n) extra space.

归并排序采用分治策略：将列表分成两半，递归排序每一半，然后合并有序的两半。比较次数 ≈ n log₂ n。所有情况时间复杂度均为 O(n log n)，但需要 O(n) 额外空间。

---

10. Network Delay Calculations | 网络延迟计算

agation delay = Distance / Propagation speed of the medium (≈ 2×10⁸ m/s for copper/fibre).

传输延迟（将所有比特推送到链路上的时间）= 数据量 (比特) / 带宽 (bps)。传播延迟 = 距离 / 介质传播速度（铜缆/光纤约为 2×10⁸ 米/秒）。

opagation delay + Queuing delay + Processing delay. In exam questions, queuing and processing delays are often assumed negligible unless specified.

总延迟 = 传输延迟 + 传播延迟 + 排队延迟 + 处理延迟。考试题目中，除非另有说明，排队和处理延迟通常被视为可忽略。

For a packet‑switched network, transmission delay is incurred per hop, while propagation delay depends on the physical distance of each link.

对于分组交换网络，每一跳都会产生传输延迟，而传播延迟取决于每条链路的物理距离。

---

11. Error Detection Techniques | 错误检测技术

A parity bit is added to a binary word so that the total number of 1s is even (even parity) or odd (odd parity). It can detect a single‑bit error but not two errors.

奇偶校验位被添加到二进制字中，使得 1 的总数为偶数（偶校验）或奇数（奇校验）。它可以检测单个比特错误，但无法检测两个错误。

In a checksum, the data is divided into segments and the sum (or one’s complement of the sum) is appended. It helps detect multiple errors but is less robust than CRC.

在校验和中，数据被划分为若干段，将其和（或和的反码）附加在后面。它有助于检测多个错误，但不如循环冗余校验 (CRC) 健壮。

CRC (Cyclic Redundancy Check) treats the data as a polynomial and divides it by a generator polynomial. The remainder becomes the checksum. It can detect burst errors up to the degree of the generator polynomial.

CRC（循环冗余校验）将数据视为多项式，并除以生成多项式。余数成为校验码。它可以检测长度不超过生成多项式次数的突发错误。

---

12. Finite State Machines (FSM) | 有限状态机

A Moore machine’s outputs depend only on the current state. In a state transition diagram, outputs are written inside the state node, and transition conditions label the arcs.

摩尔型状态机的输出仅取决于当前状态。在状态转换图中，输出写在状态节点内部，转换条件标记在弧上。

A Mealy machine’s outputs depend on the current state and the input. Outputs are written on the transition arcs alongside the input condition, typically in the format ‘input/output’.

米利型状态机的输出取决于当前状态和输入。输出与输入条件一起写在转换弧上，通常格式为“输入/输出”。

FSMs can be represented by state transition tables listing current state, input, next state, and output. They are used to model control logic, communication protocols, and string matching with regular expressions.

有限状态机可以用状态转换表表示，列出当前状态、输入、下一状态和输出。它们用于建模控制逻辑、通信协议和正则表达式的字符串匹配。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）