ANALISI E PROGETTAZIONE DI ALGORITMI

iten
Codice
80306
ANNO ACCADEMICO
2021/2022
CFU
6 cfu al 2° anno di 8759 INFORMATICA (L-31) GENOVA

6 cfu al 2° anno di 9011 MATEMATICA (LM-40) GENOVA

SETTORE SCIENTIFICO DISCIPLINARE
INF/01
LINGUA
Italiano
SEDE
GENOVA (INFORMATICA )
periodo
2° Semestre
materiale didattico

PRESENTAZIONE

L'obiettivo del primo modulo è apprendere e analizzare dal punto di vista di
correttezza ed efficienza 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. L'obiettivo del secondo modulo è imparare ad applicare nozioni fondamentali dalla teoria della probabilità nell’analisi di algoritmi randomizzati e imparare a valutare i benefici della randomizzazione nella progettazione di algoritmi.

 

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Apprendere algoritmi e schemi algoritmici classici, saper analizzare correttezza ed efficienza di un algoritmo

MODALITA' DIDATTICHE

Tradizionale.

PROGRAMMA/CONTENUTO

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.

TESTI/BIBLIOGRAFIA

Note a cura del docente.
 

DOCENTI E COMMISSIONI

Ricevimento: Su appuntamento.

Ricevimento: Appointment through email

Commissione d'esame

ELENA ZUCCA (Presidente)

PAOLA MAGILLO

ALESSANDRO VERRI (Presidente Supplente)

LEZIONI

MODALITA' DIDATTICHE

Tradizionale.

Orari delle lezioni

L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

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

Data Ora Luogo Tipologia Note