| 24 | 28-05-2015
PROVA DI ESONERO |
| 23 | 26-05-2015
IL Calcolo del Mediano in un vettore non ordinato.
L'algortimo Random Sampling.
L'analisi dell'errore e del tempo
mediante la disuguaglianza di Chebyshev |
| 22 | 21-05-2015
Il problema dell ordinamento di un vettore.
Il Random Quick Sort.
Analisi del numero medio di confonti mediante la linearita' del valor medio.
IL problema del Min-Cut su Grafi. L'algoritmo randomizzato basato sulla contrazione archi. L'analisi del tempo mediante il teorema di Bayes sulle probabilita' condizionate. |
| 21 | 19-05-2015
Un Algoritmo Randomizzato per la Verifica di prodotti tra matrici
definizione, analisi probabilistica dell errore, complessita' |
| 20 | 14-05-2015
I metodi randomizzati e loro importanza in Computer Science.
IL problema della verifica efficiente di identita' polinomiali
Metodo Randomizzato
Analisi dell'errore
|
| 19 | 12-05-2015
Costruzione randomizzata efficiente di BLC per BSC con Rate e con errore medio molto vicini al II THM di Shannon:
Random BLC e Syndrome-Decoding |
| 18 | 05-05-2015
Esercitazione a cura del Dr. Natale |
| 17 | 07-05-2015
- Costruzione efficiente di Codici Correttori
- Distanza e Spazio di Hamming
- Binary Linear Codes
- Distanza minima di un BLC
- Inesistenza di BLC con worst-case error e rate ottimali: definizione
di codici perfetti.
|
| 16 | 30-04-2015
- Lemma Jointly-Typicality.
- Prova del Lemma JT.
- Significato del Lemma JT
- Applicazione del Lemma JT per limitare la prob. di errore della Codifica JT di Shannon.
- Dimostrazione formale del II Thm di Shannon
|
| 15 | 28-04-2015
- Passi fondamentali della dimostrazione del II THM di Shannon (Parte positiva):
scelta random del Codice (sequenze X-Typ),
Decodifica in base alla definizione di JT.
Definizione dei tipi di possibili tipi di errori.
|
| 14 | 23-04-2015
- Verifica del II Thm. di Shannon sul canale: Noisy-Typewriter
- Discussione della dimostrazione della Parte positiva del II THM. di Shannon.
- Def. di Seq. Jointly-Typical
- Esempi di Sequenze JT su BSC. |
| 13 | 21-04-2015
- II Thm. di Shannon
- Discussione del significato del II Thm. di Shannon
- Codifica, Trasmissione e Decodifica a Blocci
- Definizioni di entropia, mutua informazione e rate su trasmissione a blocchi.
- Definizione di Block-Error
- Decodifica Ottimale
- Enunciato formale del II THM di Shannon |
| 12 | 16-04-2015
ESERCITAZIONE (DR. Natale) |
| 11 | 14-04-2015
Entropia condizionata,
Calcolo della muta informazione in un canale
vari tipi di canali,
esempi sul canale BSC e ZC
Definizione e significato della Capacita' di un Canale |
| 10 | 09-04-2015
Esercitazione sul I thm di Shannon e su
distribuzioni congiunte
(Dr. Natale) |
| 9 | 02-04-2015
Dimostrazione parte Upper Bound del I Thm di Shannon.
Dimostrazione parte Lower Bound del I Thm di Shannon
Considerazioni finali. |
| 8 | 31-03-2015
Enunciato Formale del I Thm. di Shannon.
Concetti e definizioni preliminari per la dimostrazione del Thm.
Esempio nel caso binario.
Distribuzione Binomiale, Valor Medio e Varianza.
Fig. 4.11 (del Libro)
Definizione formale di sequenze tipiche (con parametro)
Asymptotic Equipartition Principle.
Legge dei grandi numeri |
| 7 | 26-03-2015
Esercitazioni sulle ultime due lezioni
(Dr. Natale) |
| 6 | 24-03-2015
La compressione dati. a) Lossy Compression (codifica a blocchi) e b) Lossless Compression (codifica a lungh variabile).
Introduzione alla Compressione a.
- Insiemi Tipici: Definizione informale mediante la funzione di Entropia su blocchi di 1 simbolo.
Esempio 4.6 (sul libro)
- Codifica di N simboli.
Definizione dell'Insieme di sequenze tipiche.
-Esempio 4.7 sul libro
- Descrizione e discussione del I Teorema di Shannon mediante le figure 4.7, 4.8, e 4.9 |
| 5 | 17-03-2015
Definizione formale dell'Entropia di una Sorgente Random. Il contenuto informativo di una sorgente.
Decomposizione dell'Entropia ed esempi. Esempio delle 12 monete.
Il grafico delle Entropia Binaria, Massimo e Minimo valore.
Entropia congiunta di due sorgenti indipendenti.
Entropia di distribuzioni non uniformi. Esempio del sottomarino. |
| 4 | 12-03-2015
Esercitazione sulle prime tre lezioni
(Dr. Natale) |
| 3 | 10-03-2015
Cenni ed intuizioni sul II Thm di Shannon: la Capacita' di un canale e l'entropia di una sorgente random
Richiami di Probabilita' discreta:
spazi di probabilita', spazi congiunti, marginali, probabilita' condizionali, indipendenza, teorema di bayes. Esercizi ed esempi
La probabilita' inversa, il likehood, l'inferenza statistica: esempi |
| 2 | 05-03-2015
Calcolo della probabilita' di errore della majority rule per i repetition code ed ottimalita' della rule.
I block code, gli hamming code, la matrice di parita', la sindrome, la correzione dell errore attraverso i dischi, la prob di errore di L(7,4) |
| 1 | 03-03-2015
Introduzione alla teoria dell'informazione. Sorgenti random, compressione, trasmissione
Semplici esempi di codici ridondanti, il repetition Code R3 ed il concetto di rate ed errore su un canale binario simmetrico |