Algoritmi e strutture dati (2007/2008)

Corso a esaurimento

L'insegnamento è organizzato come segue:
Modulo Crediti Settore disciplinare Periodo Docenti
Teoria 8 INF/01-INFORMATICA 1° Q, 2° Q Roberto Segala
Laboratorio 2 INF/01-INFORMATICA 2° Q Isabella Mastroeni
Roberto Posenato

Obiettivi formativi

Modulo: Teoria
-------
Nel corso vengono esaminati i concetti di base per la formulazione di soluzioni algoritmiche a problemi concreti. Vengono studiate soluzioni a problemi formulati in termini di strutture matematiche astratte (liste, code, grafi, ...) e vengono descritte metodologie per identificare i problemi astratti che più si addicono allo studio di un problema concreto. Gli algoritmi vengono valutati e confrontati in base alla quantità di risorse che richiedono. Il corso si concentra inoltre sul ruolo che ha lo studio delle strutture di dati nella formulazione e valutazione di nuovi algoritmi.


Modulo: Laboratorio
-------
Nel corso di laboratorio di Algoritmi e Strutture Dati vengono raffinate le conoscenze dello studente circa la pratica della programmazione ad oggetti, soprattutto nell'implementazione di algoritmi e strutture dati avanzate. Le lezioni sono svolte in linguaggio Java di cui si assume una conoscenza di base.

Programma

Modulo: Teoria
-------
Il corso viene svolto in 64 ore di lezione frontale, di cui 32 ore nel primo quadrimestre e 32 ore nel secondo quadrimestre. Nelle 64 ore di lezione sono comprese 20 ore di esercitazione durante le quali gli studenti devono risolvere problemi specifici sotto la guida del docente.

Complessità: complessità degli algoritmi, notazione asintotica, metodi di risoluzione delle equazioni di ricorrenza, analisi ammortizzata.

Ordinamento e Selezione: insertion sort, merge sort, heap sort, quick sort, quick sort probabilistico. Studio della complessità degli algoritmi di ordinamento, limite inferiore dell'ordinamento per confronti. Algoritmi lineari, counting sort, radix sort, bucket sort. Algoritmi di selezione, minimo, massimo, selezione in tempo medio lineare, selezione in tempo pessimo lineare.

Strutture dati: Code, pile, liste, heap, alberi binari di ricerca, alberi RB, heap binomiali, insiemi disgiunti, tecniche di estensione di una struttura dati.

Grafi: Definizione e rappresentazione di un grafo, visita in ampiezza, visita in profondità, ordinamento topologico, componenti connesse, alberi di copertura di costo minimo (Prim e Kruskal), cammini minimi a sorgente singola (Dijkstra e Bellman-Ford) e multipla (Floyd-Warshall e Johnson), flusso massimo (Ford-Fulkerson, Karp), matching massimale su grafo bipartito.

Lezione 1:Introduzione al corso, Elementi di complessità.

Lezione 2:Complessità degli algoritmi, Notazione asintotica O(f), Omega(f), e Theta(f).

Lezione 3: Algoritmi ricorsivi, Risoluzione di equazioni di ricorrenza (metodo iterativo, metodo di sostituzione, teorema principale).

Lezione 4: Algoritmi di ordinamento, Insertion sort, merge sort, Studio della complessità, Stabilità e ordinamento in loco.

Lezione 5: Algoritmi di ordinamento: heap sort.

Lezione 6: Algoritmi di ordinamento: quick sort, quick sort probabilistico, Limite inferiore alla complessità di ordinamento per confronti.

Lezione 7:Algoritmi di ordinamento lineari: counting sort, radix sort, bucket sort.

Lezione 8:Algoritmi di Selezione. Tempi medio e peggiore lineari.

Lezione 9: Strutture dati elementari. Stack, code, liste,
Alberi binari di ricerca

Lezione 10:RB-alberi.

Lezione 11: Estensione di una struttura dati. Alberi di intervalli.

Lezione 12:Heap binomiali.

Lezione 13:Strutture per insiemi disgiunti.

Lezione 14:Programmazione dinamica.

Lezione 15:Algoritmi greedy.

Lezione 16:Grafi: definizione e rappresentazione.

Lezione 17:Visita di grafi. BFS, DFS.

Lezione 18: Ordinamento topologico. Componenti connesse.

Lezione 19:Alberi di copertura di costo minimo. Algoritmi di Kruskal e Prim.

Lezione 20:Cammini minimi. Algoritmi di Dijkstra e Bellman-Ford per sorgente singola.

Lezione 21:Cammini minimi. Algoritmi di Floyd-Warshall e Johnson per sorgenti multiple.

Lezione 22:Flusso massimo. Algoritmo di Ford-Fulkerson. Matching massimale su grafo bipartito.


Modulo: Laboratorio
-------
Lezione 1: Uso del meccanismo dell'Interfaccia. Esempio di applicazione con l'implementazione dell'ADT Lista, Coda e Pila.

Lezione 2: Uso dell'interfaccia Comparable. Implementazione degli algoritmi di ordinamento per inserimento (InsertionSort) e per passo calante (ShellSort).

Lezione 3: Tecniche di confronto di implementazioni. Confronto tra due implementazioni di algoritmi di ordinamento: QuickSort e MergeSort.

Lezione 4: Implementazioni dell'ADT HashTable.

Lezione 5: Implementazione di un algoritmo di programmazione dinamica: ricerca massima sottosequenza comune (MaxSSC).

Lezione 6: Implementazioni dell'ADT Albero e Albero di ricerca binario. Uso dell'interfaccia Iterator. Implementazioni metodi di visita.

Lezione 7: Implementazione di un algoritmo greedy: algoritmo di Kruskal.

Modalità d'esame

Modulo: Teoria
-------
L'esame di teoria di algoritmi e strutture dati consiste di una esercitazione scritta di due ore contenente tre esercizi di difficoltà crescente chee cercano di valutare sia le conoscenze acquisite che le capacità di ragionamento nell'ambito della materia. L'esercitazione scritta si intende superata se lo studente ottiene una votazione di almeno 18/30 considerando che ogni esercizio vale 1/3 del punteggio totale.

All'esercitazione scritta lo studente può portare un foglio formato A4 scritto su entrambe le facciate a penna di proprio pugno. Su ogni facciata il foglio deve riportare nome, cognome, e numero di matricola. Non sono imposti limiti ai contenuti del foglio A4.

L'esame di algoritmi e strutture dati è superato a condizione che il candidato ottenga una valutazione positiva anche nel modulo di laboratorio. La votazione proposta sarà la media ponderata tra il risultato della prova di teoria (75%) e della prova di laboratorio (25%). Chi ottiene una valutazione finale di almeno 24/30 può sostenere una prova orale facoltativa. In tal caso il voto finale dell'esame sarà basato puramente sulla prova orale senza tenere in alcun conto l'esito delle prove scritte.


Modulo: Laboratorio
-------
L'esame di laboratorio di Algoritmi e Strutture Dati consiste di una prova scritta contenente una serie di esercizi che richiedono la conoscenza delle esercitazione fatte in laboratorio. Questo significa che le esercitazioni stesse (comprensive di tutti i concetti ad esse collegate) e variazioni di esse sono da considerarsi argomento d'esame. L'obiettivo dell'esame e' quello di verificare la capacità di formulare un algoritmo o una struttura dati nel linguaggio Java. La prova si intende superata se il candidato ottiene una valutazione di almeno 16/30. Il risultato della prova di laboratorio viene integrato con il risultato della prova di teoria secondo le modalità descritte nel modulo di teoria.

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

Statistiche esiti
Esiti Esami Esiti Percentuali Media voti Deviazione Standard
Positivi 30.23% 21 3
Respinti 33.72%
Assenti 33.72%
Ritirati --
Annullati 2.32%
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
53.8% 0.0% 11.5% 3.8% 0.0% 3.8% 3.8% 7.6% 0.0% 7.6% 0.0% 3.8% 3.8% 0.0%

Valori relativi all'AA 2007/2008 calcolati su un totale di 86 iscritti. I valori in percentuale sono arrotondati al numero intero più vicino.