Learning objectives
First of all the student needs to get familiar with the abstract representation of real problems, in particular through the use of graphs.
Next, the student needs to learn how to develop an algorithm and how to perform its analysis which concerns both the correctness of the algorithm (the ability of returning a solution of ecah instance of the problem) and the study of its complexity (number of operations required to return a solution).
Finally, the student needs to distinguish the problems on the basis of the categories defined by the complexity theory. In particular, the solution of large instnaces of problems classified as difficult ones, is usually unfeasible and one needs to think about using heuristic techniques.
Prerequisites
Basic notions about algorithms
Course unit content
In the first part of the course the main tools to give representations of real problems (mathematical models, simulation models, scale models). In particular, for what concerns mathematical models, on which we will focus the attention, graphs are introduced. This introductive part requires 4 .
In the second part of the course, through some (simple) applicative examples the use of graphs as powerful tools to give abstract representations of real problems is illustrated.
Different problems over graphs are discussed (shortest path, minimum spanning tree, flow problems, assignment,knapsack) with the related solution techniques, whose correctness and complexity is also dealt with.
This part requires 34 hours distributed as follows:
- shortest path : 4 h
- minimum spanning trees: 6 h
- flow problems: 10 h
- assignment problems: 6 h
- knapsack problems : 8 h
In the third and last part of the course some basic notions about the complexity of the problems are discussed. The classes P and NP, the NP-complete problems are introduced. It is also discussed the complexity of the problems in relation to the ability of delivering approximate solutions for them. This part requires 10 h.
Full programme
In the first part of the course the main tools to give representations of real problems (mathematical models, simulation models, scale models). In particular, for what concerns mathematical models, on which we will focus the attention, graphs are introduced.
In the second part of the course, through some (simple) applicative examples the use of graphs as powerful tools to give abstract representations of real problems is illustrated.
Different problems over graphs are discussed (shortest path, minimum spanning tree, flow problems, assignment,knapsack problems) with the related solution techniques, whose correctness and complexity is also dealt with.
In the third and last part of the course some basic notions about the complexity of the problems are discussed. The classes P and NP, the NP-complete problems are introduced. It is also discussed the complexity of the problems in relation to the ability of delivering approximate solutions for them.
Bibliography
Teaching material made available online through the Elly platform.
Teaching methods
The main way to transmit knowledge is through frontal lessons, during which the students are invited to interact in order to reach by themselves some conclusions.
Exercises are also proposed in order to consolidate what has been seen during the lessons.
No project is assigned and there is no laboratory activity.
Assessment methods and criteria
The written exam is made up by exercises and theoretical questions, which have the same impact on the final mark. There is no half-term examination. The oral examination is only made if required by the professor.
Other information
The teaching material is available at the Elly web site
2030 agenda goals for sustainable development
Problems which can be modeled and solved as graph problems include problems about the efficient use of networks (electrical, telecommunications, and so on)
