CODICE 80306 ANNO ACCADEMICO 2025/2026 CFU 6 cfu anno 2 INFORMATICA 8759 (L-31) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE INF/01 LINGUA Italiano SEDE GENOVA PERIODO 2° Semestre PROPEDEUTICITA Propedeuticità in ingresso Per sostenere l'esame di questo insegnamento è necessario aver sostenuto i seguenti esami: INFORMATICA 8759 (coorte 2024/2025) ALGORITMI E STRUTTURE DATI 80298 2024 MATERIALE DIDATTICO AULAWEB 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 ALESSANDRO VERRI Ricevimento: Appointment through email ENRICO PUPPO 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 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.
