Teoria dell'Informazione e Crittografia 2017/18

Orari del corso:

• mercoledí I fascia, aula 48
• venerdí II fascia, aula 48

Argomenti trattati a lezione

1. 04/10/2017. 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. 06/10/207. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza.
3. 11/10/2017. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Entropia della distribuzione congiunta. Tasso del codice. Ottimalità asintotica dei codici di Shannon-Fano.
4. 13/10/2017. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Il codice di Huffman. Entropia condizionata.
5. 18/10/2017. Tipi. Dimensioni e numero dei tipi e principali limiti. Codice multinomiale. Lunghezza del prefisso. Lunghezza del suffisso. Ottimalità asintotica del codice multinomiale.
6. 20/10/2017. Stima asintotica della cardinalità di un tipo. Complessità di Kolmogorov. Introduzione e principali limiti superiori.
7. 25/10/2017. Complessità di Kolmogorov: limite superiore per una stringa binaria lunga n con k 1. Cmplessità di sequenza di valori non indipendenti (come la temperatura). Visione dei "programmi minimi" come codice di sorgente: Equivalenza (media) della complessità' di Kolmogorov con la codifica ottima B-LV. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete.
8. 27/10/2017. Controdisuguaglianza di Kraft. Generazione di famiglie complete. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità finita del codice di Tunstall. (cenno a codici LV-LV: sequenza Tunstall-Huffman e limiti teorici)
9. 3/11/2017. Ottimalità asintotica dei codici di Tunstall. Breve storia di LZ, LZW, BW. Codice universale di Ziv Lempel Studio della compressione massima di Ziv Lempel.
10. 08/11/2017. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
11. 17/11/2017. Codifica B-B senza e con errore. Algoritmo greedy per un insieme di minima cardinalità e massima probabilità. Codici δ-tipici e loro ottimalità asintotica.

    PARTE 2

    Codifica di canale: generalità. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard.
12. 22/11/2017. 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). Significato della capacità del canale. Calcolo della capacità del canale simmetrico binario. Esercizio: Canale simmetrico q-ario e con cancellazione.
13. 24/11/2017. 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.
14. 29/11/2017. Codici Correttori di Errore: introduzione ai codici algebrici. Matrice generatrice G Condizioni necessarie dell'alfabeto per poter parlare di codici algebrici. Cenni ai campi finiti: con p elementi (Z_p) e con p^r elementi (con polinomi). Albegra dei polinomi per i campi finiti (Qualche appunto).
15. 01/12/2017. 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. Codice di Hamming ed esteso.
16. 06/12/2017. Codice di Hamming esteso. Codici BCH. Codici BCH 2-correttori. Esempio.
17. 13/12/2017. Codici ciclici. Definizioni principali, polinomio generatore g, Teorema principale. 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.
18. 15/12/2017. Uso dei polinomi minimi per determinare il polinomio generatore. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon.
19. 20/12/2017. Codici convolutivi e l'algoritmo di Viterbi. Un trellis su cui fare esercizio

    PARTE 3

    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.
20. 22/12/2017. 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. L'Advanced Encryption Standard (AES). LUCIDI AES.
21. 10/01/2018. Crittografia a chiave pubblica. LUCIDI LEZIONI 2018. Diffie e Hellman. Richiami. Algoritmo di Euclide tradizionale ed esteso. Correttezza e complessità. Diffie e Merkle e il cifrario del fusto. Piccolo teorema di Fermat. Funzione e Teorema di Eulero. Calcolo efficiente dell'Esponente in un campo finito.

    RESTO DEL CORSO, DA SISTEMARE

22. 15/01/2018. Rivest Shamir e Adlemann e il cifrario RSA. Elgamal ed il logaritmo finito.
23. Attacchi a Elgamal.
24. Codici ellittici.