Salta al contenuto principale della pagina

ANALISI E PROGETTAZIONE DI ALGORITMI

CODICE 80306
ANNO ACCADEMICO 2020/2021
CFU
  • 6 cfu al 2° anno di 8759 INFORMATICA (L-31) - GENOVA
    		•
    SETTORE SCIENTIFICO DISCIPLINARE INF/01
    LINGUA Italiano
    SEDE
  • GENOVA
    		•
    PERIODO 2° Semestre
    MATERIALE DIDATTICO AULAWEB

    PRESENTAZIONE

    L'obiettivo del corso è l'apprendimento e l'analisi dal punto di vista di
    correttezza ed efficienza di strutture dati e 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. 

     

    OBIETTIVI E CONTENUTI

    OBIETTIVI FORMATIVI

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

    MODALITA' DIDATTICHE

    Tradizionale.

    PROGRAMMA/CONTENUTO

    Metodologie di analisi e progettazione di algoritmi: notazioni asintotiche e correttezza e complessità di algoritmi ricorsivi (approfondimenti da ASD), correttezza di algoritmi iterativi, analisi ammortizzata, divide-et-impera, programmazione dinamica e algoritmi greedy.
    Algoritmi di ordinamento: algoritmi elementari e mergesort (richiami da ASD), quicksort, heapsort, delimitazione inferiore problema dell'ordinamento per confronti, algoritmi di ordinamento non per confronti.
    Strutture dati avanzate: heap, strutture union-find.
    Grafi: definizioni, rappresentazioni, visite, ordinamento topologico, componenti fortemente connesse, cammini minimi (algoritmo di Djikstra), minimo albero ricoprente (algoritmi di Prim e Kruskal).
    Teoria della NP-completezza: classi di complessità, problemi NP-completi, algoritmi di approssimazione.

    TESTI/BIBLIOGRAFIA

    Note a cura del docente.
    Per approfondimenti:
    Algoritmi e strutture dati. Demetrescu, Finocchi, Italiano. McGraw Hill. Seconda edizione, 2008.
    Introduzione agli algoritmi e strutture dati. Cormen, Leiserson, Rivest, Stein. McGraw Hill. Terza edizione, 2009.

    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
    27/01/2021 09:00 GENOVA Scritto aula 506
    18/06/2021 09:00 GENOVA Scritto aula 506
    09/07/2021 09:00 GENOVA Scritto aula 506
    26/07/2021 09:00 GENOVA Scritto aula 506
    07/09/2021 09:00 GENOVA Scritto aula 506
    19/01/2022 09:00 GENOVA Scritto aula 506