CODICE 80306 ANNO ACCADEMICO 2020/2021 CFU 6 cfu anno 2 INFORMATICA 8759 (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 ELENA ZUCCA Ricevimento: Su appuntamento. ALESSANDRO VERRI Ricevimento: Su appuntamento via email Commissione d'esame ELENA ZUCCA (Presidente) PAOLA MAGILLO ALESSANDRO VERRI (Presidente Supplente) LEZIONI Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale 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 appello Orario Luogo Tipologia Note 27/01/2021 09:00 GENOVA Scritto 18/06/2021 09:00 GENOVA Scritto 09/07/2021 09:00 GENOVA Scritto 26/07/2021 09:00 GENOVA Scritto 07/09/2021 09:00 GENOVA Scritto 19/01/2022 09:00 GENOVA Scritto