Programma del corso di
Algoritmi e strutture dati II
A.A. 1998/99
Dr. Angelo Monti

L'obiettivo del corso è lo studio e l'approfondimento degli aspetti fondamentali per la risoluzione di problemi mediante l'applicazione di appropriate tecniche di progettazione di algoritmi. Vengono curati in modo particolare gli aspetti metodologici.

Progetto ed analisi di algoritmi:

Il metodo "divide et impera":

quicksort e sua analisi al caso pessimo e al caso medio, quicksort randomizzato e sua analisi al caso pessimo e al caso medio, selezione in tempo lineare, selezione randomizzata e sua analisi al caso pessimo e al caso medio. (ref. 3. cap. 8, 10)

Analisi ammortizzata:

il metodo del potenziale, applicazioni: operazioni su pile, incremento di contatore binario, inserimento in tabelle dinamiche. (ref. 3. cap. 18)

Il metodo greedy:

selezione di attività, zaino a variabili reali, minimo albero ricoprente (algoritmo di Kruskal), cammino minimo su grafo (algoritmo di Dijkstra), codici di Huffman. (ref. 3. cap. 17, 24, 25, ref. 1. cap. 5.1)

Il metodo della programmazione dinamica:

prodotto di catena di matrici, la più lunga sottosequenza comune, cammini minimi su grafo (algoritmo di Floyd-Warshall), zaino a variabili 0/1, somma di sottoinsiemi (ref. 2. cap. 5, ref. 3. cap. 16, 26, 37.4)

Il metodo della ricerca locale:

il problema del massimo flusso (il metodo di Ford-Fulkerson e l'algoritmo di Edmonds-Karp) (ref. 1. cap 2, 5.1, ref 3, cap. 27)

Algoritmi di enumerazione. Ricerca esaustiva:

Backtracking: somma di sottoinsiemi, zaino a variabili 0/1, la k-colorazione, valutazione delle prestazioni (medoto di Monte Carlo) (ref. 2. cap. 7)

Branch-&-Bound: il 15-puzzle, zaino a variabili 0/1, il problema del commesso viaggiatore (ref. 2. cap. 8)

Tramite i seguenti links è possibile scaricare le due "prove" valide come esoneri: la prima riguarda una tesina sugli algoritmi greedy e la programmazione dinamica (formato Word '97, file zip da 63 Kb), mentre la seconda sono tre esercizi da risolvere mediante l'algoritmo opportuno in linguaggio C (formato Word '97, file zip da 47 Kb). Il mio ringraziamento va alle mie due instancabili colleghe con le quali ho condiviso queste fatiche: Roberta Civica e Laura Orso.

1° esonero	2° esonero

Testi consultati:
1 - G. Ausiello, A. Marchetti-Spaccamela, A. Protasi, "Teoria e progetto di algoritmi fondamentali", Franco Angeli 1985

2 - E. Horowitz, S. Sahni, "Fundamentals of computer algorithms", Computer Science Press 1978

3 - T. H. Cormen, C. E. Leiserson, R. L. Rivest, "Introduction to algorithms", McGraw-Hill 1990

Indietro