PRESENTAZIONE

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.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

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.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

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.

PREREQUISITI

Nozioni base su algoritmi e strutture dati.

MODALITA' DIDATTICHE

Lezioni frontali.

PROGRAMMA/CONTENUTO

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.

TESTI/BIBLIOGRAFIA

Note a cura del docente.
 

DOCENTI E COMMISSIONI

Commissione d'esame

ELENA ZUCCA SCHILLANI (Presidente)

PAOLA MAGILLO

ALESSANDRO VERRI (Presidente Supplente)

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica

Orari delle lezioni

ANALISI E PROGETTAZIONE DI ALGORITMI

ESAMI

MODALITA' D'ESAME

Prova scritta e orale.

MODALITA' DI ACCERTAMENTO

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.

Calendario appelli