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

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

This quick-reference handbook brings together the key formulas, theorems, and complexity results required for the Year 13 OCR Computer Science specifications. Use it to revise Boolean logic, algorithmic efficiency, number representation, theoretical models of computation, networking equations, and file-size calculations. Each section presents the essential relationships in a concise, exam-ready style, with English explanations immediately followed by their Chinese equivalents.

本速查手册汇集了 Year 13 OCR 计算机科学课程所需的关键公式、定理和复杂度结论。可用于复习布尔逻辑、算法效率、数值表示、计算理论模型、网络方程以及文件大小计算。每个小节以简洁、面向考试的风格呈现基本关系，英文说明后紧跟中文对应内容。

---

1. Boolean Algebra Laws | 布尔代数定律

The fundamental laws of Boolean algebra govern the simplification and manipulation of logic expressions. They are essential for reducing gate circuits and proving logical equivalence.

布尔代数的基本定律支配着逻辑表达式的化简和变换，是减少门电路和证明逻辑等价性的基础。

Identity laws: A + 0 = A, A · 1 = A
Null laws: A + 1 = 1, A · 0 = 0
Idempotent laws: A + A = A, A · A = A
Complement laws: A + ¬A = 1, A · ¬A = 0
Involution law: ¬(¬A) = A

同一律： A + 0 = A，A · 1 = A
零律： A + 1 = 1，A · 0 = 0
幂等律： A + A = A，A · A = A
互补律： A + ¬A = 1，A · ¬A = 0
对合律： ¬(¬A) = A

Commutative laws: A + B = B + A, A · B = B · A
Associative laws: (A + B) + C = A + (B + C), (A · B) · C = A · (B · C)
Distributive laws: 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
Absorption laws: A + (A · B) = A, A · (A + B) = A

交换律： A + B = B + A，A · B = B · A
结合律： (A + B) + C = A + (B + C)，(A · B) · C = A · (B · C)
分配律： A · (B + C) = (A · B) + (A · C)，A + (B · C) = (A + B) · (A + C)
德摩根定理：
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
吸收律： A + (A · B) = A，A · (A + B) = A

---

2. Logic Gates & Truth Tables | 逻辑门与真值表

Every Boolean expression can be implemented using a combination of basic logic gates. The standard gate set and their truth tables are central to digital circuit design.

每个布尔表达式都可以用基本逻辑门的组合来实现。标准门集及其真值表是数字电路设计的核心。

Gate	Symbol	Boolean Function	Description
AND	·	A · B	Output 1 only if all inputs are 1
OR	+	A + B	Output 1 if at least one input is 1
NOT	¬	¬A	Inverts the input
NAND	↑	¬(A · B)	AND followed by NOT; functionally complete
NOR	↓	¬(A + B)	OR followed by NOT; functionally complete
XOR	⊕	A ⊕ B = (¬A·B) + (A·¬B)	Output 1 if inputs differ
XNOR	⊙	A ⊙ B = (A·B) + (¬A·¬B)	Output 1 if inputs are equal

中文速览： AND 门输出仅在全部输入为 1 时为 1；OR 门只要有输入为 1 即输出 1；NOT 反转输入；NAND 和 NOR 各自功能完备，可构建任何电路；XOR 检测输入是否不同，XNOR 检测输入是否相等。

---

3. Algorithmic Complexity & Big O Notation | 算法复杂度与大 O 表示法

Algorithmic efficiency is measured by time and space complexity, expressed in Big O notation as a function of input size n. This provides an upper bound on the growth rate.

算法效率通过时间和空间复杂度来衡量，用大 O 表示法表示为输入规模 n 的函数，给出增长速率的上界。

Common classes:
O(1) – constant time (e.g., array access by index)
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(2ⁿ) – exponential time (e.g., brute-force travelling salesman)

常见复杂度：
O(1) – 常数时间（例如按索引访问数组）
O(log n) – 对数时间（例如二分查找）
O(n) – 线性时间（例如线性查找）
O(n log n) – 线性对数时间（例如归并排序）
O(n²) – 平方时间（例如冒泡排序、插入排序）
O(2ⁿ) – 指数时间（例如暴力解旅行商问题）

When analysing sorting and searching, you are expected to know both best-case and worst-case complexities. For example, quicksort is O(n log n) on average, but degrades to O(n²) in the worst case. Space complexity is often O(n) for recursive algorithms due to call-stack depth, or O(1) for in‑place sorts like bubble sort.

分析排序和搜索时，需要掌握最好情况和最坏情况复杂度。例如，快速排序平均为 O(n log n)，但最坏情况退化为 O(n²)。递归算法的空间复杂度通常为 O(n)，源于调用栈深度；冒泡排序等原地排序则为 O(1)。

---

4. Data Structure Operations & Complexities | 数据结构操作与复杂度

Different data structures offer trade-offs for insertion, deletion, and search. Below are the typical time complexities for fundamental structures in their standard implementations.

不同数据结构在插入、删除和搜索上各有取舍。以下是基本数据结构在标准实现中的典型时间复杂度。

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Singly Linked List	O(n)	O(n)	O(1)⁺	O(1)⁺
Doubly Linked List	O(n)	O(n)	O(1)⁺	O(1)⁺
Stack (array-based)	O(n)	O(n)	O(1)	O(1)
Queue (circular array)	O(n)	O(n)	O(1)	O(1)
Binary Search Tree (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Hash Table	N/A	O(1) avg	O(1) avg	O(1) avg

⁺ Insertion and deletion at a known position in a linked list are O(1); finding the position still requires O(n) search.

⁺ 在已知位置处对链表进行插入和删除为 O(1)；但查找该位置仍需 O(n) 的搜索时间。

---

5. Number Systems & Conversions | 数制及其转换

Understanding binary, hexadecimal, and two’s complement representation is essential for low‑level programming and data storage questions in the exam.

理解二进制、十六进制和二进制补码表示对于考试中的底层编程和数据存储题目至关重要。

Binary to decimal: multiply each bit by 2ⁿ, where n is the bit position from 0 on the right.
Example: 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 2 + 1 = 11₁₀

二进制转十进制： 每位数乘以 2ⁿ，n 为从右起的位置编号（从 0 开始）。
示例：1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 2 + 1 = 11₁₀

Hexadecimal ↔ binary: each hex digit corresponds to exactly 4 bits. Convert digit‑wise, then concatenate.
Example: A3₁₆ = 1010 0011₂

十六进制↔二进制： 每个十六进制位正好对应 4 位二进制。按位转换后连接。
示例：A3₁₆ = 1010 0011₂

Two’s complement for negative numbers: flip all bits of the positive magnitude and add 1.
For an 8‑bit representation, the range is –128 to +127. The most significant bit acts as the sign bit (1 for negative).
Example: –5 in 8‑bit two’s complement: 5 = 0000 0101 ⇒ flip → 1111 1010 ⇒ +1 → 1111 1011
Addition of two’s complement numbers uses normal binary addition, ignoring the carry out of the most significant bit.

二进制补码表示负数： 将正数绝对值的所有位取反，再加 1。
8 位补码的表示范围为 –128 到 +127。最高位是符号位（1 表示负数）。
示例：–5 的 8 位补码：5 = 0000 0101 ⇒ 取反 → 1111 1010 ⇒ +1 → 1111 1011
补码加法可直接按二进制加法进行，忽略最高位的进位输出。

---

6. Floating Point Representation & Errors | 浮点数表示与误差

Real numbers are stored in binary using a mantissa and an exponent, with a sign bit. The exam typically gives a format, e.g., 1‑bit sign, m‑bit mantissa, e‑bit exponent, and asks for the decimal value or the binary representation.

实数以二进制存储，采用尾数和指数并带符号位。考试通常给定一个格式，例如 1 位符号、m 位尾数、e 位指数，然后要求求出十进制值或二进制表示。

General form: value = (–1)ˢ × mantissa × 2ᵉˣᵖᵒⁿᵉⁿᵗ
Both mantissa and exponent are usually stored in two’s complement or biased notation; the specification uses two’s complement for the exponent. The mantissa is usually normalised so that the first two bits differ (0.1 or 1.0 for positive/negative).

通用形式： 值 = (–1)ˢ × 尾数 × 2ᵉˣᵖᵒⁿᵉⁿᵗ
尾数和指数通常以二进制补码或移码形式存储；OCR 规范中指数使用二进制补码，尾数需规范化，使前两位不同（正数为 0.1，负数为 1.0）。

Absolute error: |exact value − stored value|
Relative error: absolute error ÷ exact value
These arise from the finite precision of the mantissa. When the number is too large or too small, overflow or underflow occurs. The smallest positive normalised number and the machine epsilon define the precision limits.

绝对误差： |精确值 – 存储值|
相对误差： 绝对误差 ÷ 精确值
这些误差源于尾数的有限精度。当数值过大或过小时会发生上溢或下溢。最小正规格化数和机器精度定义了精度极限。

---

7. Finite State Machines (FSMs) | 有限状态机

An FSM is a computational model consisting of states, inputs, outputs, and transitions. It can be deterministic (DFA) or non‑deterministic (NFA). OCR requires you to draw state‑transition diagrams, determine the language accepted, and simplify machines.

有限状态机是一种由状态、输入、输出和转换组成的计算模型，可分为确定型 (DFA) 和非确定型 (NFA)。OCR 要求绘制状态转换图，确定接受的语言，并对机器进行化简。

Mealy machine: outputs are associated with transitions (output depends on state and input).
Moore machine: outputs are associated with states (output depends only on current state).
Conversion between the two types is possible.

Mealy 机： 输出与转换关联（输出取决于状态和输入）。
Moore 机： 输出与状态关联（输出仅取决于当前状态）。
两种类型之间可以互相转换。

Accepting state / language: a string is accepted if, after processing all symbols from the start state, the machine ends in an accepting (final) state. The set of all accepted strings defines the language of the FSM.

接受状态 / 语言： 若从起始状态开始处理完所有符号后机器处于接受（终止）状态，则该字符串被接受。所有被接受的字符串构成该 FSM 的语言。

Regular expressions describe regular languages exactly recognised by FSMs. The pumping lemma can be used to prove that a language is not regular.

正则表达式描述的正则语言恰好可以被 FSM 识别。泵引理可用于证明某语言不是正则语言。

---

8. Turing Machines & Computability | 图灵机与可计算性

A Turing machine (TM) is a more powerful model of computation that can read and write on an infinite tape according to a set of transition rules. It underpins the theory of what can and cannot be computed.

图灵机是一种能力更强的计算模型，可依据一组转换规则在无限长纸带上读写。它为可计算与不可计算理论奠定了基础。

Church–Turing thesis: any effectively calculable function can be computed by a Turing machine. This is the foundation of classical computability theory.

邱奇–图灵论题： 任何可有效计算的函数都能被某个图灵机计算。这是经典可计算性理论的基石。

Halting problem: there is no Turing machine that can decide, for every pair (TM, input), whether that TM halts on that input. The halting problem is undecidable. This demonstrates a fundamental limit of computation.

停机问题： 不存在一台图灵机能对每一个 (TM, 输入) 对决定该 TM 是否会在该输入上停机。停机问题是不可判定的，体现了计算的根本局限。

Other undecidable questions include determining whether a TM accepts any string, or whether two context‑free grammars generate the same language. Recognising these limits is a key skill for the written paper.

其他不可判定的问题包括判断某个图灵机是否接受任一字符串，或两个上下文无关文法是否产生相同的语言。识别这些局限性是笔试的关键技能。

---

9. Regular Expressions & Formal Grammars | 正则表达式与形式文法

Formal languages are described using regular expressions (for regular languages) and context‑free grammars (for more expressive languages). You need to be able to write an expression for a given pattern, parse strings, and construct simple syntax diagrams.

形式语言使用正则表达式（描述正则语言）和上下文无关文法（描述表达能力更强的语言）来表述。需要能够为给定模式写出表达式、解析字符串并构建简单的语法图。

Regular expression symbols:
· (concatenation), | (alternation/choice), * (Kleene star, zero or more), + (one or more), ? (zero or one), () for grouping.
Example: a(b|c)*d matches ‘ad’, ‘abcd’, ‘abccd’, etc.

正则表达式符号：
·（连接），|（或/选择），*（Kleene 星号，零次或多次），+（一次或多次），?（零次或一次），() 用于分组。
示例：a(b|c)*d 可以匹配 ‘ad’、’abcd’、’abccd’ 等。

Backus–Naur form (BNF) and syntax diagrams are used to define the syntax of programming languages. For instance, a simple digit definition:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
You may be asked to draw a syntax diagram or derive a string using the production rules.

巴科斯–诺尔范式 (BNF) 和语法图用于定义编程语言的语法。例如，简单的数字定义：
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
可能会要求绘制语法图或使用产生式规则推导字符串。

---

10. Cryptography & Key Exchange | 密码学与密钥交换

Modern security protocols rely on symmetric and asymmetric encryption. You need to recall the formulas for symmetric ciphers (e.g., Caesar shift, Vernam cipher) and the mathematical basis of RSA and Diffie–Hellman.

现代安全协议依赖于对称和非对称加密。需要回顾对称密码的公式（如凯撒移位、Vernam 密码）以及 RSA 和 Diffie–Hellman 的数学基础。

Caesar cipher (shift by k): encryption E(x) = (x + k) mod 26, decryption D(y) = (y − k) mod 26, assuming A=0, B=1, …, Z=25.

凯撒密码（偏移 k）： 加密 E(x) = (x + k) mod 26，解密 D(y) = (y − k) mod 26，设 A=0, B=1, …, Z=25。

RSA key generation: choose two large primes p, q. Compute n = p × q, φ(n) = (p−1)(q−1). Choose public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. Compute private exponent d ≡ e⁻¹ (mod φ(n)).
Encryption: c = mᵉ mod n
Decryption: m = cᵈ mod n

RSA 密钥生成： 选择两大素数 p, q。计算 n = p × q，φ(n) = (p−1)(q−1)。选择公钥指数 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。计算私钥指数 d ≡ e⁻¹ (mod φ(n))。
加密：c = mᵉ mod n
解密：m = cᵈ mod n

Diffie–Hellman key exchange: public parameters: large prime p, generator g. Alice chooses secret a, sends A = gᵃ mod p. Bob chooses secret b, sends B = gᵇ mod p. Both compute shared secret K = Bᵃ mod p = Aᵇ mod p = gᵃᵇ mod p.

Diffie–Hellman 密钥交换： 公开参数：大素数 p，生成元 g。Alice 选择秘密 a，发送 A = gᵃ mod p。Bob 选择秘密 b，发送 B = gᵇ mod p。双方计算共享密钥 K = Bᵃ mod p = Aᵇ mod p = gᵃᵇ mod p。

---

11. Networking & Data Transmission | 网络与数据传输

Calculations involving data transfer delay, packet sizes, IP addressing, and error detection are common in the exam. The formulas below cover the core quantities.

涉及数据传输延迟、数据包大小、IP 寻址和错误检测的计算在考试中很常见。以下公式涵盖了核心量。

Transmission time = file size / bandwidth
Ensure consistent units: bits vs bytes, and remember that 1 byte = 8 bits, 1 kB = 1000 bytes (or 1024 in some contexts – OCR requires the SI convention for storage: 1 kB = 1000 B, 1 KiB = 1024 B).

传输时间 = 文件大小 / 带宽
保证单位一致：注意比特与字节，并记住 1 字节 = 8 位；OCR 存储采用国际单位制：1 kB = 1000 B，1 KiB = 1024 B。

Propagation delay = distance / speed of signal (speed ≈ 2×10⁸ m/s in copper/fibre)

传播延迟 = 距离 / 信号速度（铜缆/光纤中速度约为 2×10⁸ 米/秒）

Packet header overhead: total data sent = payload + header size. Efficiency = payload / packet size.

数据包头开销： 发送总量 = 有效载荷 + 头部大小。效率 = 有效载荷 / 数据包大小。

IP addressing – subnetting: given a CIDR notation like 192.168.1.0/24, the number of host addresses is 2³²⁻ⁿ − 2 (usually reserving network and broadcast addresses).
Network address is obtained by bitwise AND of IP and subnet mask.

IP 寻址 – 子网划分： 给定 CIDR 表示如 192.168.1.0/24，主机地址数为 2³²⁻ⁿ – 2（通常保留网络地址和广播地址）。
将 IP 地址与子网掩码按位 AND 即可得到网络地址。

Hamming distance and error detection: the number of bit errors that can be detected by an error‑detecting code is d−1, where d is the minimum Hamming distance between valid codewords. Parity check can detect all odd numbers of bit errors.

汉明距离与错误检测： 错误检测码可检测的比特错误数为 d−1，其中 d 是有效码字间的最小汉明距离。奇偶校验可检测所有奇数个比特错误。

---

12. Image & Sound File Size Calculations | 图像与声音文件大小计算

Media file size formulas appear frequently in the computational theory section. Always convert to bits where necessary.

多媒体文件大小公式经常出现在计算理论部分。必要时一律转换为位。

Image file size (bits) = width × height × colour depth
Colour depth is the number of bits per pixel. For a full‑colour RGB image, it is typically 24 bits (8 bits per channel). If the image includes an alpha channel, add another 8 bits.
Example: a 1920×1080 image with 24‑bit colour depth uses 1920 × 1080 × 24 ≈ 49,766,400 bits ≈ 6.2 MB (using 1 MB = 8×10⁶ bits).

图像文件大小（位）= 宽度 × 高度 × 颜色深度
颜色深度是每像素的位数。全彩 RGB 图像通常为 24 位（每通道 8 位）。若包含 alpha 通道，需再加 8 位。
示例：1920×1080 图像，24 位颜色深度，占用 1920 × 1080 × 24 ≈ 49,766,400 位 ≈ 6.2 MB（按 1 MB = 8×10⁶ 位计算）。

Sound file size (bits) = sample rate × bit depth × duration (seconds) × number of channels
For CD‑quality audio: 44,100 Hz × 16 bits × 2 (stereo) × duration. A 3‑minute stereo CD track therefore takes about 44,100 × 16 × 2 × 180 = 254,016,000 bits ≈ 31.8 MB.

声音文件大小（位）= 采样率 × 位深度 × 持续时间（秒）× 声道数
CD 质量音频：44,100 Hz × 16 位 × 2（立体声） × 时长。一段 3 分钟立体声 CD 音轨大约需要 44,

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

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