Esercizi su Codici e Rappresentazione Informazione Numerica

Esercizio 1

Alcuni semplici esercizi (in inglese), sulla rappresenzazione dei numeri.

Esercizio 2

Si consideri di avere a disposizione un elaboratore con parole di 16 bit che usa per i numeri negativi una rappresentazione in complemento a due.
Si dica per quali numeri e' possibile fornire una rappresentazione secondo le convenzioni di cui sopra. Per i numeri per cui tale rappresentazione e' possibile, fornire la rappresentazione di

-128   +35700  +32767  -65000 +105

Soluzione (by F. Cascio).

Esercizio 3

Sia data la seguente stringa di 12 cifre binarie:

101101110000

(1) Trovare il valore della stringa interpretata come:

(2) Convertire in base 8 i valori assoluti dei numeri ricavati nei casi (a) e (b), e sommarli

Esercizio 4

Siano date le seguenti relazioni fra numeri in base diversa:

(110)baseX = (12)base10
(110)baseS = (272)base10
(110)baseW = (6)base10
(110)baseZ = (56)base10

Determinare le basi X, S, W, Z.

Soluzione (non controllata).

Esercizio 5

Completare le due seguenti tabelle affinche' indichino il risultato ed il riporto (in base 4) per la moltiplicazione e la somma delle cifre della base 4 (0,1,2,3).

        +   0    1    2    3                  *   0    1    2    3

        0  -/-  -/-  -/-  -/-                 0  -/-  -/-  -/-  -/-

        1  -/-  -/-  -/-  -/-                 1  -/-  -/-  -/-  -/-

        2  -/-  -/-  -/-  -/-                 2  -/-  -/-  -/-  -/-

        3  -/-  -/-  -/-  -/-                 3  -/-  -/-  -/-  -/-

Utilizzare tali tabelle per eseguire la moltiplicazione (3123)base4 * (323)base4 con l'algoritmo classico per la moltiplicazione.

Esercizio 6

Presa la rappresentazione di un numero negativo utilizzando la codifica in complemento a due con n cifre, dimostrare che la rappresentazione dello stesso numero, ma con la codifica in complemento a due con n+m cifre, si ottiene aggiungendo m volte "1" alla sinistra.

Esercizio 7
Si condideri la seguente stringa di 8 bit:

10101010

ottenuta applicando una funzione di codifica ad un numero n.
Dire qual'e' il valore di n (e come si e' ottenuto) quando la codifica e':

(a) codifica posizionale a lunghezza fissa (8) in base due a per numeri natur ali
(b) codifica posizionale a lunghezza fissa (6) in base due a per numeri natur ali
(c) codifica posizionale a lunghezza variabile in base due per numeri natural i
(d) codifica posizionale a lunghezza fissa (8) in base sette per numeri natur ali
(e) codifica posizionale a lunghezza fissa (8) in base uno per numeri natural i
(f) codifica posizionale a lunghezza fissa (8) in base 2 in complemento a due per numeri interi
(g) codifica posizionale a lunghezza fissa (8) in base 2 in complemento a uno per numeri interi
(h) codifica posizionale a lunghezza fissa (7) in base 2 in modulo e segno pe r numeri interi
(i) codifica posizionale a lunghezza fissa in base sette in complemento alla base

Esercizio 8

(a) Si consideri di avere a disposizione un elaboratore con parole di 10 b it che usa per i numeri negativi una rappresentazione in complemento a due.
Si dica per quali numeri e' possibile fornire una rappresentazione secondo le convenzioni di cui sopra. Per i numeri per cui tale rappresentazione e' possibile, fornire la rappresentazione di

-128  -733 +105

(b) Fornire la dimostrazione di correttezza dell'algoritmo di complementazione di un n umero rappresentato in complemento a 2. Dimostrare cioe' che, data la rappresentazione di un numero in complemento a due, la rappresentazione del suo opposto si ottiene lasciando inalterati gli 0 meno significativi fino all'1 meno significativo compreso, ed applicando poi la negazione logica al resto delle cifre.

Esercizio 9

Dimostrare che nella codifica in complemento a due dei numeri interi la rappresentazione dei i numeri positivi ha "0" come cifra piu' a sinistra, mentre quella dei numeri negativi "1".

Esercizio 10
Descrivere l'algoritmo che, dato un numero naturale n, fornisca la sua rappresentazione posizionale in base B. Dimostrarne la correttezza.

Esercizio 11
Fornire la definizione di Codice. Cos'e' un codice ad espansione? Descrivere brevemente uno dei possibili codici ad espansione.

Esercizio 12
Si consideri il numero naturale la cui rappresentazione posizionale in base 8 e' 274.
Lo si rappresenti in base 7
Lo si rappresenti poi in base 2 nel modo piu' veloce possibile.
Giustificare la risposte.

Esercizio 13

Un semplice algoritmo per passare dalla notazione posizionale binaria a quella esadecimale e' il seguente: Dividiamo la stringa della rappresentazione binaria in blocchi da 4 bit (partendo da destra) e per ogni blocco consideriamo la cifra esadecimale corrispondente al numero rappresentato dai vari blocchi.
Dimostrare la correttezza di tale algoritmo.

Esercizio 14
Descrivere l'isomorfismo di Cantor tra N ed NxN.

Si consideri l'alfabeto A={a,c}. Associamo inoltre ad 'a' il numero 0 ed a 'c' il numero 2. Dire quindi (descrivendo il procedimento seguito) qual e' la codifica della stringa "aac" utilizzando l'isomorfismo di Cantor come descritto nel testo del corso. Si determini, inoltre, se possibile, la stringa codificata dal numero 18.

Esercizio 15
Dimostrare che la rappresentazione di (n mod B) si ottiene prendendo la cifra piu' a destra della rappresentazione in notazione posizionale, in base B, di n.

Esercizio 16
Descrivere un efficiente algoritmo di conversione da base 2 a base 8 e giustificarne formalmente la correttezza.

Esercizio 17
Fornire la definizione di codice in complemento a due per numeri interi ed un semplice algoritmo per passare dalla rappresentazione in complemento a due di un numero n a quella di -n.

Esercizio 18
Definire alcuni codici ad espansione.

Esercizio 19
Giustificare formalmente la correttezza del seguente algoritmo di conversione da base 4 a base 2:
Si sostituisce ogni cifra della rappresentazione in base 4 con la coppia di cifre binarie che rappresenta, in base 2 il numero associato alla cifra della base 4. (Es.: (322)₄ = (111010)₄).

Esercizio 20
Si consideri la seguente stringa di 8 bit:

10101010

ottenuta applicando una funzione di codifica ad un numero n.
Dire qual e' il valore di n (e, sinteticamente, come si e' ottenuto) quando la codifica e':

(i) codifica posizionale a lunghezza fissa (8) in base due a per numeri naturali
(ii) codifica posizionale a lunghezza fissa (6) in base due a per numeri naturali
(iii) codifica posizionale a lunghezza variabile in base due per numeri naturali
(iv) codifica posizionale a lunghezza fissa (8) in base tre per numeri naturali
(v) codifica posizionale a lunghezza fissa (8) in base uno per numeri naturali
(vi) codifica posizionale a lunghezza fissa (8) in base 2 in complemento a due per numeri interi
(vii) codifica posizionale a lunghezza variabile in base 2 in complemento a due per numeri interi

Esercizio 21
Fornire brevemente la definizione di codice ad espansione con configurazione di espansione. Fornire un codice ad espansione con configurazione di espansione per l'insieme {pippo, pluto, paperino, paperoga, minni} utilizzando due formati: un bit e tre bit. Qual e' il vantaggio, in questo caso, rispetto ad un codice a formati multipli predefiniti?

Esercizio 22
(a) Si dimostri, descrivendo l'isomorfismo di Cantor, che N (i numeri naturali) ed NxN (l'insieme delle coppie di numeri naturali) hanno la stessa cardinalita'.

(b) Si definisca una codifica (e decodifica) per l'insieme {a,c,b,d}⁺ utilizzando l'isomorfismo di Cantor.

Esercizio 23
Fornire la rappresentazione in base nove del numero rappresentato in base tre dalla seguente sequenza di cifre

10002102

Non si deve passare dalla rappresentazione in base 10.
Giustificare la risposta nel modo piu' completo possibile.

Esercizio 24
Fornire la definizione di codice in complemento alla base B per i numeri interi.

Esercizio 25
Fornire la definizione di codice a lunghezza variabile e descrivere un codice ad espansione.

Esercizio 26
Sia data la seguente stringa di 6 cifre binarie:

110000

Trovare il valore della stringa interpretata come intero senza segno (numero naturale), e come intero negativo in complemento a due. Convertire in base 8 i valori assoluti dei numeri ricavati nei due casi precedenti, e sommarli, restituendo il risultato in notazione posizionale binaria.

Esercizio 27
Che cosa e' codificato con la seguente stringa di cifre binarie?

1001001

Esercizio 27
Definire formalmente il codice in complemento a due per i numeri interi.

Esercizio 28
Fornire un esempio di codice a espansione con configurazione di espansione.

Esercizio 29
Siano X e Y numeri negativi. Si dimostri che

cod_Zc2(X - Y) = cod_Zc2(X) (+) cod_Zc2(-Y)

(Dove con "(+)" tra rappresentazioni intendiamo il normale algoritmo di somma cifra per cifra con riporto e risultato troncato a p cifre, mentre con '+' tra numeri intendiamo la funzione matematica binaria di addizione)

Esercizio 30
Supponiamo di voler utilizzare un codice a lunghezza variabile con quattro formati predefiniti:
4 bit
8 bit
12 bit
16 bit

Dire, giustificando le risposte, qual e' la cardinalita' massima di un insieme per il quale si possa definire un codice ad espansione nel caso di:
1) formati multipli predefiniti
2) espansione con cifra di espansione
3) espansione con configurazione di espansione

Esercizio 31
Fornire le definizioni di codice, codice a lunghezza variabile e codice a lunghezza fissa. Cosa caratterizza i codici ad espansione tra quelli a lunghezza variabile?

Esercizio 32
Dimostrare che il seguente algoritmo, che prende in input un numero naturale, produce le cifre c_p-1c_p-2....c₂c₁c₀ della sua codifica in notazione posizionale in base B.
input n val := n i:= 0 REPEAT quoz := val val := quoz div B c_i := quoz mod B i := i+1 UNTIL (quoz < B)

Esercizio
Dimostrare che, per x e y numeri positivi,

cod_Zc2^p(-x) (+) cod_Zc2^p(-y) = cod_Zc2^p(-x-y)

Dove (+) rappresenta l'algoritmo di somma per i numeri naturali codificati in notazione posizionale.

Esercizio XX

Esercizio XX

Esercizio XX