Esercizio
●
Una sorgente di informazione può produrre 8
diversi simboli con probabilità diverse, e
presenta una entropia effettiva di 2.4
bit/simbolo. Quale è il numero medio di byte
necessari per contenere un messaggio di 1000
simboli consecutivi generato da questa
sorgente?
–
Sol. In media un simbolo è rappresentabile con 2.4
binit il che significa che 1000 simboli occuperanno
in media 2400 binit pari a 2400/8=300 bytes.
Esercizio
●
Una moneta viene lanciata 1000 volte. Su 1000
lanci, per 600 volte esce croce. Quale è la
ridondanza presente nella moneta?
–
Sol: assumendo la frequenza come misura della
probabilità dei due simboli (T e C) abbiamo:
●
●
●
●
pT=0.4 e pC=0.6;
H=-pT·log2pT -pC·log2pC = -0.4 ·log20.4 -0.6·log20.6= 0.529
+ 0.442 = 0.971 bit/simb
HMAX = log22 = 1 bit/simb
R = 1-H/HMAX = 1-0.971 = 0.029
Esercizio
●
Un dado genera i simboli da 1 a 6. Un dado
truccato presenta una entropia effettiva di 2.16
bit. Quale è la quantità media di byte
necessaria per memorizzare il risultato di 100
lanci?
–
Sol: il numero medio di binit per rappresentare un
messaggio di M simboli è Nb=M · H; se M=100
lanci allora Nb=100 · H = 100 · 2.16=216 binit
–
216 binit=216/8=27 bytes
Esercizio
●
Un canale di trasmissione può trasmettere
54Kbit al secondo. Quale sarà il tempo minimo
di trasmissione di un file di 1 megabyte che
presenta entropia effettiva di 4 bit? Il file è
equivalente ad una sorgente dove ogni simbolo
corrisponde ad un byte.
–
Sol: il file costituisce un messaggio di M=220
simboli. Ogni simbolo occupa in media 4 binit per
cui in totale avremo Nb=M·H=4·220 binit
–
se la velocità di trasmissione è vt= 54 Kbit/s
allora t=Nb/vt=4·220/54000=77.672 s
Esercizio
●
Un Ospedale decide di trasformare in formato digitale
l’archivio radiografico. Per questo scopo viene
utilizzato uno scanner da 600 dpi e 48 bpp. Di quanto
spazio di memoria ci sarà bisogno considerando che
la dimensione di una radiografia è circa di 11 x 11
pollici.
–
Dimensioni radiografia:
●
orizzontale: 11·600 pixel
●
verticale: 11·600 pixel
●
numero pixel per radiografia:(11·600)2 =43,560,000 pixel
●
ogni pixel occupa 48/8=6 bytes
●
occupazione radiografia=43,560,000·6=261,360,000 bytes
Esercizio
●
Un laboratorio fotografico deve digitalizzare una
collezione di 100 fotografie a colori di
dimensioni A4 (8x11 pollici), ed ha a
disposizione, per memorizzare le immagini, un
disco da 10 gigabyte. Quale è la risoluzione
massima che si potrà utilizzare, in termini di
dpi, se si sceglie una profondità di 24 bbp?
Calcolare il risultato e spiegare il procedimento.
Esercizio
●
Soluzione
–
Detta r la risoluzione (uguale in verticale e in
orizzontale) in dpi si ha:
●
●
●
●
●
occupazione foto: 8·r·11·r pixel=88·r2 pixel
ogni pixel occupa 24/8=3 bytes
occupazione foto in bytes=88·r2·3 bytes=264 · r2 bytes
100 foto occuperanno 26400 · r2 bytes
tale valore deve essere inferiore a 10Gb:
–
–
26400·r2<10·230 da cui
r < (10·230/26400)1/2=637.746 dpi
Esercizio
●
Viene utilizzato uno scanner da 200 dpi e 24
bpp. Usando questo scanner vengono
digitalizzate 10 fotografie di 10x15 centimetri
che vengono memorizzate senza
compressione. Quanto spazio di memoria
occuperanno le foto? Calcolare il risultato e
spiegare il procedimento. (1 pollice = 2,54 cm)
Esercizio
●
Soluzione
–
occupazione foto in pixel: 10 · 15/2.542
pixel=930,001,860 pixel
–
ogni pixel occupa 24/8=3 bytes
–
occupazione foto in bytes=930,001,860 · 3
bytes=2,790,005,580 bytes
–
10 foto occuperanno 27,900,055,800 = 26.608 Mb
·
2002
Esercizio
●
Con uno scanner da 300 dpi e 24 bpp vengono
digitalizzate 11 lastre fotografiche ciascuna
delle dimensioni di 6x4 pollici. Le immagini
digitali ottenute vengono poi memorizzate con
compressione jpeg 1:15. Quanto spazio di
memoria occuperanno le immagini? Calcolare il
risultato e spiegare il procedimento.
Esercizio
●
Soluzione
–
occupazione foto in pixel: 6 · 300 · 4 · 300 pixel =
2,160,000 pixel
–
ogni pixel occupa 24/8=3 bytes
–
occupazione foto in bytes=2,160,000 · 3
bytes=6,480,000 bytes
–
compressione: 6,480,000/15=432,000 bytes
–
11 foto occuperanno 11 · 432,000=4,752,000 bytes
Esercizio

Scrivere l'output del seguente programma, prestando
attenzione agli indici e ai limiti dell'array e ignorando le
istruzioni di stampa illegali (se ci sono). Supporre
disattivato il controllo sul valore degli indici degli array.
int main(void){
int a[4][4];
int *p,*q;
int i,j,k=8,s=1;
for(i=0; i<16; i++)
a[0][i] = --k * (s=-s);
for(i=0; i < 2; i++){
for(j=1; j < 7;j++)
printf("%5d",a[i][j]);
printf("\n");
}
...
Esercizio
...
}
p = &a[1][1];
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
a[*p-1][p[2]]);
*(p+*(p+5)));
*(&p[3]+p[3]-**a));
a[&p[4]-a[2]][2]);
*(&p[3]+--*p));
*(&a[0][0]-*(p-3)));
Esercizio
-7
-3
1
5
6
2
-2
-6
-5
-1
3
7
4
0
-4
-8
6
2
-5
-1
4
0
-3
1
Contenuto della
matrice
2
-2
-1
3
for(i=0; i < 2; i++){
for(j=1; j < 7; j++)
printf("%5d",a[i][j]);
printf("\n");
}
Esercizio
-7
-3
1
5
6
2
-2
-6
-5
-1
3
7
4
0
-4
-8
Contenuto della
matrice
-3
1
??
-1
-2
1
p = &a[1][1];
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
printf(" %d\n",
a[*p-1][p[2]]);
*(p+*(p+5)));
*(&p[3]+p[3]-**a));
a[&p[4]-a[2]][2]);
*(&p[3]+--*p));
*(&a[0][0]-*(p-3)));
Esercizio
Nel gioco del Sudoku le caselle di uno schema di 9 righe
8
6
5
e 9 colonne devono essere riempite con i numeri da 1 a 9 9
3
4
in modo tale che un numero compaia una sola volta per
7
1
9
ogni riga, per ogni colonna e in ciascuno dei 9 quadrati 3
3
9
per 3 in cui può essere suddiviso lo schema (vedi figura).
Ad esempio, considerando lo schema della figura, nella
2
5
7
casella in seconda riga e ottava colonna potrà essere posto
6
o il numero 1 o il numero 6 o il numero 8 in quanto i
6
8
2
numeri 9, 3 e 4 compaiono sulla stessa riga, i numeri 2 e
7 compaiono sulla stessa colonna e il numero 5 compare 3
4
nello stesso quadrato della cella in questione.
9
7
6
Scrivere una funzione C che ricevuti come parametri:
• una matrice 9 x 9 di interi contente uno schema parzialmente riempito (la casella vuota è
rappresentata dal numero 0);
• le coordinate r (riga) e c (colonna) di una casella;
• un numero x candidato ad occupare la casella di coordinate r e c
restituisca un valore di verità falso/vero (0/1) che indichi se il numero x può occupare la
casella di coordinate r e c.
Scrivere inoltre un main di prova della funzione.
sudoku
int main(void){
int a[N][N];
int n,m,r,c,x;
leggimatricedafile("datiB.txt",a,&n,&m);
printf("matrice:\n");
stampamatrice(a,n,m);
printf("Introduci le coordinate:");
scanf("%d%d",&r,&c);
for (x=1; x<=N; x++)
if (sudokuCheck(a,n,r,c,x))
printf("%d ammissibile\n",x);
else
printf("%d non ammissibile\n",x);
}
sudoku
int sudokuCheck( int A[N][N], int n,
int r, int c, int x){
int k, ammissibile;
ammissibile = A[r][c] == 0;
for (k=0; k<n && ammissibile; k++)
ammissibile = A[r][k] != x &&
A[k][c] != x;
ammissibile = ammissibile &&
quadratoAmmissibile(A,S,r/S*S,c/S*S,x);
return ammissibile;
}
sudoku
int quadratoAmmissibile( int A[N][N], int n,
int r, int c, int x){
int i,j, ammissibile;
ammissibile = 1;
for (i=0; i<n && ammissibile; i++)
for (j=0; j<n && ammissibile; j++)
ammissibile = A[r+i][c+j] != x;
}
return ammissibile;
LIFE
●
Scrivere un programma che simuli una zona di
spazio popolata da cellule (asterischi) che
evolvono di generazione in generazione
secondo le seguenti regole di nascita, morte e
sopravvivenza:
–
Nascita di una cellula: spazio vuoto circondata da 3
cellule
–
Morte di una cellula: se circondata da meno di 2 o
più di 3 cellule
–
Sopravvivenza di una cellula: se circondata da 2 o
3 cellule