Year 13 AQA Computer Science Formula & Theorem Quick Reference Handbook | AQA 13年级计算机科学公式定理速查手册

📚 Year 13 AQA Computer Science Formula & Theorem Quick Reference Handbook | AQA 13年级计算机科学公式定理速查手册

This handbook brings together the most essential formulas, laws, and theorems encountered throughout the Year 13 AQA A-Level Computer Science specification. It covers Boolean algebra, sequential logic, algorithm analysis, cryptography, computational theory, and more — all presented as bite-sized bilingual summaries for quick revision.

本书册汇集了AQA A级计算机科学13年级课程中最重要的公式、定律和定理，内容涵盖布尔代数、时序逻辑、算法分析、密码学、计算理论等多个模块，以简洁的中英对照方式呈现，便于快速复习。

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

• Identity Law: A + 0 = A and A · 1 = A

  同一律：A + 0 = A，A · 1 = A

• Null Law: A + 1 = 1 and A · 0 = 0

  零一律：A + 1 = 1，A · 0 = 0

• Idempotent Law: A + A = A and A · A = A

  幂等律：A + A = A，A · A = A

• Complement Law: A + A’ = 1 and A · A’ = 0

  互补律：A + A’ = 1，A · A’ = 0

• Double Negation: (A’)’ = A

  双重否定：(A’)’ = A

• Commutative Law: A + B = B + A and A · B = B · A

  交换律：A + B = B + A，A · B = B · A

• Associative Law: A + (B + C) = (A + B) + C and 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) and A + (B · C) = (A + B) · (A + C)

  分配律：A · (B + C) = (A · B) + (A · C)，A + (B · C) = (A + B) · (A + C)

• Absorption Law: A + (A · B) = A and A · (A + B) = A

  吸收律：A + (A · B) = A，A · (A + B) = A

• De Morgan’s Theorem: (A + B)’ = A’ · B’ and (A · B)’ = A’ + B’

  德摩根定理：(A + B)’ = A’ · B’，(A · B)’ = A’ + B’

2. Logic Gates and Combinational Circuits | 逻辑门与组合电路

• Half Adder: Sum S = A ⊕ B, Carry C = A · B

  半加器：和 S = A ⊕ B，进位 C = A · B

• Full Adder: Sum S = A ⊕ B ⊕ Cᵢₙ, Carry Cₒᵤₜ = (A · B) + (Cᵢₙ · (A ⊕ B))

  全加器：和 S = A ⊕ B ⊕ Cᵢₙ，进位 Cₒᵤₜ = (A · B) + (Cᵢₙ · (A ⊕ B))

• Multiplexer (2-to-1): Output = (A · S’) + (B · S)

  2选1多路选择器：输出 = (A · S’) + (B · S)

• Karnaugh Map simplification groups must be rectangular, contain 1,2,4,8… cells of 1s, and wrap‑around is allowed.

  卡诺图化简时分组必须为矩形，包含1、2、4、8…个1，允许上下/左右环绕。

3. Sequential Circuits and Flip-Flop Equations | 时序电路与触发器方程

• SR NOR Latch: S=1,R=0 sets Q=1; S=0,R=1 resets Q=0; S=0,R=0 holds state; S=1,R=1 is forbidden.

  SR NOR锁存器：S=1,R=0 置位Q=1；S=0,R=1 复位Q=0；S=0,R=0 保持；S=1,R=1 禁止。

• D-type flip-flop (positive edge-triggered): Qₙₑₓₜ = D

  D型触发器（上升沿触发）：Qₙₑₓₜ = D

• JK flip-flop (positive edge-triggered): Qₙₑₓₜ = J · Q’ + K’ · Q

  JK触发器（上升沿触发）：Qₙₑₓₜ = J · Q’ + K’ · Q

• Toggle state for JK: when J=1 and K=1, Qₙₑₓₜ = Q’ (toggles on each clock edge).

  JK翻转状态：当 J=1 且 K=1 时，Qₙₑₓₜ = Q’（每个时钟沿翻转）。

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

• Big O formal definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

  大O的形式化定义：f(n) = O(g(n)) 当存在正常数c和n₀，使得对所有 n ≥ n₀，有 0 ≤ f(n) ≤ c·g(n)。

• Common orders of growth (fastest to slowest): 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ⁿ)、O(n!)

• Space complexity is analysed similarly; only count auxiliary memory used by the algorithm.

  空间复杂度分析与之类似，只计算算法额外使用的辅助内存。

5. Recurrence Relations for Recursive Algorithms | 递归算法的递归关系

• Binary Search: T(n) = T(n/2) + O(1) → T(n) = O(log n)

  二分查找：T(n) = T(n/2) + O(1) → T(n) = O(log n)

• Merge Sort: T(n) = 2T(n/2) + O(n) → T(n) = O(n log n)

  归并排序：T(n) = 2T(n/2) + O(n) → T(n) = O(n log n)

• Tree traversals (pre/in/post-order) on a complete binary tree: visit each node once → O(n)

  完全二叉树的先序/中序/后序遍历：每个节点访问一次 → O(n)

• Solving by recursion tree or by substitution method, looking for repeating patterns until base case is reached.

  可通过递归树或代入法求解，寻找重复模式直至达到基准情形。

6. Sorting and Searching Algorithm Costs | 排序与搜索算法成本

• Bubble sort: best O(n) when already sorted, average O(n²), worst O(n²); stable.

  冒泡排序：最好情况（已排好序）O(n)，平均 O(n²)，最坏 O(n²)；稳定。

• Insertion sort: best O(n), average O(n²), worst O(n²); stable.

  插入排序：最好 O(n)，平均 O(n²)，最坏 O(n²)；稳定。

• Merge sort: best O(n log n), average O(n log n), worst O(n log n); stable; requires O(n) extra space.

  归并排序：最好 O(n log n)，平均 O(n log n)，最坏 O(n log n)；稳定；需要 O(n) 额外空间。

• Quick sort: best O(n log n), average O(n log n), worst O(n²); not stable (in-place version).

  快速排序：最好 O(n log n)，平均 O(n log n)，最坏 O(n²)；不稳定（原地排序版本）。

• Linear search: O(n) worst case; binary search: O(log n) on sorted array; hash table search: average O(1).

  线性搜索：最坏 O(n)；二分查找：有序数组中 O(log n)；散列表搜索：平均 O(1)。

7. Data Structures and Operation Complexities | 数据结构及其操作复杂度

• Array access: O(1); insertion/deletion at arbitrary position: O(n) due to shifting.

  数组随机访问：O(1)；任意位置插入/删除：O(n)（需要移动元素）。

• Linked list (singly): search O(n), insert/delete at head O(1), insert/delete given node O(1) if pointer is known.

  单向链表：查找 O(n)，表头插入/删除 O(1)，已知节点指针时插入/删除 O(1)。

• Binary search tree: average search/insert/delete O(log n), worst O(n) for unbalanced tree.

  二叉搜索树：平均查找/插入/删除 O(log n)，非平衡树最坏 O(n)。

• Stack and queue (implemented with array or linked list): push/pop or enqueue/dequeue O(1).

  栈和队列（数组或链表实现）：入栈/出栈、入队/出队操作均为 O(1)。

• Hash table with good hash function: average search/insert/delete O(1), worst O(n) (collision resolution required).

  良好散列函数下的哈希表：平均查找/插入/删除 O(1)，最坏 O(n)（需冲突解决）。

8. Graph Algorithms and Their Efficiencies | 图算法及其效率

• Dijkstra’s algorithm (non-negative weights): shortest path from source, O(V²) with adjacency matrix, O((V+E) log V) with binary heap and adjacency list.

  迪杰斯特拉算法（非负权值）：单源最短路径，邻接矩阵 O(V²)，二叉堆+邻接表 O((V+E) log V)。

• A* search: uses heuristic h(n) with f(n) = g(n) + h(n); g(n) is actual cost, h(n) estimated cost to goal.

  A*搜索：使用启发式函数 h(n)，估价函数 f(n) = g(n) + h(n)；g(n) 为实际代价，h(n) 为目标估值。

• Kruskal’s minimum spanning tree: O(E log E) or O(E log V) with union-find.

  克鲁斯卡尔最小生成树算法：使用并查集，复杂度 O(E log E) 或 O(E log V)。

• Prim’s MST: O(V²) with adjacency matrix, O(E log V) with binary heap.

  普里姆最小生成树：邻接矩阵 O(V²)，二叉堆 O(E log V)。

• Depth-first search (DFS) and Breadth-first search (BFS): both O(V+E) when using adjacency list.

  深度优先搜索（DFS）和广度优先搜索（BFS）：使用邻接表时均为 O(V+E)。

9. Encryption: RSA Key Generation, Encryption and Decryption | 加密：RSA密钥生成、加密与解密

• Select two large primes p and q; compute n = p × q and φ(n) = (p – 1)(q – 1).

  选取两个大素数 p 和 q；计算 n = p × q，φ(n) = (p – 1)(q – 1)。

• Choose public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.

  选择公开指数 e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。

• Compute private exponent d as the modular inverse of e modulo φ(n): e·d ≡ 1 (mod φ(n)).

  计算私钥指数 d，为 e 模 φ(n) 的乘法逆元：e·d ≡ 1 (mod φ(n))。

• Encryption: C = Mᵉ mod n (where M < n).

  加密：C = Mᵉ mod n（M 为明文，且 M < n）。

• Decryption: M = Cᵈ mod n.

  解密：M = Cᵈ mod n。

10. Compression: Huffman Coding and Run Length Encoding | 压缩：哈夫曼编码与游程编码

• Huffman coding builds a binary tree from symbols sorted by frequency. Average code length L = Σ (pᵢ · lᵢ) where pᵢ is probability and lᵢ is code length.

  哈夫曼编码按频率构建二叉树。平均码长 L = Σ (pᵢ · lᵢ)，p

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

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

  Share this:

  • Email
  • More

  • LinkedIn
  • X
  • Facebook
  • Tumblr
  • Reddit
  • Pinterest
  • Telegram
  • WhatsApp

  Like this:

  Like Loading…