Corso di Complementi di Algoritmi e Strutture Dati (Laurea Triennale in Informatica)
Docente: Elena Zucca
Attenzione: si tratta del corso del nuovo ordinamento (L-31), attivato per la prima volta in quest'anno accademico, di 8 crediti.
Il corso del vecchio ordinamento (L-26 ad esaurimento), di 6 crediti, è disattivato, per le modalità di esame 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 ad algoritmi, complessità e strutture dati elementari.
AulaWeb a.a. 11/12
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 (non viene conservato in caso di orale fallito).
Programma
- Metodologie di analisi e progettazione di algoritmi: notazioni asintotiche e correttezza e complessità di algoritmi ricorsivi (richiami da ASD), correttezza di algoritmi iterativi
[NON FATTO: analisi di algoritmi randomizzati, analisi ammortizzata, programmazione dinamica e algoritmi greedy (approfondimenti di ASD)]
- 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 avanzate: alberi binari di ricerca (richiami da ASD), alberi AVL e B-alberi, strutture union-find
[NON FATTO: tabelle hash (approfondimenti di ASD)]
- 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 provvisoria)
Per approfondimenti potete consultare:
Algoritmi e strutture dati di Demetrescu, Finocchi, Italiano, disponibili in biblioteca tre copie
Introduzione agli algoritmi e strutture dati di Cormen, Leiserson, Rivest, Stein, disponibili in biblioteca: una copia della terza edizione in italiano, due copie di un'edizione precedente (una in italiano, una in inglese)
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
Per suggerimenti e commenti si prega di scrivere a: Elena Zucca zucca@disi.unige.it
Ultima modifica: 2 febbraio 2012
|
