Algoritmi e Strutture Dati II

Programma del corso, anno accademico 1999/2000

Strutture Dati Avanzate.

B-Trees
Alberi Red-Black.
Estensione di Strutture Dati. Interval trees.
Heap Binomiali.
Analisi ammortizzata.
Heap di Fibonacci.
Algoritmi.

Reti per l'ordinamento.
Circuiti aritmetici.
Operazioni su matrici.
Polinomi ed FFT.
Algoritmi in Teoria dei Numeri. Crittografia a chiave pubblica. RSA.
String Matching.
Complessità Computazionale. NP-Completezza.
Algoritmi di Approssimazione.
Compressione Dati.

Codifica di Huffman adattiva.
Arithmetic Coding.
Algoritmi di Lempel-Ziv (LZ77, LZ78).
JPEG ed MPEG.
Algoritmi in Computer Graphics.

Testi di riferimento:
T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press - McGraw-Hill.
Mark Nelson, The Data Compression Book, Second Edition, M&T Books, 1995.
J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, Computer Graphics: Principles and Practice, Second Edition in C, Addison-Wesley, 1997.
Compiti di verifica a.a. 1997/98: 20nov97, 12gen98, 30gen98.
Compiti di verifica a.a. 1998/99: 26apr99, 24mag99, 17giu99.
Compiti di verifica a.a. 1999/2000: 26nov99, 14gen2000, 4feb2000 (ps, pdf).
Compiti di verifica a.a. 2000/2001: 30nov00 (ps, pdf) Valutazioni compitini a. a. 2000/2001.