This module is about two related issues:
How problems can be modelled as standard problems. We use the terminology "model a problem (of type) A as a problem (of type) B" to mean the following. Given a problem A, we do not try to solve it directly. Instead, we construct a problem B in such a way that the solution to B will tell us the solution to A.
We can imagine that we are given a "black box" that solves problem type B. We are not allowed to open it up to see how it works; all we can do is feed it a problem of type B, and get the solution. But by modelling problem A as problem B, we can use the black box to solve A, even though it was not designed to do this!
You met this idea in the last module, when we asked you to solve (e.g.) the network flow problem as a linear programming problem. We considered Mathematica as a "black box" that solves LP problems, and used it to solve the network flow problem.
Give examples of problems or data that can be modelled in terms of each of the following basic mathematical concepts:
Consider a project with many people involved, and many tasks to do. For each task T, we know:
In this problem we will consider how a directed network can be used for planning and management of such projects.
Hint: For this problem, make up a simple example and check that your solutions give the correct answer when applied to your example.
I am going to attend a big conference, with many talks, all with different start times, end times and durations. At any time, there are usually several talks happening simultaneously. I have decided I want to attend as many talks as possible.
I have the timetable for all the talks. You may assume that, if I attend a talk, then I will stay for its entire duration.
Investigate if this problem can be modelled as any of the following standard problems:
Description of some standard problems
You may search for these standard problems on the web if you think it is helpful.
Consider the following two problems:
These are both NP-complete problems, which are important in computer science. We know that any two NP-complete problems can be modelled as each other (or "reduced to" each other).
Do not submit an incomplete module! We are available to help you, and you can receive a short extension if you contact us.