Fondamenti di Informatica - INTRANETcesposito/materiale/lezioni/Argomento02_Codi... · I Linguaggi...

FondamentidiInformaticaLinguaggi , Codif icaeRappresentazionedel l ’ Informazione

Prof. Chr i st ian Espos i toCorso d i Laurea in Ingegner ia Meccanica e Gest iona le (C lasse I )A .A . 2017/18

Linguaggi,CodificaeRappresentazionedell’Informazione

Cosaabbiamovistolavoltascorsa

• Glielaboratorisonostrumentiperrisolvere(oaiutarearisolvere)problemibasatisulleinformazioni

• Macomeciòavviene?1. Abbiamobisognodicodificare ememorizzareopportunamente

dati einformazioni2. Abbiamobisognodiimpartire legiusteistruzioniperrisolvere

correttamenteproblemi

Linguaggi,CodificaeRappresentazionedell’Informazione 01/109

Cosavedremooggi• Glielaboratorisonostrumentiperrisolvere(oaiutarearisolvere)problemibasatisulleinformazioni

• Macomeciòavviene?1. Abbiamobisognodicodificareememorizzareopportunamente

datieinformazioni2. Abbiamobisognodiimpartire legiusteistruzioniperrisolvere

correttamenteproblemi


QualeLinguaparla l’Elaboratore?• Comerendere dati einformazioni comprensibili adunelaboratore?

• Informazioni edati peressere trattati daunelaboratore devono essereopportunamente codificati


Linguaggio• Alfabeto

• Collezionedisimboligrafici,aventidisolitounordinebenpreciso,cheservonoarappresentareleparolediunalingua

• I simbolispesso(manonsempre)sonolettereovverorappresentazionescrittadisuonilinguistici

• Vocabolario(olessico)• Insiemedelleparoleammissibilidiunalingua

• Grammatica• Insiemediregoleutiliallacorrettacostruzionedifrasi,sintagmieparole

• Ilterminesiriferisceallostudiodellesuddetteregole

• Semantica• Studiailsignificatodelleparole(semanticalessicale),degliinsiemidelleparole,dellefrasi(semanticafrasale)edeitesti


LaFunzionedeiLinguaggi• Ilinguaggi(verbali,nonverbali,orali,scritti,etc.)sonostrumentichecontribuisconoa• Rappresentareleinformazioni

• Concetti,pensieri,emozioni,etc.,vengonoformalizzatiattraversoilinguaggiperpoteresserememorizzati,trasferitiedelaborati

• Memorizzareleinformazioni• Lascrittura

• Trasferireleinformazioni• Lacomunicazione

• Elaborareleinformazioni• Lededuzioninellalogica


ProblemirelativiaiLinguaggi• Accordosuisimboli

• abcdef g…

• Accordosullessico• casa,gatto,automobile,vado,…

• Accordosullagrammatica• <soggettoverbocomplemento>

• Accordosullasemantica• Lanonnachiudelaporta(OK)• Laportachiudelanonna(NO)

• Accordosullacodifica• Regolepertrasformaresimboli,paroleefrasidiunlinguaggioinunanuovarappresentazioneconpossibilitàdieffettuareinmanieracorrettaanchel’operazioneinversa• “a”incodiceMorse(SamuelMorse,pittoreestoricoinglese)è“.– ”• “b”incodiceMorseè“– ...”


CodiceBraille• Lettera“a”

• Lettera“b”


CodificadeiNumeri• Linguaggiodipartenza

• Inumeri

• Codifica1• Numerazionedecimale

• 5,45,670

• Codifica2• Numerazionebinaria

• 101,…

• Codifica3


Quipo• Quipo èuninsiemedicordicelleannodate,distanziateinmodosistematicotraloroelegateaunacordapiùgrossaecortachelesorregge.

•Iquipo servivanopericalcolimatematici.Inodidellecordesonodidiversicolori:rappresentavanonumeri,edallalororeciprocaposizionesenepotevanoricavareleunità,ledecine,lecentinaiaelemigliaia.


ILinguaggiNaturali:Ambiguità• Percomunicaretralorogliuominihannosviluppatoilinguagginaturali

• Italiano,inglese,francese,etc

• Unacaratteristicanegativa ditalilinguaggièlaloroinerenteambiguità• Unaqualsiasifrase formulataèpotenzialmentepolisemica• Ilsignificatochevienedatoallafrasedachiriceveilmessaggiopuòesserediversodaquellodatoglidalmittente

• Comprendereilsignificatodiunafraseinlinguaggionaturale èpiùsemplicesequestavienepronunciatainundatocontesto


ILinguaggiNaturali:Disambiguazione

• Comprendereilsignificatodiunafraseinlinguaggionaturaleèpiùsemplicesequestavienepronunciatainundatocontesto• ConcorsoIppico• CircoloScacchistico• Sartoria• Palestra


ILinguaggiNaturalinellaComunicazioneconiCalcolatori

• Percomunicareconunelaboratore,l’ambiguità deilinguagginaturalirappresentaungrossoproblema

• Bisognerebbefornireall’elaboratoreancheilcontestoelaconoscenza(leregole)perdisambiguarelefrasi• Larappresentazione(comprensibilealcalcolatore)dicontestoeregoleèmoltocomplicata

• Inalcunicasiladisambiguazioneèdifficileanchepergliuomini

• Ènecessariol’utilizzodeicosiddettiLinguaggiFormali


ILinguaggiFormali• Sviluppatiedimpiegatiintuttigliambitiincuiènecessarioevitarel’ambiguità• Informatica,matematica,logica,etc

• LadefinizionediunLinguaggioFormaleprevede• L’individuazionediunalfabeto,ovvero,diunelenco(finito)disimboli• Ladefinizionediunagrammaticaformale,ovverouninsiemediregolesintattichechespecificanocomeisimbolidell’alfabetopossonoesserecombinatitraloropercostituirelefrasibenformateall’internodellinguaggiostesso

• Inoltre,lesemanticheformaliconsentonodiattribuireunsignificatononambiguoallefrasiinunlinguaggioformale


UsareeProgrammareilcomputer

• IProgrammi(osoftware)risolvonoproblemispecificiconapprocciobasatosulleinformazionievengonoeseguitidaicomputer

Usare programmi realizzati da altri

Programmare

scrivere su Facebook

scrivere una relazione con Word

realizzareProgrammi complessi come ad es. Facebook

realizzarecontenuti didattici interattivi

realizzareProgrammi con Matlab

Linguaggi naturali

Linguaggi formali (di programmazione)

Numeri binari, codifica binaria dei caratteri, etc.


Rappresentazionedell’Informazione:AccordosuiSimboli

• L’informazioneèrappresentatadaidati,chealorovoltasonoespressiin formadisimboli

• Lastessainformazione puòesserecodificataconsimboliemodalitàdiverse• 1963->simboli“0”,“1”,“2”,…• MCMLXIII->simbolidellacodificaromana• Millenovecentosessantatre ->rappresentazionetestuale• …


Rappresentazionedell’informazioneneicalcolatori– 1/2

• Consideriamounalfabetoridottochecontienesoloisimboli“0”e“1”

• Unbit (contrazionedibinary digit)èunsimbolosceltosull’alfabeto{0,1}

• Neicalcolatoriognielemento (numeri,testo,audio,video,istruzioni,etc)vienerappresentato esclusivamenteconsequenzedibit

• Idati e leistruzioni vengonocodificati consequenzedibit


Rappresentazionedell’informazioneneicalcolatori– 2/2

• Pertrattare(memorizzare,elaborare,trasmettere,etc.)l’informazione,ilcalcolatore• Codifica l’informazionedisponibilescrivendosuunsupportofisico• Manipola ilsupportoconopportunetrasformazionifisiche,ottenendounaversionemodificatadelsupporto

• Decodifica l’informazionecorrispondentealrisultatodell’elaborazioneleggendodallaversionemodificatadelsupporto


CodificaBinaria• Alfabetobinario: usiamosoloduecifre0,1(bit)

• Problema: assegnareunasequenzadibitunivocaatuttiglioggettiinuninsiemepredefinito

• Quantioggettipossorappresentareconk bit?• 1bit=>2stati(0,1)=>2oggetti• 2bit =>4stati(00,01,10,11)=>4oggetti• 3bit =>8stati(000,001,…,111)=>8oggetti• …• k bit=>2k stati=>2k oggetti

• QuantibitmiservonopercodificareN oggetti?• N ≤ 2𝑘 =>k≥ 𝑙𝑜𝑔2𝑁 =>k= 𝑙𝑜𝑔2𝑁 (interosuperiore)


CombinazionidiBitBit a disposizione

Lecombinazioni Il numero di combinazioni

1 0, 1 2 =21

2 00, 01, 10,11 4 =22

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

8 =23

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

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

5 00000, 00001, 00010,… 32 =25

… … …


UnPrimoEsempiodiCodifica:Interruttore

• Duesolepossibilità(stati)• Spento• Acceso

• L’informazionesullostatodell’interruttorecorrispondedunqueallasceltafraduesolealternative


UnPrimoEsempiodiCodifica:Interruttore

• 1bitrappresentalostatodell’interruttore• Interruttoreacceso:1• Interruttorespento:0


Codificadiun’InformazioneconPiùdiDueStati:IlSemaforo


DiverseCodificheperleStesseInformazioni

• Rappresentazionedeglistatidiunsemaforomediantebit

Stato Codifica

ROSSO 1 0 0

VERDE 001

GIALLO 0 1 0

Stato CodificaROSSO 0 0

VERDE 01

GIALLO 1 0

3 bit

2 bit


Codificadiun’InformazioneconPiùdiDueStati:GiornidellaSettimana

• Problema: assegnareuncodicebinariounivocoatuttiigiornidellasettimana

• Giornidellasettimana:N =7=>𝑘 ≥ 𝑙𝑜𝑔27 => 𝑘 = 3

• Con3bitpossiamoottenere8diversesequenze• Neservono7,qualiutilizziamo?• Qualeconfigurazioneassociamoaqualegiorno?

• Osservazione: quantodettofinoadoravalesottol’ipotesicheicodiciabbianotuttilastessalunghezza


IGiornidellaSettimanainBinario

Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica

000001010011100101

111110

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 bit2 “gruppi”

2 bit4 “gruppi”

3 bit8 “gruppi”


IGiornidellaSettimanainBinario

Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica

000001010011100101

111110

Giovedì

Lunedì

Venerdì

MartedìSabato

MercoledìDomenica

00

01

10

11

Sabato

Giovedì

Martedì

DomenicaLunedì

Mercoledì

Venerdì

0

1

Lunedì

Sabato

Giovedì

Venerdì

Martedì

Domenica

Mercoledì

1 bit2 “gruppi”

2 bit4 “gruppi”

3 bit8 “gruppi”


CodificadeiCaratteri– 1/5• Problema: èpossibileapplicarequesteideeallarappresentazionediinformazionepiùcomplessa,adesempiodiuntesto?• Untestoèrappresentatoattraversounasuccessionedicaratteri• Ognicaratterevienesceltoall’internodiuninsiemefinitodisimboli(alfabeto)


CodificadeiCaratteri– 2/5• Con8bit,èpossibilerappresentarelasceltafra256alternativediverse(28=256)• Da00000000…a11111111• Passandopertuttelecombinazioniintermedie(00000001,00000010,…)

• Nelcasodeltesto,possiamofarcorrisponderediversecombinazionidi8bit(ottocellette,ciascunadellequalipuòcontenere0o1)acaratteridiversi

OgnisingoloCARATTEREvienecodificatoconunacombinazionedi8

bit


CodificadeiCaratteri– 3/5• Adesempio:

• 00000000->A• 00000001->B• 00000010->C• 00000011->D• 00000100->E

• ….ecosìvia


CodificadeiCaratteri– 4/5


• Sono stati proposti vari standard per lacodifica dei caratteri, tra cui il piùdiffuso è quello ASCII (AmericanStandard Code for InformationInterchange) del 1968, che con 7 bitcodifica un alfabeto di 128 caratteri.

•Lo standard che sta prendendo piede eche dovrebbe essere il successore diASCII è UTF-8 del 1992, codificaprincipale di Unicode per Internetsecondo il W3C.

CodificadeiCaratteri- 5/5• Soluzione: unaparola(opiùparole)saràrappresentatadalcomputercomeunasuccessionedigruppidi8bit

O G G I P I O V E01001111 01000111 01000111 01001001 00100000 01010000 01001001 01001111 01010110 01000101


LaCodificadeiNumeri• Obiettivo

• Codificainbinariodeinumeriperfavorirel’elaborazione dapartedeicalcolatori

• Vincoli• Codificaedecodificadevonoesseredefiniteinmanierataledapoteresserecompiuteinmanieraautomatica

• Problema• Deveesserepossibilecodificaretuttiinumeri

• 0,1,2,3,…• -1,-2,-3,…• -12.4,-2.004,0.56,134.89,…

• …insequenze• 0000000,000001,000010,…


NotazionePosizionale• Concettodibasedirappresentazione B

• Rappresentazionedelnumero comesequenzadisimboli,detticifre• AppartenentiadunalfabetocompostodaB simbolidistinti

• Ognisimbolorappresentaunvalorefra0eB-1

• Ilvalorediunnumerov espressoinquestanotazioneèricavabile• Apartiredalvalorerappresentatodaognisimbolo• Pesatoinbaseallaposizionecheoccupanellasequenza


ValorediunNumeroinNotazionePosizionale

• Formalmente,ilvalorediunnumerov espressoinquestanotazioneèdatodallaformula

• DoveB èlabase

• dk (0≤ 𝑘 ≤ 𝑛 − 1)sonolecifre(compresetra0e𝐁 − 1)

• Osservazione: unasequenzadicifrenonèinterpretabilesenonsiprecisalabaseincuièespressa


NotazionePosizionale• Unnumerov puòessererappresentatocome

v =dn *Bn-1 +dn-1 *Bn-2 +...+d2 *B1 +d1*B0

642può essere scritto come63 *102 + 42 *10+ 21

Bè labasedelnumero

nè il numerodicifre nel numero

dè lacifra allaiesima posizione nel numero


SistemidiNumerazionePosizionale

• Ilnostrosistemadinumerazione• Utilizzaunanotazioneposizionale edèinbase10• L’alfabetoutilizzatoèl’insiemedeisimboli{0,1,2,…,9}• Nonèl’unicosistemapossibile

• Essendoposizionale,ilvalorediuna“sequenza”disimbolivienecalcolataassegnandodei“pesi”adognisimboloasecondadellasuaposizione

452310 =4*103 + 5*102+2*101+ 3*100

migliaia cent inaia dec ine uni tà

3 2 1 0Posizion i

Stringa di simboli

Base


SistemidiNumerazionePosizionale

• 3251• 1 unità,5 decine,2 centinaia,3 unitàdimigliaia

• 745814763• 3 unità,6 decine,7 centinaia,4 unitàdimigliaia,1 decinadimigliaia,8centinaiadimigliaia,5 unitàdimilioni,4 decinedimilioni,7 centinaiadimilioni


SistemidiNumerazionepiùDiffusi

Sistema Base SimboliUsatodagliumani?

Usato daicomputer?

Decimale 10 0, 1, … 9 Si NoBinario 2 0, 1 No SiOttale 8 0, 1, … 7 No No

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

No No


Esempio

2510 =110012 =318 =1916

Base


ConversionitraBasi(piùDiffuse)

• Lepossibilità

Esadecimale

Decimale Ottale

Binario


Dadecimaleadecimale

Esadecimale

Decimale Ottale

Binario


DaDecimaleaDecimale


12510 => 5 x 100 = 5 +2 x 101 = 20 +1 x 102 = 100

125

Base

Peso

DaBinarioaDecimale

Esadecimale

Decimale Ottale

Binario


DaBinarioaDecimale:Tecnica• Moltiplica ciascun bitper2n,doven è il “peso”delbit

• Ilpesoè dato dalla posizione delbit,apartire da0sulla destra

• Somma i risultati


DaBinarioaDecimale:Esempio


1010112 => 1 x 20 = 1 +1 x 21 = 2 +0 x 22 = 0 +1 x 23 = 8 +0 x 24 = 0 +1 x 25 = 32

4310

Bitinposizione “0”

DaBinarioaDecimale:Esempio


N2 = 101010

N10 = 1 x 25 + 0 x 24 + 1 x + 0 x 22 + 1 x + 0 x 20

= 32 + 8 + 2 = 42

N2 = 11011

N10 = 20 + 21 + 23 + 24 = 1 + 2 + 8 + 16 = 27

23 21

DaBinarioaDecimale:AltriEsempi

• 10011010 = 1*27 + 0*26 + 0*25 + 1*24 + 1*23 + 0*22 + 1*21 + 0*20

= 27 + 24 + 23 + 21

= 128 + 16 + 8 + 2= 154

• 00101001 = 0*27 + 0*26 + 1*25 + 0*24 + 1*23 + 0*22 + 0*21 + 1*20

= 25 + 23 + 20

= 32 + 8 + 1= 41


DaDecimaleaBinario

Esadecimale

Decimale Ottale

Binario


DaDecimaleaBinario:Tecnica• Dividiperdueetienitracciadelresto

• Ilprimoresto èilbitinposizione0 (LSB,least-significant bit)

• Ilsecondoresto èilbitinposizione1

• Ecosìvia…


DaDecimaleaBinario:Esempio

2 0 1

2 1 1

2 3 1

2 7 1

2 15 1

2 31 0

2 12562 1

12510 = 11111012

12510 = ?2


DaDecimaleaBinario:Esempio

N10 = 51(Da decimale a binario)

N2 = ???

511

225 2

1 12 20 6

0231

211

20N2 = 110011

51 = 1*25+1*24+0*23+0*22 +1*21+1*20


DaOttaleaDecimale

Esadecimale

Decimale Ottale

Binario


DaOttaleaDecimale:Tecnica• Moltiplica ciascun bitper8n,doven è il “peso”delbit

• Ilpesoè dato dalla posizione delbit,apartire da0sulla destra



DaOttaleaDecimale:Esempio

7248 =>4 x 80 = 4 +2 x 81 = 16 +7 x 82 = 448

46810


DaEsadecimaleaDecimale

Esadecimale

Decimale Ottale

Binario


DaEsadecimaleaDecimale:Tecnica

• Moltiplica ciascun bitper16n,doven è il “peso”delbit• Ilpesoè dato dalla posizione delbit,apartire da0sulla destra



DaEsadecimaleaDecimale:Esempio

ABC16 => C x 160 = 12 x 1 = 12 +B x 161 = 11 x 16 = 176 +A x 162 = 10 x 256 = 2560

274810


DaOttaleaBinario

Esadecimale

Decimale Ottale

Binario


DaOttaleaBinario:Tecnica• Convertiognicifraottaleinunarappresentazionebinariaequivalentea3-bit


DaOttaleaBinario:Esempio7058 = ?2

7 0 5

111 000 101

7058 = 1110001012


DaEsadecimaleaBinario

Esadecimale

Decimale Ottale

Binario


DaEsadecimaleaBinario:Tecnica

• Convertiognicifraesadecimaleinunarappresentazionebinariaequivalentea4bit


DaEsadecimaleaBinario:Esempio

10AF16 = ?2

1 0 A F

0001 0000 1010 1111

10AF16 = 00010000101011112


DaDecimaleaOttale

Esadecimale

Decimale Ottale

Binario


DaDecimaleaOttale:Tecnica• Dividiper8

• Tienitracciadelresto


DaDecimaleaOttale:Esempio

8 1234154 2819 282 380 2

123410 = 23228

123410 = ?8


DaDecimaleadEsadecimale

Esadecimale

Decimale Ottale

Binario


DaDecimaleadEsadecimale:Tecnica

• Dividiper16

• Tienitracciadelresto


DaDecimaleadEsadecimale:Esempio123410 = ?16

123410 = 4D216

16 123477 2164 13 = D160 4


DaBinarioadOttale

Esadecimale

Decimale Ottale

Binario


DaBinarioadOttale• Raggruppaibitingruppiditre,partendodalladestra

• Convertiincifreottali


DaBinarioadOttale:Esempio10110101112 = ?8

1 011 010 111

1 3 2 7

10110101112 = 13278


DaBinarioadEsadecimale

Esadecimale

Decimale Ottale

Binario


DaBinarioadEsadecimale:Tecnica

• Raggruppaibitingruppidiquattro,partendodalladestra

• Convertiincifreesadecimali


DaBinarioadEsadecimale:Esempio

10101110112 = ?16

10 1011 1011

2 B B

10101110112 = 2BB16


DaOttaleadEsadecimale

Esadecimale

Decimale Ottale

Binario


DaOttaleadEsadecimale:Tecnica

• Idea: usarelacodificabinariacomerappresentazioneintermedia


DaOttaleadEsadecimale:Esempio

10768 = ?161 0 7 6

001 000 111 110

2 3 E

10768 = 23E16


DaEsadecimaleadOttale

Esadecimale

Decimale Ottale

Binario


DaEsadecimaleadOttale:Tecnica

• Idea: usarelacodificabinariacomerappresentazioneintermedia


DaEsadecimaleadOttale:Esempio

1F0C16 = ?8

1 F 0 C

0001 1111 0000 1100

1 7 4 1 4

1F0C16 = 174148


Piùingenerale…• Perconvertire unnumero binario inunsistema che hacomebase2z

• Raggruppare lecifre ingruppi diz elementi• Convertire separatamente ciascun gruppo


RappresentazionedegliInteri:“ModuloeSegno”

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

• Come possiamo rappresentare ilsegno diun numero?

• Idea: Aggiungiamo un ulteriore bit che poniamo a• 1 seilnumeroè negativo• 0 altrimenti

N10 = +14

N10 = -14

Nms = 01110

Nms = 11110

Esempio


RappresentazionedegliInteri:“ModuloeSegno”

• Alfabetobinario• Ancheilsegnoèrappresentatoda0o1• Indispensabileindicareilnumerokdibitutilizzati

• Moduloesegno• 1bit disegno (0positivo,1negativo)• k-1 bit dimodulo

• Esempio:+610= 0110ms-610= 1110ms

• Sirappresentanoivalorida-2k-1+1a2k-1-1• Con4bit ivalorivannoda-7 a+7• Con8bit ivalorivannoda-127 a+127

• Osservazione: duerappresentazionidello0• Con4bit sono+010 =0000ms -010=1000ms


RappresentazionedegliInteri:“ModuloeSegno”:LimitisuiNumeriRappresentabili

• 4bit adisposizione• Possiamorappresentareda0000a0111eda1000a1111,indecimaleda0a7eda0a-7

• 5bit adisposizione• Possiamorappresentareda00000a01111eda10000a11111,indecimaleda0a15eda0a-15

•…

• Conkbit adisposizionepossiamorappresentarenumerida0a2k-1- 1 eda-(2k-1- 1)a0


NumeriInteriinComplementoaDue– 1/5

• Idea: l’interpretazioneposizionalevienemantenutaesimodificasoltantoilpesodelbitpiùsignificativo,invertendolo

• Caratteristiche• Lozerohaunarappresentazioneunica• Tuttiinumerichehannoilbitpiùsignificativougualea1sononegativi(comeprima)

• Èsemprenecessariospecificareilnumerodibitk chesivuoleutilizzareperrappresentareundeterminatonumero

• Sirappresentanoivalorida−2k−1 a+2k−1−1• Con4bit ivalorivannoda−8 a+7• Con8bit ivalorivannoda−128 a+127



• Consideriamoungenericonumerobinariosu8bit

• Perstabilirelacodificadiungenericonumeronegativon <0,sapendochenecessariamenteilbitpiùsignificativovapostoa1,èsufficienteriportareneirestantibitilnumeropositivoche,sommatoa−27,dailvaloren

• Peresempio,proviamoacodificare−37.Essendounnumeronegativo,ilbitpiùsignificativovale1:

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

−27 26 25 24 23 22 21 20

1 ? ? ? ? ? ? ?



• Lacodificabinariadi91 è1011011,cheriportatonellatabellaprecedenteforniscelacodificadesiderata:

−27 26 25 24 23 22 21 20

1 1 0 1 1 0 1 1



• Unmetodomoltocomodopercalcolarelarappresentazionedi−X apartiredaquelladi+Xèilseguente• Idea: effettuareilcomplementodiognibitdiX,poiaggiungere11. Codificabinariadi+610 =>01102 (N.B.civogliono4bit)2. Complementodituttiibit=>1001C2 (corrisponderebbea−710)3. Aggiungere1=>1010C2 (checorrispondea−610)

Linguaggi,CodificaeRappresentazionedell’Informazione

1+1=0colriportodi1

−23+21 =−8+2=−6

Ilcomplementodi1è0Ilcomplementodi0è1

1001+1=

1010

89/109


• Estensionedel“segno”• Ivaloripositiviinizianocon0,quellinegativicon1• Datalarappresentazionediunnumerosukbit,larappresentazionedellostessonumerosuk+1bitsiottieneaggiungendo(asinistra)unbitugualealprimo

• Esempi• Rappresentazionedi-6su4bit=1010• Rappresentazionedi-6su5bit=11010• Rappresentazionedi-6su8bit=11111010


Codificadeirealiedeifrazionari(1/6)

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

X=r(x)=x± 𝜀 ∶ 0 ≤ 𝜀 ≤12

• Rappresentazionedeifrazionari• Unnumerofrazionariorappresentaunaclassedirealiinmodulominoredi1,eperessinonèsignificativalarappresentazionemedianteinteri.

• Siapplicaunfattorediscala𝑀 = 𝑏G,conn ilnumerodicifreeblabasedirappresentazione.Pertantolarappresentazionedifrazionarinonnegativimedianteinteridiventa:

𝑋 = 𝑥 J 𝑀 ± 𝜀 ∶ 𝑥𝜖 0,1 , |𝜀| ≤ NOP

Q• Esempio:0,500conM=103 vienerappresentatocome500,e0,499diventa499.



• Conversionedeinumerifrazionari• MOLTIPLICHIAMO la parte frazionaria del numero dato per 2;• continuiamo a moltiplicare il RISULTATO ottenuto per 2 tenendo presenteche, 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.



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

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

• Dicesi in virgola mobile (o floating point) una rappresentazione in cui unnumero reale è indicato dalla coppia (M,E), dove il primo termine prende ilnome 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 diottenere una migliore approssimazione. Tra le possibili coppie cherappresentano x bisogna scegliere quella con l’approssimazione più alta,detta normalizzata, ovvero quando 𝑏TU ≤ 𝑀 < 1.



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

Float shift right:𝑀W J 𝑏SX = 𝑀 J 𝑏S = YNJ 𝑏SZU

• Uno shift a sinistra avviene come segue:Float shift left:𝑀W J 𝑏SX = 𝑀 J 𝑏S = (𝑀𝑏) J 𝑏STU

• L’aritmetica in virgola mobile effettua le operazioni operando separatamentesu 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 loshift a destra fino ad ottenere Ea = Eb, altrimenti quello a sinistra. Successivamente,si sommano le mantisse.Esempio: Sommiamo A = (123 ×100) e B = (456 ×10-2), effettuiamo due shift adestra su B fino ad ottenere B = (4,56 ×100), sommiamo le mantisse e il risultato èC = (127,56 ×100).

• Moltiplicazione – Prodotto delle mantisse e somma degli esponenti con eventualenormalizzazione.



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

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

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

seM = UZ]Q, sihachex = (−1)[J (1 + 𝑓) J 2STU

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

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



• Lo standard presenta vari formati di rappresentazione, tra i quali abbiamo quello a singolaprecisione su 32 bit e quella a doppia precisione su 64 bit. Nel primo caso, dati gli 8 bit perla rappresentazione dell’esponente, si ha che il suo intervallo di rappresentazione è pari a0 < 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 bitnascosto:


Esercizi1• Scrivereinbinariosempliceiseguentinumeriinbase10

• 5310• 21110

• Scrivereinbinariosemplicesu7bitilnumero1310• Scrivereinmoduloesegnosu7bitilnumero1310• Scrivereinmoduloesegnosu7bitilnumero-1310• Scrivereinmoduloesegnosu5bitilnumero1710


SoluzioneEsercizi• Scrivereinbinariosemplicesu7bitilnumero1310

• 0001101

• Scrivereinmoduloesegnosu7bitilnumero1310• 0001101

• Scrivereinmoduloesegnosu7bitilnumero-1310• 1001101

• Scrivereinmoduloesegnosu5bitilnumero1710• 10001,Inmoduloesegnoè-110• RISPOSTA:Nonèpossibile.Hobisognodialmeno6bit(010001)


Esercizisvolti• 53=32+16+4+1

=25 +24 +22 +20=1*25 +1*24 +0*23 +1*22 +0*21 +1*20=110101inbinario

• 211=128+64+16+2+1=27 +26 +24 +21 +20=1*27 +1*26 +0*25 +1*24 +0*23 +0*22 +1*21 +1*20

=11010011inbinario


Esercizi2• Scrivereinbinariosemplicesu7bitilnumero1110• Scrivereinmoduloesegnosu8bitilnumero2510• Scrivereinmoduloesegnosu7bitilnumero-1210• Scrivereinmoduloesegnosu5bitilnumero2010


Esercizi3• UnnumerorealeèrappresentatoinvirgolamobilesecondolostandardIEEE754su32bitnelseguentemodo:

s =1E =10000111f =11011000000000000000000

•Ricavareilcorrispondentevaloredecimale.

•Convertire i seguenti numeri decimali in virgola mobile in singolaprecisione secondo lo standard IEEE 754:1. −23.375102. −127.25103. +131.5104. −300.25105. −3.610


EserciziSvolti• Dato che e = 100001112 = 13510.Si ha N=(−1)s·2(e−127)·1.f==−1·2135−127·1.11011 =−1·28·1.11011=−1110110002=−(28+27+26+24++23)10=−47210



• N10=−23.37510=−10111.0112=



• N10=−23.37510=−10111.0112=-(24+22+21+20+2-2+2-3)10=

=-(16+4+2+1+0.25+0.125)10=-23.37510


2021

22

23

24

2-12-22-3


• N10=−23.37510=−10111.0112=−1.01110112·24

s=−=1,e=4,er=4+127=13110=100000112m=1.0111011=0111011(con hidden bit).

• N10=131.510=10000011.12=1.000001112·27

s=+=0,e=7,er=127+7=134=100001102m=1.00000111=00000111(comhidden bit).


Indovinello:comecontaET?• UnExtra-TerrestrevienesullaTerraecidicecheirediRomasono13.Quanteditahal’Extra-Terrestre?• Il13deveessereinterpretatocomeunastringadisimboli• Nonconosciamolabasedellaloronumerazione• SappiamocheillorosistemadinumerazioneèPOSIZIONALE• SappiamocheindecimaleirediRomasono7

• EsedicessecheirediRomasono111?


Indovinello:comecontaET?• UnExtra-TerrestrevienesullaTerraecidicecheirediRomasono13.Quanteditahal’Extra-Terrestre?• Il13deveessereinterpretatocomeunastringadisimboli• Nonconosciamolabasedellaloronumerazione• SappiamocheillorosistemadinumerazioneèPOSIZIONALE• SappiamocheindecimaleirediRomasono7

13x = 1 * X1 + 3 * X0 = X + 3 = 710

Þ 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}


Esercizisusistemidinumerazioneposizionale

• IrediRomasono710• Base10,simboli{0,…,9}

• IrediRomasono134• Base4,simboli{0,1,2,3}

• IrediRomasono1112• Base2,simboli{0,1}

134 = 1 * 41 + 3 * 40 = 710

1112 = 1 * 22 + 1 * 21 + 1 * 20= 710

710 = 7 * 100 = 710


Riferimenti• Libroditesto

• Capitolo2


Fondamenti di Informatica - INTRANETcesposito/materiale/lezioni/Argomento02_Codi... · I Linguaggi...

Documents

Transcript of Fondamenti di Informatica - INTRANETcesposito/materiale/lezioni/Argomento02_Codi... · I Linguaggi...