一文读懂A-level中的Decision 决策数学

Decision 决策数学是Alevel考试中比较独特的一个科目，分为D1和D2,考试内容是各种算法的详细操作。这个科目是为计算机专业打基础的。由于相对来说比较简单，所以很多学生在考Alevel数学和高数时会选择考这两个。

考纲改革之后，GCE考试D1 和D2都可以选，但IAL考试只能选D1。D2比较难，一般没有学生选择。D1一共考12种算法：Flow chart；Bubble sort; quick sort; Binary search; Bin-packing(3种); Kruskal's algorithm；Prim's algorithm; Dijkstra's algorithm; Route inspection algorithm; Activity network; Linear programming; Maximum matching algorithm.

每种算法本身难度并不大，但考试时会有关于算法的概念题或简答题出现，这也是学生容易丢分的地方。尤其是近几年，这类题所占分值很大，很多学生这块儿丢分严重，导致D1成绩始终上不去。

下表展示了近五年概念题和简答题所占分值及比例：

这些概念及相关的简答涉及到12种算法中的每一种，需要我们在学习的时候总结全面。今天，锦秋小编将对这些概念和简答做出全面总结！

常考概念

Graph: A graph consists of vertices which are connected by edges.

Degreeorvalencyororder: the number of edges incident to a vertex.

Path: A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.

Walk: A path in which you are permitted to return to vertices more than once.

Cycleor circuit: A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.

Tree: A connected graph with no cycles.

Spanning tree: A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a graph.

Minimum spanning tree: A spanning tree such that the total length of its arcs is as small as possible.

Early event time: is the earliest time of arrival at the event allowing for the completion of all preceding activities.

Late event time: is the latest time that the event can be left without extending the time needed for the project.

Critical activity:An activity is described as a critical activity if any increase in its duration results in a corresponding increase in the duration of the whole project.

Critical path:A path from the source node to the sink node which entirely follows critical activities.

Total float: The total float of an activity is the amount of time that its start may be delayed without affecting the duration of the project.

Matching: A matching is the 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y.

Bipartite graph:Consists of two sets of vertices, X and Y. the edges only join vertices in X to vertices in Y, not vertices within a set.

Maximal matching:A matching in which the number of arcs is as large as possible.

Complete matching:If both sets have n nodes, a complete matching is a matching with n arcs.

Alternating path:Starts at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately ‘not in’ or ‘in’ the initial matching. 

常考简答

1.  Describe how to carry out the first pass of a bubble sort on the numbers in the list.

Start at the beginning of the list. Pass through the list and compare adjacent values. For each pair of values

If they are in order, leave them.

If they are not in order, swap them.

2.   A list of n numbers needs to be sorted into descendingorder starting at the left-hand end of the list.

(a)  State which number in the list is guaranteed to be in the correct final position after the first pass. The smallest one

(b)  Write down the maximum number of passes required to sort a list of n numbers.

(c)  Write down the maximum number of compares required to sort a list of n numbers.

(d)  Write down the maximum number of swaps required to sort a list of n numbers.

3.   The binary search is applied to an ordered list of 1000 items. Determine the maximum number of iterations needed.

4.   It is not possible to draw a graph with an odd number of vertices of odd degree. Explain why not.

 Because the sum of the degrees is twice the sum of the number of edges.

5.   Describe the differences between Prim’s algorithm and Kruskal’s algorithm.

6.   State, giving a reason for your answer, which algorithm is preferable for a large network for find the minimum spanning tree?

7.   A minimum spanning tree for a connected network has n edges. State the number of vertices in the network.

关于D1的答题还有很多方法和技巧，彻底掌握这些，D1满分也是小菜一碟的。五六月份的Alevel考试越来越近了，为了让辛苦两年的学生们能取得理想的最终成绩，锦秋A-level开设数学、进阶数学、物理、化学、生物、经济学、会计学等课程，紧抓中国学生理科优势，进行课程组合化，配备海量国际背景的教师和专业助教团队，双管齐下，奠定每一位学员的之路。