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

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

LunedìGiovedì

MartedìMercoledì

Sabato

Venerdì

Domenica

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

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

Esempio

2510 =110012 =318 =1916

ConversionitraBasi(piùDiffuse)• Lepossibilità

Esadecimale

Decimale Ottale

Binario

DaDecimaleaDecimale

Esadecimale

Decimale Ottale

Binario

DaDecimaleaDecimale

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

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

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…

2 12562 1

12510 = 11111012

Esempio: 12510 = ?2

DaDecimaleaBinario:Esempio5110

(Da decimale a binario)X2 = ???

1 12 20 6

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=

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

El Alfabeto de Italiano

Alfabeto di arduino - lezione 4

Storielle Lettere Alfabeto

GUIDA - alfabeto-api.fideuram.it

03 ALFABETO FONOLOGICO

Alfabeto Cirillico - Wikipedia

Corso unitre 3 lezione_3

alfabeto camuno

Alfabeto de Gina

Alfabeto Vita

ALFABETO ITALIANO

Alfabeto di Arduino - lezione 6

660889 PUNCH BOARD ALFABETO · 660889 punch board alfabeto (tamaÑo de corte 7,5*12,5 cm) • punch board alfabeto 663004 punch board minialfabeto (tamaÑo de corte 3,5*8,5 cm) •

Alfabeto arabo

Alfabeto falso - I Bassifondi Ensembleibassifondi.com/wp-content/uploads/2016/10/PROG-Alfabeto... · 2016-11-02 · Alfabeto falso Quando le lettere nascondono qualcosa Giovanni Paolo

Alfabeto italianoitalianolinguadue.altervista.org/.../Alfabeto-italiano.pdf · 2014-03-13 · L’alfabeto

Jet alfabeto 3

Jet alfabeto 5

Jet alfabeto 9

Alfabeto e Pronunciazione

660889 PUNCH BOARD ALFABETO · 660889 punch board alfabeto (tamaÑo de corte 7,512,5 cm) • punch board alfabeto 663004 punch board minialfabeto (tamaÑo de corte 3,58,5 cm) •