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
Nozioni di base sugli algoritmi
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. 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 34 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 : 8 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 10 ore.
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
Materiale didattico fornito dal docente e disponibile tramite la piattaforma elly.
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 se richiesto dal docente.
Altre informazioni
Il materiale didattico e' disponibile al sito web Elly
Obiettivi agenda 2030 per lo sviluppo sostenibile
Tra i problemi modellabili e risolvibili come problemi su grafi, ci sono problemi relativi all'uso efficiente delle reti (elettriche, di telecomunicazione, ecc.)
