Sillabo dell'insegnamento

• A - Fondamenti
TIC - Teoria dell'Informazione e Codici
Teorema di Shannon. Codici ottimali. Costo della trasmissione e condizioni di decifrabilità. Caso di costo del canale non uniforme e congettura di Schutzenberger. Codice di Shor. Problema del completamento dei codici. Codifica delle sorgenti estese.
TIC - Teoria dell'Informazione e Codici
Teoria dei codici a lunghezza variabile. Codici univocamente decifrabili. Algoritmo di Sardinas e Patterson. Disuguaglianza di Kraft-McMillan. Codici con ritardo (di decifrazione) finito. Codici prefissi. Codici bifissi. Codici massimali. Teorema di Schutzenberger sui codici massimali a ritardo limitato. Codici prefissi, codici bifissi e disuguaglianza di Kraft-McMillan.
TIC - Teoria dell'Informazione e Codici
Introduzione alla teoria dell'Informazione di Shannon. Lo schema di Shannon: sorgente e canale. Sorgenti senza memoria e canali senza rumore. Entropia della sorgente come misura dell'informazione prodotta dalla sorgente nell'unità di tempo. Proprietà dell'entropia. Codifica del canale. Costo della codifica: lunghezza media del codice. Problema di minimizzazione del costo. Entropia e compressione. Asymptotic Equipartition Property (AEP). Cenni sulla teoria algoritmica dell'informazione.
• B - Algoritmi
* ASC - Algoritmi su Strutture Combinatorie
Block-sorting data compression methods di Burrows e Wheeler. La Trasformata di Burrows-Wheeler (BWT). Invertibilità della BWT. Proprietà matematiche della BWT. Calcolo della BWT mediante il suffix-tree. Perchè l'output della BWT è più comprimibile: clustering effect. Metodo di compressione: BWT + MTF + Huffman. Analisi del metodo di compressione basato su BWT. Sorgenti con memoria e entropia empirica di ordine k. Clustering effect e parole bilanciate. Compressione ecombinatoria delle parole.
* ASC - Algoritmi su Strutture Combinatorie
Codifica universale. Codifica degli interi. Codifica γ e δ di Elias. Codifica di Fibonacci. Unbounded searching (Bentley e Yao). Metodi di compressione dati. Metodi statistici (Shannon). Teoria algoritmica dell' informazione e Compressione grammaticale. Compressione basata su dizionari. Algoritmo di Lempel-Ziv. Analisi di LZ78.
* ASC - Algoritmi su Strutture Combinatorie
Entropia e compressione dati. Ricerca di codici ottimali: metodo di Shannon, algoritmo di Shannon-Fano, algoritm di Huffman, codifica aritmetica. Metodi dinamici di codifica e compressione. Algoritmo di Bentley, Sleator, Tarjan e Wei: Move-To-Front (MTF). Block-sorting data compression methods di Burrows e Wheeler. La Trasformata di Burrows-Wheeler (BWT). Invertibilità della BWT. Proprietà matematiche della BWT. Calcolo della BWT mediante il suffix-tree. Perchè l'output della BWT è più comprimibile: clustering effect. Metodo di compressione: BWT + MTF + Huffman. Analisi del metodo di compressione basato su BWT. Sorgenti con memoria e entropia empirica di ordine k. Clustering effect e parole bilanciate. Compressione ecombinatoria delle parole.