MODELLI E ALGORITMI PER IL SUPPORTO ALLE DECISIONI

Nella prima parte del corso si introducono i principali strumenti per dare rappresentazioni di problemi reali (modelli matematici, di simulazione, in scala). In particolare, nell'ambito dei modelli matematici, su cui e' incentrato il corso, si introducono i grafi.

Nella seconda parte del corso, attraverso la discussione di alcuni (semplici) esempi reali, si illustra l'uso dei grafi come strumenti di rappresentazione astratta di problemi reali. Vengono discussi diversi problemi su grafi (cammino a costo minimo, albero di supporto a peso minimo, problemi di flusso, problemi di assegnamento) con le relative tecniche risolutive di cui si discute sia la correttezza che la complessita'.
In questa parte si discutono anche problemi di schedulazione con i relativi algoritmi di risoluzione.

Nella terza e ultima parte del corso si discutono nozioni di base di complessita' dei problemi, introducendo le classi P, NP, i problemi NP-completi. Viene discussa anche la difficolta' dei problemi in relazione alla difficolta' di inviduare soluzioni approssimate.