A레벨_Further Mathematics(AS)_Decision 1 > A레벨_AS
교재 : edexcel / 수강기간 : 30일
Decision Mathematics 1
Decision Mathematics is the study using algorithms to solve discrete mathematics problems that are common in the real world and in computing.
Chapter 1 - Algorithms
We introduce the basic concept of an algorithm before looking at algorithms to sort numbers into order by using the bubble sort and quick sort. Then the problem of bin packing is studied including the concept of a lower bound and finding an optimal solution. Finally, we use binary search to find items in an ordered list.
Chapter 2 - Graphs and Networks
Here the basic language and concepts of graph theory are introduced. This chapter is essential preparation for the majority of the rest of the course. In particular, definitions around spanning trees, and the representation of graphs using matrices are important concepts used later.
Chapter 3 - Algorithms on graphs
Two methods of finding minimum spanning trees, Prim’s and Kruskal’s algorithms, are introduced, and we see how we can apply Prim’s to a distance matrix. We also see how to find short paths through networks of least distances with the Nearest Neighbour Algorithm. Finally, the shortest path between two nodes in a network is found using Dijkstra’s algorithm.
Chapter 4 - Route Inspection
First we look at the conditions for traversability on a graph to determine if an Eulerian Cycle exists, a semi-Eulerian path, or no such path exists. This then leads to the Route Inspection algorithm (commonly known as the Chinese Postman Problem) of finding the shortest route in a network that covers every arc and returns to its starting point.
Chapter 5 - The Travelling Salesman Problem
Here the classic problem of finding the shortest cycle visiting everyone node once is introduced. The two forms of the problem - the classical and practical problems - are discussed, and how they merge into one problem when considering networks of least distances. Because finding exact solutions is difficult, we instead look at using minimum spanning trees and nearest neighbour routes in clever ways to establish upper and lower bounds to ‘trap’ and find the optimal solution.
Chapter 6 - Critical Path Analysis
Often used in management for project and time management, Critical Path Analysis starts with going from a table of precedence to an activity network. We can then convert this into a Gantt Chart (Cascade Diagram) which then allows us to create a schedule for completion of the tasks in minimum time. We use the ‘Activity on arc’ convention throughout.
Chapter 7 - Linear Programming
Moving away from the world of graph theory for the final chapter, Linear Programming describes the process of taking multiple real world variables and setting up a series of constraints to allow us to find maximal or minimal solutions. We can do things like maximise profit, or minimise costs, etc. We also look at how we can find optimal integer solutions to these problems.
- 19 강의