Corso di Complementi di Algoritmi e Strutture Dati (Laurea Triennale in Informatica L-31)
[per il corso del vecchio ordinamento (L-26 ad esaurimento), di 6 crediti, disattivato, vedi in fondo alla pagina]
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.
AulaWeb a.a. 12/13
AulaWeb a.a. 11/12
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 (algoritmo di Djikstra), 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
NOTE delle lezioni (versione a.a. 12/13) vedi AulaWeb a.a. 12/13
NOTE delle lezioni (versione a.a. 11/12)
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
Potete inoltre fare riferimento all'archivio esami del corso del vecchio ordinamento.
Corso di CASD disattivato (L-26 ad esaurimento)
AulaWeb a.a. 10/11
Archivio esami
Modalità d'esame
L'esame consta di prova scritta, prova orale e progetto. Il voto del progetto viene sommato al voto dello scritto e costituisce la base di partenza (che può anche abbassarsi!) al momento dell'orale.
La prova scritta si svolge contestualmente alla prova scritta di CASD del nuovo ordinamento.
Più precisamente, il testo della prova scritta sarà organizzato in tre parti:
- Esercizi base: su argomenti comuni a CASD vecchio e nuovo ordinamento (riferimento: registro lezioni e lucidi su AulaWeb a.a. 10/11)
- Esercizi avanzati: su argomenti di CASD nuovo ordinamento (riferimento: registro lezioni su AulaWeb a.a. 11/12 e note delle lezioni)
- Esercizio di programmazione (Java)
Chi si prenota per lo scritto dovrà indicare quale esame deve sostenere (vecchio o nuovo ordinamento). Chi deve sostenere CASD nuovo ordinamento dovrà svolgere gli esercizi base e quelli avanzati, chi deve sostenere CASD vecchio ordinamento e ha il voto del progetto dovrà svolgere solo gli esercizi base, chi deve sostenere CASD vecchio ordinamento e NON ha il voto del progetto dovrà svolgere gli esercizi base e l'esercizio di programmazione, OPPURE potrà optare (dichiarandolo al momento DELLA PRENOTAZIONE) per svolgere gli esercizi base e gli esercizi avanzati.
Ritorno alla pagina precedente
Ultima modifica: 26 settembre 2012
