Fondamenti di Informatica

(1)

Fondamenti di Informatica

Linguaggi, Codifica e Rappresentazione dell’Informazione

Prof. Christian Esposito

Corso di Laurea in Ingegneria Meccanica e Gestionale (Classe I)

(2)

Cosa abbiamo visto la volta scorsa

• Gli elaboratori sono strumenti per risolvere (o aiutare a risolvere) problemi basati sulle informazioni

• Ma come ciò avviene?

1. Abbiamo bisogno di codificare e memorizzare opportunamente dati e informazioni

2. Abbiamo bisogno di impartire le giuste istruzioni per risolvere correttamente problemi

Linguaggi, Codifica e Rappresentazione dell’Informazione ⁰¹^/109

(3)

Cosa vedremo oggi

• Gli elaboratori sono strumenti per risolvere (o aiutare a risolvere) problemi basati sulle informazioni

• Ma come ciò avviene?

1. Abbiamo bisogno di codificare e memorizzare opportunamente dati e informazioni

2. Abbiamo bisogno di impartire le giuste istruzioni per risolvere correttamente problemi

(4)

Quale Lingua parla l’Elaboratore?

• Come rendere dati e informazioni comprensibili ad un elaboratore?

• Informazioni e dati per essere trattati da un elaboratore devono essere opportunamente codificati

Linguaggi, Codifica e Rappresentazione dell’Informazione ⁰³^/109

(5)

Linguaggio

• Alfabeto

• Collezione di simboli grafici, aventi di solito un ordine ben preciso, che servono a rappresentare le parole di una lingua

• I simboli spesso (ma non sempre) sono lettere ovvero rappresentazione scritta di suoni linguistici

• Vocabolario (o lessico)

• Insieme delle parole ammissibili di una lingua

• Grammatica

• Insieme di regole utili alla corretta costruzione di frasi, sintagmi e parole

• Il termine si riferisce allo studio delle suddette regole

• Semantica

• Studia il significato delle parole (semantica lessicale), degli insiemi delle parole, delle frasi (semantica frasale) e dei testi

(6)

La Funzione dei Linguaggi

• I linguaggi (verbali, non verbali, orali, scritti, etc.) sono strumenti che contribuiscono a

• Rappresentare le informazioni

• Concetti, pensieri, emozioni, etc., vengono formalizzati attraverso i linguaggi per poter essere memorizzati, trasferiti ed elaborati

• Memorizzare le informazioni

• La scrittura

• Trasferire le informazioni

• La comunicazione

• Elaborare le informazioni

• Le deduzioni nella logica

Linguaggi, Codifica e Rappresentazione dell’Informazione ^05/109

(7)

Problemi relativi ai Linguaggi

• Accordo sui simboli

• a b c d e f g …

• Accordo sul lessico

• casa, gatto, automobile, vado, …

• Accordo sulla grammatica

• <soggetto verbo complemento>

• Accordo sulla semantica

• La nonna chiude la porta (OK)

• La porta chiude la nonna (NO)

• Accordo sulla codifica

• Regole per trasformare simboli, parole e frasi di un linguaggio in una nuova rappresentazione con possibilità di effettuare in maniera corretta anche l’operazione inversa

• “a” in codice Morse (Samuel Morse, pittore e storico inglese) è “ . – ”

“b” in codice Morse è “ – . . . ”

(8)

Codice Braille

• Lettera “a”

• Lettera “b”

(9)

Codifica dei Numeri

• Linguaggio di partenza

• I numeri

• Codifica 1

• Numerazione decimale

• 5, 45, 670

• Codifica 2

• Numerazione binaria

• 101, …

• Codifica 3

(10)

Quipo

• Quipo è un insieme di cordicelle annodate, distanziate in modo sistematico tra loro e legate a una corda più grossa e corta che le sorregge.

•I quipo servivano per i calcoli matematici. I nodi delle corde sono di diversi colori: rappresentavano numeri, e dalla loro reciproca posizione se ne potevano ricavare le unità, le decine, le centinaia e le migliaia.

(11)

I Linguaggi Naturali: Ambiguità

• Per comunicare tra loro gli uomini hanno sviluppato i linguaggi naturali

• Italiano, inglese, francese, etc

• Una caratteristica negativa di tali linguaggi è la loro inerente ambiguità

• Una qualsiasi frase formulata è potenzialmente polisemica

• Il significato che viene dato alla frase da chi riceve il messaggio può essere diverso da quello datogli dal mittente

• Comprendere il significato di una frase in linguaggio naturale è più semplice se questa viene pronunciata in un dato contesto

(12)

I Linguaggi Naturali:

Disambiguazione

• Comprendere il significato di una frase in linguaggio naturale è più semplice se questa viene pronunciata in un dato contesto

• Concorso Ippico

• Circolo Scacchistico

• Sartoria

• Palestra

(13)

I Linguaggi Naturali nella

Comunicazione con i Calcolatori

• Per comunicare con un elaboratore, l’ambiguità dei linguaggi naturali rappresenta un grosso problema

• Bisognerebbe fornire all’elaboratore anche il contesto e la conoscenza (le regole) per disambiguare le frasi

• La rappresentazione (comprensibile al calcolatore) di contesto e regole è molto complicata

• In alcuni casi la disambiguazione è difficile anche per gli uomini

• È necessario l’utilizzo dei cosiddetti Linguaggi Formali

(14)

I Linguaggi Formali

• Sviluppati ed impiegati in tutti gli ambiti in cui è necessario evitare l’ambiguità

• Informatica, matematica, logica, etc

• La definizione di un Linguaggio Formale prevede

• L’individuazione di un alfabeto, ovvero, di un elenco (finito) di simboli

• La definizione di una grammatica formale, ovvero un insieme di regole sintattiche che specificano come i simboli dell’alfabeto possono essere combinati tra loro per costituire le frasi ben formate all’interno del linguaggio stesso

• Inoltre, le semantiche formali consentono di attribuire un significato non ambiguo alle frasi in un linguaggio formale

(15)

Usare e Programmare il computer

• I Programmi (o software) risolvono problemi specifici con approccio basato sulle informazioni e vengono eseguiti dai computer

Usare

programmi realizzati da altri

Programmare

scrivere su Facebook scrivere una relazione con

realizzare Programmi complessi come ad es.

Facebook realizzare

contenuti didattici interattivi

realizzare

Programmi con Matlab

Linguaggi naturali

Linguaggi formali (di programmazione)

Numeri binari, codifica binaria dei caratteri, etc.

(16)

Rappresentazione dell’Informazione:

Accordo sui Simboli

• L’informazione è rappresentata dai dati, che a loro volta sono espressi in forma di simboli

• La stessa informazione può essere codificata con simboli e modalità diverse

• 1963 -> simboli “0”, “1”, “2”, …

• MCMLXIII -> simboli della codifica romana

• Millenovecentosessantatre -> rappresentazione testuale

• …

(17)

Rappresentazione dell’informazione nei calcolatori – 1/2

• Consideriamo un alfabeto ridotto che contiene solo i simboli “0” e “1”

• Un bit (contrazione di binary digit) è un simbolo scelto sull’alfabeto {0, 1}

• Nei calcolatori ogni elemento (numeri, testo, audio, video, istruzioni, etc) viene rappresentato esclusivamente con sequenze di bit

• I dati e le istruzioni vengono codificati con sequenze di bit

(18)

Rappresentazione dell’informazione nei calcolatori – 2/2

• Per trattare (memorizzare, elaborare, trasmettere, etc.) l’informazione, il calcolatore

• Codifica l’informazione disponibile scrivendo su un supporto fisico

• Manipola il supporto con opportune trasformazioni fisiche, ottenendo una versione modificata del supporto

• Decodifica l’informazione corrispondente al risultato dell’elaborazione leggendo dalla versione modificata del supporto

(19)

Codifica Binaria

• Alfabeto binario: usiamo solo due cifre 0,1 (bit)

• Problema: assegnare una sequenza di bit univoca a tutti gli oggetti in un insieme predefinito

• Quanti oggetti posso rappresentare con k bit?

• 1 bit => 2 stati (0, 1) => 2 oggetti

• 2 bit => 4 stati (00, 01, 10, 11) => 4 oggetti

• 3 bit => 8 stati (000, 001, …, 111) => 8 oggetti

• …

• k bit => 2^k stati => 2^k oggetti

• Quanti bit mi servono per codificare N oggetti?

• N ≤ 2^𝑘=> k ≥ 𝑙𝑜𝑔₂𝑁 => k = 𝑙𝑜𝑔₂𝑁 (intero superiore)

(20)

Combinazioni di Bit

Bit a

disposizione Lecombinazioni Il numero di

combinazioni

1 0, 1 2 =2

¹

2 00, 01, 10, 11 4 =2

²

3 000, 001, 010, 011, 100, 101, 110, 111

8 =2

³

4 0000, 0001, 0010, 0011, 0100, 16 =2

⁴

0101, 0110, 0111,1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

5 00000, 00001, 00010, … 32 =2

⁵

… … …

(21)

Un Primo Esempio di Codifica:

Interruttore

• Due sole possibilità (stati)

• Spento

• Acceso

• L’informazione sullo stato dell’interruttore corrisponde dunque alla scelta fra due sole alternative

(22)

Un Primo Esempio di Codifica:

Interruttore

• 1 bit rappresenta lo stato dell’interruttore

• Interruttore acceso: 1

• Interruttore spento: 0

(23)

Codifica di un’Informazione con

Più di Due Stati: Il Semaforo

(24)

Diverse Codifiche per le Stesse Informazioni

• Rappresentazione degli stati di un semaforo mediante bit

Stato Codifica

ROSSO 1 0 0

VERDE 0 0 1

GIALLO 0 1 0

Stato Codifica

ROSSO 0 0

VERDE 0 1

GIALLO 1 0

3 bit

2 bit

(25)

Codifica di un’Informazione con Più di Due Stati: Giorni della Settimana

• Problema: assegnare un codice binario univoco a tutti i giorni della settimana

• Giorni della settimana: N = 7 => 𝑘 ≥ 𝑙𝑜𝑔₂ 7 => 𝑘 = 3

• Con 3 bit possiamo ottenere 8 diverse sequenze

• Ne servono 7, quali utilizziamo?

• Quale configurazione associamo a quale giorno?

• Osservazione: quanto detto fino ad ora vale sotto l’ipotesi che i codici abbiano tutti la stessa lunghezza

(26)

I Giorni della Settimana in Binario

Lunedì Martedì Mercoledì

Giovedì Venerdì Sabato Domenica

000 001 010 011 100 101 111 110

Lunedì Martedì

Giovedì Mercoledì

Sabato Venerdì

Domenica

00 01 10 11

Lunedì Giovedì Martedì

Mercoledì

Sabato Venerdì Domenica

0

1

Lunedì

Sabato

Giovedì Venerdì

Martedì Domenica

Mercoledì

1 bit

2 “gruppi”

2 bit

4 “gruppi”

3 bit

8 “gruppi”

(27)

I Giorni della Settimana in Binario

Lunedì Martedì

Mercoledì Giovedì

Venerdì Sabato

Domenica

000 001 010 011 100 101 111 110

Giovedì

Lunedì Venerdì Martedì

Sabato Mercoledì

Domenica

00 01 10 11

Sabato Giovedì Martedì

Domenica Lunedì Mercoledì

Venerdì

0

1

Lunedì

Sabato

Giovedì Venerdì

Martedì Domenica

Mercoledì

1 bit

2 “gruppi”

2 bit

4 “gruppi”

3 bit

8 “gruppi”

(28)

Codifica dei Caratteri – 1/5

• Problema: è possibile applicare queste idee alla rappresentazione di informazione più complessa, ad esempio di un testo?

• Un testo è rappresentato attraverso una successione di caratteri

• Ogni carattere viene scelto all’interno di un insieme finito di simboli (alfabeto)

(29)

Codifica dei Caratteri – 2/5

• Con 8 bit, è possibile rappresentare la scelta fra 256 alternative diverse (2⁸=256)

• Da 00000000… a 11111111

• Passando per tutte le combinazioni intermedie (00000001, 00000010, …)

• Nel caso del testo, possiamo far corrispondere diverse combinazioni di 8 bit (otto cellette, ciascuna delle quali può contenere 0 o 1) a caratteri diversi

Ogni singolo CARATTERE viene

codificato con una combinazione di 8

bit

(30)

Codifica dei Caratteri – 3/5

• Ad esempio:

• 00000000 -> A

• 00000001 -> B

• 00000010 -> C

• 00000011 -> D

• 00000100 -> E

• …. e così via

(31)

Codifica dei Caratteri – 4/5

• Sono stati proposti vari standard per la codifica dei caratteri, tra cui il più diffuso è quello ASCII (American Standard Code for Information Interchange) del 1968, che con 7 bit codifica un alfabeto di 128 caratteri.

•Lo standard che sta prendendo piede e che dovrebbe essere il successore di ASCII è UTF-8 del 1992, codifica principale di Unicode per Internet secondo il W3C.

(32)

Codifica dei Caratteri - 5/5

• Soluzione: una parola (o più parole) sarà rappresentata dal computer come una successione di gruppi di 8 bit

O G G I P I O V E

01001111 01000111 01000111 01001001 00100000 01010000 01001001 01001111 01010110 01000101

(33)

La Codifica dei Numeri

• Obiettivo

• Codifica in binario dei numeri per favorire l’elaborazione da parte dei calcolatori

• Vincoli

• Codifica e decodifica devono essere definite in maniera tale da poter essere compiute in maniera automatica

• Problema

• Deve essere possibile codificare tutti i numeri

• 0, 1, 2, 3, …

• -1, -2, -3, …

• -12.4, -2.004, 0.56, 134.89, …

• …in sequenze

• 0000000, 000001, 000010, …

(34)

Notazione Posizionale

• Concetto di base di rappresentazione B

• Rappresentazione del numero come sequenza di simboli, detti cifre

• Appartenenti ad un alfabeto composto da B simboli distinti

• Ogni simbolo rappresenta un valore fra 0 e B-1

• Il valore di un numero v espresso in questa notazione è ricavabile

• A partire dal valore rappresentato da ogni simbolo

• Pesato in base alla posizione che occupa nella sequenza

(35)

Valore di un Numero in Notazione Posizionale

• Formalmente, il valore di un numero v espresso in questa notazione è dato dalla formula

• Dove B è la base

n è il numero

di cifre nel numero d è la cifra alla

i

^esima

posizione nel numero

(37)

Sistemi di Numerazione Posizionale

• Il nostro sistema di numerazione

• Utilizza una notazione posizionale ed è in base 10

• L’alfabeto utilizzato è l’insieme dei simboli {0, 1, 2, …, 9}

• Non è l’unico sistema possibile

• Essendo posizionale, il valore di una “sequenza” di simboli viene calcolata assegnando dei “pesi” ad ogni simbolo a seconda della sua posizione

4523

10

=

4 * 10 ³ + 5 * 10 ² +2 * 10 ¹ + 3 * 10 ⁰

3 2 1 0

P o sizio n i

Stringa di simboli

Base

(38)

Sistemi di Numerazione Posizionale

• 3251

• 1 unità , 5 decine, 2 centinaia , 3 unità di migliaia

• 745814763

• 3 unità, 6 decine, 7 centinaia, 4 unità di migliaia, 1 decina di migliaia, 8 centinaia di migliaia, 5 unità di milioni, 4 decine di milioni, 7 centinaia di milioni

(39)

Sistemi di Numerazione più Diffusi

Sistema Base Simboli

Usato dagli umani?

Usato dai computer?

Decimale

10 0, 1, … 9 Si No

Binario

2 0, 1 No Si

Ottale

8 0, 1, … 7 No No

Esadecimale

16 0, 1, … 9, A, B, … F

No No

(40)

Esempio

25 ₁₀ = 11001 ₂ = 31 ₈ = 19 ₁₆

Base

(41)

Conversioni tra Basi (più Diffuse)

• Le possibilità

Esadecimale

Decimale Ottale

Binario

(42)

Da decimale a decimale

Esadecimale

Decimale Ottale

Binario

(43)

Da Decimale a Decimale

125₁₀ => 5 x 10⁰ = 5 + 2 x 10¹ = 20 + 1 x 10² = 100

125

Base

Peso

(44)

Da Binario a Decimale

Esadecimale

Decimale Ottale

Binario

(45)

Da Binario a Decimale: Tecnica

• Moltiplica ciascun bit per 2ⁿ, dove n è il “peso” del bit

• Il peso è dato dalla posizione del bit, a partire da 0 sulla destra

• Somma i risultati

(46)

Da Binario a Decimale:

Esempio

101011

₂

=> 1 x 2

⁰

= 1 + 1 x 2

¹

= 2 + 0 x 2

²

= 0 + 1 x 2

³

= 8 + 0 x 2

⁴

= 0 + 1 x 2

⁵

= 32

43

₁₀

Bit in posizione “0”

(47)

Da Binario a Decimale:

Esempio

N

₂

= 101010

N

₁₀

= 1 x 2

⁵

+ 0 x 2

⁴

+ 1 x + 0 x 2

²

+ 1 x + 0 x 2

⁰

= 32 + 8 + 2 = 42

N

₂

= 11011

N = 2

⁰

+ 2

¹

+ 2

³

+ 2

⁴

= 1 + 2 + 8 + 16 = 27

2

³

2

¹

(48)

Da Binario a Decimale: Altri Esempi

(49)

Da Decimale a Binario

Esadecimale

Decimale Ottale

Binario

(50)

Da Decimale a Binario: Tecnica

• Dividi per due e tieni traccia del resto

• Il primo resto è il bit in posizione 0 (LSB, least-significant bit)

• Il secondo resto è il bit in posizione 1

• E così via…

(51)

Da Decimale a Binario:

Esempio

2

0 1 2

1 1 2

3 1 2

7 1 2

15 1 2

31 0 2 125

62 1

125₁₀ = 1111101₂ 125₁₀ = ?₂

(52)

Da Decimale a Binario:

Esempio

N

₁₀

= 51 (Da decimale a binario) N

₂

= ???

51 1 2

25 2

1 12 2

0 6

0 2

3 1 2

1 1 2 N

₂

= 110011 0

(53)

Da Ottale a Decimale

Esadecimale

Decimale Ottale

Binario

(54)

Da Ottale a Decimale: Tecnica

(55)

Da Ottale a Decimale: Esempio

724₈ =>4 x 8⁰ = 4 + 2 x 8¹ = 16 + 7 x 8² = 448

468₁₀

(56)

Da Esadecimale a Decimale

Esadecimale

Decimale Ottale

Binario

(57)

Da Esadecimale a Decimale:

Tecnica

(58)

Da Esadecimale a Decimale:

Esempio

ABC₁₆ => C x 16⁰ = 12 x 1 = 12 + B x 16¹ = 11 x 16 = 176 + A x 16² = 10 x 256 = 2560

2748₁₀

(59)

Da Ottale a Binario

Esadecimale

Decimale Ottale

Binario

(60)

Da Ottale a Binario: Tecnica

• Converti ogni cifra ottale in una rappresentazione binaria equivalente a 3-bit

(61)

Da Ottale a Binario: Esempio

705₈ = ?₂

7 0 5

111 000 101

(62)

Da Esadecimale a Binario

Esadecimale

Decimale Ottale

Binario

(63)

Da Esadecimale a Binario:

Tecnica

• Converti ogni cifra esadecimale in una rappresentazione binaria equivalente a 4 bit

(64)

Da Esadecimale a Binario:

Esempio

10AF₁₆ = ?₂

1 0 A F

0001 0000 1010 1111

10AF₁₆ = 0001000010101111₂

(65)

Da Decimale a Ottale

Esadecimale

Decimale Ottale

Binario

(66)

Da Decimale a Ottale: Tecnica

• Dividi per 8

• Tieni traccia del resto

(67)

Da Decimale a Ottale: Esempio

8 1234

154 2 8

19 2 8

2 3 8

0 2

1234₁₀ = 2322₈ 1234₁₀ = ?₈

(68)

Da Decimale ad Esadecimale

Esadecimale

Decimale Ottale

Binario

(69)

Da Decimale ad Esadecimale:

Tecnica

• Dividi per 16

• Tieni traccia del resto

(70)

Da Decimale ad Esadecimale:

Esempio

1234₁₀ = ?₁₆

1234₁₀ = 4D2₁₆

16 1234

77 2 16

4 13 = D 16

0 4

(71)

Da Binario ad Ottale

Esadecimale

Decimale Ottale

Binario

(72)

Da Binario ad Ottale

• Raggruppa i bit in gruppi di tre, partendo dalla destra

• Converti in cifre ottali

(73)

Da Binario ad Ottale: Esempio

1011010111₂ = ?₈

1 011 010 111

1 3 2 7

(74)

Da Binario ad Esadecimale

Esadecimale

Decimale Ottale

Binario

(75)

Da Binario ad Esadecimale:

Tecnica

• Raggruppa i bit in gruppi di quattro, partendo dalla destra

• Converti in cifre esadecimali

(76)

Da Binario ad Esadecimale:

Esempio

1010111011₂ = ?₁₆

10 1011 1011

2 B B

1010111011₂ = 2BB₁₆

(77)

Da Ottale ad Esadecimale

Esadecimale

Decimale Ottale

Binario

(78)

Da Ottale ad Esadecimale:

Tecnica

• Idea: usare la codifica binaria come rappresentazione intermedia

(79)

Da Ottale ad Esadecimale:

Esempio

1076₈ = ?₁₆

1 0 7 6

001 000 111 110

2 3 E

1076 = 23E

(80)

Da Esadecimale ad Ottale

Esadecimale

Decimale Ottale

Binario

(81)

Da Esadecimale ad Ottale:

Tecnica

• Idea: usare la codifica binaria come rappresentazione intermedia

(82)

Da Esadecimale ad Ottale:

Esempio

1F0C₁₆ = ?₈

1 F 0 C

0001 1111 0000 1100

1 7 4 1 4

1F0C₁₆ = 17414₈ Linguaggi, Codifica e Rappresentazione dell’Informazione ^81/109

(83)

Più in generale…

• Per convertire un numero binario in un sistema che ha come base 2^z

• Raggruppare le cifre in gruppi di z elementi

• Convertire separatamente ciascun gruppo

(84)

Rappresentazione degli Interi:

“Modulo e Segno”

• N = 0, +1, -1, +2, -2, +3, -3,…

• Come possiamo rappresentare il segno di un numero?

• Idea: Aggiungiamo un ulteriore bit che poniamo a

• 1 se il numero è negativo

• 0 altrimenti

N

₁₀

= +14 N

₁₀

= -14

N

_ms

= 01110 N

_ms

= 11110

Esempio

(85)

Rappresentazione degli Interi:

“Modulo e Segno”

• Alfabeto binario

• Anche il segno è rappresentato da 0 o 1

• Indispensabile indicare il numero k di bit utilizzati

• Modulo e segno

• 1 bit di segno (0 positivo, 1 negativo)

• k-1 bit di modulo

• Esempio: +6₁₀= 0110ms -6₁₀= 1110_ms

• Si rappresentano i valori da -2^k-1+1 a 2^k-1-1

• Con 4 bit i valori vanno da -7 a +7

• Con 8 bit i valori vanno da -127 a +127

• Osservazione: due rappresentazioni dello 0

• Con 4 bit sono +0₁₀ = 0000_ms -0₁₀=1000_ms

(86)

Rappresentazione degli Interi: “Modulo e Segno”: Limiti sui Numeri

Rappresentabili

• 4 bit a disposizione

• Possiamo rappresentare da 0000 a 0111 e da 1000 a 1111, in decimale da 0 a 7 e da 0 a -7

• 5 bit a disposizione

• Possiamo rappresentare da 00000 a 01111 e da 10000 a 11111, in decimale da 0 a 15 e da 0 a -15

•…

• Con k bit a disposizione possiamo rappresentare numeri da 0 a 2^k-1- 1 e da -(2^k-1- 1) a 0

(87)

Numeri Interi in Complemento a Due – 1/5

• Idea: l’interpretazione posizionale viene mantenuta e si modifica soltanto il peso del bit più significativo, invertendolo

• Caratteristiche

• Lo zero ha una rappresentazione unica

• Tutti i numeri che hanno il bit più significativo uguale a 1 sono negativi (come prima)

• È sempre necessario specificare il numero di bit k che si vuole utilizzare per rappresentare un determinato numero

• Si rappresentano i valori da −2^k−1 a +2^k−1−1

• Con 4 bit i valori vanno da −8 a +7

• Con 8 bit i valori vanno da −128 a +127

(88)

Numeri Interi in Complemento a Due – 2/5

• Consideriamo un generico numero binario su 8 bit

• Per stabilire la codifica di un generico numero negativo n < 0, sapendo che necessariamente il bit più significativo va posto a 1, è sufficiente riportare nei restanti bit il numero positivo che, sommato a −2⁷, da il valore n

• Per esempio, proviamo a codificare −37. Essendo un numero negativo, il bit più significativo vale 1:

• Nella parte restante della tabella dovremo inserire quel numero che sommato a −128 da −37

• −128 + x = −37 => x = 128 – 37 = 91

−2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰

1 ? ? ? ? ? ? ?

(89)

Numeri Interi in Complemento a Due – 3/5

• La codifica binaria di 91 è 1011011, che riportato nella tabella precedente fornisce la codifica desiderata:

−2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰

1 1 0 1 1 0 1 1

(90)

Numeri Interi in Complemento a Due – 4/5

• Un metodo molto comodo per calcolare la

rappresentazione di −X a partire da quella di +X è il seguente

• Idea: effettuare il complemento di ogni bit di X, poi aggiungere 1

1. Codifica binaria di +6₁₀ => 0110₂ (N.B. ci vogliono 4 bit)

2. Complemento di tutti i bit => 1001_C2 (corrisponderebbe a −7₁₀) 3. Aggiungere 1 => 1010_C2 (che corrisponde a −6₁₀)

Linguaggi, Codifica e Rappresentazione dell’Informazione

1 + 1 = 0 col riporto di 1

−2³+ 2¹ = −8 + 2 = −6

Il complemento di 1 è 0

Il complemento di 0 è 1 1001 +

10101 =

89/109

(91)

Numeri Interi in Complemento a Due – 5/5

• Estensione del “segno”

• I valori positivi iniziano con 0, quelli negativi con 1

• Data la rappresentazione di un numero su k bit, la rappresentazione dello stesso numero su k+1 bit si ottiene aggiungendo (a sinistra) un bit uguale al primo

• Esempi

• Rappresentazione di -6 su 4 bit = 1010

(92)

Codifica dei reali e dei frazionari (1/6)

• Rappresentazione mediante interi

• L’insieme degli interi X può essere adoperato per rappresentare i reali x compresi nel medesi intervallo, approssimando il reale all’intero più prossimo.

X=r(x)=x ± 𝜀 ∶ 0 ≤ 𝜀 ≤ 1 2

• Rappresentazione dei frazionari

• Un numero frazionario rappresenta una classe di reali in modulo minore di 1, e per essi non è significativa la rappresentazione mediante interi.

• Si applica un fattore di scala 𝑀 = 𝑏^G, con n il numero di cifre e b la base di rappresentazione. Pertanto la rappresentazione di frazionari non negativi mediante interi diventa:

𝑋 = 𝑥 J 𝑀 ± 𝜀 ∶ 𝑥 𝜖 0,1 , |𝜀| ≤ ^N^OP

Q

• Esempio: 0,500 con M = 10³ viene rappresentato come 500, e 0,499 diventa 499.

(93)

Codifica dei reali e dei frazionari (2/6)

• Conversione dei numeri frazionari

• MOLTIPLICHIAMO la parte frazionaria del numero dato per 2;

• continuiamo a moltiplicare il RISULTATO ottenuto per 2 tenendo presente che, se il numero ottenuto è maggiore di 1 sottraiamo 1;

• andiamo avanti fino a quando

• non otteniamo un RISULTATO uguale a UNO oppure

• fino a quando otteniamo un RISULTATO GIA' OTTENUTO IN PRECEDENZA.

(94)

Codifica dei reali e dei frazionari (3/6)

• Virgola fissa e mobile

• Dicesi in virgola fissa una rappresentazione dei numeri con n cifre, in cui la posizione della virgola è predeterminata e non va esplicitamente espressa.

• Esempio: il numero .789x10^-1 è rappresentato come 078900 in una rappresentazione a 6 cifre.

• Dicesi in virgola mobile (o floating point) una rappresentazione in cui un numero reale è indicato dalla coppia (M,E), dove il primo termine prende il nome di mantissa e il secondo di esponente o caratteristica:

x = 𝑀 J 𝑏^S ± 𝜀

• M ed E possono essere rappresentati in modi diversi.

• Se b|M|<1, allora esiste un’altra rappresentazione (bM, E-1) che consente di ottenere una migliore approssimazione. Tra le possibili coppie che rappresentano x bisogna scegliere quella con l’approssimazione più alta, detta normalizzata, ovvero quando 𝑏^TU ≤ 𝑀 < 1.

(95)

Codifica dei reali e dei frazionari (4/6)

• Aritmetica in virgola mobile

• Data una coppia (M,E) si può effettuare uno shift a destra della mantissa ed incremento dell’esponente, sempre che E+1 sia rappresentabile:

Float shift right: 𝑀^W J 𝑏^S^X = 𝑀 J 𝑏^S = ^Y

N J 𝑏^SZU

• Uno shift a sinistra avviene come segue:

Float shift left: 𝑀^W J 𝑏^S^X = 𝑀 J 𝑏^S = (𝑀𝑏) J 𝑏^STU

• L’aritmetica in virgola mobile effettua le operazioni operando separatamente su mantissa ed esponente ed effettuando ove necessario operazioni di shift.

• Addizione – Dati due numeri (A, Ea) e (B, Eb), se Ea è maggiore di Eb si effettua lo shift a destra fino ad ottenere Ea = Eb, altrimenti quello a sinistra. Successivamente, si sommano le mantisse.

Esempio: Sommiamo A = (123 ×10⁰) e B = (456 ×10^-2), effettuiamo due shift a destra su B fino ad ottenere B = (4,56 ×10⁰), sommiamo le mantisse e il risultato è C = (127,56 ×10⁰).

(96)

Codifica dei reali e dei frazionari (5/6)

• Standard IEEE 754

• Per la rappresentazione dei numeri reali in macchina si adopera quella della virgola mobile binaria, come specificato nello standard IEEE 754. Per b=2, tale rappresentazione è la seguente:

x = (−1)^[J 𝑀 J 2^S

• Essendo M normalizzata, ha il primo bit uguale a 1, ciò consente di ometterlo, così da avere un bit in più per la rappresentazione del numero. Questa tecnica prende il nome di bit nascosto:

se M = ^UZ]_Q , si ha che x = (−1)^[J (1 + 𝑓) J 2^STU

• così che la rappresentazione è data dalla tripla (s, f, E).

• Per l’esponente si ha la rappresentazione polarizzata: dato il numero di bit N_e, e l’esponente da rappresentare, E quello rappresentato e bias la costante di polarizzazione si ha E = e + bias, con l’intervallo degli esponenti effettivi pari a 𝑒_abG ≤ 𝑒 ≤ 𝑒_acd.

(97)

Codifica dei reali e dei frazionari (6/6)

• Lo standard presenta vari formati di rappresentazione, tra i quali abbiamo quello a singola precisione su 32 bit e quella a doppia precisione su 64 bit. Nel primo caso, dati gli 8 bit per la rappresentazione dell’esponente, si ha che il suo intervallo di rappresentazione è pari a 0 < e < 255. Pertanto la formula di rappresentazione diventa:

x = (−1)^[J 2 ^eTUQf J (1 + 𝑓)

Y

con f pari alla parte frazionaria della mantissa, rappresentata con la tecnica del bit nascosto:

(98)

Esercizi 1

• Scrivere in binario semplice i seguenti numeri in base 10

• 5310

• 21110

• Scrivere in binario semplice su 7 bit il numero 13₁₀

• Scrivere in modulo e segno su 7 bit il numero 13₁₀

• Scrivere in modulo e segno su 7 bit il numero -13₁₀

(99)

Soluzione Esercizi

• 0001101

• 1001101

• 10001, In modulo e segno è -1₁₀

• RISPOSTA: Non è possibile. Ho bisogno di almeno 6 bit (010001)

(100)

Esercizi svolti

• 53 = 32 + 16 + 4 + 1

f = 11011000000000000000000

•Ricavare il corrispondente valore decimale.

•Convertire i seguenti numeri decimali in virgola mobile in singola precisione secondo lo standard IEEE 754:

1. −23.375₁₀ 2. −127.25₁₀ 3. +131.5₁₀ 4. −300.25₁₀ 5. −3.6₁₀

(103)

Esercizi Svolti

• Dato che e = 10000111₂ = 135₁₀.Si ha N=(−1)^s·2^(e−127)·1.f=

=−1·2^135−127·1.11011 =−1·2⁸·1.11011=−111011000₂=−(2⁸+2⁷+2⁶+2⁴+ +2³)₁₀=−472₁₀

(104)

Esercizi Svolti

=−1·2^135−127·1.11011 =−1·2⁸·1.11011=−111011000₂=−(2⁸+2⁷+2⁶+2⁴+ +2³)₁₀=−472₁₀

• N₁₀=−23.375₁₀=−10111.011₂=

(105)

Esercizi Svolti

=−1·2^135−127·1.11011 =−1·2⁸·1.11011=−111011000₂=−(2⁸+2⁷+2⁶+2⁴+ +2³)₁₀=−472₁₀

• N₁₀=−23.375₁₀=−10111.011₂=-(2⁴+2²+2¹+2⁰+2^-2+2^-3)₁₀=

=-(16+4+2+1+0.25+0.125)₁₀=-23.375₁₀

2⁰ 2¹ 2² 2³ 2⁴

2^-12^-22^-3

(106)

Esercizi Svolti

=−1·2^135−127·1.11011 =−1·2⁸·1.11011=−111011000₂=−(2⁸+2⁷+2⁶+2⁴+ +2³)₁₀=−472₁₀

• N₁₀=−23.375₁₀=−10111.011₂=−1.0111011₂·2⁴ s= − =1, e=4, e_r= 4 + 127 = 131₁₀= 10000011₂ m=1.0111011 = 0111011 (con hidden bit).

• N₁₀= 131.5₁₀= 10000011.1₂=1.00000111₂·2⁷ s= + =0, e=7, e_r= 127 + 7 = 134 = 10000110₂ m=1.00000111 = 00000111 (com hidden bit).

(107)

Indovinello: come conta ET?

• Un Extra-Terrestre viene sulla Terra e ci dice che i re di Roma sono 13.

Quante dita ha l’Extra-Terrestre?

• Il 13 deve essere interpretato come una stringa di simboli

• Non conosciamo la base della loro numerazione

• Sappiamo che il loro sistema di numerazione è POSIZIONALE

• Sappiamo che in decimale i re di Roma sono 7

• E se dicesse che i re di Roma sono 111?

(108)

Indovinello: come conta ET?

• Un Extra-Terrestre viene sulla Terra e ci dice che i re di Roma sono 13.

Quante dita ha l’Extra-Terrestre?

• Il 13 deve essere interpretato come una stringa di simboli

• Non conosciamo la base della loro numerazione

• Sappiamo che il loro sistema di numerazione è POSIZIONALE

• Sappiamo che in decimale i re di Roma sono 7

13_x= 1 * X¹ + 3 * X⁰ = X + 3 = 7₁₀ Þ X = 7 – 3 = 4

Þ L’Extra-Terrestre conta in base 4 per cui (sfruttando

l’esperienza del sistema decimale) possiamo dire che ha 4 dita (2 per mano)

Þ L’Extra-Terrestre usa l’alfabeto {0, 1, 2, 3}