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.

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.