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.


AulaWeb a.a. 17/18

AulaWeb a.a. 16/17

AulaWeb a.a. 15/16

AulaWeb a.a. 14/15


Programma

  • Metodologie di analisi e progettazione di algoritmi: notazioni asintotiche e correttezza e complessità di algoritmi ricorsivi, correttezza di algoritmi iterativi, analisi di algoritmi randomizzati, analisi ammortizzata
  • 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, tabelle hash
  • 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. Un voto sufficiente allo scritto può essere conservato per i due appelli successivi.

Esempi di esercizi d'esame

Archivio esami

Corso di CASD disattivato (L-26 ad esaurimento)

Archivio esami

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: 6 luglio 2017