IN420 - Teoria dell'Informazione - AA 2015-2016

Lezioni

Diario delle lezioni dell'AA 2015-2016


Le lezioni si tengono nel I semestre con il seguente orario:
  • [-] lunedì ore 9.00-11.00 (lezione, Aula 211/Laboratorio Informatico);
  • [-] lunedì ore 14.00-16.00 (esercitazioni, Laboratorio Informatico);
  • [-] giovedì ore 9.00-11.00 (lezione, Aula 311/Laboratorio Informatico).

Lezione n. 1 - Monday 21 September 2015

  • Presentazione del corso: libri di testo, valutazione in itinere, argomenti trattati. Descrizione del modello di Shannon. Distribuzione binomiale, distribuzione di Poisson, formula di Stirling, approssimazione dell'esponenziale. 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. Codifica per ripetizione: il codice R_3.

Lezione n. 2 - Thursday 24 September 2015

  • Decodifica a maggioranza del codice R_3. Valutazione del rapporto di verosimiglianza. Dimostrazione che la decodifica a maggioranza corrisponde alla decodifica che massimizza il rapporto di verosimiglianza. Decodifica piu' probabile. Introduzione ai codici a correzione d'errore. Codici Lineari: codice Hamming (7,4).

Lezione n. 3 - Monday 28 September 2015

  • Codici Lineari: matrice generatrice, matrice per il controllo della parita'. Definizione di sindrome. Decodifica per sindrome. Codici a blocchi. Codici Lineari: codice Hamming (7,4). Valutazione dell'errore nel caso del canale BSC con prob. di errore f. Proprieta' dell'entropia: regola della somma, scomposizione. Entropia relativa, Divergenza di Kullback-Lieber. Introduzione a Wolfram Mathematica. Calcolo simbolico. Linguaggi Funzionali. Applicazione del Calcolo Simbolico alla Teoria dell'Informazione. Esempi di Calcolo dell'Entropia

Lezione n. 4 - Thursday 1 October 2015

  • Proprieta` elementari della funzione entropia. Divergenza informazionale.

Lezione n. 5 - Monday 5 October 2015

  • 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. Operazioni su campi finiti. Implementazione di codici lineari. Calcolo del controllo di parita'. Calcolo della sindrome. Calcolo del nullspace.

Lezione n. 6 - Thursday 8 October 2015

  • Proprieta' dell'entropia: regola della somma, scomposizione. Entropia relativa, Divergenza di Kullback-Lieber.

Lezione n. 7 - Monday 12 October 2015

  • Definizioni delle operazioni base sui campi finiti con Mathematica. Implementazione di alcuni modelli di canale. Proprieta' elementari dell'entropia. Esempi di calcolo in cui l'operazione massimizza il contenuto di informazione. Principio di MAP: maximal a posteriori probability.

Lezione n. 8 - Thursday 15 October 2015

  • Definizione di insieme di delta-sufficienza. Calcolo dell'entropia grezza dell'insieme delta-sufficiente. Definzione di insieme di tipicita'. Principio di equipartizione asintotica. Teorema di Codifica della sorgente. Insiemi di tipicita'. Dimostrazione del Teorema come applicazione della legge dei grandi numeri.

Lezione n. 9 - Monday 19 October 2015

  • 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. 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. 10 - Thursday 22 October 2015

  • Codifica della sorgente. Lunghezza media delle parole codice. Entropia e lunghezza media. Codici Simbolici. Decodificabilita' unica. Codici Prefissi. Esempi.

Lezione n. 11 - Monday 26 October 2015

  • Codici Simbolici. Decodificabilita' unica. Codici Prefissi. Esempi.

Lezione n. 12 - Thursday 29 October 2015

  • Codici ottimali. Codifica di Huffman Codici a flusso. Modello Bayesiano.

Lezione n. 13 - Monday 9 November 2015

  • Implementazione di codici lineari. Calcolo della matrice generatrice. Forma canonica della matrice generatrice. Introduzione ai codici a flusso. Codici aritmetici.

Lezione n. 14 - Thursday 12 November 2015

  • Algoritmo di decodifica di un codice Aritmetico. Esempio di decodifica.

Lezione n. 15 - Monday 16 November 2015

  • 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. 16 - Thursday 19 November 2015

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

Lezione n. 17 - Monday 23 November 2015

  • mplementazione di vari modelli di canale: BSC (binary simmetric channel), BEC (binary eraser channel).

Lezione n. 18 - Thursday 26 November 2015

  • Canale discreto senza memoria. Informazione trasportata da un canale. Mutua informazione.

Lezione n. 19 - Monday 30 November 2015

  • 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. 20 - Thursday 3 December 2015

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

Lezione n. 21 - Thursday 10 December 2015

  • Dimostrazione Teorema codifica sorgente per canali discreti senza-memoria con rumore. Dimostrazione Teorema codifica sorgente per canali discreti senza-memoria con rumore.

Lezione n. 22 - Monday 14 December 2015

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

Lezione n. 23 - Thursday 17 December 2015

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

Lezione n. 24 - Monday 21 December 2015

  • Seconda Prova in Itinere Seconda Prova in Itinere