A레벨_Further Mathematics(AS)_Decision 1 > A레벨
교재 : edexcel / 수강기간 : 30일
Decision Mathematics 1
Decision Mathematics 1 gives a brief overview of the field of discrete mathematics and some of the foundational problems that developed the field. These ideas later developed into the field of Computer Science, and here we look at the algorithms that were formulated to solve some of these initial problems.
Chapter 1: Algorithms
The concept of an algorithm is introduced, and the flow chart formulation of problem solving is presented. The chapter then looks at the following algorithms: the bubble sort and quick sort for sorting lists into order; the binary search algorithm to find items within ordered lists; and the First-fit, First-fit decreasing and Full Bin algorithms for solving the basic bin packing problem.
Chapter 2: Graphs and Networks
In this chapter we develop the language of Graph Theory necessary to allow us to formulate the problems we are going to solve. This area of Mathematics was developed simultaneously in different languages leading to more than one naming conventions. We then look at the ways we can use matrices to represent graphs.
Chapter 3: Algorithms on Graphs
The problem of finding minimum spanning trees for a network is solved using two distinct algorithms: Prim’s algorithm and Kruskal’s algorithm. The nearest neighbour algorithm is introduced, which helps find short paths connecting all nodes. Finally, the problem of finding the shortest path through a network is addressed using Dijkstra’s algorithm.
Chapter 4: Route Inspection
The concept of Eulerian and semi-Eulerian graphs are introduced, and how they affect circuits containing every arc exactly once. We then take on the famous ‘Chinese Postman Problem’ of finding the shortest path travelling every arc of a network using the route inspection algorithm, and considered the two cases where our start and end points are either the same or different.
Chapter 5: The Travelling Salesman Problem
The travelling salesman problem involves finding the shortest tour that visits every node once. It is divided between the classical problem, where each vertex must be visited only once, and the practical problem where vertices can be visited more than once. Using a combination of the nearest neighbour algorithm and minimum spanning trees, upper and lower bounds are found to constraint the solution to this problem.
Chapter 6: Critical Path Analysis
Dependency tables and activity networks are introduced, and the idea of using dummy arcs to carry dependence is used. Next critical activities are identified using early/late times, and the float of activities are calculated. We use Gantt charts to represent all the activities and their times, and use this information to create scheduling diagrams for either a fixed or variable number of workers.
Chapter 7: Linear Programming
Using the idea of decision variables and constraints, we reduce complex problems down to their fundamental variables. By carefully plotting the constraints on a graph, we use multiple methods to find the optimal solution to these problems, involving the case where integer valued solutions are required.
- 19 강의