24 | 26-05-2016
Svolgimento dell'esonero sulla prima parte del corso (Teoria dell'Informazione e dei Codici) |
23 | 23-05-2016
Esercitazione del Dr. Natale |
22 | 19-05-2016
Il calcolo del mediano
la varianza e le disuguaglianze di Markov e Chebyshev
analisi delle performance
|
21 | 16-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 |
20 | 12-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
|
19 | 09-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 |
18 | 05-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 |
17 | 02-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 |
16 | 28-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. |
15 | 21-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. |
14 | 18-04-2016
Dimostrazione della prima parte del Thm di Shannon
Concetto Joint-Typicality
Joint-Typicality Thm
Joint-Typicality Decoding
Analisi dell'errore |
13 | 14-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
|
12 | 11-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 |
11 | 07-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
|
10 | 04-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 |
9 | 31-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 |
8 | 24-03-2016
I Thm. di Shannon: dimostrazione del Lower Bound.
Discussione conclusiva del I Thm di Shannon sulla compressione con errore |
7 | 21-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. |
6 | 17-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 |
5 | 14-03-2016
Esercitazioni sull'Entropia di sorgenti random e sulla compressione dati |
4 | 10-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 |
3 | 07-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. |
2 | 03-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 |
1 | 29-02-2016
Introduzione alla teoria dell'Informazione ed ai codici
Nozioni base di probabilita' discreta
Struttura del corso |