📚 Decision Maths 1 Complete Revision Guide | 决策数学 1 完整复习指南
Decision Maths 1 introduces the core algorithms and models used in discrete mathematics. This revision guide summarises the essential methods, notation and exam techniques for A-level Further Mathematics.
决策数学 1 介绍离散数学中使用的核心算法与模型。本复习指南总结了 A-level 进阶数学所需的方法、符号与考试技巧。
1. Algorithms and Sorting | 算法与排序
An algorithm is a finite, step-by-step sequence of instructions that solves a problem. In Decision Maths 1, you must be able to trace and compare sorting algorithms such as bubble sort and quick sort.
算法是解决问题的一组有限、逐步执行的指令。在决策数学 1 中，你需要能够追踪并比较冒泡排序和快速排序等排序算法。
Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each pass the next largest element 'bubbles' to the end. Its worst-case and average time complexity is O(n²).
冒泡排序通过反复比较相邻元素并在顺序错误时交换它们来工作。每一轮后，下一个最大元素会“冒泡”到末尾。其最坏情况和平均时间复杂度为 O(n²)。
Quick sort chooses a pivot, partitions the list into values less than and greater than the pivot, and recursively sorts the sublists. It has average complexity O(n log n) but can degenerate to O(n²) if a bad pivot is chosen.
快速排序选择一个基准值，将列表划分为小于和大于基准值的两部分，并递归排序子列表。其平均复杂度为 O(n log n)，但如果选择不当，可能退化为 O(n²)。
2. Binary Search and Big-O Notation | 二分查找与大 O 表示法
Binary search operates on a sorted list. It compares the target with the middle value: if equal, the item is found; if the target is smaller, search the left half; if larger, search the right half.
二分查找在有序列表上进行。它将目标值与中间值比较：若相等则找到；若目标较小，搜索左半部分；若较大，搜索右半部分。
The process halves the search space each time, so the maximum number of comparisons is log₂(n), making the time complexity O(log n). Linear search, by contrast, has O(n).
该过程每次将搜索范围减半，因此最多比较 log₂(n) 次，时间复杂度为 O(log n)。相比之下，线性查找的时间复杂度为 O(n)。
Big-O notation describes an upper bound on the growth rate of an algorithm as the input size n increases. It ignores constants and lower-order terms.
大 O 表示法描述当输入规模 n 增大时算法增长率的上界。它忽略常数项和低阶项。
3. Graph Theory Foundations | 图论基础
A graph consists of vertices (nodes) and edges (arcs) joining pairs of vertices. A simple graph has no loops or multiple edges. The degree of a vertex is the number of edges incident to it, with a loop counting twice.
图由顶点（节点）和连接顶点对的边（弧）组成。简单图没有环或多重边。顶点的度数是与该顶点关联的边数，环在度数中计两次。
A path is a sequence of edges where no vertex repeats; a cycle is a closed path. A connected graph has a path between every pair of vertices. A tree is a connected graph with no cycles.
路径是指不重复顶点的边的序列；回路是闭合的路径。连通图中任意两个顶点之间都有路径。树是连通且无回路的图。
The complete graph Kₙ has n vertices and every possible edge between distinct vertices, giving n(n − 1) ÷ 2 edges. A bipartite graph has vertices divided into two sets with edges only between sets.
完全图 Kₙ 有 n 个顶点，且每对不同顶点之间都有边，共有 n(n − 1) ÷ 2 条边。二分图的顶点分为两个集合，边只在不同集合之间。
A graph can be represented by an adjacency matrix, where element aᵢⱼ is the number of edges from vertex i to vertex j, or by a distance matrix for weighted graphs.
图可以用邻接矩阵表示，其中元素 aᵢⱼ 表示从顶点 i 到顶点 j 的边数；对于带权图，还可以用距离矩阵表示。
4. Minimum Spanning Trees: Kruskal and Prim | 最小生成树：Kruskal 与 Prim 算法
A spanning tree of a connected graph is a subgraph that includes all vertices and is a tree. A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.
连通图的生成树是包含所有顶点且为树的子图。最小生成树（MST）是总边权最小的生成树。
Kruskal's algorithm lists all edges in ascending weight order and adds each edge unless it would form a cycle. It is useful when edges are already sorted or the graph is sparse.
Kruskal 算法按权重升序列出所有边，并添加每条边，除非它会形成回路。它适用于边已排好序或图较稀疏的情况。
Prim's algorithm starts at any vertex and repeatedly adds the cheapest edge connecting a vertex already in the tree to a vertex not yet in the tree. It can be implemented with a priority queue.
Prim 算法从任意顶点开始，反复添加连接树内顶点与树外顶点的最便宜边。它可以用优先队列实现。
Both algorithms always produce an MST if the edge weights are unique; if ties exist, different MSTs may have the same total weight but different edges.
当边权唯一时，两种算法总能产生同一个 MST；若存在相同权重，可能会产生总权重相同但边不同的多个 MST。
5. Dijkstra's Shortest Path Algorithm | Dijkstra 最短路径算法
Dijkstra's algorithm finds the shortest path from a start vertex to every other vertex in a weighted graph with non-negative edges. It uses permanent labels and temporary labels.
Dijkstra 算法用于在边权非负的带权图中，求从起点到所有其他顶点的最短路径。它使用永久标签和临时标签。
At each stage, choose the unvisited vertex with the smallest temporary distance, make its label permanent, and update neighbours by adding the edge weight. Record the previous vertex for traceback.
在每一步，选择拥有最小临时距离的未访问顶点，将其标签设为永久，并通过加上边权更新邻居。记录前驱顶点以便回溯路径。
The algorithm terminates when all vertices have permanent labels or when the target vertex is fully labelled. Follow the previous-vertex pointers backwards from the destination to the start to construct the shortest path.
当所有顶点都获得永久标签，或目标顶点已完成标记时，算法结束。从终点沿前驱顶点指针反向追踪到起点，即可构造最短路径。
Dijkstra's algorithm fails if any edge weight is negative because a shorter path might be discovered after a vertex is made permanent.
如果存在负权边，Dijkstra 算法会失效，因为某个顶点被设为永久后可能还会发现更短路径。
6. Critical Path Analysis: Activity Networks | 关键路径分析：活动网络
A project can be modelled as an activity-on-arc network where edges represent activities and vertices represent events. Each activity has a duration and may depend on predecessors.
项目可以建模为弧表示活动、顶点表示事件的网络。每项活动有持续时间，并可能依赖于前置活动。
can occur, found by a forward pass: EET(next) = max(EET(previous) + duration). Start at 0.
最早事件时间（EET）是事件最早可以发生的时间，由正向遍历求得：EET(下一个) = max(EET(前一个) + 持续时间)。起点为 0。
a backward pass: LET(previous) = min(LET(next) − duration). The final event has LET = EET.
最晚事件时间（LET）是事件最晚可以发生而不延误项目的时间，由反向遍历求得：LET(前一个) = min(LET(下一个) − 持续时间)。终点事件的 LET = EET。
iest start. Critical activities form a critical path, which determines the minimum project duration.
关键活动的总浮动时间为零：总浮动时间 = 最晚开始时间 − 最早开始时间。关键活动构成关键路径，决定最短项目工期。
7. Floats and Scheduling | 浮动时间与调度
Total float is the maximum time an activity can be delayed without delaying the whole project. Free float is the delay possible without affecting any successor. Independent float assumes worst-case predecessor and successor constraints.
总浮动时间是一项活动在不延误整个项目的前提下可以延迟的最大时间。自由浮动时间是不影响任何后续活动的可延迟时间。独立浮动时间假设最差的前驱和后续约束。
rliest start = latest finish − earliest finish. Critical activities have total float zero.
总浮动时间 = 最晚开始时间 − 最早开始时间 = 最晚完成时间 − 最早完成时间。关键活动的总浮动时间为零。
A Gantt chart displays activities on a horizontal time axis, often using critical activities first, then scheduling non-critical activities within their floats. It helps visualise resource smoothing.
甘特图在水平时间轴上显示活动，通常先安排关键活动，再在其浮动时间内安排非关键活动。它有助于可视化资源平滑。
Resource histograms show the number of workers or machines required over time. If a resource is over-allocated, delay non-critical activities, prioritise critical activities, or adjust durations.
资源直方图显示随时间所需工人或机器的数量。如果资源超配，可以延迟非关键活动、优先安排关键活动或调整持续时间。
8. Linear Programming: Formulation and Graphs | 线性规划：建模与图解
Linear programming (LP) maximises or minimises a linear objective function subject to linear inequalities. Define decision variables such as x and y, and express constraints as inequalities.
线性规划（LP）在若干线性不等式约束下最大化或最小化线性目标函数。需要定义决策变量（如 x 和 y），并将约束表示为不等式。
Plot the constraints on a coordinate grid, shade the unwanted regions, and identify the feasible region where all constraints are satisfied simultaneously. The feasible region is often a convex polygon.
在坐标网格上绘制约束，标出不可行区域，并确定同时满足所有约束的可行域。可行域通常为凸多边形。
The optimal solution occurs at a vertex of the feasible region. Evaluate the objective function at each vertex, or draw an iso-profit line and slide it parallel until leaving the region.
最优解出现在可行域的顶点处。计算每个顶点处的目标函数值，或绘制等利润线并
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图