Sillabo dell'insegnamento

• A - Fondamenti
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).
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
Metodi statistici di compressione. 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. Entropia e compressione dati. Ricerca di codici ottimali: metodo di Shannon, algoritmo di Shannon-Fano, algoritmo di Huffman, codifica aritmetica.
TIC - Teoria dell'Informazione e Codici
Metodi dinamici di codifica e compressione. Algoritmo di Bentley, Sleator, Tarjan e Wei: Move-To-Front (MTF) Codifica universale. Codifica degli interi. Codifica γ e δ di Elias. Codifica di Fibonacci. Unbounded searching (Bentley e Yao)
TIC - Teoria dell'Informazione e Codici
Metodi di compressione dati. Cenni sulla Teoria Algoritmica dell'Informazione. Teoria algoritmica dell' informazione e Compressione grammaticale. Compressione basata su dizionari. Algoritmi di Lempel-Ziv: LZ77 e LZ78. Analisi di LZ78.
TIC - Teoria dell'Informazione e Codici
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. Compressione e combinatoria delle parole