📚 Year 13 CIE Computer Science Formula & Theorem Quick Reference | CIE计算机公式定理速查手册
This quick reference compiles the essential formulas, theorems and computational rules required for the Year 13 CIE A‑Level Computer Science syllabus. Use it as a daily revision companion to memorise key quantitative relationships, Boolean identities, performance equations and algorithmic efficiencies. Every topic is matched with a concise explanation in both English and Chinese so you can cross‑check understanding instantly.
本速查手册汇总了 Year 13 CIE A‑Level 计算机科学课程必备的公式、定理与计算规则。把它作为日常复习伙伴，记住关键的数量关系、布尔恒等式、处理器性能方程和算法效率。每个主题都配有中英双语简明解释，方便即时对照理解。
1. Number Representation & Two’s Complement | 数字表示与补码
For an n‑bit two’s complement integer, the representable range is –2n‑1 to 2n‑1 – 1. To negate a value, invert all bits and add 1. The most significant bit acts as the sign bit (1 for negative, 0 for non‑negative).
n 位二进制补码整数的表示范围是 –2n‑1 到 2n‑1 – 1。求负数时，将所有位取反后再加 1。最高位作为符号位（1 表示负，0 表示非负）。
| n | Range | Example (8‑bit) |
| 8 | –128 to 127 | –1 = 1111 1111₂ |
| 16 | –32 768 to 32 767 | –2 = 1111 1111 1111 1110₂ |
| 32 | –2 147 483 648 to 2 147 483 647 | –5 = FFFFFFFB₁₆ |
2. Floating‑Point Representation | 浮点数表示
A binary floating‑point number is stored as mantissa × 2exponent. Both mantissa and exponent use two’s complement. The precision depends on mantissa bits; the range depends on exponent bits. To convert, normalise the mantissa so that the first two bits differ (01 or 10).
二进制浮点数存储为 尾数 × 2指数。尾数和指数均采用补码。精度由尾数位数决定，范围由指数位数决定。转换时需将尾数规格化，保证前两位不同（01 或 10）。
Decimal Value = mantissa × 2exponent
Example: in a 16‑bit register with 10‑bit mantissa and 6‑bit exponent, the normalised form of 5.5 is mantissa 0101100000, exponent 000011 (exponent = 3).
示例：16 位寄存器中若尾数 10 位、指数 6 位，5.5 的规格化形式为尾数 0101100000，指数 000011（指数=3）。
3. Boolean Algebra Laws & De Morgan’s Theorems | 布尔代数定律与德摩根定理
Boolean algebra provides identities for simplifying logic circuits. Key laws include commutativity, associativity, distributivity, absorption and De Morgan’s theorems. De Morgan’s theorems are essential for NAND/NOR gate conversion.
布尔代数提供了化简逻辑电路的恒等式，主要定律包括交换律、结合律、分配律、吸收律以及德摩根定理。德摩根定理对与非门/或非门转换至关重要。
De Morgan’s Theorem: ¬(A ∧ B) = ¬A ∨ ¬B and ¬(A ∨ B) = ¬A ∧ ¬B
-
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)
-
Absorption: A + A·B = A, A·(A+B) = A
吸收律：A + A·B = A, A·(A+B) = A
-
Identity: A+0 = A, A·1 = A, A+1 = 1, A·0 = 0
恒等律：A+0 = A, A·1 = A, A+1 = 1, A·0 = 0
4. Logic Gate Simplification & Karnaugh Maps | 逻辑门化简与卡诺图
Karnaugh maps (K‑maps) provide a visual method to simplify Boolean expressions to minimal Sum‑of‑Products (SOP) or Product‑of‑Sums (POS) forms. Group adjacent 1s (or 0s) in powers of two, ensuring groups are as large as possible. Overlapping is allowed.
卡诺图 (K‑map) 提供了一种图形化方法，将布尔表达式化简为最简与或式 (SOP) 或最简或与式 (POS)。按 2 的幂次将相邻的 1（或 0）分组，确保组尽可能大，允许重叠。
For a 3‑variable K‑map, a group of four 1s eliminates two variables; a group of two eliminates one. Don’t care conditions (X) may be treated as 0 or 1 to enlarge groups.
对于三变量卡诺图，四个 1 的一组消去两个变量，两个 1 的一组消去一个。无关项 (X) 可视为 0 或 1 以扩大分组。
SOP Simplification: F(A,B,C) = Σ(1,3,4,5,6,7) → F = A + C
5. CPU Performance Metrics | 处理器性能指标
CPU execution time, CPI (Cycles Per Instruction) and MIPS (Million Instructions Per Second) quantify processor speed. Clock frequency f is the inverse of clock period T.
CPU 执行时间、CPI（每条指令周期数）和 MIPS（每秒百万指令数）用于量化处理器速度。时钟频率 f 是时钟周期 T 的倒数。
Execution Time = Instruction Count × CPI × Clock Period
Execution Time = (Instruction Count × CPI) / Clock Frequency
MIPS = Instruction Count / (Execution Time × 10⁶)
Example: 2 million instructions, average CPI=2.5, clock rate 1 GHz → Time = (2×10⁶ × 2.5) / 10⁹ = 5 ms.
示例：2 百万条指令，平均 CPI=2.5，时钟速率 1 GHz → 时间 = (2×10⁶ × 2.5) / 10⁹ = 5 毫秒。
6. Data Transmission & File Size Calculations | 数据传输与文件大小计算
File size, transmission time and bandwidth are linked by the formula time = size / rate. Be careful with units: bits vs. bytes (1 B = 8 b), and SI prefixes (kilo=10³, mega=10⁶) vs. binary prefixes (kibi=2¹⁰, mebi=2²⁰).
文件大小、传输时间和带宽的关系为：时间 = 大小 / 速率。需注意单位：比特与字节 (1 B = 8 b)，以及 SI 前缀 (k=10³, M=10⁶) 与二进制前缀 (Ki=2¹⁰, Mi=2²⁰) 的区别。
Transmission Time (s) = File Size (bits) / Bit Rate (bps)
For a 5 MiB file over 100 Mbps link: size = 5 × 2²⁰ × 8 b ≈ 5 × 8.388 Mbit ≈ 41.94 Mbit. Time ≈ 41.94/100 ≈ 0.42 s.
以 100 Mbps 链路传输 5 MiB 文件：大小 = 5 × 2²⁰ × 8 b ≈ 5 × 8.388 Mb ≈ 41.94 Mb，时间 ≈ 41.94/100 ≈ 0.42 s。
7. Sound & Image Sampling | 声音与图像采样
Digital audio size depends on sample rate, bit depth, number of channels and duration. Image size depends on resolution and colour depth. Video combines both.
数字音频大小取决于采样率、位深度、声道数和时长。图像大小取决于分辨率和颜色深度。视频则结合两者。
Audio File Size = Sample Rate × Bit Depth × Channels × Duration (seconds)
Image File Size = Width (px) × Height (px) × Colour Depth (bits)
CD quality: 44.1 kHz, 16‑bit, stereo → bit rate = 44 100 × 16 × 2 = 1.4112 Mbps. One minute ≈ 10.6 MB.
CD 品质：44.1 kHz、16 位、立体声 → 比特率 = 44 100 × 16 × 2 = 1.4112 Mbps，一分钟约 10.6 MB。
8. Algorithm Complexity (Big O Notation) | 算法复杂度
Big O notation describes the upper bound of an algorithm’s time or space requirement as input size n grows. Common complexities: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
大 O 记号描述当输入规模 n 增长时，算法时间或空间需求的增长上限。常见复杂度有：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。
-
Binary search – O(log n)
二分查找 – O(log n)
-
Linear search – O(n)
线性查找 – O(n)
-
Bubble sort, insertion sort – O(n²)
冒泡排序、插入排序 – O(n²)
-
Merge sort, heap sort – O(n log n)
归并排序、堆排序 – O(n log n)
-
Recursive Fibonacci – O(2ⁿ)
递归斐波那契 – O(2ⁿ)
-
Tree traversal – O(n)
树遍历 – O(n)
9. Recursive Algorithms & Recurrence Relations | 递归算法与递推关系
A recursive algorithm calls itself with a smaller instance. Its behaviour can be expressed by a recurrence relation. Base case stops recursion.
递归算法通过调用自身处理更小的实例。其行为可用递推关系表示，基础情形终止递归。
Factorial: n! = n × (n‑1)!, base case 0! = 1. Recurrence: T(n) = T(n‑1) + O(1) → T(n) = O(n).
阶乘：n! = n × (n‑1)!，基础情形 0! = 1。递推关系：T(n) = T(n‑1) + O(1) → T(n) = O(n)。
Fibonacci: F(n) = F(n‑1) + F(n‑2), F(0)=0, F(1)=1. Recurrence: T(n) = T(n‑1) + T(n‑2) + O(1) → O(2ⁿ).
斐波那契：F(n) = F(n‑1) + F(n‑2)，F(0)=0，F(1)=1。递推关系：T(n) = T(n‑1) + T(n‑2) + O(1) → O(2ⁿ)。
10. File Organisation & Access Time | 文件组织与访问时间
In indexed sequential files, the number of block accesses depends on index levels and data blocks. For a two‑level index, access time ≈ index search + data block retrieval.
在索引顺序文件中，块访问次数取决于索引级数和数据块数。对于二级索引，访问时间 ≈ 索引查找 + 数据块检索。
Access Time = (Index levels) × (Block access time) + 1 Data block access
Hash files aim for O(1) access time. Collisions may increase the average access time depending on the overflow handling method (e.g. open addressing or chaining).
散列文件目标为 O(1) 访问时间。冲突可能根据溢出处理方式（如开放寻址或链表法）增加平均访问时间。
11. Error Detection & Correction | 差错检测与纠正
Parity bits, checksums, CRC and Hamming code are common error control methods. Hamming distance d means the code can detect up to d‑1 errors and correct floor((d‑1)/2) errors.
奇偶校验位、校验和、循环冗余校验 (CRC) 和汉明码是常见的差错控制方法。汉明距离 d 意味着该编码最多可检测 d‑1 个错误，并纠正 ⌊(d‑1)/2⌋ 个错误。
Detectable errors ≤ d − 1
Correctable errors ≤ floor((d − 1)/2)
For simple parity: d=2, detects 1 error, corrects 0. For CRC‑16: d=4, typically detects bursts of length ≤ 16.
对于简单奇偶校验：d=2，检测 1 个错误，纠正 0 个。对于 CRC‑16：d=4，通常可检测长度 ≤ 16 的突发错误。
12. Relational Database Normalisation | 关系数据库规范化
Normalisation reduces data redundancy by applying functional dependency rules. 1NF eliminates repeating groups; 2NF removes partial dependencies; 3NF removes transitive dependencies. BCNF handles remaining anomalies.
规范化通过函数依赖规则减少数据冗余。1NF 消除重复组；2NF 消除部分函数依赖；3NF 消除传递函数依赖；BCNF 处理余下的异常。
A functional dependency X → Y means Y depends on X. Partial dependency: a non‑key attribute depends on part of a composite key. Transitive dependency: a non‑key attribute depends on another non‑key attribute.
函数依赖 X → Y 意味着 Y 依赖于 X。部分依赖：非主属性依赖于复合主键的一部分。传递依赖：非主属性依赖于另一个非主属性。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply