Informazioni in aggiornamento fino al 30/06/2026 CODICE 80306 ANNO ACCADEMICO 2026/2027 CFU 6 cfu anno 2 INFORMATICA 11896 (L-31 R) - 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 2025/2026) ALGORITMI E STRUTTURE DATI 80298 2025 INFORMATICA 11896 (coorte 2025/2026) ALGORITMI E STRUTTURE DATI 80298 2025 PRESENTAZIONE Nella prima parte si illustra come analizzare gli algoritmi 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 della 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 classici. 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. Tecniche di programmazione dinamica e tecniche golose. Algoritmi su grafi: visite, ordinamento topologico, componenti fortemente connesse, alberi di ricoprimento minimi, cammini minimi. Cenni di teoria della NP-completezza 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 dei docenti. Per approfondimenti: Cormen, Leiserson, Rivest, Stein, 2005, Introduzione agli algoritmi e strutture dati (Seconda edizione), McGraw Hill. (o meglio Terza edizione, in lingua inglese) 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: https://corsi.unige.it/corsi/8759/studenti-orario Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy ESAMI MODALITA' D'ESAME Test a quiz e prova orale. Il test ha il solo scopo di ammissione alla prova orale: sono ammessi gli studenti che superano una soglia minima di risposte esatte. 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 MODALITA' DI ACCERTAMENTO La prova orale verifica la comprensione dei concetti, la capacità di illustrarli in modo appropriato e di mettere in pratica le tecniche viste a lezione. ALTRE INFORMAZIONI Per ulteriori informazioni, consultare il modulo Aulaweb dell'insegnamento o contattare il docente.
