Programma per l'anno accademico 2007-08
(Testo di riferimento: Robert Sedgewick.
Algoritmi in Java. Terza edizione. Pearson Education Italia, 2003, Milano)
Per tutte le strutture dati, salvo diversa indicazione, č prevista la
conoscenza della loro implementazione in Java. Fra parentesi quadre sono
indicate le sezioni del testo di riferimento corrispondenti agli argomenti
elencati. La corrispondenza fra argomenti svolti a lezione e sezioni del testo
č puramente indicativa, tesa a definire un sottoinsieme di sezioni che possano
coprire gli argomenti del corso.
- Modello di analisi dei costi, equazioni di ricorrenza e concetto di upper/lower bound
[2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7]
- Cenno alla Metodologia "divide et impera" e "master
theorem" [5.2]
- Richiami su strutture dati lineari (liste, pile, code) [Cap. 3
(richiami), 4.0, 4.1, 4.2, 4.3, 4.4, 4.5, 4.7]
- Alberi
 | Alberi n-ari [5.4]
 | Tipo astratto, implementazione, operazioni ed algoritmi |
| Attraversamento di alberi (visite in profonditā, visita in
ampiezza) |
|
| Alberi binari [5.5, 5.6, 5.7]
| Implementazione, operazioni ed algoritmi |
| Attraversamento di alberi binari (visite in profonditā, visita
in ampiezza) |
|
| Alberi binari di ricerca (BST) [12.6, 12.7, 12.8, 12.9, 13.0,
13.4 (sono i red-black, possono essere studiati in alternativa
agli alberi AVL)]
| Implementazione, operazioni ed algoritmi |
| Alberi bilanciati (AVL, senza codice Java): proprietā ed
algoritmi per il mantenimento del bilanciamento (rotazioni) |
|
Heap [9.0, 9.1, 9.2, 9.3, 9.5]
| operazioni, rappresentazione ed algoritmi |
| applicazione alle code di prioritā |
Ordinamento [6.1, 6.3, 6.4, 6.6, 7.1, 7.2, 8.1, 8.3, 9.4]
| SelectionSort, QuickSort, HeapSort, MergeSort, InsertionSort |
| Alberi di decisione e lower bound |
| Lower bound dell'ordinamento |
Hashing [14.0, 14.1, 14.2, 14.3, 14.4]
| tavole hash |
| funzioni hash |
| tecniche di gestione delle collisioni |
Grafi [Non presenti nel testo di riferimento. Possono essere
studiati sul volume [2], capitoli da
17 a 21 (il capitolo 21 č
disponibile online)]
| Definizioni e proprietā |
| Rappresentazioni dei grafi |
| Attraversamenti di un grafo (DFS e BFS) |
| Applicazioni della DFS (ordinamento topologico e individuazione cicli) |
| Cammini minimi (Dijkstra) |
| Alberi ricoprenti minimi (Kruskal e Prim) |
Altro materiale per la preparazione dell'esame
Č bene precisare che nelle lezioni, nelle esercitazioni e nell'attivitā di
laboratorio, la cronologia degli argomenti affrontati e sviluppati non coincide
necessariamente con quella che si evince in maniera naturale dal programma
illustrato. |
