Appunti di Fondamenti di informatica

Informatica e pensiero computazionale per le scienze umane e sociali (Start@unito)

1. Rappresentazione delle informazioni

1.1 La codifica binaria

Le origini in Leibniz

Asini e bit

• Dedichiamo questo breve approfondimento all’origine della notazione binaria, anche allo scopo di accennare brevemente ad uno dei molti contributi che il filosofo e matematico di G. W. Leibniz (1646-1716) ha dato alle origini del pensiero computazionale. Sappiamo che con 1 bit si rappresenta una scelta tra 2 alternative. Nell’immagine si può vedere il famoso asino di Buridano che è assetato ma indeciso su quale secchio d’acqua scegliere per iniziare a bere.

Le origini della numerazione binaria

• In assenza di informazione l’asino è costretto a morire di sete. Quello che gli manca è un bit di informazione che lo aiuti a dirigersi verso il secchio a sinistra (0) o il secchio a destra (1). In realtà, questa storia semplifica la motivazione dei filosofi per discutere questa parabola, che è il problema del determinismo e del libero arbitrio.

Come rappresentare una scelta tra più di 2 alternative? Usando sequenze di bit, di lunghezza adeguata al numero di alternative da rappresentare.

In generale: n bit permettono di rappresentare una scelta tra alternative; per rappresentare una scelta tra N ≥ 1 alternative, sono necessari circa bit.

ESEMPIO: con quindi con 3 bit avrò 8 = 3 = 8² 8 alternative.

Entra Leibniz

• Leibniz era in contatto epistolare con i missionari gesuiti in Cina, in particolare il Padre Bouvet che lo informò nel 1701 che il metodo di contare con i numeri in base 2 comunicatogli in precedenza da Leibniz svelava il mistero delle figure di Fo-Hi, associate allo yin e yang della filosofia taoista secondo il Libro dei Mutamenti, o I-Ching (vedi immagine).

Leibniz e il pensiero cinese (il Tao e i numeri binari)

• La rappresentazione delle figure per lo yin e lo yang mediante linee spezzate permette la costruzione di 2³ trigrammi (cioè sequenze di 3 figure) e di 2⁶ esagrammi (cioè sequenze di 6 figure), equivalentemente di 8 numeri binari di 3 bit e di 64 numeri binari di 6 bit.

Esempio di un tentativo di traduzione dell’interpretazione tradizionale: l’interpretazione di Leibniz e di Bouvet lega appunto le figure di Fo-Hi alla numerazione binaria come si vede nella figura seguente (vedi immagine).

Peano e il byte

• C’è una specie di appendice a questa breve storia della scoperta leibniziana della corrispondenza tra rappresentazione binaria e le figure dell’I-Ching. Infatti, le sequenze prese in considerazione da Leibniz non comprendono le sequenze di 8 bit che costituiscono il byte, il gruppo di bit associato ai caratteri della tabella ASCII (estesa). Tuttavia, un pioniere della logica matematica e ammiratore dell’opera di Leibniz, Giuseppe Peano, nel 1898 inventa una stenografia basata su elementi che corrispondono a gruppi di 8 cifre binarie, osservando che il loro numero è all’incirca pari a quello delle sillabe delle lingue europee. Non è ancora l’origine ufficiale del byte, perché non abbiamo prove che l’idea di Peano abbia avuto influenza sull’origine di questa unità di misura. Quello che è noto è però che Peano si dedicò alla realizzazione di un congegno meccanico per scrivere utilizzando questo codice.

Bit e byte

• BIT il bit è l’unità minima di misura dell’informazione (dall’inglese “binary digit”), definita come la quantità minima di informazione che serve a distinguere due possibili eventi. Un bit è una cifra binaria, ovvero uno dei due simboli del sistema numerico binario, classicamente chiamati “zero” 0 e “uno” 1.
• BYTE una sequenza di 8 bit viene chiamata byte, nome che deriva dalla parola inglese “bite” (“morso”, “boccone”, “pezzo” in italiano) coniato anche per assonanza col termine “bit”, ma rinominato per evitare confusioni accidentali di pronuncia con questo. Il byte è divenuto l’unità di misura fondamentale della quantità di informazione e delle capacità di memoria.

La possibilità di rappresentare informazioni di varia natura attraverso numeri permette di manipolare le informazioni rappresentate attraverso operazioni fra numeri che i calcolatori sono in grado di compiere in modo efficiente.

Rappresentazione di numeri in bit

Rappresentazione decimale

• Comunemente, i numeri vengono scritti in notazione posizionale. In notazione posizionale, il significato di ogni cifra dipende dalla sua posizione. Per esempio, i due numeri 73 e 37 hanno significati diversi nonostante siano composti dalle stesse cifre (“3” e “7”). In base 10, le cifre che compongono i numeri interi hanno significato (da destra verso sinistra) di unità, decine, centinaia, etc. ESEMPIO: 235 = 2 centinaia, 3 decine, 5 unità = 2x100 + 3x10 + 5x1.

Rappresentazione binaria

• Allo stesso modo, nella rappresentazione di numeri in base 2 (binaria), le “cifre” possibili sono soltanto due “0” e “1” e, in modo analogo nella base 10, il loro valore è uguale a potenze crescenti della base numerazione 1 = 2⁰, 2 = 2¹, 4 = 2², 8 = 2³, etc (destra verso sinistra).

ESEMPIO: il numero binario 10011 sarà uguale al numero = 1x16 + 0x8 + 0x4 + 1x2 + 1x1 = (10011)₂ (19)₁₀.

Da un numero decimale a un numero binario

Il sistema binario o a "base due" ha solo due simboli: 0 e 1. Per aggiungere un’unità in binario basta modificare la cifra meno significativa da 0 a 1.

Questa regola vale solo se l’ultima cifra a destra del numero in esame è uno 0. Nel caso di numeri grandi bisogna semplicemente ignorare le cifre più significative e fare sempre riferimento a quella meno significativa. Se tutte le cifre del numero in esame sono pari a 1, dovrai aggiungerne un’altra. Semplicemente, si aggiunge una nuova cifra (con valore 1) all’estrema sinistra del numero e si impostano a 0 tutte le altre estremità (Esempio: 0 = zero, 1 = uno e 10 = due). A differenza del sistema decimale, il dieci (1010) non rappresenta un numero "speciale"? In binario è il numero otto (1000) a essere molto più importante e speciale perché è il risultato di 2 x 2 x 2, allo stesso modo lo sono anche il sedici (10000) e il trentadue (100000) e così via.

Da un numero binario a un numero decimale

Prendi nota della posizione occupata dalle singole cifre che compongono il numero binario da convertire. Il sistema binario ha solo due simboli, quindi la posizione assunta da ogni singola cifra rappresenta una potenza di due, il cui indice si incrementa spostandosi verso sinistra:

• 1 è in prima posizione (2⁰ = 1).
• 10 è in seconda posizione (2¹ = 2).
• 100 è in quarta posizione (2² = 4).
• 1000 è in ottava posizione (2³ = 8).

Adesso moltiplica ogni cifra del numero da convertire per il valore corrispondente alla sua posizione. Inizia dalla cifra meno significativa, quella all’estrema destra, e moltiplica il relativo valore (0 o 1) per uno. Adesso, su una nuova riga, moltiplica il valore della seconda cifra per due. Ripeti questa operazione per tutte le cifre che compongono il numero binario da convertire continuando a moltiplicare il relativo valore per la rispettiva posizione occupata (cioè per la corrispondente potenza di due). Adesso che abbiamo convertito ogni singola cifra binaria nel corrispettivo decimale, per calcolare il valore finale occorre semplicemente sommare fra loro i singoli prodotti.

ESEMPIO: Qual è il corrispettivo in decimale del numero binario 10011? (si parte da destra)

• 1x1 = 1.
• 1x2 = 2.
• 0x4 = 0.
• 0x8 = 0.
• 1x16 = 16.
• 1 + 2 + 16 = 19.

Quindi il numero binario 10011 corrisponde al numero decimale 19.

Si osservi che si usa la notazione per dire che il numero è rappresentato in base In una() .sequenza di bit si usa chiamare il bit più a destra come il meno significativo (in quanto è quello che “vale” meno, come le unità in base 10). Analogamente, il bit più a sinistra si chiama bit più significativo.

Rappresentazione esadecimale

• Esiste inoltre, un’altra rappresentazione che riveste un ruolo di notevole importanza nell’informatica: la rappresentazione esadecimale. Il sistema numerico esadecimale (a volte abbreviato come hex) è un sistema numerico posizionale in base 16. Per questo motivo, ha necessità di usare 16 simboli per rappresentare le cifre. Oltre alle “classiche” cifre da 0 a 9 presenti nella numerazione in base 10, che hanno lo stesso valore della base 10, la rappresentazione esadecimale utilizza le seguenti sei cifre aggiuntive:

• “a” oppure “A”, con valore 10.
• “b” oppure “B”, con valore 11.
• “c” oppure “C”, con valore 12.
• “d” oppure “D”, con valore 13.
• “e” oppure “E”, con valore 14.
• “f” oppure “F”, con valore 15.

La tabella (vedi immagine) elenca tutte le cifre esadecimali (seconda colonna), il loro valore in base 10 (prima colonna) e la rappresentazione di ogni cifra in base 2 (terza colonna).

Da un numero esadecimale a un numero decimale

Un metodo per convertire un numero esadecimale in decimale è quello di moltiplicare le sue cifre per le potenze della base 16.

Esempio: FB3 in esadecimale corrisponde al numero 4019 in base decimale.

x + x + 3 x = 15 x + 11 x + 3 x = 15 x 256 + 11 x 16 + 3 x 1 = 3840² 1 0 2 1 0(3) = 16 16 16 16 16 1616 + 176 + 3 = 4019.

Da un numero decimale a un numero esadecimale

L’operazione inversa - da decimale ad esadecimale - si realizza con una serie di divisioni successive. Si utilizza la divisione con resto.

Esempio: convertiamo 4019 in esadecimale.

4019:16 = 251 con resto 3 il resto 3 è dato dalla divisione ulteriore per 16 della parte prima della virgola, quindi: 4019:16 = 251,1875. Facendo quindi 0,1875 x 16 = 3.

Il quoziente 251 va di nuovo diviso per 16, facendo quindi 251:16 = 15 con resto 11 il resto 11 è dato dalla divisione ulteriore per 16 della parte prima della virgola, quindi: 251:16 = 15,6875. Facendo quindi 0,6875 x 16 = 11.

Il quoziente 15 è minore della base 16 e il procedimento di divisione si arresta. Si scrive quindi il numero partendo dall’ultimo risultato ottenuto e si risale la successione dei resti. Il numero esadecimale è 15-11-3 cioè F-B-3 che si scrive FB3, da cui 4019 = (3)₁₆.

• Si noti come la cifra più grande in ogni base di numerazione abbia sempre il valore della base meno uno: in base 10 la cifra più grande è 9 = 10-1, in base 2 la cifra più grande è 1 = 2-1, mentre in base 16 la cifra più grande è = 16-1 che vale 15.() = (15)₁₆ 10.
• Rispetto alla rappresentazione binaria, la rappresentazione esadecimale è più compatta: siccome la rappresentazione in base 16 può utilizzare più cifre (16) allora uno stesso numero si può scrivere con un numero minore di cifre.

Esempio: il numero 235 si scrive con 2 cifre esadecimali, 3 cifre in base 10 e 8 cifre in base 2.

= 2x100 + 3x10 + 5x1(235)₁₀

= 1x128 + 1x64 + 1x32 + 1x8 + 1x2 + 1x1(11101011)₂ = 14x16 + 11()₁₆

Conversione di base

• Per convertire un numero x dalla base 10 ad un’altra base b, si eseguono una serie di divisioni. Tale procedura è descritta di seguito:

1. Si ponga e k = 0 =.
2. Si divida per b. Siano il quoziente della divisione e il resto.
3. Se è uguale a 0 si termina e la rappresentazione di x in base b è data da tutti i resti nel seguente ordine: = ( … ) −.
4. Ovvero con l’ultimo resto ottenuto bit più significativo, andando indietro fino al bit meno significativo che è dato dal primo resto ottenuto.
5. Se è diverso da 0, si pone si incrementa k e si torna al passo 2. = +.

Esempio1: viene convertito il numero 235 da base 10 a base 2 effettuando la sequenza di divisioni precedentemente illustrate (i resti delle divisioni sono evidenziati in grassetto).

• 235 : 2 = 117,5 resto 0,5 x 2 = 1.
• 117 : 2 = 58,5 resto 0,5 x 2 = 1.
• 58 : 2 = 29 resto 0.
• 29 : 2 =14,5 resto 0,5 x 2 = 1.
• 14 : 2 = 7 resto 0.
• 7 : 2 = 3,5 resto 0,5 x 2 = 1.
• 3 : 2 = 1,5 resto 0,5 x 2 = 1.
• 1 : 2 = 0,5 resto 0,5 x 2 = 1.

Alla luce del risultato delle divisioni, possiamo dire che (235) = (11101011)₁₀ 2.

Esempio 2: in modo simile, è possibile convertire lo stesso numero 235 in base 16 facendo le seguenti divisioni.

• 235 : 16 = 14,6875 resto 0,6875 x 16 = 11.
• 14 : 16 = 0,875 resto 0,875 x 16 = 14.

Ricordando che le cifre di valore 11 e 14 in base 16 sono rispettivamente “B” e “E”, possiamo concludere che (235) = ()₁₀ 16.

Conversione fra binario ed esadecimale e viceversa

• La conversione di un numero rappresentato in una certa base b in un’altra base, quindi potenza a-esima di b, è molto semplice in quanto si riesce a fare senza compiere la sequenza di divisioni viste in precedenza. È questo il caso della conversione da base 2 a base, molto frequente 4 16 = 2 in informatica.

Nel passaggio da base 2 a base è sufficiente: =

1. Raggruppare le cifre binarie in gruppi di 4 a partire dal bit meno significativo;
2. Codificare il singolo gruppo di bit con la cifra esadecimale corrispondente;
3. Affiancare le cifre esadecimali ottenute secondo l’ordine dei gruppi di 4 bit che le hanno generate.

Esempio: (11101011) = ((1110)(1011)) = ()₂ 2 16.

• 0 x 1 = 0 e 1 x 2 = 2 e 1 x 4 = 4 e 1 x 8 = 8 0+2+4+8 = 14.
• Dal binario 1110 ottengo il decimale 14 ottengo l’esadecimale E.
• 1 x 1 = 1 e 1 x 2 = 2 e 0 x 4 = 0 e 1 x 8 = 8 1+2+0+8 = 11.
• Dal binario 1011 ottengo il decimale 11 ottengo l’esadecimale B.

Analogamente, per convertire da esadecimale (base 16) a binario (base 2), si possono affiancare le conversioni delle singole cifre.

Esempio: (3) = ((11)(1101)) = (111101)₁₆ 2 2.

• 3 = 11 e poi D =13 = 1101.
• Perché: 0=0, 1=1, 2=10, 3=11, 4=100, 5=101, 6=110, 7=111, 8=1000, 9=1001, 10=1010, 11=1011, 12=1100 e 13=1101.

Si osservi che questa proprietà che permette la conversione fra basi senza fare le divisioni, si può sfruttare soltanto per conversioni fra basi di cui una è potenza dell’altra (come 16 e 2). Non si può fare invece nel passaggio da base 10 a base 2. Difatti:

Esempio: (83) ≠ ((1000)(0011))₁₀ 2.

Operazioni fra bit (e byte)

I calcolatori compiono le operazioni su bit a partire da alcune operazioni fondamentali dette operazioni booleane.

• NOT corrisponde alla negazione NOT x è la negazione della variabile x.
• AND corrisponde alla congiunzione x AND y è vera se sia x che y sono vere.
• OR corrisponde alla disgiunzione x OR y è vera se almeno una fra x e y è vera;
• XOR corrisponde alla OR esclusivo x XOR y è vera operazioni XOR AND booleane se soltanto una fra x e y è vera. Lo XOR si può anche vedere come un “indicatore di diversità” x XOR y vale 1 se x e y hanno un valore diverso, 0 se hanno lo stesso valore. OR.

Un’operazione si dice:

• Unaria, se richiede soltanto una variabile (la NOT è un’operazione unaria).
• Binaria, se utilizza due variabili (le operazioni AND, OR e XOR sono binarie).

Bisogna prestare attenzione al fatto che in questo caso, l’aggettivo “binario” sottolinea il numero di operandi dell’operazione, non la base di numerazione in cui si opera.

La combinazione di operazioni booleane, anche con l’uso di parentesi, definisce espressioni booleane. I valori delle espressioni booleane si rappresentano in tabelle di verità. In una tabella di verità sono elencate tutte le possibili combinazioni delle variabili coinvolte in un’espressione su ogni riga. Inoltre, per ogni possibile valore delle variabili viene scritto il valore dell’espressione. Nelle tabelle di verità, il valore “1” rappresenta “vero”, mentre lo “0” rappresenta “falso”. Nell’immagine sono riportate le tabelle di verità delle sopra menzionate operazioni elementari. Inoltre, è possibile comporre espressioni booleane complesse.

Esempio: espressione booleana complessa (vedi l’immagine della tabella della verità a destra) ( = ) ( ).

Si osservi che:

• Il numero di combinazioni possibili, ovvero il numero di righe, è pari a con n uguale al numero delle variabili coinvolte nell’espressione;
• La tabella di verità di un’espressione complessa è costruita a partire dalle tabelle di verità delle espressioni che la compongono.

Le operazioni appena descritte (NOT, AND, OR, XOR) si possono appli