Le lezioni si tengono nel II semestre con il seguente orario:

• [-] lunedì ore 14.00-16.00 (lezione, Aula F/Laboratorio Informatico);
• [-] mercoledì ore 14.00-16.00 (lezione, Aula C);
• [-] giovedì ore 16.00-18.00 (esercitazione, Laboratorio Informatico).

Lezione n. 1 - Wednesday 28 February 2018

Presentazione del Corso. Digressione sull'approssimazione del fattoriale con la formula di Stirling.

Lezione n. 2 - Thursday 1 March 2018

Introduzione alla programmazione con Mathematica. FrontEnd/Kernel. Regole di valutazione. Assegnazione immediata/posticipata. Liste. Matrici. Entropia Binaria. Grafico. Matrici.

Lezione n. 3 - Wednesday 7 March 2018

Entropia binaria. Il problema centrale della Teoria dell'Informazione: migliorare le caratteristiche del canale mediante opportuna codifica. Caratteristiche dei mezzi di informazione. Canale Binario Simmetrico.

Lezione n. 4 - Thursday 8 March 2018

Introduzione ai codici a correzione d'errore. Codici Lineari: codice Hamming (7,4). Codici Lineari: matrice generatrice, matrice per il controllo della parita'. Definizione di sindrome. Decodifica per sindrome.

Lezione n. 5 - Monday 12 March 2018

Codici a blocchi. Codici Lineari: codice Hamming (7,4). Valutazione dell'errore nel caso del canale BSC con prob. di errore f.

Lezione n. 6 - Thursday 15 March 2018

Definizione di Entropia. Richiami di calcolo delle probabilita'. Funzioni convesse. Disuguaglianza di Jensen. Applicazioni della disuguaglianza di Jensen, Disuaguaglianza di Gibbs. Formula ricorsiva per il calcolo dell'entropia. Decodifica per sindrome nel caso di matrici per il controllo di parita' generate in modo casuale.

Lezione n. 7 - Monday 19 March 2018

Regole di concatenazione per il calcolo dell'entropia. Distanza di Kullback Liebler o entropia relativa. Disuguaglianza di Gibbs.

Lezione n. 8 - Wednesday 21 March 2018

Implementazione di alcuni modelli di canale. Proprieta' elementari dell'entropia. Esempi di calcolo in cui l'operazione massimizza il contenuto di informazione.

Lezione n. 9 - Thursday 22 March 2018

Discussione sulla ricerca di codici lineari. Matrice generatrice del codice e relazione con il nucleo della trasformazione lineare associata. Implementazione in Mathematica della funzione che cerca buoni candidati per la matrice generatrice di un codice lineare.

Lezione n. 10 - Monday 26 March 2018

Introduzione ai codici a flusso. Codici aritmetici.

Lezione n. 11 - Wednesday 28 March 2018

Calcolo dell'entropia grezza dell'insieme delta-sufficiente. Definzione di insieme di tipicita'. Principio di equipartizione asintotica.

Lezione n. 12 - Thursday 29 March 2018

Calcolo dell'insieme di tipicità per la distribuzione ricavata da un'immagine. Svolgimento esercizi.

Lezione n. 13 - Wednesday 4 April 2018

Teorema di Shannon di codifica della sorgente (fine dimostrazione). Discussione sulle classi di complessita' polinomiale e non deterministica polinomiale. Introduzione ai codici simbolici.

Lezione n. 14 - Thursday 5 April 2018

Codici Simbolici. Decodificabilita' unica. Codici Prefissi. Esempi. Codici ottimali. Codifica di Huffman Codici a flusso. Modello Bayesiano.

Lezione n. 15 - Monday 16 April 2018

Correzione esonero. Codici Simbolici. Disuguaglianza di Kraft. Esistenza di un codice prefisso che soddisfa la disuguaglianza. Teorema di Shannon. Codici Huffman.

Lezione n. 16 - Wednesday 18 April 2018

Codici Aritmetici: algoritmo di codifica. Modelli probabilisitici usati nei codici aritmetici. Applicazioni della codifca aritmetica alla generazione di grafi casuali. Applicazioni dei codici aritmetici.

Lezione n. 17 - Thursday 19 April 2018

Algoritmo di compressione di Lempel-Ziv. Esempio di applicazione dell'algoritmo.

Lezione n. 18 - Monday 23 April 2018

Definizione di entropia condizionata. Mutua informazione. Proprieta` elementari. Algoritmo di compressione di Lempel-Ziv. Implementazione con alberi dei prefissi.

Lezione n. 19 - Thursday 26 April 2018

Implementazione di vari modelli di canale: BSC (binary simmetric channel), BEC (binary eraser channel). Canale discreto senza memoria. Informazione trasportata da un canale. Mutua informazione.

Lezione n. 20 - Monday 30 April 2018

Definizione di Capacita` di un Canale. Canali con rumore senza memoria.

Lezione n. 21 - Wednesday 2 May 2018

Dimostrazione Teorema codifica sorgente per canali discreti senza-memoria con rumore. Sequenze di tipicita` congiunta (sorgente-destinazione). Dimostrazione Teorema codifica sorgente per canali discreti senza-memoria con rumore. Sequenze di tipicita` congiunta (sorgente-destinazione).

Lezione n. 22 - Thursday 3 May 2018

Definizione di Capacita` di un Canale. Canali con rumore senza memoria. Definizione di probabilita` media di errore per blocco, e probabilita` di errore massimale per blocco e per bit.

Lezione n. 23 - Wednesday 9 May 2018

Dimostrazione Teorema codifica sorgente per canali discreti senza-memoria con rumore. Sequenze di tipicita` congiunta (sorgente-destinazione).

Lezione n. 24 - Thursday 10 May 2018

Dimostrazione della prima parte del Teorema di Shannon. Teorema delle Sequenze congiuntamente tipiche. Dimostrazione dell'esistenza del codice che realizza il rapporto di trasmissione e la probabilita' di errore prescritta nella prima parte del Teorema di Shannon.

Lezione n. 25 - Monday 14 May 2018

Dimostrazione della terza parte del Teorema di Shannon nel caso di canali con rumore senza memoria. Dimostrazione dell'esistenza del codice che realizza il rapporto di trasmissione e la probabilita' di errore prescritta nella prima parte del Teorema di Shannon.

Lezione n. 26 - Wednesday 16 May 2018

Il problema dell'Information Retrieval. Soluzioni semplici al problema dell'IR. Codici Hash: metodo della divisione, concatenazione di stringhe. Codici Hash.

Lezione n. 27 - Monday 21 May 2018

Calcolo della capacita` di un canale ottenuto per composizione parallela di due canali BSC. Calcolo dell'efficienza di un codice ottenuto come composizione di due codici Huffman.

Lezione n. 28 - Wednesday 23 May 2018

Calcolo della decodifica di una sequenza di Lempel-Ziv su un alfabeto ternario. Calcolo della capacita' di un zeta-channel. Calcolo della codifica di una sequenza con un codice aritmetico.

Lezione n. 29 - Thursday 24 May 2018

Collisioni nelle funzioni di Hash. Metodi per la risoluzione delle collisioni. Probabilita` di collisione. Paradosso del compleanno. Codici Binari.