Algoritmi per Internet e Web
“Compressione di Testi”

A.A. 2003/2004

 

 

Informazioni generali:

 

·       Docente: Prof. Paolo Ferragina, Dipartimento di Informatica, Pisa.

·       Impegno:  20 ore, per un totale di 3 CFU.

·    Orario delle lezioni: Lunedì 14-16 (B) e Mercoledì 14-16 (B), primo semestre (fino al primo compitino).

·    Per esercitarsi sugli argomenti del corso è disponibile ora una pagina sul Web.

 

 

---

 

Obiettivi del corso: Studio, progetto e analisi di algoritmi per la compressione di dati testuali. Dopo una breve introduzione sui fondamenti della Teoria dell'Informazione, si descriveranno dettagliatamente svariati algoritmi: Huffman, Huffword, Aritmetico, LZ77, LZ78 e LZW (con Gzip), Move-To_front, Run-Length-Encoding, trasformata BW (con Bzip). L'obiettivo di questa carrellata e' di fornire allo studente un quadro sufficientemente esteso, ma chiaramente non esaustivo, delle tecniche e degli algoritmi oggi disponibili per la memorizzazione compressa di archivi testuali. Si investigheranno inoltre alcune tecniche per la compressione degli interi, particolarmente utili per la realizzazione efficiente dei moderni Motori di Ricerca.

 

---

 

Modalità di esame:  scritto + prova  orale.

Durante la prova scritta gli studenti NON possono consultare i propri appunti o libri. Le date degli appelli sono consultabili via Web all'indirizzo della nostra Segreteria Didattica. Gli studenti che superano la prova scritta, nel caso vogliano incrementare il voto ottenuto devono sostenere la prova orale nello stesso appello. La data e il luogo dell'orale vengono comunicati dal docente durante la prova scritta. E' possibile tentare al massimo QUATTRO prove durante tutto l'anno accademico; si considera "un tentativo" anche il ritiro durante la prova scritta.

Testi di esame:

 

 

---

 

Libro di testo:

[MG]  Managing Gigabytes. I.H. Witten e A. Moffat e T.C. Bell. Morgan Kaufmann, 1999.
 

 

 

---

  

Programma del corso (registro elettronico delle lezioni)

 

Argomenti integrativi: