INFORMATICA
MATTEO CRISTANI
INDICE

CICLO DELLE LEZIONI
LEZ. 1
LEZ. 2
LEZ. 3
LEZ. 4
LEZ. 5
INTRODUZIONE AL
CORSO
I CALCOLATORI
ELETTRONICI
ELEMENTI DI
TEORIA DELL’
INFORMAZIONE
MISURE DELLA
INFORMAZIONE
CALCOLO BINARIO:
CONVERSIONI DI
BASE
LEZ. 6
LEZ. 7
LEZ. 8
LEZ. 9
LEZ. 10
CALCOLO BINARIO:
OPERAZIONI IN
BASE 2
ESERCITAZIONE DI
CALCOLO BINARIO
ESERCITAZIONE DI
CALCOLO BINARIO
PORTE LOGICHE
PROGETTO DI
CIRCUITI DIGITALI
LEZ. 11
LEZ. 12
LEZ. 13
LEZ. 14
LEZ. 15
INTRODUZIONE
AGLI ALGORITMI
PRODUTTIVITA’
INDIVIDUALE
IL WEB
RICERCA DI
DOCUMENTI
USO DEI MOTORI
DI RICERCA
LEZ. 16
LEZ. 17
LEZ. 18
LEZ. 19
LEZ. 20
SICUREZZA
INFORMATICA
ELEMENTI DI
CRITTOGRAFIA
ESERCITAZIONE DI
CRITTOGRAFIA
ESERCITAZIONE
GENERALE
SOMMARIO DEL
CORSO
AGENDA



ESERCIZI BASE SULLE MISURE DELLA
INFORMAZIONE
ESERCIZI SUI CODICI
ESERCIZI AVANZATI SULLE MISURE DELLA
INFORMAZIONE
ESERCIZI BASE DI TEORIA DELL’INFORMAZIONE
1.
2.
3.
Dato un sistema di Shannon con un alfabeto di canale di
23 simboli equiprobabili, calcolare la quantità di
informazione portata da tre messaggi.
Dato un sistema di Shannon con un alfabeto di canale
con 16 simboli calcolare la ridondanza di una codifica
ternaria.
Dato un sistema di Shannon in cui la quantità di
informazione portata da due messaggi è pari a circa 7
bit, sapendo che la distribuzione di probabilità dei
messaggi è uniforme trovare l’ampiezza dell’alfabeto di
canale.
SOLUZIONE ESERCIZIO 1

L’informazione portata da un singolo simbolo è
I  log 2 (23)  4,52

L’informazione portata da tre messaggi è quindi
I  3  log 2 (23)  13,57
SOLUZIONE ESERCIZIO 2

Le codifiche ternarie portano i simboli dell’alfabeto su
blocchi di simboli 0, 1, 2. Con tre simboli, il numero
minimo di codici necessari per 16 elementi dell’alfabeto di
canale è 2, perché
log 3 (16)  1,2
SOLUZIONE ESERCIZIO 2

Quindi, ad esempio, supponendo che i glifi dei sedici
elementi dell’alfabeto di canale siano le prime sedici
lettere dell’alfabeto latino esteso, si avrebbe la codifica
della tabella del prossimo lucido
SOLUZIONE ESERCIZIO 2
A
0
0
0
I
0
2
2
B
0
0
1
J
1
0
0
C
0
0
2
K
1
0
1
D
0
1
0
L
1
0
2
E
0
1
1
M
1
1
0
F
0
1
2
N
1
1
1
G
0
2
0
O
1
1
2
H
0
2
1
P
1
2
0
SOLUZIONE ESERCIZIO 2

Naturalmente sono invalide le seguenti codifiche
-
1
1
2
2
1
2
-
2
2
1
1
1
2
-
2
2
2
0
0
0
0
1
2
-
2
2
2
2
2
2
0
1
2
-
2
1
0
-------------------------------
SOLUZIONE ESERCIZIO 3


Se due messaggi portano circa sette bit, nell’ipotesi di
codici semplici (un simbolo, un messaggio), allora un
messaggio porta circa 3,5 bit.
Quindi,
3,5  log 2 n
n  23,5  11,31

Da cui le due ipotesi possibili, ovvero che il codice sia di
11 simboli oppure che sia di 12 simboli.
SOLUZIONE ESERCIZIO 3

Con 11 simboli avremmo
n  log 2 11  3,45


Se scegliessimo una codifica a blocchi servirebbero 4
simboli binari.
Con 12 simboli avremmo
n  log 2 12  3,58

Se scegliessimo una codifica a blocchi servirebbero
sempre 4 simboli binari.
ESERCIZI BASE DI TEORIA DELL’INFORMAZIONE
4.
5.
Dato un canale con alfabeto di 21 simboli a codifica
semplice, che invia 5 segnali al secondo, misurare la
velocità di trasmissione.
Se un canale ha velocità di trasmissione pari a 23 Kbps e
l’alfabeto di canale è formato da 4 simboli, e la codifica è
semplice, quanti segnali invia la sorgente sul canale ogni
secondo?
SOLUZIONE ESERCIZIO 4


Su un canale a codifica semplice di 21 simboli d’alfabeto,
un messaggio porta
I  log 2 21  4,39
Quindi, cinque segnali portano circa
I  5  4,39  21,96

La velocità di trasmissione è di circa 22 bps
SOLUZIONE ESERCIZIO 5

Se un canale trasmette 4 simboli a codifica semplice un
messaggio porta due bit. Poiché la velocità di trasmissione
è di 23 Kbps, passeranno
23 1024
n
 11706m / s
2
ESERCIZI SUI CODICI
6.
7.
Una codifica diretta a blocchi di tredici simboli binari è
utilizzata per mappare un alfabeto di canale di 104
simboli. Calcolare la ridondanza del codice.
Si vuole costruire un codice a codifica d’errore basato
sul metodo dell’alternanza di simboli validi ed invalidi. Se
l’alfabeto di canale è costituito da 77 simboli, e la
codifica scelta è a blocchi di 7 simboli binari, quanti bit
servono per garantire la costruzione corretta del
codice?
SOLUZIONE ESERCIZIO 6


Un codice a blocchi di tredici simboli binari codifica
213=8192 simboli. Il codice è quindi sovrabbondante. Se il
codice fosse abbondante occorrerebbero sette simboli
binari, perché 27=128.
Il codice scelto avrebbe ridondanza
8192  104
r
 98,7%
8192

Per il codice abbondande a sette bit
128  104
r
 18,75%
128
SOLUZIONE ESERCIZIO 7

Con sette simboli binari la codifica ha una ridondanza
pari a
128  77
r
 39,84%
128

Per un codice con alternanza occorre che la ridondanza
della codifica sia almeno del cinquanta per cento, cosa che
si ottiene aggiungendo un singolo bit al codice.
ESERCIZI SULL’ERRORE
8.
9.
10.
Un canale ha un tasso d’errore di 1/1024. Si misuri
l’affidabilità, sapendo che trasmette a 22 Kbps.
Un canale ha un tasso d’errore di 1/2048 e trasmette a
12 Kbps. Se si osservano i messaggi giunti alla
destinazione, che cosa si può dire di una sequenza di sei
messaggi?
Quanti messaggi errati ci sono in una sequenza di venti
su un canale a tasso d’errore 1/16?
SOLUZIONE ESERCIZIO 8

L’affidabilità di canale si ottiene riducendo alla percentuale
di messaggi corretti determinata dal tasso d’errore la
velocità del canale
1
a  (1 
)  22 1024  22 1023  22506bps
1024
PROPOSTE SOLUZIONE ESERCIZIO 9
a)
b)
c)
d)
e)
f)
Almeno uno dei messaggi è errato
Nessuno dei messaggi è errato
Tutti i messaggi sono errati
Se il primo messaggio è errato allora anche gli altri lo
sono
Se il primo messaggio è errato allora gli altri non lo
sono
Non possono esserci più di due messaggi errati
SOLUZIONE ESERCIZIO 10

Non esiste una soluzione corretta, perché il tasso
d’errore misura la probabilità che un messaggio sia
corretto, non prevede il numero di messaggi errati in una
sequenza.
ESERCIZI AVANZATI DI TEORIA DELL’INFORMAZIONE
11.
12.
Si determini un codice lineare con un bit di controllo di
parità per correggere errori su un canale con alfabeto di
26 simboli codificato in base 2.
Si determini la velocità effettiva di canale quando un
alfabeto di 100 simboli codificati in base due viene
esteso con due bit di controllo di parità, in presenza di
un tasso d’errore di 1/2048 bit su un canale a 215 Kbps.
SOLUZIONE ESERCIZIO 11


Un alfabeto di 26 simboli richiede 5 bit per la codifica
binaria.
Questa codifica ha ridondanza inferiore al 50%, in
particolare la ridondanza risultante è
32  26 6
r

 18,75%
32
32

Occorre quindi codificare a sei bit.
SOLUZIONE ESERCIZIO 11: CODICI VALIDI
GLIFO
B1
B2
B3
B4
B5
C.P.
GLIFO
B1
B2
B3
B4
B5
C.P.
A
0
0
0
0
0
0
N
0
1
1
0
1
1
B
0
0
0
0
1
1
O
0
1
1
1
0
1
C
0
0
0
1
0
1
P
0
1
1
1
1
0
D
0
0
0
1
1
0
Q
1
0
0
0
0
1
E
0
0
1
0
0
1
R
1
0
0
0
1
0
F
0
0
1
0
1
0
S
1
0
0
1
0
0
G
0
0
1
1
0
0
T
1
0
0
1
1
1
H
0
0
1
1
1
1
U
1
0
1
0
0
0
I
0
1
0
0
0
1
V
1
0
1
0
1
1
J
0
1
0
0
1
0
W
1
0
1
1
0
1
K
0
1
0
1
0
0
X
1
0
1
1
1
0
L
0
1
0
1
1
1
Y
1
1
0
0
0
0
M
0
1
1
0
0
0
Z
1
1
0
0
1
1
SOLUZIONE ESERCIZIO 11: CODICI INVALIDI
GLIFO
B1
B2
B3
B4
B5
C.P.
GLIFO
B1
B2
B3
B4
B5
C.P.
-
0
0
0
0
0
1
-
0
1
1
0
1
0
-
0
0
0
0
1
0
-
0
1
1
1
0
0
-
0
0
0
1
0
0
-
0
1
1
1
1
1
-
0
0
0
1
1
1
-
1
0
0
0
0
0
-
0
0
1
0
0
0
-
1
0
0
0
1
1
-
0
0
1
0
1
1
-
1
0
0
1
0
1
-
0
0
1
1
0
1
-
1
0
0
1
1
0
-
0
0
1
1
1
0
-
1
0
1
0
0
1
-
0
1
0
0
0
0
-
1
0
1
0
1
0
-
0
1
0
0
1
1
-
1
0
1
1
0
0
-
0
1
0
1
0
1
-
1
0
1
1
1
1
-
0
1
0
1
1
0
-
1
1
0
0
0
1
-
0
1
1
0
0
1
-
1
1
0
0
1
0
SOLUZIONE ESERCIZIO 11: NON CODICI
VALIDI
INVALIDI
GLIFO
B1
B2
B3
B4
B5
C.P.
GLIFO
B1
B2
B3
B4
B5
C.P.
-
1
1
0
1
0
1
-
1
1
0
1
0
0
-
1
1
0
1
1
0
-
1
1
0
1
1
1
-
1
1
1
0
0
1
-
1
1
1
0
0
0
-
1
1
1
0
1
0
-
1
1
1
0
1
1
-
1
1
1
1
0
0
-
1
1
1
1
0
1
-
1
1
1
1
1
1
-
1
1
1
1
1
0
ESEMPI DI TRASMISSIONE

CASO 1:
SPEDIAMO UN GLIFO E NE GIUNGE UN
ALTRO

CASO 2:
SPEDIAMO UN GLIFO E GIUNGE UN
NON CODICE VALIDO

CASO 3:
SPEDIAMO UN GLIFO E GIUNGE UN
CODICE INVALIDO

CASO 4:
SPEDIAMO UN GLIFO E GIUNGE UN
NON CODICE INVALIDO
CASO I

Se, ad esempio, parte il glifo X e giunge il glifo H allora lo
schema di trasmissione è.
X
H



1
0
-
0
0
+
1
1
+
1
1
+
1
1
+
0
1
-
Come si vede il numero di errori commessi è 2.
L’errore non viene corretto.
In generale, se il codice a correzione d’errore è lineare il
numero di errori commessi se parte un glifo e ne giunge un
altro è pari.
CASO 2

Se parte il glifo X e giunge un non codice, allora si potrebbe
avere, ad esempio
X



1
1
+
0
1
-
1
1
+
1
1
+
1
1
+
0
1
-
Il numero di errori è 2.
L’errore viene riconosciuto perché i non codici non sono
ammissibili
In generale, se il codice a correzione d’errore è lineare il
numero di errori commessi se parte un glifo e giunge un non
codice valido è pari.
CASO 3

Se parte il glifo X e giunge un codice invalido, allora si
potrebbe avere, ad esempio
X



1
1
+
0
0
+
1
1
+
1
1
+
1
1
+
0
1
-
Il numero di errori è 1.
L’errore viene riconosciuto.
In generale, se il codice a correzione d’errore è lineare il
numero di errori commessi se parte un glifo e giunge un
codice invalido è dispari.
CASO 4

Se parte il glifo X e giunge un non codice invalido, allora si
potrebbe avere, ad esempio
X



1
1
+
0
1
-
1
1
+
1
0
-
1
1
+
0
1
-
Il numero di errori è 3.
L’errore viene riconosciuto.
In generale, se il codice a correzione d’errore è lineare il
numero di errori commessi se parte un glifo e giunge un non
codice invalido è dispari.
SOLUZIONE ESERCIZIO 12



Per codificare 100 simboli occorrono 7 bit.
Se si aggiungono 2 bit di controllo di parità il codice
risulta di 9 bit.
La ridondanza è quindi
512  100
r
 80,4%
512


La velocità di trasmissione viene ridotta quindi in misura
pari ai bit effettivamente trasmessi mediante il processo
di correzione del codice lineare.
Adotteremo il metodo dello stream standard.
METODO DELLO STREAM STANDARD




Lo stream standard è uno stream di bit lungo n, tale per
cui il tasso d’errore risulti di 1/n.
Se il tasso d’errore è espresso in frazione egizia 1/n,
ovviamente n è la lunghezza dello stream standard.
Se il tasso d’errore è espresso in percentuale equivalente
alla frazione p/q, allora per calcolare n, lunghezza dello
stream standard, dove [x] è il più piccolo intero più
grande di x.
Se un codice è a blocchi, ovviamente, il numero n è
approssimato.
q
n 
 p
ESEMPIO



Supponiamo che un codice a blocchi di 12 bit sia
utilizzato su un canale a tasso d’errore 1/1024.
Lo stream standard è costituito da un numero di blocchi
che formi uno stream il più corto possibile rispetto a
1024 bit.
Il numero minimo di blocchi è 86, e la lunghezza
corrispondente è 1032 bit.
PROCESSO DI CORREZIONE
1.
2.


Trasmissione di uno stream standard di bit;
Ripetizione dei blocchi riconosciuti errati;
[SI CONSIDERA UNA SOLA RIPETIZIONE]
Lo stream così ottenuto viene posto al denominatore di
una frazione al cui numeratore si mette il numero di
blocchi effettivamente inviati.
Si moltiplica poi la frazione così ottenuta per la velocità
di canale.
CALCOLO




Poiché il tasso d’errore è 1/2048 lo stream standard è
2048 bit. Poiché la codifica base è a sette bit lo stream
trasferisce 293 blocchi base.
L’estensione a nove bit comporta che per inviare 293
blocchi base occorre inviare 293 blocchi a nove bit, che
portano lo stream standard a 2637 bit.
Il tasso d’errore di 1/2048 comporta che l’errore
commesso sullo stream standard possa portare alla
ripetizione di un blocco di nove bit per correggere il
primo errore sui 2048 bit dello stream base.
Come approssimazione per eccesso si stima la ripetizione
ulteriore di un ulteriore blocco.
LUNGHEZZA EFFETTIVA DELLO STREAM



Lo stream effettivo è quindi 2637+18=2655.
Poiché uno stream di 2655 bit porta 293 blocchi, ognuno
dei quali esprime, in effetti, l’informazione pari a log2(100).
Quindi la velocità effettiva di canale è
293  log 2 (100)
v
 215Kbps  0,73  215 1024bps 
2655
 160717bps  157 Kbps