Teoria dell'Informazione, Crittografia e Complessità 2010/2011

Orari del corso:

• lunedí II fascia (10:30 - 5)
• martedí II fascia (10:30 - 49)
• giovedí I fascia (8:30 - 5)

Argomenti trattati a lezione

1. 27/09/2010. Presentazione del corso. Discussione sul concetto di informazione.
2. 30/09/2010. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Decodificabilità istantanea e non.
3. 04/10/2010. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice.
4. 07/10/2010. Entropia. Divergenza. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Tasso del codice.
5. 11/10/2010. Entropia della distribuzione congiunta. Ottimalità asintotica dei codici di Shannon-Fano. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna).
6. 12/10/2010. Il codice di Huffman. Entropia condizionata, mutua informazione e loro relazioni. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso.
7. 14/10/2010. Ottimalità asintotica del codice multinomiale. Descrizione con variabili aleatorie di una sorgente di Informazione. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete. Contro-disuguaglianza di Kraft. Generazione di famiglie complete.
8. 18/10/2010. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità degli stessi. Rapporti asintotici del tasso dei codici di Tunstall con l'entropia della sorgente.
9. 19/10/2010. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel (e cenni pratici, ad esempio la variante Deflate).
10. 21/10/2010. Codice universale di Burrows-Wheeler. Codice universale di Lempel, Ziv e Welch.
11. 25/10/2010. Codici LV-LV. Limiti e codici asintoticamente ottimi. Codifica B-B. Valutazione del tasso in codifica priva di errore. Modelli con errore: ricerca di una famiglia ottima. Determinazione delle dimensioni di un tipo T con il metodo probabilistico.
12. 26/10/2010. Codici δ-tipici e Secondo Teorema di Shannon. Introduzione alla Complessità di Kolmogorov.
13. 28/10/2010. Complessità di Kolmogorov (incondizionata e condizionata). Indipendenza dal formalismo. Limiti superiori. Complessità di Kolmogorov di una stringa binaria.
14. 4/11/2010. Complessità di una stringa binaria in un tipo. Confronti con codifica Shannoniana: Codice B-LV indotto dalla Complessità di Kolmogorov e sua ottimalità asintotica.
15. 8/11/2010. Codifica di canale: generalità. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard. Il modello del canale: matrice di canale, funzioni di codifica e decodifica, tasso e probabilità di errore.
16. 9/11/2010. Esempi. Capacità di un canale e Teorema di Shannon di canale (no dim). Significato della capacità del canale. Calcolo della capacità dei canali: inutile, senza rumore, deterministico. Capacità del canale simmetrico binario. Esercizio: Canale simmetrico q-ario.
17. 11/11/2010. Discriminazione di Ipotesi Statistiche: a massima verosimiglianza e a massima probabilità a posteriori. 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. Relazioni tra tasso di correzione la Probabilità di errore.
18. 15/11/2010. Tasso di trasmissione, Tasso di correzione, loro relazioni nei codici. Limitazioni di Singleton e Plotkin. e Hamming, e Gilbert. Studio asintotico delle limitazioni di Hamming e Gilbert.
19. 16/11/2010. Codici Correttori di Errore: introduzione ai codici algebrici. Campi finiti: con p elementi e con p^r elementi. Albegra dei polinomi per i campi finiti.
20. 18/11/2010. 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.
21. 22/11/2010. Codice di Hamming binario ed esteso. Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore.
22. 23/11/2010. Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori.
23. 25/11/2010. Codici ciclici. Definizioni principali, polinomio generatore, teorema principale (no dim). Esempi su matrice generatrice dei codici ciclici. Polinomio di controllo h e matrice H corrispondente.
24. 29/11/2010. Richiamo sulle radici primitive dell'unità nei campi finiti e relativi polinomi minimi. 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.
25. 06/12/2010. Codici convolutivi e l'algoritmo di Viterbi. Valutazione del corso (I modulo).
26. 07/12/2010. Crittografia. Storia e terminologia. Cifrari a sostituzione monoalfabetica. Cifrari omofonici e nomenclatori. LUCIDI LEZIONE.
27. 09/12/2010. Cifrari polialfabetici. Tecniche per scoprire lunghezza della chiave e chiave. Esempio pratico di cifrazione Vigenere e sua decrittazione. LUCIDI LEZIONE.
28. 13/12/2010. 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.
29. 14/12/2010. Codici a trasposizione. Il Data Encryption Standard. Funzionamento e decrittazione. LUCIDI LEZIONE.
30. 17/12/2010. Richiami. Algoritmo di Euclide tradizionale ed esteso. Correttezza e complessità. Piccolo teorema di Fermat.
31. 20/12/2010. Funzione e Teorema di Eulero. Esponenziale e logaritmo finito. L'Advanced Encryption Standard (AES). LUCIDI LEZIONE.
32. 21/12/2010. Crittografia a chiave pubblica. Diffie e Hellman e il logaritmo finito. Diffie e Merkle e il cifrario del fusto. Rivest Shamir e Adlemann e il cifrario RSA. LUCIDI LEZIONE.
33. 10/01/2011. Richiami di complessità. Problemi e linguaggi. Macchine di Turing deterministiche a k-nastri. Classi in tempo. Le classi P ed EXP.
34. 11/01/2011. Macchine di Turing non deterministiche. Classi in tempo. La classe NP. Principali inclusioni. Riduzione di problemi.
35. 13/01/2011. NP completezza. Problemi NP completi. Classi funzionali. FP e FNP. Definizione di one-way-function.
36. 17/01/2011. La classe UC, e le relazioni tra P, UC e 1e one-way functions. Valutazione del corso.