📚 Edexcel Maths Computer Science (PG Online) | Edexcel 数学计算机科学（PG Online）
This revision guide connects the mathematical techniques required in Edexcel A Level Mathematics and Further Mathematics with the computational thinking examined in Computer Science courses such as those supported by PG Online. The focus is on algorithms, discrete mathematics, logic and optimisation, which appear in Decision Mathematics units and underpin many programming tasks.
本复习指南将 Edexcel A Level 数学和进阶数学所需的数学技巧与 PG Online 等计算机科学课程考查的计算思维联系起来。重点包括算法、离散数学、逻辑和优化，这些内容出现在决策数学单元中，并构成许多编程任务的基础。
1. Algorithms and Complexity | 算法与复杂度
An algorithm is a finite sequence of precise instructions for solving a problem. In both Edexcel Decision Mathematics and Computer Science, you must be able to describe algorithms using flowcharts, pseudo-code and written steps. Each step must be unambiguous, and the algorithm must terminate after a finite number of operations.
算法是解决问题的有限精确指令序列。在 Edexcel 决策数学和计算机科学中，你必须能用流程图、伪代码和文字步骤描述算法。每一步都必须无歧义，并且算法必须在有限次操作后终止。
Complexity measures how many operations or how much memory an algorithm uses as the input size grows. A more efficient algorithm may be harder to describe, but it will scale better for large inputs. Exam questions often ask you to trace a simple algorithm and state the output.
复杂度衡量算法随输入规模增长而使用的操作次数或内存量。更高效的算法可能更难描述，但在大规模输入时扩展性更好。考试题常要求你跟踪一个简单算法并写出输出。
2. Sorting Algorithms | 排序算法
In bubble sort, pairs of adjacent items are compared and swapped if they are out of order. The list is complete after a full pass with no swaps. Bubble sort is simple but inefficient for large lists because its worst-case complexity is quadratic.
在冒泡排序中，比较相邻的一对元素，如果顺序错误则交换。经过一趟没有发生交换的完整扫描后，列表排序完成。冒泡排序简单，但对大列表效率低，因为其最坏情况复杂度是平方级。
Quick sort chooses a pivot and partitions the list into items less than and greater than the pivot. The same process is then applied recursively to each sublist. Quick sort is often faster than bubble sort, but its performance depends on the choice of pivot.
快速排序选择一个基准值，并将列表划分为小于基准值和大于基准值的部分。然后对每个子列表递归地应用相同过程。快速排序通常比冒泡排序快，但其性能取决于基准值的选择。
Binary search repeatedly halves an ordered list by comparing the target with the middle value. If the target is smaller, search the left half; if larger, search the right half. It only works on sorted data and has logarithmic time complexity.
二分查找通过将目标值与中间值比较，不断将有序列表减半。如果目标更小，则搜索左半部分；如果更大，则搜索右半部分。它只适用于已排序数据，并具有对数时间复杂度。
3. Big-O Notation | 大 O 记号
Big-O notation describes how the running time or space of an algorithm grows with input size n. It ignores constant factors and lower-order terms because they have little effect on growth for large n.
大 O 记号描述算法的运行时间或空间如何随输入规模 n 增长。它忽略常数因子和低阶项，因为它们在 n 很大时对增长影响很小。
T(n) = O(n²)
This means that for sufficiently large n, the time is at most a constant multiple of n². Common complexities from fastest to slowest include O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ).
这表示当 n 足够大时，时间至多是 n² 的常数倍。从快到慢的常见复杂度包括 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 和 O(2ⁿ)。
| Complexity | Example |
| O(1) | Accessing an array element |
| O(log n) | Binary search |
| O(n) | Linear search |
| O(n log n) | Merge sort, quick sort average |
| O(n²) | Bubble sort, insertion sort |
4. Boolean Algebra and Logic Gates | 布尔代数与逻辑门
Boolean algebra uses binary variables and the logical operators AND, OR and NOT. In computer science, these correspond directly to logic gates in circuits. In Decision Mathematics and discrete maths, Boolean expressions are simplified using laws such as De Morgan's laws and the distributive law.
布尔代数使用二进制变量以及逻辑运算符与、或、非。在计算机科学中，它们直接对应电路中的逻辑门。在决策数学和离散数学中，布尔表达式使用德摩根定律和分配律等规则进行化简。
A · B, A + B, ¬A
The dot represents AND, the plus represents OR, and the bar or ¬ represents NOT. Truth tables list the output for every possible combination of inputs, and Karnaugh maps provide a visual method for simplifying expressions up to four variables.
点号表示与运算，加号表示或运算，横线或 ¬ 表示非运算。真值表列出每种可能输入组合的输出，卡诺图提供了一种化简最多四个变量表达式的可视化方法。
A common exam task is to show that two Boolean expressions are equivalent by simplification or by comparing their truth tables. Simplifying a circuit reduces the number of gates and therefore lowers cost and power consumption.
常见的考试任务是证明两个布尔表达式通过化简或比较真值表而等价。化简电路可减少门数量，从而降低成本和功耗。
5. Binary and Hexadecimal | 二进制与十六进制
Computers store integers using base-2 binary, where each digit is either 0 or 1. Hexadecimal is base-16 and is a compact way of representing binary numbers because each hex digit corresponds to exactly four binary digits.
计算机使用二进制存储整数，每位数字为 0 或 1。十六进制是 16 进制，是表示二进制数的紧凑方式，因为每个十六进制数字恰好对应四位二进制数字。
1011₂ = 11₁₀ = B₁₆
Converting from base 10 to another base uses repeated division by the target base. The remainders, read from last to first, give the digits of the new number. Binary addition, subtraction and multiplication follow the same column methods as decimal, but with carries when a column sum reaches 2 rather than 10.
从十进制转换到其他进制需要对目标基数反复做除法。余数从最后一个到第一个读取，即为新数的各位数字。二进制加法、减法和乘法遵循与十进制相同的列式方法，但当列和达到 2 而不是 10 时产生进位。
Hex is often used to represent memory addresses and colour codes. For example, the RGB colour white is FF FF FF in hexadecimal, which is 255 255 255 in decimal.
十六进制常用于表示内存地址和颜色代码。例如，RGB 颜色白色在十六进制中是 FF FF FF，在十进制中是 255 255 255。
6. Graphs and Networks | 图与网络
A graph consists of vertices, also called nodes, connected by edges, also called arcs. In Decision Mathematics, edges may be directed or undirected, and weighted or unweighted. A directed edge is drawn with an arrow to show the allowed direction of travel.
图由顶点（也称为节点）和边（也称为弧）连接组成。在决策数学中，边可以是有向或无向、带权或无权。有向边用箭头画出，表示允许的行进方向。
A tree is a connected graph with no cycles. A spanning tree is a subgraph that connects all vertices using a subset of the edges and contains no cycles. A graph with n vertices has a spanning tree with exactly n − 1 edges.
树是连通且无环的图。生成树是使用边的子集连接所有顶点且不含环的子图。具有 n 个顶点的图的生成树恰好有 n − 1 条边。
Graphs can be represented by an adjacency matrix, where entry (i, j) shows whether an edge connects vertex i to vertex j, or by an adjacency list. Exam questions often ask you to draw a graph from a matrix or to write a matrix from a diagram.
图可以用邻接矩阵表示，其中 (i, j) 项表示顶点 i 与顶点 j 之间是否有边连接；也可以用邻接表表示。考试题常要求你根据矩阵画图，或根据图写矩阵。
7. Shortest Path Algorithms | 最短路径算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. It works by assigning temporary labels and making them permanent in order of distance from the source.
Dijkstra 算法在非负权重的带权图中，找出从源顶点到所有其他顶点的最短路径。它通过分配临时标签并按距源点的距离顺序将其永久化来工作。
At each stage, choose the unvisited vertex with the smallest working label and make its label permanent. Then update the working labels of its neighbours by comparing the existing value with the distance via the current vertex. Continue until all vertices have permanent labels.
在每一阶段，选择具有最小工作标签的未访问顶点，并将其标签永久化。然后通过比较现有值与经过当前顶点的距离来更新其邻居的工作标签。持续进行，直到所有顶点都有永久标签。
If the graph has a destination vertex, Dijkstra's algorithm can stop as soon as that vertex receives a permanent label. The path is reconstructed by tracing backwards from the destination using the recorded preceding vertices.
如果图有目标顶点，Dijkstra 算法可以在该顶点获得永久标签时立即停止。路径通过使用记录的前驱顶点从目标处反向回溯来重构。
8. Minimum Spanning Trees | 最小生成树
A minimum spanning tree is a spanning tree with the smallest possible total edge weight. It is used to model problems such as laying cables or pipelines at minimum cost. Two common methods are Kruskal's algorithm and Prim's algorithm.
最小生成树是总边权尽可能小的生成树。它用于建模以最小成本铺设电缆或管道等问题。两种常用方法是 Kruskal 算法和 Prim 算法。
Kruskal's algorithm sorts all edges by weight and adds the cheapest edge that does not form a cycle. Continue until n − 1 edges have been selected, where n is the number of vertices.
Kruskal 算法将所有边按权重排序，并添加不形成环的最便宜边。继续直到选择了 n − 1 条边，其中 n 是顶点数。
Prim's algorithm grows a tree from an arbitrary starting vertex. At each step, add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. This guarantees a connected, acyclic subgraph at every stage.
Prim 算法从任意起始顶点生长树。每一步添加连接已在树中的顶点与尚未在树中的顶点且权重最小的边。这保证在每个阶段子图都是连通且无环的。
Both algorithms always produce a minimum spanning tree, but they may find different trees if edges have equal weights. In exams, state which algorithm you are using and show the edges in the order they are added.
两种算法总能产生最小生成树，但如果边权相同，它们可能找到不同的树。在考试中，说明你使用的算法，并按添加顺序展示边。
9. Linear Programming | 线性规划
Linear programming maximises or minimises a linear objective function subject to linear inequality constraints. It is used in business and industry to allocate limited resources such as time, money or raw materials.
线性规划在线性不等式约束下最大化或最小化线性目标函数。它用于商业和工业中分配有限资源，如时间、资金或原材料。
Maximise P = ax + by subject to cx + dy ≤ e, x ≥ 0, y ≥ 0
In a two-variable problem, the constraints form a feasible region on a coordinate grid. The optimal value of the objective function occurs at a vertex of the feasible region, so the graphical method evaluates the objective function at each vertex.
在双变量问题中，约束在坐标网格上形成可行域。目标函数的最优值出现在可行域的顶点，因此图解方法在每个顶点处计算目标函数值。
Integer linear programming adds the requirement that some or all variables must be whole numbers. In this case, the optimal integer solution is not necessarily the nearest integer vertex; you must check all integer points near the boundary of the feasible region.
整数线性规划增加了部分或全部变量必须为整数的要求。在这种情况下，最优整数解不一定是最接近的整数顶点；你必须检查可行域边界附近的所有整数点。
10. Critical Path Analysis | 关键路径分析
Critical path analysis schedules activities by representing precedence constraints in an activity network. Each activity is shown on an arc or node with its duration, and the network shows which activities must be completed before others can begin.
关键路径分析通过在活动网络中表示先后约束来安排活动。每个活动在弧或节点上显示其持续时间，网络显示哪些活动必须在其他活动开始前完成。
The critical path is the longest path through the network from start to finish. Any delay on a critical activity delays the entire project, so managers focus resources on these activities.
关键路径是网络中从开始到结束的最长路径。关键活动上的任何延迟都会推迟整个项目，因此管理者将资源集中在这些活动上。
Earliest start time is the soonest an activity can begin, calculated by moving forward through the network and taking the maximum of predecessor finish times. Latest finish time is the latest an activity can finish without delaying the project, calculated by moving backward and taking the minimum of successor start times.
最早开始时间是一个活动可以开始的最早时间，通过向前遍历网络并取前驱活动完成时间的最大值来计算。最晚完成时间是一个活动在不延误项目的情况下可以完成的最晚时间，通过向后遍历并取后继活动开始时间的最小值来计算。
Float is the amount of time an activity can be delayed without affecting the project duration. It is calculated as latest finish time minus earliest start time minus activity duration. Critical activities have zero float.
浮动时间是一个活动可以延迟而不影响项目总时长的时间量。它等于最晚完成时间减最早开始时间减活动持续时间。关键活动的浮动时间为零。
11. Recursion and Recurrence Relations | 递归与递推关系
Many efficient algorithms are defined recursively, meaning they call themselves on smaller subproblems. Binary search, merge sort and quick sort are classic examples. Recursion leads naturally to recurrence relations that describe the running time.
许多高效算法都是递归定义的，即它们对较小的子问题调用自身。二分查找、归并排序和快速排序是经典例子。递归自然导致描述运行时间的递推关系。
T(n) = T(n/2) + O(1)
comparison plus the time to solve a problem of size n/2. Its solution is T(n) = O(log n).
这个二分查找的递推关系表示，解决规模为 n 的问题需要一次比较加上解决规模为 n/2 的问题的时间。其解为 T(n) = O(log n)。
T(n) = 2T(n/2) + O(n)
rsively, then merges them in linear time. Solving this recurrence gives T(n) = O(n log n).
这个归并排序的递推关系将列表分成两半，递归地对每一半排序，然后在线性时间内合并它们。求解该递推关系得到 T(n) = O(n log n)。
In Further Mathematics, recurrence relations are also solved using iteration, characteristic equations or substitution. Exam questions may ask you to find the order of a recurrence or to calculate several terms from a given relation.
在进阶数学中，递推关系还通过迭代、特征方程或代入法求解。考试题可能要求你找出递推关系的阶数，或根据给定关系计算若干项。
12. Exam Tips | 考试技巧
Show all working in Decision Mathematics questions because method marks are awarded for correct intermediate labels, tables and edge selections. A correct answer with no working may score few or no marks.
在决策数学题目中展示所有步骤，因为正确的中间标签、表格和边选择可获得方法分。仅有正确答案而没有步骤可能得分很少或不得分。
For algorithm questions, practise tracing a given input through the steps and recording the state after each iteration. Write down the list, labels or graph clearly after every pass so examiners can follow your reasoning.
对于算法题，练习用给定输入跟踪每一步，并记录每次迭代后的状态。在每次扫描后清晰地写出列表、标签或图，以便考官能跟上你的推理。
Check arithmetic carefully in base conversions, Dijkstra labels and linear programming vertex tests. A single arithmetic slip can change the final answer and may lose accuracy marks even if the method is correct.
在进制转换、Dijkstra 标签和线性规划顶点检验中仔细检查算术。一个算术差错可能改变最终答案，即使方法正确也可能失去准确性分数。
In critical path analysis, draw the activity network accurately before calculating times. Label each vertex with its earliest start time and latest finish time, and clearly mark the critical path with double lines or a colour.
在关键路径分析中，计算时间前先准确画出活动网络。用最早开始时间和最晚完成时间标记每个顶点，并用双线或颜色清晰标出关键路径。
Published by TutorHao | Maths Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图