Salta al contenuto principale della pagina

ANALISI E PROGETTAZIONE DI ALGORITMI

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
  • PERIODO 2° Semestre
    MATERIALE DIDATTICO AULAWEB

    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

    Commissione d'esame

    ELENA ZUCCA (Presidente)

    PAOLA MAGILLO

    ALESSANDRO VERRI (Presidente Supplente)

    LEZIONI

    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
    17/06/2022 09:00 GENOVA Scritto 7 settembre aula 506
    08/07/2022 09:00 GENOVA Scritto 7 settembre aula 506
    06/09/2022 09:00 GENOVA Scritto 7 settembre aula 506
    18/01/2023 09:00 GENOVA Scritto 7 settembre aula 506
    09/02/2023 09:00 GENOVA Scritto 7 settembre aula 506