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

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

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

LunedìGiovedì

MartedìMercoledì

Sabato

Venerdì

Domenica

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

Sabato

Giovedì

Martedì

DomenicaLunedì

Mercoledì

Venerdì

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

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

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

Esempio

2510 =110012 =318 =1916

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

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

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

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 15 1

2 31 0

2 12562 1

12510 = 11111012

12510 = ?2

DaDecimaleaBinario:Esempio

N10 = 51(Da decimale a binario)

N2 = ???

1 12 20 6

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

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

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

10101110112 = 2BB16

DaOttaleadEsadecimale

Esadecimale

Decimale Ottale

Binario

DaOttaleadEsadecimale:Tecnica

• Idea: usarelacodificabinariacomerappresentazioneintermedia

DaOttaleadEsadecimale:Esempio

10768 = ?161 0 7 6

001 000 111 110

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=

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

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...

AlgoBuild Esercitazione - INTRANETcesposito/materiale/lezioni/AlgoBuild... · Esercitazione AlgoBuild. Esercizio 3 Classificazione di un triangolo • Scrivere un diagramma di flusso

Analisi degli adempimenti formali durante la selezione dei gestori finanziari.

Introduzione a Linguaggi formali e compilazione

Problemi, Soluzioni ed Algoritmi - INTRANETcesposito/materiale/lezioni/Argomento05... · programmazione, etc Problemi ... Collegare il bollitore alla corrente elettrica 2. ... Diagrammi

Linguaggi Formali e Compilazione: Automi

Linguaggi Formali e Compilatori Proﬀ. Breveglieri, Crespi ... · Linguaggi Formali e Compilatori Proﬀ. Breveglieri, Crespi Reghizzi, Morzenti Prova scritta 1: Domanda relativa

Fondamenti di Informatica - INTRANETcesposito/materiale/lezioni/Lezione_1.pdf · • Nota anche come macchina di Von Neumann o modello di Von Neumann • Modello concettuale di un’architettura

Modelli e Linguaggi 2020. 3. 9. · Modelli dell’informatica Linguaggio Formale Modelli formali Uso dei modelli formali 1 Formalizzazione del problema: ottenere una descrizione astratta

· Web view- Valorizzare gli apprendimenti formali, non formali ed informali per promuovere competenze funzionali all’apprendimento permanente: predisporre un “insieme” di

Leconomia mondiale. Le aree delleconomia mondiale Nel mondo si distinguono i paesi più sviluppati nelle regioni del Nord e paesi meno sviluppati nelle.

Disturbi formali del pensiero

IL RICONOSCIMENTO DELLE COMPETENZE NON FORMALI E …

VIZI FORMALI E ANNULLABILITA’ DELL’ATTO · PDF fileVIZI FORMALI E ANNULLABILITA’ DELL’ATTO AMMINISTRATIVO Working-paper Klaus Füßer, Avvocato specializzato in diritto amministrativo,

Introduzione ai Linguaggi Formali - home.deib.polimi.ithome.deib.polimi.it/martinen/courses/api/1-01LinguaggiFormali.pdf · Introduzione ai Linguaggi Formali. Elementi dei linguaggi

Fondamenti di Informatica - INTRANETcesposito/materiale/lezioni/Argomento11b... · espr1 espr2 esprN bloco_istr_1 bloco_istr_2 bloco_istr_N bloco_istr_altrimenti VERA VERA VERA FALSA

Orazio Battaglia - CORSO TECNICO DI RETI | Blog di ... · software sviluppati per ambiente Windows e software sviluppati per ambiente Linux, esecuzione ... principale lavoro è la

Metodi formali nel progetto dellinterazione Anna Labella.

Ingegneria genetica Presente e futuro nei paesi sviluppati ... · Ingegneria genetica Presente e futuro nei paesi sviluppati e in via di sviluppo Juan M. Hernandez Monsanto. Università

Linguaggi Formali e Automi

Linguaggi naturali e linguaggi formali Sistemi formali.