Formula & Theorem Quick Reference Guide | 公式定理速查手册

📚 Formula & Theorem Quick Reference Guide | 公式定理速查手册

This quick reference guide brings together the most important formulae and theorems for SQA Year 12 Computing Science. It covers data representation, Boolean logic, algorithm efficiency, database design, cryptography and more. Use it to consolidate your knowledge and as a go‑to revision tool before assessments.

本速查手册汇总了SQA十二年级计算机科学中最关键的公式与定理，涵盖数据表示、布尔逻辑、算法效率、数据库设计、密码学等核心领域。可用作巩固知识、备考复习的得力工具。

---

1. Data Representation & Conversion | 数据表示与转换

Binary, decimal and hexadecimal conversions rely on positional weighting. The value of a digit depends on its place, weighted by powers of the base.

二进制、十进制和十六进制转换基于位权展开。每一位数字的值由其位置决定，权重为基数的幂。

Binary to decimal: multiply each bit by 2ⁿ, where n is the bit position from the right starting at 0, then sum.

二进制转十进制：每一位乘以2ⁿ（n为从右起位置编号，从0开始），然后求和。

Decimal to binary: repeatedly divide the decimal number by 2, recording the remainders, and read the remainders from bottom to top.

十进制转二进制：不断除以2，记录每次的余数，按从下到上的顺序读取余数即得二进制。

Hexadecimal to decimal: multiply each hex digit by 16ⁿ, using A=10, B=11, ..., F=15.

十六进制转十进制：每位乘以16ⁿ，字母A=10, B=11, …, F=15。

Binary to hexadecimal: group bits in sets of four from the right, then convert each 4‑bit nibble to its hex equivalent.

二进制转十六进制：从右开始每4位分组，然后将每组4位二进制转换为对应的十六进制数字。

Decimal = Σ (digit × base^position)

---

2. Binary Arithmetic & Two's Complement | 二进制算术与补码

0+1=1, 1+0=1, and 1+1=0 with a carry of 1. Negative integers are commonly stored using two's complement representation.

二进制加法遵循简单规则：0+0=0, 0+1=1, 1+0=1, 1+1=0 并向高位进1。负整数通常用补码表示。

To obtain the two's complement of a binary number: invert all bits (one's complement) then add 1. For an n‑bit word, the representable range is -2^n‑1 to 2^n‑1 - 1.

求一个二进制数的补码：所有位取反（反码）后加1。对于n位字长，可表示的范围是 -2^n‑1 到 2^n‑1 - 1。

Subtraction A - B is performed by adding A to the two's complement of B, then discarding any overflow beyond n bits.

减法 A - B 可通过 A 加上 B 的补码来实现，并丢弃超出n位的溢出。

Two's Complement = ¬bits + 1

---

3. Floating‑Point Representation | 浮点数表示

Real numbers are stored in normalised scientific notation: (-1)^S × (1 + M) × 2^{E - Bias}, where S is the sign bit, M is the fractional mantissa, and E is the biased exponent.

实数以规范化的科学记数法存储：(-1)^S × (1 + M) × 2^{E - Bias}，其中S为符号位，M为小数部分尾数，E为带偏移的指数。

IEEE 754 single precision uses 32 bits: 1 sign, 8 exponent (bias 127), 23 mantissa bits. Double precision uses 64 bits with 11‑bit exponent (bias 1023).

IEEE 754单精度使用32位：1位符号、8位指数（偏移127）、23位尾数。双精度使用64位，指数11位（偏移1023）。

To convert from normalised binary to decimal, separate the components, apply the bias, and reconstruct the number using the formula.

将规范化二进制转换为十进制时，分离各部分，减去偏移后利用公式重新组合出真值。

Value = (-1)^S × (1 + M) × 2^{E - Bias}

---

4. File Size Calculations | 文件大小计算

Estimating file size is essential for data transmission and storage planning. Each multimedia type has its own formula.

估算文件大小对数据传输和存储规划至关重要。不同的多媒体类型有各自的公式。

Text: size (bytes) ≈ number of characters × bytes per character encoding (ASCII = 1 byte, UTF‑8 up to 4 bytes).

文本：大小（字节）≈ 字符数 × 每字符编码字节数（ASCII为1字节，UTF‑8最多4字节）。

Bitmap image: pixels × height in pixels × colour depth in bits; then convert to bytes by dividing by 8.

位图图像：大小（位）= 宽度像素 × 高度像素 × 色彩深度(位)；然后除以8转换为字节。

Uncompressed sound: size (bits) = sample rate (Hz) × bit depth × duration (s) × number of channels.

未压缩音频：大小（位）= 采样率(Hz) × 位深度 × 时长(秒) × 声道数。

ytes, 1 MB = 1024 KB, etc. For transmission time, size in bits is divided by the bit rate.

务必注意单位换算：1字节=8位，1 KB=1024字节，1 MB=1024 KB等。计算传输时间时，用位为单位的大小除以比特率。

Image size (bits) = W × H × Colour Depth

---

5. Boolean Algebra Laws & Theorems | 布尔代数定律与定理

Boolean algebra uses the operators AND (·), OR (+), and NOT (¬) to simplify logic expressions. The following laws are the foundation for circuit reduction and Karnaugh mapping.

布尔代数使用与(·)、或(+)、非(¬)运算符来简化逻辑表达式。下列定律是化简电路和卡诺图的基础。

ntity: A + 0 = A, A · 1 = A. Null: A + 1 = 1, A · 0 = 0. Idempotent: A + A = A, A · A = A.

同一律：A+0=A, A·1=A。零律：A+1=1, A·0=0。幂等律：A+A=A, A·A=A。

Complement: A + ¬A = 1, A · ¬A = 0. Double Negation: ¬(¬A) = A.

互补律：A+¬A=1, A·¬A=0。双重否定：¬(¬A)=A。

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

De Morgan's Theorems: ¬(A·B) = ¬A + ¬B, ¬(A+B) = ¬A · ¬B.

德摩根定理：¬(A·B)=¬A+¬B, ¬(A+B)=¬A·¬B。

Absorption: A + (A·B) = A, A · (A+B) = A.

吸收律：A+(A·B)=A, A·(A+B)=A。

---

广告 / Sponsored

6. Karnaugh Map Simplification | 卡诺图化简

A Karnaugh map (K‑map) is a visual tool for minimising sum‑of‑products (SOP) Boolean expressions. Adjacent cells differ by a single variable.

卡诺图（K图）是一种用于最小化积之和（SOP）布尔表达式的可视化工具。相邻单元仅有一位变量不同。

Group adjacent 1s in rectangles of size 1, 2, 4, 8, etc. Each group must be as large as possible, and all 1s must be covered. Wraparound edges are allowed.

将相邻的1圈成大小为1、2、4、8等的矩形组。每组应尽可能大，所有1都必须被覆盖。允许边界环绕。

For each group, write the product term of variables that remain constant. Sum all the product terms to get the minimal SOP expression.

对每一组，写出保持不变变量的乘积项。将所有乘积项相加即得最简积之和表达式。

Don't‑care conditions (X) can be treated as 0 or 1 to create larger groups, further simplifying the circuit.

无关项（X）可视为0或1以便组成更大的圈，从而进一步简化电路。

---

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

Logic gates implement Boolean functions in hardware. The basic gates are AND, OR, NOT, NAND, NOR, XOR (exclusive OR) and XNOR (equivalence).

逻辑门在硬件中实现布尔函数。基本门包括与门、或门、非门、与非门、或非门、异或门和同或门。

A truth table lists all possible input combinations and the resulting output. For n inputs there are 2ⁿ rows.

真值表列出所有可能的输入组合及其对应输出。对于n个输入，共有 2ⁿ 行。

Gate	Boolean Expression	Symbol
AND	A · B	∧
OR	A + B	∨
NOT	¬A	¬
NAND	¬(A · B)	↑
NOR	¬(A + B)	↓
XOR	A ⊕ B = A·¬B + ¬A·B	⊕

NAND and NOR are universal gates; any Boolean circuit can be built using only NAND gates (or only NOR gates).

与非门和或非门是通用门；任何布尔电路都可以仅用与非门（或仅用或非门）来构建。

---

8. Database Normalisation & Keys | 数据库规范化与键

Normalisation reduces data redundancy and improves integrity. The process moves through normal forms (1NF, 2NF, 3NF) by resolving specific dependency problems.

规范化旨在减少数据冗余并提高完整性。该过程通过解决特定的依赖问题，逐步达到第一、第二和第三范式。

1NF: Eliminate repeating groups; every attribute must hold atomic (single) values. A primary key must be identified.

第一范式(1NF)：消除重复组；每个属性必须包含原子值（不可再分）。必须确定主键。

2NF: Must be in 1NF and have no partial dependencies – all non‑key attributes must depend on the whole primary key, not on part of it (relevant for composite keys).

第二范式(2NF)：满足1NF且不存在部分依赖——所有非键属性必须完全依赖于整个主键，而非主键的一部分（与复合键有关）。

3NF: Must be in 2NF and have no transitive dependencies – a non‑key attribute must not be functionally dependent on another non‑key attribute.

第三范式(3NF)：满足2NF且不存在传递依赖——非键属性不能函数依赖于其他非键属性。

hat for each value of X there is exactly one value of Y. Candidate keys are minimal sets of attributes that uniquely identify a row; one is chosen as the primary key. Foreign keys link tables by referencing primary keys in other tables.

函数依赖（X → Y）意味着对于X的每一个值，Y有且仅有一个值。候选键是可以唯一标识一行且属性最少的集合，从中选出一个作为主键。外键通过引用其他表的主键来建立表间联系。

---

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

Big O notation describes the upper bound (worst‑case) time or space complexity of an algorithm as the input size n grows. It focuses on the dominant term and ignores constant factors.

大O表示法描述当输入规模n增大时，算法在最坏情况下的时间或空间复杂度的上界。它着眼于主项并忽略常数因子。

Common complexity classes from fastest to slowest: 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ⁿ)指数阶。

ermining Big O: drop all constant multipliers (e.g., 5n → O(n)), and keep only the highest‑order term (e.g., n² + n → O(n²)).

确定大O的规则：舍去所有常数乘数（如5n → O(n)），并只保留最高次项（如 n² + n → O(n²)）。

A linear search on an unsorted list is O(n), whereas binary search on a sorted array is O(log n). Merge sort and quicksort average O(n log n) comparisons.

在无序列表上线性搜索是O(n)，而在有序数组上二分搜索是O(log n)。归并排序和快速排序的平均比较次数为O(n log n)。

---

10. Compression Ratios & Network Performance | 压缩比与网络性能

Compression ratio measures how much a file is reduced in size. It can be expressed as a ratio or percentage saving.

压缩比衡量文件大小缩减的程度，可以用比值或节省百分比来表示。

Compression Ratio = Uncompressed Size / Compressed Size

ratio means the original file is four times larger than the compressed one. Space saving (%) = (1 − Compressed/Original) × 100%.

例如，4:1的压缩比表示原始文件是压缩后文件的四倍大。空间节省百分比 = (1 − 压缩后/原始) × 100%。

Network transmission time depends on file size and bandwidth. Always use consistent units – typically convert file size to bits and time to seconds.

网络

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

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