. |
Algoritmi e Strutture Dati
OBIETTIVI FORMATIVINel corso di teoria 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. Nel corso di laboratorio vengono raffinate le conoscenze dello studente circa la pratica della programmazione a 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. ATTIVITÀ FORMATIVEIl corso di teoria 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. Il corso di laboratorio viene svolto in 24 ore di esercitazione in laboratorio suddivise in 8 lezioni da 3 ore ciascuna. Si ricorda che il corso vale 2 CFU, per cui sono previste ulteriori 25 ore di lavoro individuale da svolgersi presso i laboratori didattici. PROGRAMMA DEL CORSO
LIBRI DI TESTO
PIANO DELLE LEZIONILezione 1:Introduzione al corso, Elementi di complessità.Riferimenti: [CLR] Capitolo 1. Si consiglia di ripassare il materiale dei capitoli 3 e 5.
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,
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.
PIANO DELLE ESERCITAZIONI DI LABORATORIOLezione 1: Uso del meccanismo dell'Interfaccia . Esempio di applicazione
con l'implementazione dell'ADT Lista, Coda e Pila.
Lezione 2: Uso dell'interfaccia 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
Lezione 7: Implementazione di un algoritmo greedy: algoritmo di Kruskal.
MODALITÀ DI VERIFICA
L'esame di algoritmi e strutture dati consiste di una esercitazione scritta
seguita da un eventuale colloquio orale facoltativo. Per superare l'esame è necessario
ottenere una valutazione di almeno 18/30 nell'esercitazione scritta e nell'eventuale colloquio
orale. Per poter sostenere il colloquio orale è necessario ottenere una valutazione di
almeno 24/30 sull'esercitazione scritta. |
. |