MASTER in CALCOLO SCIENTIFICO
Corso di Algoritmi e Strutture Dati
Dott.ssa Tiziana CALAMONERI
ESAMI
MARTEDI' 4 MARZO 2003 ore 14.30 in via Salaria 113, III piano, stanza 334.
Si prega comunicare preventivamente l'intenzione di sostenere l'esame.
LINEE GUIDA
1. Il filo conduttore del corso: la complessità computazionale (pp 21-28 e pp 33-50)
Ordine di grandezza del tempo di esecuzione di un algoritmo (p 21 e pp 33-36)
Complessità temporale asintotica
Notazione asintotica: notazione O, notazione Theta, notazione Omega, algebra della notazione asintotica (pp 22-28 e pp 46-50).
Regole generali per calcolare la complessità temporale asintotica di un algoritmo.
Un esempio di ottimizzazione della complessita': il problema dell'ordinamento (pp 129-174 e pp 230-254).
Ordinamenti "naif": bubble sort, insertion sort, selection sort, con complessità O(n^2).
Ordinamenti più sofisticati: cenno a heap sort e merge sort, con complessità O(n log n).
Il problema della complessità spaziale: cenno a Quick sort, con complessità nel caso medio O(n log n).
Teorema della limitazione inferiore della complessità temporale di un algoritmo di ordinamento per confronti.
"Trucchi" per progettare algoritmi di ordinamento lineari: cenno a Counting sort, Bucket sort, Radix sort.
2. Il problema dei dizionari (pp 185-237 e pp 230-254)
Definizione di insieme dinamico di dati e di dizionario (p 185).
Un primo banale esempio: l'array disordinato (pp 168-170).
Passaggio all'array ordinato e vantaggio dell'uso della ricerca dicotomica (pp 171-178).
Problema dello scorrimento in fase di inserimento e cancellazione: la lista concatenata ordinata. Impossibiltà all'accesso casuale (pp 192-194).
Tabella ad indirizzamento diretto. Obbligo di allocare memoria proporzionale all'universo delle chiavi (pp 207-209 e p 178).
Soluzione del problema precedente tramite tabelle hash. Il problema delle collisioni. Il fattore di carico e l'ipotesi di uniformità semplice della funzione hash (pp 209-214 e pp 178-186).
Soluzione delle collisioni tramite concatenzaione (liste di trabocco) e tramite indirizzamento aperto. Scansione lineare, quadratica e hashing doppio. Problema della impossibilità di cancellare fisicamente (pp 219-223).
Una struttura dati più sofisticata: alberi binari di ricerca (pp 229-237).
Definizione di ABR. Visita in ordine simmetrico per ottenere la lista ordinata degli elementi.Ricerca di un elemento.
Cenno ad inserimento e cancellazione.
Il problema della dipendenza della complessità dall'altezza dell'albero: cenno ad alberi bilanciati (pp 185-237 e pp 186-192).
Il problema del numero di accessi a memoria secondaria: B-alberi (pp 185-237 e pp 200-202+205).
3. Un problema di cammino minimo (pp 447-462+491-ss e pp 265-293)
Definizione di grafo e possibili strutture dati per la sua memorizzazione (pp 447-449 e pp 265-276).
Visita di un grafo (pp 450-462+503-506 e pp 279-287).
Un problema di cammino minimo da una sorgente prefissata e sue applicazioni nella realtà.
Il caso non pesato (pp 453-456).
Il caso pesato: l'algoritmo di Dijkstra (pp 503-506 e pp 287-293).
La problematica dei pesi non negativi (p 492).
4. Il problema del minimo albero ricoprente (pp 477-486 e pp 309-317)
Il problema del minimo albero ricoprente e sue applicazioni nella realtà.
L'algoritmo di Prim (pp 483-486 e pp 311-313).
L'algoritmo di Kruskal (pp 482-483 e pp 314-317).
Aumentare l'efficienza avvalendosi di opportune strutture dati (cenno a union-find-set per l'algoritmo di Kruskal e a all'heap per l'algoritmo di Prim).
5. Problemi algebrici (pp 94-96; pp 366-371e pp 697-698)
Il prodotto tra due interi di n cifre. Equazione di ricorrenza. (pp 94-96)
Il prodotto tra due matrici di dimensione n x n. L'algoritmo di Strassen. Equazione di ricorrenza per il numero di prodotti e per il numero di somme (pp 366-371e pp 697-698).
6. Problemi enumerativi (pp 80-94)
Generazione di tutti i sottinsiemi di un insieme.
Generazione di tutte le permutazioni su n elementi.
Il problema delle 8 regine: il metodo del backtracking.
7. Il problema della bisaccia (pp 100-110)
Bisaccia a variabili reali.
Bisaccia a variabili intere.
Il metodo del branch & bound.
8. Il problema dei problemi (pp 863-920 e pp 131-160)
Tempo polinomiale. Problemi e codifica. La classe di complessità P. Verifica. La classe di complessità NP. Riduzioni polinomiali. NP-completezza. Enunciato del teorema di Cook.
Alcuni esempi di riduzioni: il problema della cricca, il problema della copertura di vertici.
Algoritmi di approssimazione. Scostamento garantito. Un algoritmo approssimante per il problemadella copertura dei vertici. Un algoritmo approssimante per il problema del commesso viaggiatore con l'ipotesi delle disuguaglianze triagolari.
Non approssimabilita'. Dimostrazione di non approssimabilità del problema del commesso viaggiatore.
POSSIBILI TEMI DI APPROFONDIMENTO
* Il Quicksort: l'algoritmo e la sua complessita' nel caso peggiore, medio e migliore
* Gli Alberi Binari di Ricerca e le operazioni che si possono implementare su di essi: ricerca, inserimento, cancellazione, ricerca del successore **NON DISPONIBILE**
* La struttura dati heap e l'heapsort **NON DISPONIBILE**
* L'algoritmo di Bellman-Ford per la ricerca dei cammini minimi da sorgente singola **NON DISPONIBILE**
* Applicazioni della visita in profondita': ordinamento topologico e componenti fortemente connesse (pp 465 ss)
* Una riduzione a scelta tra quelle presenti sul [CLR] e non fatta a lezione
LIBRI DI TESTO CONSIGLIATI
[CLR] T.H. Cormen, C.E. Leiserson, R.L. Rivest "Introduction to Algorithms"The MIT Press, Mc-Graw Hill Book Company (anche in italiano ed. Jackson Libri).
[ASP] G. Ausiello, A. Marchetti-Spaccamela, M. Protasi "Teoria e Progetto di Algoritmi Fondamentali" Franco Angeli