MODELLI E ALGORITMI PER IL SUPPORTO ALLE DECISIONI
cod. 1004642

Anno accademico 2015/16
3° anno di corso - Secondo semestre
Docente
Settore scientifico disciplinare
Ricerca operativa (MAT/09)
Field
Attività formative affini o integrative
Tipologia attività formativa
Affine/Integrativa
42 ore
di attività frontali
6 crediti
sede: PARMA
insegnamento
in - - -

Obiettivi formativi

Lo studente del corso deve innanzitutto familiarizzare con il concetto di rappresentazione astratta di un problema, nello specifico di rappresentazione di un problema tramite l'uso di grafi.

Deve poi comprendere come si sviluppa un algoritmo e come si effettua la sua analisi che comporta sia la verifica di corretezza (restituzione di una soluzione del problema) che lo studio della complessita' (numero di operazioni richieste per risolvere le istanze del problema).

Infine, lo studente deve imparare a distinguere i problemi sulla base di categorie di difficolta' definite dalla teoria della complessita'. In particolare, per istanze di grandi dimensioni di problemi classificati come difficili, l'uso di algoritmi corretti e' sconsigliabile (per via degli eccessivi tempi di esecuzione) e si puo' pensare di utilizzare tecniche euristiche.

Prerequisiti

- - -

Contenuti dell'insegnamento

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.

Programma esteso

Nella prima parte del corso si introducono i principali strumenti per dare rappresentazioni astratte 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 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'.

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.

Bibliografia

Dispense fornite dal docente e disponibili in rete.

Metodi didattici

La principale modalita' di trasmissione della conoscenza e' la lezione frontale, durante la quale si cerca di coinvolgere gli studenti per portarli da soli alle conclusioni. Sono previste anche esercitazioni per consolidare quanto visto nelle lezioni. Non sono assegnati progetti e non si svolge attivita' di laboratorio.

Modalità verifica apprendimento

L'esame scritto e' composto da esercizi e domande di teoria che hanno lo stesso impatto sulla votazione finale.
Non sono previste prove in itinere.
L'esame orale e' previsto solo su richiesta dello studente.

Altre informazioni

Il materiale didattico e' disponibile al sito lea.unipr.it