Teoria dell'Informazione e Crittografia 2015/16

Orari del corso:

Argomenti trattati a lezione

  1. 29/09/2013. Presentazione del corso.
    PARTE 1
    Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Alberi e codici prefix-free (in breve, a prefisso). Decodificabilità istantanea e non.
  2. 30/09/2015. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia.
  3. 08/10/2015. Divergenza. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi.
  4. 13/10/2015. Entropia della distribuzione congiunta. Tasso del codice. Ottimalità asintotica dei codici di Shannon-Fano. Introduzione al codice di Huffman: geminazione e taglio.
  5. 15/10/2015. Teorema di preservazione ottimalità per geminazione (opportuna). Il codice di Huffman. Entropia condizionata. Tipi. Dimensioni e numero dei tipi.
  6. 20/10/2015. Codice multinomiale. Lunghezza del prefisso. Lunghezza del suffisso. Ottimalità asintotica del codice multinomiale. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete. Controdisuguaglianza di Kraft.
  7. 22/10/2015. Generazione di famiglie complete. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità finita del codice di Tunstall.
  8. 27/10/2015. Ottimalità asintotica dei codici di Tunstall. Codici LV-LV: sequenza Tunstall-Huffman e limiti teorici. Breve storia di LZ, LZW, BW. Codice universale di Ziv Lempel Studio della compressione massima di Ziv Lempel.
  9. 29/10/2015. Codice universale di Lempel e Ziv. Codice universale di Burrows-Wheeler.
  10. 03/11/2015. Approfondimenti ed applicaioni delle trasformate di BW e LZ. A cura di Nicola Prezza. Materiale
  11. 04/11/2013. Codice universale di Lempel, Ziv e Welch. Codifica B-B senza e con errore. Algoritmo greedy per un insieme di minima cardinalità e massima probabilità. Stima asintotica della cardinalità di un tipo.
  12. 10/11/2015. Codici δ-tipici e loro ottimalità asintotica.
    PARTE 2
    Codifica di canale: generalità.
  13. 12/11/2015. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard. Tasso di trasmissione e tasso di correzione. Il modello del canale: matrice di canale, funzioni di codifica e decodifica, tasso e probabilità di errore. Esempi. Capacità di un canale e Teorema di Shannon di canale (no dim).
  14. 17/11/2015. Significato della capacità del canale. Calcolo della capacità del canale simmetrico binario. Esercizio: Canale simmetrico q-ario e con cancellazione. Decodifica di canale a massima verosimiglianza su CSB, CSQ: decodifica a minima distanza di Hamming. Distanza minima di un codice e relazioni con la capacità di correzione.
  15. 19/11/2015. Cenni alle limitazioni asintotiche. Codici Correttori di Errore: introduzione ai codici algebrici. Matrice generatrice G (matrici equivalenti e in forma canonica). Peso minimo di un codice lineare. Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian.
  16. 24/11/2015. Codice di Hamming binario, ed esteso. Campi finiti: con p elementi e con p^r elementi. Albegra dei polinomi per i campi finiti (Qualche appunto). Codici BCH. Introduzione.
  17. 26/11/2015. Codici BCH 2-correttori. Esempio. Codici ciclici. Definizioni principali, polinomio generatore g, teorema principale (punti 1 e 2).
  18. 01/12/2015. Teorema principale, punti (3)..(6). Esempi su matrice generatrice dei codici ciclici. (Qualche appunto). Polinomio di controllo h e matrice H corrispondente Richiamo sulle radici primitive dell'unità nei campi finiti e relativi polinomi minimi. Uso dei polinomi minimi per determinare il polinomio generatore.
  19. 03/12/2015. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon.
  20. 10/12/2012. Codici convolutivi e l'algoritmo di Viterbi. Un trellis su cui fare esercizio
    PARTE 3
  21. 15/12/2015. Crittografia. Storia e terminologia. Cifrari a sostituzione monoalfabetica. Cifrari omofonici e nomenclatori. LUCIDI LEZIONE. Cifrari polialfabetici. Tecniche per scoprire lunghezza della chiave e chiave. Esempio pratico di cifrazione Vigenere e sua decrittazione. LUCIDI LEZIONE. Codici sorgenti in quattro linguaggi per l'automazione di quanto appena visto.
  22. 17/12/2015. Cifrari polialfabetici "algebrici". One-time-pad. Perfezione del one-time-pad. Automazione della crittografia. Il rotore di Jefferson. L'Enigma, storia, funzionamento, debolezze. LUCIDI LEZIONE. Codici a trasposizione. Il Data Encryption Standard. Funzionamento e decrittazione. LUCIDI DES. Appunti della lezione (by A. Dovier)
  23. 07/01/2016. L'Advanced Encryption Standard (AES). LUCIDI AES. Crittografia a chiave pubblica. Diffie e Merkle e il cifrario del fusto. Richiami. Algoritmo di Euclide tradizionale ed esteso. Correttezza e complessità. (Qualche appunto).
  24. 12/01/2016. Piccolo teorema di Fermat. Funzione e Teorema di Eulero. Esponenziale e logaritmo finito. Rivest Shamir e Adlemann e il cifrario RSA. Elgamal ed il logaritmo finito. LUCIDI LEZIONE.

Non svolto quest'anno:

Complessità di Kolmogorov. Definizioni e principali risultati.
Home page del corso