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, problemi knapsack) 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.
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,problemi knapsack) 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 elly.dii.unipr.it
Obiettivi agenda 2030 per lo sviluppo sostenibile
- - -
