Nella prima oarte 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. Nella seconda parte 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.
Al termine dell'insegnamento lo studente/la studentessa sarà in grado di:
Conoscere algoritmi e schemi algoritmici classic.
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.
Prima parte: 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.
Seconda parte: 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: Appointment through email
Ricevimento: Su appuntamento via email a enrico.puppo@unige.it Durante il periodo di lezione si possono fissare appuntamenti per gruppi di persone postando sul forum AulaWeb
ENRICO PUPPO (Presidente)
ALESSANDRO VERRI (Presidente)
In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica: https://corsi.unige.it/corsi/8759/studenti-orario
ANALISI E PROGETTAZIONE DI ALGORITMI
Prova scritta e orale.
Indicazioni per studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali sono disponibili a partire da https://corsi.unige.it/corsi/8759/studenti-disabilita-dsa
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.
Per ulteriori informazioni, consultare il modulo Aulaweb dell'insegnamento o contattare il docente.
