📚 Year 13 CCEA Computer Science: Essential Formulas & Theorems | CCEA Year 13 计算机必会公式定理速查手册
This quick reference handbook brings together the essential formulas, theorems, and laws you must master for the CCEA Year 13 Computer Science specification. Use it to revise data representation, Boolean logic, algorithm complexity, database normalisation, and networking calculations with confidence.
本速查手册汇集了 CCEA Year 13 计算机科学课程中必须掌握的核心公式、定理和定律，助你高效复习数据表示、布尔逻辑、算法复杂度、数据库规范化与网络计算等重点内容。
1. Number Systems & Binary Arithmetic | 数制与二进制算术
Binary, denary, and hexadecimal conversions form the backbone of all data representation. In an n-bit unsigned binary number, the range of values is 0 to 2ⁿ − 1.
二进制、十进制和十六进制之间的转换是所有数据表示的基础。n 位无符号二进制数的取值范围为 0 到 2ⁿ − 1。
Two’s complement negates a binary number: for an n-bit word, the negative of an integer N is given by 2ⁿ − N. This allows subtraction to be performed as addition.
二进制补码用于表示负数：对于 n 位字长，整数 N 的负数表示为 2ⁿ − N，借此可将减法转换为加法运算。
−N = 2ⁿ − N (two’s complement)
−N = 2ⁿ − N (二进制补码)
Binary addition follows the rules 0+0=0, 0+1=1, 1+0=1, 1+1=0 with carry 1. Overflow occurs when the result exceeds the given number of bits and the sign bit is corrupted.
二进制加法遵循 0+0=0、0+1=1、1+0=1、1+1=0 进位 1。若结果超出给定位数且符号位出错，则发生溢出。
2. Boolean Algebra Laws & De Morgan’s Theorems | 布尔代数定律与德摩根定理
Boolean algebra simplifies logic circuits using a set of fundamental identities. The most important laws are listed below.
布尔代数利用基本恒等式简化逻辑电路。以下列出最重要的定律。
-
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)
结合律：(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)
分配律：A · (B + C) = A · B + A · C A + B · C = (A + B) · (A + C)
-
Identity: A · 1 = A A + 0 = A
恒等律：A · 1 = A A + 0 = A
-
Complement: A · A’ = 0 A + A’ = 1
互补律：A · A’ = 0 A + A’ = 1
-
Idempotent: A · A = A A + A = A
幂等律：A · A = A A + A = A
-
Double negation: (A’)’ = A
双重否定律：(A’)’ = A
-
Absorption: A + A · B = A A · (A + B) = A
吸收律：A + A · B = A A · (A + B) = A
De Morgan’s theorems allow conversion between AND and OR operations with negation.
德摩根定理实现了与运算和或运算在非门作用下的相互转换。
¬(A ∧ B) = ¬A ∨ ¬B or (A · B)’ = A’ + B’
¬(A ∧ B) = ¬A ∨ ¬B 即 (A · B)’ = A’ + B’
¬(A ∨ B) = ¬A ∧ ¬B or (A + B)’ = A’ · B’
¬(A ∨ B) = ¬A ∧ ¬B 即 (A + B)’ = A’ · B’
3. Logic Gates, Truth Tables & Karnaugh Maps | 逻辑门、真值表与卡诺图
The fundamental gates are AND (A·B), OR (A+B), NOT (A’ or ¬A), NAND ((A·B)’), NOR ((A+B)’), XOR (A⊕B) and XNOR (A⊙B). Truth tables define the output for every possible input combination.
基本逻辑门包括与门 (A·B)、或门 (A+B)、非门 (A’ 或 ¬A)、与非门 ((A·B)’)、或非门 ((A+B)’)、异或门 (A⊕B) 和同或门 (A⊙B)。真值表定义了每种输入组合对应的输出。
Karnaugh maps (K-maps) provide a visual method for simplifying Boolean expressions. Group adjacent cells containing 1s in powers of two (1, 2, 4, 8). Each group yields a product term; the simplified expression is the sum of these prime implicants.
卡诺图提供了一种可视化简化布尔表达式的方法。将相邻的 1 按 2 的幂次 (1、2、4、8) 分组，每组得到一个乘积项，最简表达式即这些质蕴含项之和。
Simplified SOP = m₀ + m₁ + m₃ … (sum of minterms)
最简与或式 = m₀ + m₁ + m₃ … (最小项之和)
Care must be taken to cover all 1s with the fewest groups and to exploit ‘don’t care’ conditions (X) to further minimise the circuit.
分组时需用最少的圈覆盖所有的 1，并可利用无关项 (X) 进一步化简电路。
4. Floating Point Representation | 浮点数表示
A floating-point number is stored as a signed mantissa and an exponent: Value = mantissa × 2exponent. The mantissa is normalised to ensure maximum precision, meaning it has a leading 1 (except for zero) after the binary point.
浮点数以带符号的尾数和指数存储：数值 = 尾数 × 2指数。尾数需进行规格化以保证最高精度，即二进制小数点后紧跟一个 1（零除外）。
In a typical IEEE-style format with sign S, exponent E and mantissa M, the value is (−1)S × 1.M × 2(E−bias). For an 8‑bit exponent, the bias is 127; for an 11-bit exponent, it is 1023.
在典型的 IEEE 格式中，用符号 S、指数 E 和尾数 M 表示，数值 = (−1)S × 1.M × 2(E−bias)。8 位指数时偏置值是 127，11 位指数时偏置值是 1023。
Value = (−1)S × 1.M × 2E − bias
数值 = (−1)S × 1.M × 2E − bias
Normalisation shifts the mantissa left until the most significant bit is 1, adjusting the exponent correspondingly. This maximises the number of significant digits stored.
规格化过程将尾数左移直到最高有效位为 1，并相应调整指数，从而尽可能多地保留有效位数。
5. Error Detection: Parity, Checksum & CRC | 错误检测：奇偶校验、校验和与循环冗余校验
Parity bits add an extra bit to make the total number of 1s even (even parity) or odd (odd parity). It detects single-bit errors but cannot identify which bit is wrong.
奇偶校验位添加额外的一位使得 1 的总数为偶数（偶校验）或奇数（奇校验）。它能检测单比特错误，但无法定位出错位。
Checksums compute a sum of data words, often complemented, and append it to the data block. The receiver performs the same computation and compares results.
校验和将数据字求和（常取反）后附加到数据块中；接收方执行相同计算并比较结果。
Cyclic Redundancy Check (CRC) treats data as a binary polynomial and performs modulo-2 division by a generator polynomial G(x). The remainder becomes the CRC code appended to the message.
循环冗余校验 (CRC) 将数据视为二进制多项式，并用生成多项式 G(x) 进行模 2 除法，余数即附加到消息后的 CRC 码。
Message appended with n zeros ÷ G(x) = Quotient + Remainder (CRC)
信息码后添 n 个 0 ÷ G(x) = 商 + 余数 (CRC 校验码)
Common generator polynomials: CRC‑8: X⁸+X²+X+1, CRC‑16‑CCITT: X¹⁶+X¹²+X⁵+1. CRC catches burst errors very effectively.
常用生成多项式：CRC‑8: X⁸+X²+X+1, CRC‑16‑CCITT: X¹⁶+X¹²+X⁵+1。CRC 能高效检测突发错误。
6. Algorithm Complexity & Big O Notation | 算法复杂度与大 O 记号
Big O notation describes the upper bound of an algorithm’s time or space requirement as the input size n grows. Constants and lower-order terms are ignored.
大 O 记号描述当输入规模 n 增长时算法时间或空间需求的上界。忽略常数项与低阶项。
Common complexities in increasing order: O(1) – constant, O(log n) – logarithmic, O(n) – linear, O(n log n) – linearithmic, O(n²) – quadratic, O(2ⁿ) – exponential.
常见复杂度递增顺序为：O(1) 常数阶，O(log n) 对数阶，O(n) 线性阶，O(n log n) 线性对数阶，O(n²) 平方阶，O(2ⁿ) 指数阶。
To derive Big O, count the dominating operation in the worst case. A double nested loop over n elements gives O(n²); a binary search halves the search space giving O(log n).
推导大 O 时，取最坏情况下主导操作的次数。对 n 个元素的双重嵌套循环复杂度为 O(n²)；二分搜索每次减半，复杂度为 O(log n)。
7. Searching & Sorting Algorithm Complexities | 搜索与排序算法复杂度
Linear search traverses every element – O(n). Binary search requires a sorted array and achieves O(log n).
线性搜索遍历每个元素，复杂度 O(n)。二分搜索要求数组有序，复杂度 O(log n)。
Bubble sort repeatedly swaps adjacent elements: best O(n) when already sorted, average and worst O(n²).
冒泡排序反复交换相邻元素：最佳情况（已有序）为 O(n)，平均和最坏为 O(n²)。
Insertion sort builds the sorted array one element at a time: best O(n), average and worst O(n²).
插入排序逐个元素构建有序序列：最佳 O(n)，平均和最坏 O(n²)。
Merge sort divides and merges: all cases O(n log n) but requires O(n) extra space.
归并排序采用分治策略：所有情况均为 O(n log n)，但需要 O(n) 额外空间。
Quick sort partitions around a pivot: average O(n log n), worst O(n²) when pivot is poorly chosen.
快速排序围绕主元划分：平均 O(n log n)，主元选择不佳时最坏为 O(n²)。
8. Database Normalisation (1NF – 3NF) | 数据库规范化（1NF – 3NF）
First Normal Form (1NF) eliminates repeating groups; every attribute value must be atomic. Each table must have a primary key.
第一范式 (1NF) 消除重复组，每个属性值必须原子化，且每张表需有主键。
Second Normal Form (2NF) meets 1NF and removes partial dependencies: all non-key attributes must be fully functionally dependent on the whole primary key (important for composite keys).
第二范式 (2NF) 满足 1NF 并消除部分依赖：所有非主属性必须完全函数依赖于整个主键（对复合主键尤为重要）。
Third Normal Form (3NF) meets 2NF and removes transitive dependencies: no non-key attribute should depend on another non-key attribute.
第三范式 (3NF) 满足 2NF 并消除传递依赖：非主属性不能依赖于其他非主属性。
Functional dependency X → Y means X determines Y
函数依赖 X → Y 表示 X 决定 Y
Normalisation reduces redundancy and update anomalies, ensuring data integrity in relational databases.
规范化能减少数据冗余与更新异常，确保关系数据库的数据完整性。
9. Regular Expressions & Finite State Machines | 正则表达式与有限状态机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课程辅导，国外大学本科硕士研究生博士课程论文辅导