Il codice binario e l’algoritmo

Parlare con il computer

Lez. 4

04/03/13

Le origini del calcolo binario

•  Claude Shannon nel 1938 pubblicò la sua tesi di dottorato dal titolo “A symbolic analysis of relays and switching circuits” in cui dimostrava che le regole dell’algebra di Boole potevano essere rappresentate (o simulate) con i circuiti elettrici a due stati

•  Lo studio di Shannon, finalizzato alla conoscenza del comportamento delle reti combinatorie, era orientato non solo ai circuiti telefonici di commutazione, ma a “qualunque circuito progettato per eseguire automaticamente operazioni complesse”.

INGREDIENTI: penne g 500 - polpa di pomodoro a pezzi g 500 - olive nere g 100 - aglio - prezzemolo - peperoncino in polvere - vino bianco secco - olio extravergine d’oliva - sale

Preparazione: Portate a bollore abbondante acqua salata che vi servirà per lessare la pasta. Intanto fate cuocere per 20' la polpa di pomodoro condita con sale e un filo d’olio: otterrete un salsa densa. In una larga padella, soffriggete, in 5 cucchiaiate d’olio, una grossa manciata di prezzemolo tritato e 4 spicchi d’aglio interi; sfumate il soffritto con un dito di vino, unitevi la salsa di pomodoro peperoncino in polvere in quantità a piacere, le olive e la pasta già lessata, scolata piuttosto al dente. Fatela insaporire a fuoco vivo, trasferitela nel piatto da portata e servitela subito.

Penne all’arrabbiata

Problema, per il quale vogliamo trovare una soluzione

Dati iniziali, dai quali si può arrivare alla soluzione manipolando i medesimi

Istruzioni, seguendo passo passo le quali possiamo arrivare alla soluzione

Dati finali

Proprietà della ricetta

•  Si rivolge a un cuoco generico; •  Può essere eseguita innumerevoli volte; •  Descrive relazioni generali tra gli

ingredienti (dati) e piatto finale (soluzione): per realizzare dosi per più persone basterà aumentare gli ingredienti

Algoritmo

•  La ricetta è un algoritmo •  Un algoritmo è una successione non

ambigua e ripetibile di istruzioni che permette di risolvere classi di problemi

•  Un linguaggio usato per descrivere un algoritmo ad un calcolatore è detto “linguaggio di programmazione”

Proprietà dell’algoritmo

•  Finitezza di espressione: numero finito di operazioni elementari da eseguire;

•  Finitezza di calcolo: dopo un certo numero di passaggi la macchina si deve arrestare;

•  Determinismo: ad ogni passo viene definita un’unica operazione da eseguire al passo successivo;

•  Effettività: deve poter essere eseguibile

Parliamo con il computer

•  Dobbiamo ora tradurre l’algoritmo in un linguaggio formale (vedi lez. precedente);

•  Useremo il codice binario •  Perché?

I nostri buoni motivi

•  Un computer è costituito da circuiti •  La maniera più diretta per programmarli è

gestirli in termini di presenza o assenza di corrente

•  Avremo quindi bisogno di descrivere 2 stati (acceso/spento; passa/non-passa corrente)

•  Se volessimo invece utilizzare il nostro ben più familiare sistema decimale (0-9) avremmo anche bisogno di circuiti in grado di distinguere almeno 9 tipi di segnali differenti (oltre all’assenza di segnale)

Perché il computer usa il codice binario? •  Essendo composto da circuiti il computer in grado di

riconoscere solo lo stato di alterazione elettrica: cioè può rilevare la presenza o meno di elettricità. Questi due stati (presenza e assenza di elettricità) vengono simboleggiati proprio da 0 e 1

•  I suoi circuiti elettronici (come quelli dello scaldabagno o la lampadina) possono essere solo aperti o chiusi

•  Quindi le tecniche di numerazione binaria e tutti i codici che utilizzano solo due elementi sono ideali per interagire e “comunicare” correttamente con il computer

L’unità di misura del mondo digitale: il bit

•  BIT (BInary Digit): unità di misura degli strumenti digitali di codifica

•  1 bit: la quantità di informazione fornita dalla scelta tra due diverse alternative

•  1 bit: unità minima dell’informazione digitale, è una singola cifra, 0 o 1

•  Dunque per “parlare” con un computer abbiamo bisogno di tradurre i nostri desideri (le istruzioni, o comandi) in linguaggio binario

•  Ma cosa stabilisce le relazioni tra il linguaggio naturale ed il codice binario (linguaggio formale)?

•  Dipende da ciò che dobbiamo tradurre…

L’alfabeto latino •  L'alfabeto latino, usato nella scrittura di molte

lingue nel mondo, presenta una grande quantità di varianti grafiche: –  vocali accentate (accento grave à, acuto á,

circonflesso â, dieresi ä, tilde ã) –  lettere modificate (lettere con barrette, cediglie,

segni) –  lettere speciali usate solo in una lingua, segni di

punteggiatura particolari (il punto interrogativo ed il punto esclamativo capovolti usati nello spagnolo)

–  simboli di valuta,… …e così via, senza considerare poi che gran parte di

questi segni presenta le due forme maiuscola e minuscola.

Bob Bemer (1920-2004)

•  Inventa il codice ASCII nel 1963, presso i laboratori IBM

•  Hugh McGregor Ross •  Il codice ASCII venne conosciuto

inizialmente in Europa come “codice Bemer-Ross”

Il codice ASCII •  La tabella ASCII è un codice convenzionale usato

per la rappresentazione dei caratteri di testo attraverso i byte: ad ogni byte viene fatto corrispondere un diverso carattere della tastiera (lettere, numeri, segni).

•  È una tabella che associa un numero a ogni segno usato nell’alfabeto latino, ai principali segni di interpunzione e ad alcuni caratteri speciali

•  In realtà lo standard ASCII copre solo i primi 128 byte (da 00000000 a 01111111), i successivi byte fino al 256° costituiscono la tabella ASCII estesa che presenta varie versioni a carattere nazionale.

Il codice ASCII /2

•  Nel 1963, un gruppo di studiosi americani (tra cui Robert W. Bemer), svilupparono quello che è oggi conosciuto come Ascii standard;

•  Il lavoro di sviluppo culminò nel 1968 con l'approvazione da parte dell'ente nazionale americano per la standardizzazione (ANSI);

•  La tavola prese il nome di American Standard Code for Information Interchange

•  Nella tabella ASCII standard si trovano le cifre numeriche, le lettere maiuscole e minuscole (maiuscole e minuscole hanno codici ASCII differenti) la punteggiatura, i simboli aritmetici e altri simboli ($, &, %, @, #, ecc.).

•  Essendo stata concepita in America, la tabella ASCII standard non comprende le lettere accentate (sconosciute all'ortografia inglese)

•  I primi 32 byte della tabella standard sono inoltre riservati per segnali di controllo e funzioni varie (telescriventi)

Estensioni di ASCII

•  Poiché il numero dei simboli usati nelle lingue naturali è più grande dei caratteri codificabili con ASCII è stato necessario espanderne il set di codifica

•  Nei paesi che non utilizzano l'alfabeto latino, (estremo oriente o mondo slavo) sono nati metodi non-standard afflitti da gravi problemi di compatibilità con gli altri set di caratteri

ASCII esteso

•  Queste estensioni prevedevano una codifica di ciascun byte con 8 bit

•  Ciascuna tabella dunque poteva rappresentare 256 diversi simboli (caratteri)

•  Avevano tutte in comune i primi 128 caratteri, quelli della tabella ASCII standard

Estensioni proprietarie

•  Commodore aggiunse molti simboli non-ASCII alla sua codifica denominata PETSCII, basata sullo standard originario del 1963

•  IBM introdusse una codifica a 8 bit sui suoi IBM PC con varianti per i diversi paesi (ASCII-compatibili, poiché i primi 128 caratteri del set mantenevano le corrispondenze originarie)

ISO •  In seguito al proliferare di codifiche

proprietarie, l'ISO rilasciò uno standard denominato ISO 8859 contenente varie estensioni a 8 bit del set ASCII

•  Il più importante fu l'ISO 8859-1, detto anche Iso-Latin-1, contenente i caratteri per i linguaggi dell'Europa Occidentale

•  ISO 8859-2 per i linguaggi dell'Europa Orientale, ISO 8859-5 per i caratteri cirillici e molti altri.

UNICODE

•  Questa coesistenza fra diverse versioni del codice ASCII produce spesso discordanze nella visualizzazione dei file di testo.

•  Per cercare di ovviare al problema è stato creato un nuovo standard internazionale detto Unicode, definito dallo Unicode Consortium e dalla International Organization for Standardization (ISO 10646), che alla sua nascita rappresentava i caratteri usando una coppia di byte (16 bit).

Unicode assegna un numero univoco a ogni carattere, indipendentemente dalla piattaforma, indipendentemente dall'applicazione, indipendentemente dalla lingua.

•  è un insieme di simboli univocamente associati ad un codice numerico ( da cui il nome: codice unico)

•  Tali codici sono decisi dallo UNICODE Consortium; fra i cui membri abbiamo Adobe, Apple, Microsoft, Google, Yahoo, HP, IBM, Sun, Oracle ...

Il codice unico in pratica •  il carattere UNICODE avente codice 65

( 0x41 in base esadecimale) è la A maiuscola; quindi dire A maiuscola oppure codice UNICODE 0x41 è la stessa cosa

•  non importa su quale sistema o in quale lingua si esporti il testo: il carattere 0x41 sarà sempre una A

•  UNICODE definisce anche una descrizione testuale dei caratteri in modo da non lasciare dubbi su cosa sia cosa (la A maiuscola è definita come lettera latina maiuscola a)

Visualizzare i caratteri

•  Un programma o un dispositivo in grado di elaborare testo in formato UNICODE dovrà sempre cercare di visualizzare una A quando incontra il codice 0x41

•  Esiste un insieme detto font di immagini, detti glifi, associate ai codici; il dispositivo dovrà quindi mostrare il glifo richiesto

Un palazzo di 17 piani! •  Con 2 byte il numero di combinazioni possibili

diventava 256x256 = 65.536, perciò Unicode supportava 65.536 diversi segni, al posto dei 256 di un qualunque set ASCII esteso

•  Si riescono a rappresentare non solo tutte le varianti dell'alfabeto latino, ma anche tutti gli altri alfabeti (greco, cirillico, arabo, ebraico, hindi, thai, ...) oltre all'insieme degli ideogrammi cinesi e giapponesi

•  I primi 65536 caratteri costituiscono il nucleo originario di UNICODE ed è detto BMP: piano multilingue di base.

•  Al piano di base sono stati aggiunti altri 16 piani (per un totale di 17 blocchi da 65536 caratteri l'uno)

•  Attualmente solo un paio di piani sono adibiti a lingue: oltre al piano di base abbiamo solo un secondo piano ( piano 1 o supplementare )

•  Il terzo piano ( 2 ) è quasi interamente dedicato a estensioni delle lingue asiatiche ma è ancora da definire.

UNICODE /3

•  Lo svantaggio dell'Unicode, rispetto all'ASCII, è che le dimensioni dei file di testo risultano comunque maggiori (vengono oggi usati fino a 4 byte per carattere, invece di 1 solo)

•  La dimensione di un file può quindi raddoppiare, triplicare, ecc

•  Per questo motivo sono stati creati dei charset (set di caratteri) detti UTF, Unicode Transformation Format

UNICODE /4 •  UTF utilizza una tecnica detta di “bit-

shifting” (spostamento dei bit) per codificare i caratteri •  In sostanza l'UTF usa 7 bit per carattere per codificare i

primi 127 caratteri corrispondenti all'ASCII standard, e attiva l'ottavo bit solo quando serve la codifica Unicode

•  Ogni carattere Unicode viene quindi codificato con un numero variabile di byte che va da 1 a 4. Il vantaggio è che il testo è visualizzabile con un normale editor di testi, anche se naturalmente i caratteri diversi dall'ASCII standard potrebbero apparire non correttamente.

•  Tra le codifiche UTF la più comune è la UTF-8, che tra l'altro, è la codifica di default di XML.

•  La versione attuale è la 6.2 •  Dalla 2.0 sono tutte compatibili tra loro •  Nella 5.2 erano rappresentati più di

100.000 caratteri •  Nella 6.0 sono stati aggiunti ulteriori

2.088 caratteri

Sitografia

•  http://unicode.org/ •  http://www.unicode.org/charts/

Bibliografia

•  Marcello Frixione - Dario Palladino, FUNZIONI, MACCHINE, ALGORITMI Introduzione alla teoria della computabilità, Roma, Carocci, 2004

Da Turing a Von Neumann

I “padri” dei nostri computer

Alan Turing (1912-1954) •  È alla base della nascita

dell’informatica per il concepimento della sua “macchina”, da cui derivano 2 importanti principi:

1.  Un modello matematico astratto

2.  Idea della “macchina programmabile”

La teoria della calcolabilità

•  Turing aveva concepito ciascuna macchina come dedicata ad un preciso algoritmo

•  Per ciascun algoritmo deve dunque esistere una macchina che lo computa

•  Dimostrò poi che esistono macchine universali (MTU) che, se istruite, possono eseguire qualunque algoritmo e dunque risolvere qualunque problema possa essere formalizzato algoritmicamente ed espresso per mezzo di simboli

I limiti della calcolabilità

•  Ci sono funzioni che non possono essere calcolate

•  Uno di questi casi sono le funzioni illimitate (come la ricerca di tutti i numeri primi, o le cifre decimali di un numero irrazionale, ecc)

•  Ma quando una MdT cerca in un insieme numerabile un elemento con determinate caratteristiche ma procede con tempi lunghi, cosa fare?

•  Interrompere un'elaborazione inutile? •  Oppure attendere ancora un risultato che

potrebbe essere fornito dopo un ulteriore lavoro in tempi accettabili?

Il problema della fermata

•  Mi interessa dunque sapere a priori se una MdT si fermerà oppure no

•  Questo problema è insolubile •  Non esiste nessuna MdT in grado di dire

se un’altra MdT si arresterà •  Tesi Church-Turing…

Alonzo Church

•  Americano, 1903-1995 •  Professore di matematica a Princeton •  Per ogni problema risolvibile

algoritmicamente esiste una macchina di Turing che lo risolva = la classe dei problemi risolvibili coincide con la classe dei problemi risolvibili con una macchina di Turing

John Von Neumann (1903-1957)

•  Matematico ungherese

•  Si occupò di teoria degli insiemi, fisica quantistica, economia, informatica, teoria dei giochi, fluidodinamica e matematica

•  Mette a punto la struttura logica dei moderni computer

John Von Neumann

•  Insegna matematica a Princeton insieme ad Einstein

•  Siamo nel 1933, a Princeton, nel neo-fondato Institute for Advanced Study

La teoria matematica dei giochi •  Disciplina matematica che si occupa

dello studio di situazioni di interazioni strategiche fra individui

•  Nel 1944, insieme a Oskar Morgenstern, pubblica un testo che diverrà un classico, Theory of Games and Economic Behavior

•  Alcuni anni più tardi Shannon si baserà sui lavori di von Neumann per pubblicare il suo articolo Una macchina giocatrice di scacchi.

L’accelerazione della II GM •  La necessità di calcoli molto complessi era

particolarmente sentita in vari campi:

–  La ricerca atomica: calcoli per misurare le caratteristiche esatte dell’esplosione e della posizione del materiale intorno alla fissione

–  La ricerca balistica: equazioni differenziali per la misurazione delle tavole di lancio delle armi a lunga gittata.

–  La criptanalisi: servizi segreti inglesi e macchina Enigma

I primi calcolatori elettronici

•  Tra il ’37 e il ’38 Turing è a Princeton dove collabora con Von Neumann

•  Durante la II Guerra Mondiale Von Neumann è in Pennsylvania con un gruppo di ricercatori, che…

•  …progettavano un calcolatore elettronico a programma memorizzato per migliorare il precedente ENIAC, costruito per eseguire i calcoli balistici delle tabelle di tiro degli armamenti pesanti (1943-’46)

ENIAC

•  Electronic Numeral Integrator And Computer

•  Venne progettato presso la Moore School of Electrical Engineering (Università della Pennsylvania) da J. Presper Eckert e John Mauchly (1946), per il U.S. Army Ballistics Research Laboratory

•  Rimase in funzione fino al 1955, ma si rivelò un progetto lacunoso nella parte logica già prima che entrasse in funzione

•  È considerato il primo calcolatore elettronico della storia

Occupava una stanza di grandi dimensioni, 9 x 30, per una superficie complessiva di 180 m2, e pesava 30 tonnellate

ENIAC

•  Macchinario digitale •  Sistema decimale •  Input con schede perforate •  Si programmava con dei cavi e spinotti,

ed ogni configurazione permetteva di risolvere un algoritmo diverso

EDVAC

•  Electronic Discrete Variable Automatic Computer

•  Nasce dalla revisione dell’ENIAC

•  È di fatto il vero capostipite dei computer moderni

•  Si basa sull’architettura di Von Neumann, che per questo passerà alla storia (tuttavia fu un lavoro di team)

•  Divenne operativo nel 1951, e vi rimase fino al 1961

La struttura hardware secondo von Neumann (1946)

Central Processing Unit (CPU) Unità di controllo + Unità aritmetico-logica

MEMORIA programmi e dati

INPUT OUTPUT

DATI ISTRUZIONI

Differenze Turing/Von Neumann

•  Solo dati (il programma era concepito nella struttura della macchina, tranne che per la MTU)

•  Solo Unità di controllo •  Memoria divisa in celle •  Turing voleva costruire una

macchina capace di emulare il cervello umano

•  Dati e programmi memorizzati insieme

•  Anche Unità aritmetica •  Memoria divisa in celle

(dotate di indirizzi) •  Accumulatore •  Contatore delle istruzioni •  2 nastri divisi in celle

(input/output) •  Intende costruire una

macchina calcolatrice molto potente

La logica alla base del calcolatore

•  Il computer si basa su un modello astratto, statico e isolato di manipolazione dell’informazione

•  Il modello non tiene conto delle limitazioni pratiche di tempo e di grandezza della memoria

•  Il modello non considera l’interazione con l’ambiente, cioè la gestione di informazione destrutturata (le uova sono andate a male?)

Il Programma Memorizzato (PM)

•  La novità di Eniac (in parte) e di Edvac era il programma memorizzato

•  Il concetto di PM ha vari livelli di profondità:

–  La capacità di memorizzare dati e programmi negli stessi registri (=memoria)

–  L’utilizzo automatico dell’output come nuovo input

–  La modifica dei programmi come se fossero dati

–  I programmi processati da altri programmi

Dall’EDVAC ad oggi

•  Tutti i computer successivi sono un’evoluzione di questo primo modello

•  Sono progrediti in termini di: -  Velocità nell’esecuzione di istruzioni -  Capacità di memoria -  Riduzione delle dimensioni

Interpreti e compilatori

•  Un linguaggio di programmazione è un traduttore che converte il mio linguaggio naturale in linguaggio macchina

•  2 scuole di pensiero •  Interprete = legge e traduce una istruzione

dopo l’altra ogni volta (accuratezza) •  Compilatore = traduce le istruzioni una volta

per tutte generando un file eseguibile in linguaggio macchina (velocità)

La rivoluzione digitale

•  Perché la codifica digitale è così importante?

•  Computer come mezzo per elaborare dati

e non solo rappresentarli •  Utilizzo di un unico linguaggio per

rappresentare informazioni di tipo diverso (integrazione dei codici)

ANALOGICO E DIGITALE

Analogico Digitale

Rappresentazione continua

Rappresentazione discreta

Riproduce il fenomeno per analogia

Astrae il fenomeno, lo segmenta e lo rappresenta attraverso numeri

Vinile, orologi a lancette, termometro a mercurio…

CD, orologi digitali, computer…

Le unità di misura dei dati

Grandezza Valore

1KiloByte (KB)

210 = 1024 Byte

1 Mega (MB) 220= 1.048.576 Byte

1 Giga (GB) 230= 1.073.741.824 Byte (1024 MB)

1 Tera (TB) 240= 1024 GB

1 Peta (PB) 250= 1024 TB

I linguaggi di mark-up

La testualità digitale: il testo nel computer

E il significato?

•  Impariamo una diversa (aggiuntiva) accezione di “codifica”

•  Definisco “marcatore” una stringa di caratteri che uso per descrivere determinati aspetti del documento

•  “marco”, metto cioè in evidenza alla macchina degli strati più profondi della semplice successione di caratteri

Il mark-up procedurale

•  Punta al documento •  Mettono in moto procedure per ottenere

un risultato •  Aspetto tipografico del documento

Il mark-up dichiarativo

•  Punta al testo •  Dichiara alla macchina elementi e

informazioni circa la natura astratta del testo

•  Aspetto logico del testo

Un esempio di marcatura “logica”

•  “Io sono il dottore di cui in questa novella si parla talvolta con parole poco lusinghiere.”

Aggettivi dimostrativi

Sostantivi Verbi

•  Ho quindi bisogno di un linguaggio di marcatura (set

di parole-chiave e relativa sintassi)

•  Tale linguaggio andrà a descrivere il testo in ogni sua

parte attraverso delle marche o tag, ovvero stringhe

di caratteri definite dalle due parentesi uncinate < >,

al cui interno sono specificati dei comandi.

•  L'SGML (Standard Generalized Markup Language) è un

linguaggio utilizzato per la rappresentazione di un

documento su supporto elettronico;

•  Nasce da un progetto di Charles Goldfarb per lo sviluppo di

un linguaggio GML della IBM;

•  Nel 1980 l'ente nazionale americano per la

standardizzazione (ANSI) decise di procedere alla

definizione di uno standard per la rappresentazione

elettronica dei documenti.

Storia di SGML

•  Nel 1986 l'SGML viene rilasciato dall'International

Organization for Standardization (ISO)

•  Si tratta di un metalinguaggio, dal quale è possibile

ricavare infiniti linguaggi di codifica: dallo standard

SGML sono stati creati l'HTML e l'XML.

La struttura tipografica e HTML

•  Nell’ipotesi che la pagina contenga solo elementi testuali, essa è memorizzata come una sequenza di caratteri.

•  Per consentire che, quando riprodotto sul video, il documento abbia la struttura voluta (suddivisione in paragrafi, presenza di titoli e sottotitoli, particolare evidenziazione ad alcune parti etc..), occorre descriverne tale struttura tramite i comandi di un linguaggio di marcatura (mark up language).

•  Il più noto di questi linguaggi è HTML (HyperText Markup Language).

•  Una volta caricata la pagina, il browser provvede a visualizzarla, utilizzando un particolare programma in grado di interpretare i comandi HTML (interprete HTML).

HTML •  HTML è costituito da un insieme di “tag”

predefiniti che descrivono aspetti relativi alla presentazione del documento: tipi di caratteri, spaziatura tra le linee di testo, dimensione dei caratteri etc..

•  Il linguaggio è interpretato dal browser che riproduce il documento a seconda delle indicazioni contenute nei tag.

•  Non è possibile utilizzare il linguaggio HTML per descrivere le strutture dei dati o più in generale per descrivere il contenuto di un documento.

Limiti di HTML

•  Linguaggio chiuso e non modificabile: insieme prefissato di tag. L’insieme di tag accettati da HTML è stato definito assieme al linguaggio stesso

•  Ogni nuova versione di HTML introduce nuovi tag •  Orientato prevalentemente all’impaginazione grafica

sul video di documenti web •  Una pagina web deve essere progettata per uno

schermo dotato di determinate caratteristiche (risultati non prevedibili); dipendenza dal tipo di browser utilizzato.

•  Non adatto a rappresentare strutture complesse (record di data-base, descrizione bibliografica..)

Bibliografia

•  Israel Giorgio, Millán Gasca Ana, Il mondo come gioco matematico. La vita e le idee di John von Neumann, Bollato Boringhieri, 2008

•  Numerico Teresa, Alan Turing e l'intelligenza delle macchine, Franco Angeli, Milano, 2005

Sitografia

•  http://www.turing.org.uk/turing/