Teoria dei codici e dell'informazione

Docente: Andrea Clementi

Comunicazioni

ESITO ESONERO DEL 26/05/16

30-05-2016 12:32

 

 

Nome o Matricola

ESITO

0203819

 

21/30

0221756

 

27/30

0225181

21/30

 

0204605

 

25/30

0223141

30 e Lode

 

0166124

30/30

 

 

 

 

 

 

 

 

 

 

 

Gli studenti che non compaiono hanno conseguito una votazione largamente insufficiente.

 

Gli studenti interessati a visionare il proprio elaborato prima delle sessioni

di esame, sono invitati a presentarsi presso lo studio del prof. Clementi lunedi 6 giugno dopo l'invio di una email di conferma a clementi@mat.uniroma2.it


LEZIONE DI TCI DI GIOVEDI 21/04

17-04-2016 11:15

Si avvisano gli studenti che la lezione di TCI di giovedi prossimo 21/04,

e' cancellata. Le lezioni riprenderanno normalmente giovedi 28 aprile


Lezioni

2426-05-2016

Svolgimento dell'esonero sulla prima parte del corso (Teoria dell'Informazione e dei Codici)

2323-05-2016

Esercitazione del Dr. Natale

2219-05-2016

Il calcolo del mediano 

 

la varianza e le disuguaglianze di Markov e Chebyshev

 

analisi delle performance

 

 

2116-05-2016

Algoritmi di ordinamento: il randomized quick sort

 

Analisi del tempo atteso mediante la linearita' del valor medio

 

l'analisi del caso medio della versione deterministica

 

Il problema del coupon collector

2012-05-2016

Un algoritmo di contrazione archi per il problema del Min-Cut su multigrafi.

 

Analisi delle performance mediante bounds sulle probabilita' condizionate

 

Come aumentare in modo efficiente la confidenza di un algoritmo probabilistico

 

1909-05-2016

Un algoritmo probabilistico per la verifica di moltiplicazioni tra matrici quadratiche

 

analisi delle performance e dell'errore garantito mediante il 

principle of deferred decisions e le probabilita' condizionate

1805-05-2016

Discussione conclusiva della parte del corso che riguarda 

la teoria dell'informazione e dei codici.

 

il ruolo della probabilita' in computer science

 

introduzione agli algoritmi probabilistici

 

i vari tipi di algoritmi probabilistici, il criterio di accettazione, il tipo di errore garantito

 

analisi average-case

 

Un primo esempio: la verifica randomizzata  di identita' polinomiali

1702-05-2016

Random Linear Codes

 

Funzione Enumeratrice e proprieta' algebriche delle matrici random

 

Esistenza di Random Linear Codes che verificano il II thm di Shannon per BSC(f).

 

La partity check matrix e la decodifica mediante sindrome

1628-04-2016

Lo spazio di hamming

Perfect Codes

 

Perfect t-Error Correcting Codes

 

Non esistenza di buoni  Perfect t-Error Correcting Codes su BSC con f costante.

1521-04-2016

Prova del II Thm. di Shannon: passaggo da errore medio a errore worst-case attraverso il metodo probabilistico (expurgation technique).

 

Considerazioni conclusive sul Thm. di Shannon.

1418-04-2016

Dimostrazione della prima parte del Thm di Shannon

 

Concetto Joint-Typicality

Joint-Typicality Thm

Joint-Typicality Decoding

Analisi dell'errore

1314-04-2016

I codici a blocchi

Enunciato informale del II Thm di Shannon sui Canali.

Visualizzazione asintotica.

Definizioni formali di Probabilita' di Errore.

Enunciato Formale della prima parte del II Thm di Shannon

Verifica del Thm sul NTW Channel

 

1211-04-2016

IL modello matematico di Noisy Channel Communication

La Matrice di transizione di un Canale: Le distribuzioni condizionate e marginali.

Codifica e Decodifica: Obiettivi generali

Esempi: il BSC, il Noisy TW, Z-Channel, etc

Calcolo della Mutua Informazione dei principali Canali.

La Decodifica vista come un problema di Inferenza Statistica (Thm. di Bayes)

Definizione di Capacita' di un Canale

Esempi ed Esercizi

1107-04-2016

Entropia di var. aleatorie DIPENDENTI.

Entropia condizionata

Mutua Informazione

Proprietà fondamentali e relazioni

Calcolo di queste grandezze su esempi concreti

Significato in termini di incertezza ed informazione

 

1004-04-2016

La codifica di Shannon-Fano: il metodo divide et impera

 

La struttura ottimale per un codice prefisso

 

L'algoritmo di Huffman

 

Dimostrazione di Ottimalita' dell'algoritmo di Huffman

931-03-2016

La Compressione senza errori.

La codifica a lunghezza variabile

I codici prefissi

Rappresentazione dei codici prefissi mediante alberi binari

 

Il problema di ottimizzazione: la ABL

 

Esempi

824-03-2016

I Thm. di Shannon: dimostrazione del Lower Bound.

 

Discussione conclusiva del I Thm di Shannon sulla compressione con errore

721-03-2016

Dimostrazione della prima parte del I Thm di Shannon:

upper bound sull'entropia di una sorgente random.

Costruzione delle sequenze tipiche, analisi della compressione e dell'errore commesso.

617-03-2016

La compressione con Errore

La codifica non biettiva.

La codifica a blocchi

Obiettivi della compressione: le misure di errore ed il grado di compressione

Descrizione informale del I Teoream di Shannon

Il concetto di sequenze tipiche 

Visualizzazione asintotica del I Teorema di Shannon

514-03-2016

Esercitazioni sull'Entropia di sorgenti random e sulla compressione dati

410-03-2016

Nozioni di Inferenza Statistica. Inverse probability, Likehood.

Esempi di Inferenza.

Il concetto di Entropia di una Sorgente

Proprietà fondamentali dell'Entropia

Decomposizione

Esempi

307-03-2016

La decodifica ottimale mediante l'Inferenza. Il Teorema di Bayes.

La codifica a blocchi. I codici Lineari, il codice BCH. La distanza di Hamming.

Analisi del codice di Hamming, la decodifica mediante il calcolo della sinndrome.

203-03-2016

Il concetto di compressione, il concetto di trasmissione su canali in presenza di errore. L'esempio del canale BSC. IL rate di trasmissione.

I codici correttori. Il codice R3.

Esempi

129-02-2016

Introduzione alla teoria dell'Informazione ed ai codici

Nozioni base di probabilita' discreta

Struttura del corso


Materiale didattico

Slides su Codifica  di Huffman

Slides di Probabilita' ed Algoritmi (Libro M&U)

Informazioni

Anno accademico2015-2016
Crediti6
SettoreINF/01
Anno3
Semestre2
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