📚 Pre-U OCR Computer Science: Formula & Theorem Quick Reference Handbook | Pre-U OCR 计算机：公式定理速查手册
This quick reference handbook compiles all essential formulas, theorems, and quantitative concepts required for the OCR Pre-U Computer Science examination. From Boolean algebra identities to computational complexity and data representation, each entry is presented with clear notation and paired explanations to support revision and exam preparation.
本次速查手册汇集了 OCR Pre-U 计算机科学考试中必备的公式、定理与定量概念。从布尔代数恒等式到计算复杂度与数据表示，每一条目均采用清晰符号并配有中英对照解释，助力复习与备考。
1. Boolean Algebra Identities | 布尔代数恒等式
The foundation of digital logic rests on Boolean algebra, where variables take values of 0 and 1. The following laws govern all simplification and equivalence transformations.
数字逻辑的基础在于布尔代数，其中变量取值仅为 0 和 1。以下定律支配着所有化简与等价变换。
Commutative Law: A + B = B + A, A · B = B · A
交换律：A + B = B + A，A · B = B · A
Associative Law: (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 Law: 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 Law: A + 0 = A, A · 1 = A
同一律：A + 0 = A，A · 1 = A
Complement Law: A + A̅ = 1, A · A̅ = 0
互补律：A + A̅ = 1，A · A̅ = 0
Double Complement: (A̅)̅ = A
双重否定补：A 的补再取补等于 A
Idempotent Law: A + A = A, A · A = A
幂等律：A + A = A，A · A = A
De Morgan’s Theorems: (A + B)̅ = A̅ · B̅, (A · B)̅ = A̅ + B̅
德摩根定理：(A + B) 的补等于 A 补与 B 补之积，(A · B) 的补等于 A 补与 B 补之和。
Absorption Law: A + (A · B) = A, A · (A + B) = A
吸收律：A + (A · B) = A，A · (A + B) = A
2. Logic Gate Propagation Delay and Fan-out | 逻辑门传播延迟与扇出
The physical behaviour of logic circuits can be characterised by delay times and fan-out, defined by manufacturers for each gate family.
逻辑电路的物理行为可通过传播延迟和扇出来表征，这些参数由制造商为每种门电路族定义。
Propagation delay tpd = average of tphl (high-to-low) and tplh (low-to-high). Typical tpd for TTL: 10 ns; for CMOS: 5–20 ns.
传播延迟 tpd = tphl（高到低延迟）与 tplh（低到高延迟）的平均值。典型 TTL 传播延迟为 10 ns，CMOS 为 5–20 ns。
Fan-out N = number of standard load gates driven by one gate without violating voltage levels. NL (LOW) = IOLmax / IILmax; NH (HIGH) = IOHmax / IIHmax.
扇出 N = 单个门在不破坏电压电平的情况下能驱动的标准负载门数量。低电平扇出 NL = IOLmax / IILmax；高电平扇出 NH = IOHmax / IIHmax。
Noise Margin (NM) = difference between output voltage levels and required input levels. NML = VILmax – VOLmax, NMH = VOHmin – VIHmin.
噪声容限 (NM) 是输出电压电平与所需输入电平之差。NML = VILmax – VOLmax，NMH = VOHmin – VIHmin。
3. Karnaugh Map Simplification | 卡诺图化简
Karnaugh maps (K-maps) provide a graphical method to minimise Boolean expressions. Each cell corresponds to a minterm, and adjacent cells differ by one variable.
卡诺图 (K-map) 提供了一种图形化的布尔表达式最小化方法。每个单元格对应一个最小项，相邻单元格仅在单个变量上不同。
For n variables, K-map has 2ⁿ cells. Group adjacent 1s in powers of two (1, 2, 4, 8 …). Overlapping groups are allowed.
对于 n 个变量，卡诺图包含 2ⁿ 个单元格。按 2 的幂次 (1, 2, 4, 8 …) 将相邻的 1 分组；允许分组重叠。
Essential prime implicants: groups covering a minterm not covered by any other prime implicant. Minimised expression = sum of all essential prime implicants.
必要质蕴含项：覆盖某个最小项的唯一质蕴含组。最简表达式 = 所有必要质蕴含项之和。
Don’t care conditions (X) can be used as 0 or 1 to obtain a smaller expression.
无关条件 (X) 可根据需要视为 0 或 1，以得到更简表达式。
4. Half Adder and Full Adder | 半加器与全加器
These are the fundamental building blocks for binary addition.
半加器和全加器是二进制加法的基本构建模块。
Half Adder: Sum S = A XOR B, Carry Cout = A · B. It adds two bits without carry-in.
半加器：和 S = A XOR B，进位 Cout = A · B。它实现不进位的两比特加法。
Full Adder: S = A XOR B XOR Cin, Cout = (A · B) + (Cin · (A XOR B)). Combination of two half adders plus an OR gate.
全加器：S = A XOR B XOR Cin，Cout = (A · B) + (Cin · (A XOR B))。由两个半加器和一个或门构成。
5. Binary Number Representation and Range | 二进制数表示与范围
Integer and fractional values follow different encoding schemes; range calculations are critical for data type selection.
整数和小数值采用不同编码方案；范围计算对数据类型选择至关重要。
Unsigned n-bit integer range: 0 to 2ⁿ – 1. Example: 8 bits → 0 to 255.
无符号 n 位整数范围：0 至 2ⁿ – 1。例如 8 位 → 0 到 255。
Signed two’s complement: range -2ⁿ⁻¹ to 2ⁿ⁻¹ – 1. n = 8 → -128 to +127.
有符号二进制补码：范围 -2ⁿ⁻¹ 至 2ⁿ⁻¹ – 1。n = 8 → -128 到 +127。
Floating-point (IEEE 754 single precision): value = (-1)ˢ × (1.fraction) × 2ᵉ⁻¹²⁷, where f is the mantissa (23 bits) and e is the exponent (8 bits). Special cases: denormalised numbers, infinity, NaN.
浮点数 (IEEE 754 单精度)：值 = (-1)ˢ × (1.尾数) × 2ᵉ⁻¹²⁷，其中 f 为 23 位尾数，e 为 8 位指数。特殊情况：非规格化数、无穷大、非数字 (NaN)。
6. Data Compression Ratios | 数据压缩比
Compression efficiency is measured by ratio formulas, essential for evaluating lossless and lossy compression algorithms in text, image, and audio domains.
压缩效率通过比率公式衡量，对评估文本、图像和音频领域的无损与有损压缩算法至关重要。
Compression Ratio = Uncompressed Size / Compressed Size. Space Saving = 1 – (Compressed Size / Uncompressed Size).
压缩比 = 未压缩大小 / 压缩后大小。空间节省 = 1 – (压缩后大小 / 未压缩大小)。
For Run-Length Encoding (RLE), compressed size = (number of runs) × (value + count) fields. Efficiency depends on data redundancy.
对于游程编码 (RLE)，压缩后大小 = (游程数) × (值 + 计数字段)。效率取决于数据冗余度。
Huffman coding average length L = Σ pᵢ × lᵢ, where pᵢ is probability of symbol i, lᵢ its code length. Entropy H = – Σ pᵢ log₂ pᵢ, and H ≤ L < H + 1.
霍夫曼编码平均长度 L = Σ pᵢ × lᵢ，其中 pᵢ 为符号 i 的概率，lᵢ 为其码长。熵 H = – Σ pᵢ log₂ pᵢ，且满足 H ≤ L < H + 1。
7. Computational Complexity: Big O, Θ, Ω | 计算复杂度：大 O、Θ、Ω
Asymptotic notations describe the worst-case, tight bound, and best-case performance of algorithms respectively.
渐近记号分别描述算法的最坏情况、紧确界和最好情况性能。
Big O (upper bound): f(n) = O(g(n)) if there exist c, n₀ > 0 such that f(n) ≤ c·g(n) for all n ≥ n₀. Example: linear search O(n).
大 O (上界)：若存在正常数 c 和 n₀ 使得对所有 n ≥ n₀ 有 f(n) ≤ c·g(n)，则 f(n) = O(g(n))。例如线性搜索 O(n)。
Ω (lower bound): f(n) = Ω(g(n)) if f(n) ≥ c·g(n) for n ≥ n₀. Best-case of binary search Ω(1).
Ω (下界)：若 f(n) ≥ c·g(n) 对 n ≥ n₀ 成立，则 f(n) = Ω(g(n))。二分搜索最好情况 Ω(1)。
Θ (tight bound): f(n) = Θ(g(n)) if it is both O(g(n)) and Ω(g(n)). Merge sort Θ(n log n).
Θ (紧确界)：若 f(n) 同时为 O(g(n)) 和 Ω(g(n))，则 f(n) = Θ(g(n))。归并排序 Θ(n log n)。
Common recurrences: T(n) = 2T(n/2) + n → Θ(n log n) (divide and conquer). T(n) = T(n-1) + 1 → Θ(n) (linear).
常见递推式：T(n) = 2T(n/2) + n → Θ(n log n)（分治法）；T(n) = T(n-1) + 1 → Θ(n)（线性）。
8. Cache Performance: Hit Rate and AMAT | 缓存性能：命中率与平均访存时间
Cache design formulas quantify the efficiency of the memory hierarchy, directly impacting processor performance.
缓存设计公式量化了内存层次结构的效率，直接影响处理器性能。
Hit Rate H = Number of cache hits / Total accesses. Miss Rate = 1 – H.
命中率 H = 缓存命中次数 / 总访问次数。缺失率 = 1 – H。
Average Memory Access Time (AMAT) = Hit time + Miss rate × Miss penalty. For multi-level caches: AMAT = t₁ + m₁ × (t₂ + m₂ × main memory penalty).
平均访存时间 (AMAT) = 命中时间 + 缺失率 × 缺失代价。多级缓存：AMAT = t₁ + m₁ × (t₂ + m₂ × 主存代价)。
9. Data Transfer Time and Latency | 数据传输时间与延迟
Disk and network I/O performance is modelled by seek time, rotational latency, and transfer time.
磁盘和网络 I/O 性能可通过寻道时间、旋转延迟和传输时间来建模。
Disk access time = Seek time + Rotational latency + Transfer time. Rotational latency average = 1/(2 × revolutions per second).
磁盘访问时间 = 寻道时间 + 旋转延迟 + 传输时间。平均旋转延迟 = 1/(2 × 每秒转数)。
Transfer time (seconds) = Data size / Transfer rate. Example: 1 MB file at 50 MB/s → 0.02 s.
传输时间 (秒) = 数据量 / 传输速率。例如 1 MB 文件以 50 MB/s 速率传输 → 0.02 s。
Network latency = Propagation delay + Transmission delay + Queuing delay + Processing delay. Transmission delay = Frame size / Bandwidth.
网络延迟 = 传播延迟 + 传输延迟 + 排队延迟 + 处理延迟。传输延迟 = 帧长 / 带宽。
10. Error Detection and Correction Distance | 检错与纠错码距
Hamming distance determines the capability of error-correcting codes, a core concept in reliable data transmission.
汉明距离决定了纠错码的能力，是可靠数据传输的核心概念。
Hamming distance d between two binary words: number of positions where bits differ. Minimum distance dmin of a code governs detection and correction.
两个二进制字之间的汉明距离 d：对应位不同的位数。编码的最小距离 dmin 决定检错与纠错能力。
Detection of up to e errors requires dmin ≥ e + 1. Correction of up to t errors requires dmin ≥ 2t + 1. Detection of e and correction of t (e > t) requires dmin ≥ e + t + 1.
检测最多 e 个错误需 dmin ≥ e + 1。纠正最多 t 个错误需 dmin ≥ 2t + 1。检测 e 个且纠正 t 个 (e > t) 需 dmin ≥ e + t + 1。
Parity check: appends one parity bit, minimum distance = 2, can detect single-bit errors.
奇偶校验：添加一位校验位，最小距离 = 2，可检测单个比特错误。
CRC polynomial division used for burst error detection; common polynomials: CRC-16, CRC-32.
循环冗余校验 (CRC) 采用多项式除法检测突发错误；常用多项式：CRC-16、CRC-32。
11. Relational Algebra and SQL Cardinality | 关系代数与 SQL 基数估计
Relational algebra forms the theoretical foundation of database queries; cardinality formulas assist in cost-based query optimisation.
关系代数是数据库查询的理论基础；基数公式有助于基于代价的查询优化。
Selection cardinality: |σcondition(R)| = |R| × selectivity. If condition is equality on a key, selectivity = 1/|R|; if non-key equality, selectivity = 1/(distinct values).
选择基数：|σ条件(R)| = 关系 R 的基数 × 选择率。若是键值相等条件，选择率 = 1/|R|；若是非键值相等，选择率 = 1/(不同值数量)。
Join cardinality estimate for equi-join R ⨝ S without common key: |R| × |S| / max( distinct values of join attribute in R, distinct values in S ).
非键等值连接 R ⨝ S 的基数估计：|R| × |S| / max( R 连接属性的不同值数, S 中不同值数 )。
Projection with duplicate elimination: cardinality bounded by number of distinct tuples in projected attribute list.
去重的投影操作基数最多等于投影属性列表中不同元组个数。
12. Clock Speed and Performance Metrics | 时钟频率与性能指标
Processor performance can be modelled via simple equations connecting clock speed, CPI, and instruction count.
处理器性能可通过连接时钟频率、CPI 和指令数的简单方程建模。
Execution Time = Instruction Count × CPI × Clock cycle time = (Instruction Count × CPI) / Clock rate.
执行时间 = 指令数 × CPI × 时钟周期时间 = (指令数 × CPI) / 时钟频率。
Speedup = Execution timeold / Execution timenew. Amdahl’s Law for fraction f enhanced by factor s: Speedup = 1 / ((1 – f) + f/s).
加速比 = 原执行时间 / 新执行时间。阿姆达尔定律对于增强部分 f、增强倍数 s：加速比 = 1 / ((1 – f) + f/s)。
MIPS = (Clock rate) / (CPI × 10⁶). MFLOPS for floating-point heavy loads. Benchmark scores like SPEC provide standardised comparisons.
MIPS = 时钟频率 / (CPI × 10⁶)。浮点密集型负载使用 MFLOPS。SPEC 等基准测试分数提供标准化比较。
Published by TutorHao | Pre-U OCR Computer Science Quick Revision | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply