Nel primo modulo si illustra come analizzare gli algorimi dal punto di vista di correttezza ed efficienza, e si presentano alcuni algoritmi classici nella formazione di un informatico, assumendo dal corso di Algoritmi e Strutture Dati le nozioni base relative a complessità e strutture dati elementari. Nel secondo modulo si illustra come applicare nozioni fondamentali dalla teoria della probabilità nell’analisi di algoritmi randomizzati e come valutare i benefici della randomizzazione nella progettazione di algoritmi.
Apprendere algoritmi e schemi algoritmici classici imparando ad analizzare correttezza ed efficienza di un algoritmo. Apprezzare le potenzialità della randomizzazione nella progettazione di algoritmi attraverso semplici esempi.
Nozioni base su algoritmi e strutture dati.
Lezioni frontali.
Primo modulo: Complessità di algoritmi e di problemi. Principio di induzione, correttezza e complessità di algoritmi ricorsivi. Correttezza di algoritmi iterativi con invariante di ciclo. Grafi: algoritmi di Dijkstra, Prim e Kruskal, algoritmi per ordinamento topologico e componenti fortemente connesse. Programmazione dinamica. Teoria della NP-completezza: classe NP, riduzione polinomiale, classe NP-C, P=NP.
Secondo modulo: Algoritmi randomizzati di tipo Las Vegas e Montecarlo: algoritmi di ordinamento, taglio minimo, albero di un gioco, tolleranza a guasti bizantini, test di primalità e programmazione lineare. Cenni a teoria dei giochi e a problemi di occupazione.
Note a cura del docente.
Ricevimento: Su appuntamento.
Ricevimento: Appointment through email
ELENA ZUCCA SCHILLANI (Presidente)
PAOLA MAGILLO
ALESSANDRO VERRI (Presidente Supplente)
In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica
ANALISI E PROGETTAZIONE DI ALGORITMI
Prova scritta e orale.
La prova scritta verifica la capacità dello studente di mettere in pratica le nozioni viste a lezione. La prova orale verifica la comprensione dei concetti e la capacità di illustrarli in modo appropriato.
