ALGORITHMS AND MODELS FOR DECISION SUPPORT

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.