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 FORMATIVI

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

Modalità 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.

Commissione d'esame

ELENA ZUCCA (Presidente)

PAOLA MAGILLO

ALESSANDRO VERRI (Presidente Supplente)

Modalità didattiche

Tradizionale.

ORARI

L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

Modalità d'esame

Prova scritta e orale.

Modalità 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