Fondamenti di Informatica - di-srv.unisa.itarccas/materiale/lezioni/Lezione_3.pdf · nei...

FondamentidiInformaticaLinguaggi,CodificaeRappresentazionedell’Informazione

Prof. ArcangeloCastigl ioneA.A.2016/17

Linguaggi,CodificaeRappresentazionedell’Informazione

Cosaabbiamovistolavoltascorsa• Glielaboratorisonostrumentiperrisolvere(oaiutarearisolvere)problemibasatisulleinformazioni

•Macomeciòavviene?Perfarloabbiamobisognodi1. Codificare ememorizzareopportunamentedati einformazioni2. Impartire legiusteistruzioniperrisolvere correttamentei

problemi


Cosavedremooggi• Glielaboratorisonostrumentiperrisolvere(oaiutarearisolvere)problemibasatisulleinformazioni

•Macomeciòavviene?Perfarloabbiamobisognodi1. Codificareememorizzareopportunamentedatieinformazioni2. Impartirelegiusteistruzioniperrisolverecorrettamentei

problemi


Che Linguaparla l’Elaboratore?• Comerendere dati ed informazioni comprensibili adunelaboratore?• Informazioni edati peressere trattati daunelaboratore devonoessere codificatimediante unopportuno linguaggio


Linguaggio• Alfabeto• Collezionedisimboligrafici,aventidisolitounordinebenpreciso,cheservonoarappresentareleparolediunalingua

• Vocabolario(olessico)• Insiemedelleparoleammissibilidiunalingua

• Grammatica• Insiemediregoleutiliallacorrettacostruzionedifrasi,sintagmieparole

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


LaFunzionedeiLinguaggi• Ilinguaggisonostrumentiper• Rappresentareleinformazioni• Concetti,pensieri,emozioni,etc.,vengonoformalizzatiattraversoilinguaggiperpoteresserememorizzati,trasferitiedelaborati

•Memorizzareleinformazioni• Lascrittura• Trasferireleinformazioni• Lacomunicazione• Elaborareleinformazioni• Lededuzioninellalogica


ProblemideiLinguaggi• Accordosuisimboli• A bcdef g…

• Accordosullessico• Casa,gatto,automobile,vado,…

• Accordosullagrammatica• <soggettoverbocomplemento>

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

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


EsempiodiCodifica:CodiceBraille• Lettera“a”

• Lettera“b”


EsempiodiCodifica:Numeri• Linguaggiodipartenza• Inumeri

• Codifica1• Numerazionedecimale• 5,45,670

• Codifica2• Numerazionebinaria• 101,…

• Codifica3


ILinguaggiNaturali:Ambiguità• Percomunicaretralorogliuominihannosviluppatoilinguagginaturali• Italiano,inglese,francese,etc

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


ILinguaggiNaturalinellaComunicazioneconiCalcolatori• Percomunicareconunelaboratore,l’ambiguità deilinguagginaturalirappresentaungrossoproblema


ILinguaggiNaturalinellaComunicazioneconiCalcolatori• RisultaquindinecessarialadefinizionediunLinguaggiopiù Formale,chepermettadi• Individuareunalfabeto,ovverounelencofinitodisimboli• Definireuninsiemediregolesintattiche,chespecificanocomeisimbolidell’alfabetopossonoesserecombinatitraloropercrearefrasibenformateall’internodellinguaggiostesso(grammatica)

• Attribuireunsignificatononambiguoallefrasidellinguaggio(semantica)


LinguaggiperUsareeProgrammareilComputer• 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• Consideriamounalfabeto ridotto,checontienesoloduesimboli• “0”e“1”

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

• Neicalcolatoriognielemento (numeri,testo,audio,video,istruzioni,etc)vienerappresentato (codificato)esclusivamenteconsequenzedibit• Idati e leistruzioni vengonocodificati consequenzedibit


CodificaBinaria• Problema: assegnareunasequenzadibitunivocaatuttiglioggettiinuninsiemepredefinito• Quantioggettipossorappresentareinmodounivococonk bit?• 1bit=>2stati(0,1)=>2oggetti• 2bit=>4stati(00,01,10,11)=>4oggetti• 3bit=>8stati(000,001,010,011,100,101,110,111)=>8oggetti• 4bit=>16stati(0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111)=>16oggetti

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

• QuantibitsononecessaripercodificareN oggetti?• Servonok bit,dovek= 𝒍𝒐𝒈𝟐𝑵 (parteinterasuperiore)• Percodificare8oggettiservono 𝒍𝒐𝒈𝟐𝟖 𝒃𝒊𝒕 =>3bit• Percodificare71oggettiservono 𝒍𝒐𝒈𝟐𝟕𝟏 𝒃𝒊𝒕 => 𝟕𝒃𝒊𝒕


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=> 𝒍𝒐𝒈𝟐𝟕 = 𝟑 bit

• 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”


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(sistemareinbaseadASCII)• Adesempio:• 01000001 ->A• 01000010 ->B• 01000011 ->C• 01000100 ->D• 01000101 ->E

• ….ecosìvia


CodificadeiCaratteri– 4/5American Standard Code forInformation Interchange – ASCII(Codice Standard Americano per loScambio di Informazioni) è un codicestandard per la codifica dei caratteri


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

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


LaCodificadeiNumeri• Obiettivo• Codificadeinumeriperfavorirnel’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,…


SistemidiNumerazionePosizionale– 1/5• Ilnostrosistemadinumerazione• Utilizzaunanotazioneposizionale edèinbase10• L’alfabetoutilizzatoèl’insiemedeisimboli{0,1,2,…,9}

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


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

migliaia cent inaia dec ine unità

3 2 1 0Posizion i

Stringa di simboli

Base

SistemidiNumerazionePosizionale– 2/5• 3251• 3 unitàdimigliaia• 2 centinaia• 5 decine• 1 unità

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


SistemidiNumerazionePosizionale– 3/5• Lastringadisimboliv puòessererappresentatacome

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

642 inbase10 può essere scritto come63 × 102 + 42 × 101 + 21 × 100

B è labasedelnumero

n è il numerodisimboli presenti inv

d è lacifra allaiesima posizione nel numero


0≤ 𝐣 ≤ n − 1èlaposizione (opeso)

delnumero

SistemidiNumerazionePosizionale– 4/5• Concettodibasedirappresentazione B

• Rappresentazionedelnumero comesequenzadisimboli,detticifre• AppartenentiadunalfabetocompostodaB simbolidistinti• Ognisimbolorappresentaunvalorefra0eB-1

• Ilvalorediunnumerov espressoinquestanotazioneèricavabile• Apartiredalvalorerappresentatodaognisimbolo• Pesatoinbaseallaposizionecheoccupanellasequenza


SistemidiNumerazionePosizionale– 5/5• Formalmente,ilvalorediunnumerov espressoinquestanotazioneèdatodallaformula

• DoveB èlabase

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

• Osservazione: unasequenzadicifrenonèinterpretabilesenonsiprecisalabaseincuièespressa


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 × 100 = 5 +2 × 101 = 20 +1 × 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


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:Esempi

N2 = 101010

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

= 32 + 8 + 2 = 42

N2 = 11011N10 = 1 × 24 + 1 × 23 + 0 × 22 + 1 × 21 + 1 × 20

= 16 + 8 + 2 + 1= 27


23 21

543210<- Posizioni

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(divisioneeuclidea odivisioneconresto)

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

• Ilsecondoresto èilbitinposizione1

• Ecosìvia…


21 1

23 1

27 1

215 1

231 0

2 12562 1

20 1

12510 = 11111012

Esempio: 12510 = ?2

DaDecimaleaBinario:Esempio5110

(Da decimale a binario)X2 = ???

511

225 2

1 12 20 6

0231

211

20X2 = 110011

5110 = 1×25+ 1×24 + 0×23 + 0×22 + 1×21 + 1×20


RappresentazionedegliInteri:“ModuloeSegno”– 1/7• 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

N2 = 01110

N2 = 11110

Esempio


RappresentazionedegliInteri:“ModuloeSegno”– 2/7• Alfabetobinario• Ancheilsegnoèrappresentatoda0o1• Indispensabileindicareilnumerok dibitutilizzati

•Moduloesegno(rappresentazioneconkbit)• 1bit disegno (0positivo,1negativo)• Ilprimobitèdettobitpiùsignificativo (oMost Significant Bit-MSB)• k−1 bit dimodulo


RappresentazionedegliInteri:“ModuloeSegno”– 3/7•Moduloesegno(rappresentazioneconkbit)• 1bit disegno (0positivo,1negativo)• Ilprimobitèdettobitpiùsignificativo (oMost Significant Bit-MSB)• k−1 bit dimodulo

Esempio

• k=41 1 1 0



Esempio

• k=41 1 1 0

Modulo (k– 1 bit=4– 1 bit=3 bit)



Esempio

• k=41 1 1 0

Modulo (k– 1 bit=4– 1 bit=3 bit)Segno



Esempio

• k=41 1 1 0

Modulo (k– 1 bit=4– 1 bit=3 bit)Segno

–610


RappresentazionedegliInteri:“ModuloeSegno”– 7/7• Conkbitèpossibilerappresentareivalorida−2k-1+1a +2k-1−1• Esempi• 4bità valorichevannoda−7a+7• 8bità valorichevannoda−127a+127

• Osservazione• Duepossibilirappresentazionidello0• Con4bit sono+010 =0000ms −010=1000ms


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


NumeriInteriinComplementoaDue– 2/5• 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 ? ? ? ? ? ? ?


NumeriInteriinComplementoaDue– 3/5• Lacodificabinariadi91 è1011011,cheriportatonellatabellaprecedenteforniscelacodificadesiderata:

−27 26 25 24 23 22 21 20

1 1 0 1 1 0 1 1


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


1+1=0colriportodi1

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

Ilcomplementodi1è0Ilcomplementodi0è1

1001+1=

1010

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

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


EserciziperCasa– 1/2• Scrivereinbinariosempliceiseguentinumeriinbase10• 53• 211• 5310• 21110

• Scrivereinbinariosemplicesu7bitilnumero1310• Scrivereinmoduloesegnosu7bitilnumero1310• Scrivereinmoduloesegnosu7bitilnumero-1310


EserciziperCasa– 2/2• Scrivereinbinariosemplicesu7bitilnumero1110• Scrivereinmoduloesegnosu8bitilnumero2510• Scrivereinmoduloesegnosu7bitilnumero-1210• Scrivereinmoduloesegnosu5bitilnumero2010


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

• EsecidicessecheirediRomasono111?


Riferimenti• Libroditesto• Capitolo2• Paragrafi2,2.1[NOapprofondimento2.4],2.2,2.3,2.4,2.5[NOapprofondimento2.5]

• Altrilinkutili• http://www.rapidtables.com/calc/math/Log_Calculator.htm (calcolologaritmi)

• http://www.endmemo.com/math/ceil.php (calcoloparteinterasuperiore)• http://www.exploringbinary.com/twos-complement-converter/ (calcolocomplementoadue)

• https://www.tools4noobs.com/online_tools/base_convert/


Fondamenti di Informatica - di-srv.unisa.itarccas/materiale/lezioni/Lezione_3.pdf · nei...

Documents

Transcript of Fondamenti di Informatica - di-srv.unisa.itarccas/materiale/lezioni/Lezione_3.pdf · nei...