Teoria dei codici e dell'informazione

Docente: Andrea Clementi

Comunicazioni

POSSIBILE SCIOPERO I APPELLO DI SETTEMBRE

30-08-2017 09:59

Si avvisano gli studenti interessati che il I appello di settembre (14/09/2017) di TCI, nel caso in cui lo sciopero

(https://sites.google.com/site/controbloccoscatti/home)

non fosse revocato dall'organizzazione promotrice, potrebbe non aver luogo.

Questo evento non avra' alcuna ripercussione su **tutti** gli altri appelli di *tutti* gli insegnamenti del Prof. Clementi.

ESITO ESONERO DEL 18-05-2017

21-05-2017 17:42

MATR. 0217260 -------------- 30/30

MATR. 0237924 --------------- 26/30

MATR. 0219463 ---------------- 28/30

Le votazioni che non appaiono sono da considerare insufficienti.

04-05-2017 12:44

IL giorno giovedi 18 maggio dalle 11 alle 13, si terra' la prova di esonero scritto della prima parte del corso.

INIZIO CORSO

05-03-2017 18:20

Il corso avra' inizio Lunedi 6 marzo alle ore 11.15.

Lezioni

20	29-05-2017 Ripasso generale della seconda parte del corso con domande degli studenti.
19	25-05-2017 La verfica di identita polinomiali: un algoritmo randomizzato analisi in probabilita' dell errore La verifica di moltiplicazione tra matrici: un algoritmo efficiente randomizzato, analisi in probabilita', principle of deferred decisions Analisi Bayesiana della confidenza di un algoritmo probabilistico
18	22-05-2017 Verifica esonero Parte II del corso: Algoritmi Probabilistici Introduzione Motivazioni Modelli di calcolo Probabilistici Criteri di accettazione Classi di Complessita' RP, BPP IL concettto di certificato di una prova Random Bits Analisi di un algoritmo probabilistico Esempi iniziali
17	18-05-2017 Prova di esonero scritto
16	15-05-2017 Esercitazioni su tutta la prima parte del corso, con domande proposte dagli studenti in classe
15	11-05-2017 Il II Teorema di Shannon Prova (II parte) L'applicazione del JT Theorem su codici a blocchi random il valore atteso della probabilita' di errore L'Expurgation Technique.
14	08-05-2017 IL II Teorema di Shannon. Prima parte della Dimostrazione Le sequenze Jointly Typical IL JT Theorem
13	04-05-2017 L'enunciato del II Thm di Shannon IL caso della Noisy Typewriter Le definizioni di sequenze J.Typical
12	27-04-2017 L'analisi della capacita' di un canale il calcolo della capacita' di canale Esempi importanti: il BSC. La codifica a blocchi ed i canali
11	20-04-2017 I concetti matematici della teoria della comunicazione su canali con errore. L'Entropia congiunta, condizionata, e marginale. La Mutua Informazione Relazioni fondamentali Esempi Definizione di canali: BSC e altri modelli.
10	10-04-2017 La costruzione di codici prefissi La rappresentazione mediante alberi binari etichettati L'algoritmo ''greedy'' L'algoritmo ''Top-Down'' e i suoi ''difetti'' L'approccio ''Bottom-Up'' e l'Algoritmo di Huffmann L'ottimalita' dell'Algoritmo di Huffman: struttura di soluzioni ottime ed analisi della ABL
9	06-04-2017 Introduzione alla compressione senza errori. I codici a lunghezza variabile Definizione del problema di ottimizzazione: la misura ''Average Bit Length" ABL" La relazione tra ABL e il I Thm di Shannon: il Lower Bound. I codici prefissi
8	03-04-2017 Ripasso ed esercitazione sulla dimostrazione della prima parte del Thm di Shannon - Seconda parte della dimostrazione: il Lower bound - Discussione dell'Importanza del I Thm di Shannon
7	30-03-2017 La compressione dati mediante codifiche. La compressione con errori e la compressione senza errori Introduzione al Theorema I di Shannon Enunciato del I Thm. di Shannon Le Sequenze Tipiche La dimostrazione del Thm di Shannon: Upper Bound
6	27-03-2017 - Risoluzione del problema delle 12 palline con collegamento all'entropia iniziale dell'esperimento - Proprieta additiva dell'entropia per v.a. indipendenti - Concetto di entropia per distribuzioni non uniformi: la compressione - Esempio del sottomarino
5	23-03-2017 Shannon Information Contnent Joint entropy Decomposizione di H(X) Esempi di sorgenti composite IL probelma delle 12 monete ed il concetto di Informazione necessaria Lower bounds
4	20-03-2017 SPAZI DI PROBABILITA' SPAZI CONGIUNTI DIPENDENZA ED INDIPENDENZA DI EVENTI E V.A. DISTRIBUZIONI CONDIZIONATE E MARGINALI IL THM DI BAYES LE BASI DELL'INFERENZA STATISTICA: FORWARD PROBABILITY ED INVERSE PROBABILITY, LIKELIHOOD ESEMPI DEFINIZIONE DI ENTROPIA DI UNA SORGENTE RANDOM
3	16-03-2017 IL SISTEMA DI CODIFICA A BLOCCHI: I BLOCK CODES. IL CODICE LINEARE HAMMING H(7,4) LA RAPPRESENTAZIONE MEDIANTE MATRICI IL CONCETTO DI SINDROME E L'ALGORITMO DI DECODIFICA ESEMPI ANALISI DELLA PROB. DI ERRORE E RATE DI H(7,4) E CONFRONTO CON R3 DESCRIZIONE INFORMALE DEL II THM DI SHANNON ED UNA POSISBILE VISUALIZZAZIONE GRAFICA.
2	09-03-2017 LA DECODIFICA DI R3: LA MAJORITY RULE. ANALISI ED OTTIMALITA' DELLA M.R. PER R3 IL CONCETTO DI LIKELIHOOD ED IL THM DI BAYES CALCOLO DELL'ASINTOTICA DELL PR(ERROR) su BSC(f) ESEMPI f = 10 VALUTAZIONI SU ERRORE E RATE PRIME CONSIDERAZIONI SUL TRADE-OFFS TRA ERRORE E RATE
1	06-03-2017 INTRODUZIONE AL CORSO, STRUTTURA DEL CORSO, PROPEDEUDICITA', MODALITA' DI ESAME PREVISTE. INFORMAZIONI DI CARATTERE GENERALE IL CONCETTO DI INFORMAZIONE, LA TRASMISSIONE SU CANALI, PRESENZA DI ERRORI SOLUZIONE HW E SOLUZIONE SW I CODICI CORRETTORI: CODIFICA E DECODIFICA LE MISURE DELLE PERFORMANCE DI UN SISTEMA DI CODIFICA: RATE E PROBABILITA' DI ERRORE UN ESEMPIO IMPORTANTE: IL BINARY SYMMETRIC CHANNEL (BSC) UN SEMPLICE CODICE: R3

Materiale didattico

Note sulla seconda parte del corso: Algoritmi Probabilistici
Codici Prefissi

Informazioni

Anno accademico	2016-2017
Crediti	6
Settore	INF/01
Anno	3
Semestre	2
Propedeuticità	Matematica discreta. Calcolo delle probabilità.

Programma

Corso di Laurea in Informatica
TEORIA DEI CODICI E INFORMAZIONE
A.A.   2013-14 (II Semestre)
Prof. Andrea Clementi

PROGRAMMA

1.     Introduzione alla Teoria dei Codici e dell'Informazione.
a.     Obiettivi generali
b.     Il ruolo della Probabilità
c.      Modelli Matematici per l'Informazione e la Trasmissione
d.     Modelli di Canale con Errori
e.     Codici per la Trasmissione su Canali; Rate di Trasmissione
f.      Esempi di Codici Correttori: Repetition Codes e Block Codes.
g.     Discussione informale dei risultati di Shannon
      Rif. Bibliografico: Capitolo 1 di [1]

2.     I concetti fondamentali della Teoria dell'Informazione.
a.     Richiami di Probabilità Discreta
b.     Inferenza Statistica: Il Likelihood
c.      Definizioni di Entropia e di Contenuto Informativo (di Shannon) di una Sorgente di Informazione.
d.     Proprietà utili della funzione Entropia
    Rif. Bibliografico: Capitolo 3 di [1]

3.     La Compressione Dati
a.     Variabili Aleatorie particolari: Le Sorgenti di Informazioni
b.     Entropia di una Sorgente
c.      Significato dell'Entropia di una Sorgente
d.     Esempi di Sorgenti e valutazione dell'Entropia
e.     Entropia di una Sorgente e Compressione del suo Outcome
f.      Compressione con Errore e senza
g.     Compressione di Sequenze di simboli di una Sorgente
h.     Sequenze Tipiche
i.       Il I° Teorema di Shannon
j.       Dimostrazione del I° Teorema di Shannon
Rif. Bibliografico: Capitolo 4 di [1]

4.     Codifica Binaria a Lunghezza Variabile (L.V.) senza Errori
a.     Codifica Univoca, Codici Prefissi
b.     Il I° Teorema di Shannon per la codifica a L.V.
c.      Esempi di Codici Binari a L.V.
d.     Codifica a L.V. Ottimale ed i codici di Huffman
   Rif. Bibliografici: Capitolo 5 di [1].

5.     Codifica e Decodifica per Canali di Trasmissione con Errori
a.     Il Modello di Canale attraverso spazi probabilistici congiunti.
b.     Random Variables (R.V.) Dipendenti
c.      Entropia Congiunta, Condizionata, Marginale di R.V.
d.     Il Concetto di Mutua Informazione I(X,Y)
e.     La Comunicazione su un Canale con Errori
f.      Inferenza dell'Input conoscendo l'Output
g.     Capacità di un Canale
h.     Il II° Teorema di Shannon sui Canali con Errore
i.       Descrizione informale della Dimostrazione
j.       Sequenze Congiuntamente Tipiche
k.     Dimostrazione formale (alcune parti)
       Rif. Bibliografici: Cap. 9 e 10 di [1]

6.     Canali e Codici Binari
a.     Correzione di Errori e Distanza di Hamming
b.     Codici Buoni e Cattivi
c.      Codici Perfetti
d.     Codici di Hamming
e.     Non esistenza di Codici Perfetti utili
f.      Codici Lineari Random
g.     Codici Lineari Efficienti per il Canale Binario Simmetrico
Rif. Bibliografici: Cap. 13 e 14 di [1]

7. Introduzione agli algoritmi probabilistici fondamentali

Riferimenti Bibliografici:
David J.C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, Version 7.2 (2005).

Propedeuticità: Matematica discreta. Calcolo delle probabilità.

Testi di riferimento

Riferimenti Bibliografici:
David J.C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, Version 7.2 (2005).

Ricevimento studenti

null

Modalità di esame

null