Corso di Complementi di Algoritmi e Strutture Dati (Laurea Triennale in Informatica L-31)
Docenti: Elena Zucca e Paola Magillo
Obiettivo
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.
Dal 15/16 prevede 9 CFU mentre le precedenti edizioni erano di 8 CFU.
Programma
- Metodologie di analisi e progettazione di algoritmi: notazioni asintotiche e correttezza e complessità di algoritmi ricorsivi, correttezza di algoritmi iterativi
- Algoritmi di ordinamento: algoritmi elementari (insertsort, selectsort); mergesort; quicksort (diverse versioni, calcolo complessità caso medio); heapsort; delimitazione inferiore problema dell'ordinamento per confronti; algoritmi di ordinamento non per confronti (integer sort, counting sort, radix sort)
- Strutture dati: heap, strutture union-find, alberi AVL
- Tecniche algoritmiche: divide-et-impera, programmazione dinamica, algoritmi greedy
- Grafi: definizioni, rappresentazioni, visite, ordinamento topologico, componenti fortemente connesse, cammini minimi (algoritmi di Djikstra e Floyd-Warshall), minimo albero ricoprente (algoritmi di Prim e Kruskal)
- Teoria della NP-completezza: problemi astratti e concreti, classe P, algoritmi di verifica, classe NP, NP-completezza, prova diretta di NP-completezza per bounded halting problem, prova di NP-completezza per riduzione di 3SAT e CLIQUE, algoritmi di approssimazione (esempio: VERTEX COVER)
Testi di riferimento
Le note delle lezioni sono disponibili su AulaWeb. Per approfondimenti potete consultare:Algoritmi e strutture dati di Demetrescu, Finocchi, Italiano
Introduzione agli algoritmi e strutture dati di Cormen, Leiserson, Rivest, Stein (terza edizione)
Modalità d'esame
L'esame consta di una prova scritta e una prova orale. Per sostenere l'orale occorre aver superato lo scritto (almeno 18). Il voto dello scritto costituisce la base di partenza (che può anche abbassarsi!) al momento dell'orale. Durante l'esame scritto è possibile consultare le note. Un voto sufficiente allo scritto può essere conservato per i due appelli successivi.Esempi di esercizi d'esame
Corso di CASD disattivato (L-26 ad esaurimento)
Modalità d'esame: la prova scritta si svolge contestualmente alla prova scritta di CASD del nuovo ordinamento.
Chi deve sostenere l'esame del corso disattivato è pregato di contattarmi per mail al momento della prenotazione dello scritto.
Ritorno alla pagina precedente
Ultima modifica: 18 febbraio 2018