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. Questa parte introduttiva richede 4 ore.

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, problemi knapsack) con le relative tecniche risolutive di cui si discute sia la correttezza che la complessita'. Questa parte richiede 30 ore cosi' suddivise:
- cammino a costo minimo : 4 ore
- albero di supporto a peso minimo: 6 ore
- problemi di flusso: 10 ore
- problemi di assegnamento: 6 ore
- problemi knapsack : 4 ore

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. Questa parte richiede 8 ore.