Appunti informatica A

INTRODUZIONE

L’informatica si occupa della rappresentazione e dell’elaborazione dell’informazione. Quindi l’informatica

esiste da parecchio tempo: le prime macchine in grado di elaborare le informazioni risalgono al ’600 (pascal

costruì una calcolatrice in grado di svolgere le operazioni di somma e sottrazione, poi ampliata da Leibnitz nel

1670 che la rese in grado di eseguire anche moltiplicazioni e divisioni).

Negli ultimi anni ’30 si passò da metodi meccanici a metodi pneumatici (in funzione della pressione nei tubuli

si rappresentavano ed elaboravano informazioni). Ora ci sono i calcolatori elettronici, che una volta svolgevano

compiti di natura bellica, per esempio venivano utilizzati per calcolare le traiettorie dei missili.

Con una codifica di natura elettronica (tensione e corrente) abbiamo 2 meccanismi: analogico e digitale.

Analogico : per rappresentare un valore devo immettere una tensione corrispondente ( )

Digitale : l’informazione è una giustapposizione di cifre ( visto come l’insieme di 4 cifre simbolo:

cifra simbolo “3”, cifra simbolo “.” ecc.)

Nel digitale non c’è corrente o tensione che corrisponde alla rappresentazione, ma cifre giustapposte.

Le rappresentazioni analogiche sono affette da rumore, da effetti del mondo esterno, quindi oggi si utilizza

soprattutto il mondo digitale.

RAPPRESENTAZIONE DELL’INFORMAZIONE

Vogliamo rappresentare un’informazione che poi andrà elaborata, quindi informazioni di tipo:

- Numerico

- Alfanumerico (lettere, numeri, simboli)

- Multimediale (immagini, suoni, video)

Focalizziamo l’attenzione sulle informazioni di natura numerica.

Abbiamo 5 spazi di informazioni: gli insiemi numerici .

Dato che utilizziamo il meccanismo di codifica digitale, rappresentiamo le informazioni come cifre.

Come scriverò queste cifre? In un mondo decimale l’alfabeto conterebbe 10 cifre.

Quando creiamo un alfabeto possiamo utilizzare i suoi “digit”, cioè i simboli che contiene, per rappresentare

l’informazione, creando corrispondenze biunivoche tra l’alfabeto e l’insieme numerico di riferimento.

Il mio obiettivo è quello di svolgere operazioni all’interno di un insieme numerico definito (per esempio ).

Il principio di conservazione delle proprietà formali di Dedekind ci dice che le proprietà formali in un

insieme D in base k restano valide anche in un insieme con una base diversa.

Lo strumento che utilizziamo è il transistor: un oggetto elettronico che opera in due soli stati stabili, quindi il

suo alfabeto ha due simboli, per convenzione . Quindi dovrò considerare un

sistema di riferimento in base 2. Grazie a Dedekind posso dire che le proprietà formali delle operazioni in base

10 si conservano anche per le operazioni in base 2.

Bit: quantità di informazione (qualsiasi informazione) associata ad un alfabeto composto da due simboli.

Osserviamo che se l’alfabeto è D posso codificare (rappresentare in modo univoco) un numero di simboli pari a

. Devo perciò aumentare il potere espressivo dell’alfabeto: il metodo più efficiente per ottenere ciò consiste

nel giustapporre i simboli dell’alfabeto (metodo posizionale pesato).

Poniamo , qual è il potere espressivo di tale rappresentazione?

Se avessi a disposizione n cifre, da a potrei rappresentare codifiche e arrivare al numero .

Rappresentazione posizionale e pesata: con poca spesa (n cifre) posso rappresentare un numero di informazioni

che cresce esponenzialmente con n. Per questo il metodo posizionale ha un grande potere espressivo.

: il valore assunto dai simboli dipende dalla loro posizione.

Associato ad una posizione ho uno specifico peso: il peso dipende dalla base k.

Storicamente si è passati da rappresentazioni con poco potere espressivo a rappresentazioni sempre migliori.

La notazione posizionale pesata è il metodo odierno di codifica dell’informazione.

Siano dati uno spazio simboli e

Avendo a disposizione n cifre, data la codifica , potrei disporre di codifiche distinte.

Byte: una codifica di informazioni che giustappone 8 simboli binari.

Voglio realizzare una macchina fisica che, ricevuti due numeri a e b in base 10, possa eseguire almeno qualche

operazione e fornisca un risultato .

La macchina fisica (transistor) opera in modo efficiente in base 2, quindi dovrò convertire

e anticonvertire il risultato

Poniamo C: fase di codifica delle informazioni; : fase di decodifica delle informazioni.

Consideriamo un numero

Supponiamo di disporre di un’elettronica in grado di codificare n cifre in binario.

Se dispongo di un numero finito n di cifre rappresenterò un sottoinsieme di . Per ciascun numero

rappresentato potrò creare un’associazione biunivoca tra codifica e numero. La rappresentazione dovrà essere

posizionale e pesata.

è il resto della divisione tra e 2 e la parte restante ne è il quoziente.

Ho determinato , devo generare :

è il resto della divisione tra e 2 e la parte restante ne è il quoziente.

Questo procedimento si dice algoritmo di lunga divisione.

Si dice algoritmo un procedimento che risolve un problema con un numero finito di passaggi in un tempo

finito.

Es. Ora bisogna decodificare il risultato:

Se deve essere soddisfatta la relazione e quindi : serve un byte.

ELABORAZIONE DELL’INFORMAZIONE

Per elaborare l’informazione devo essere in grado di compiere operazioni.

+ 0 1 10001001 +

0 1

0 1110001011 =

1 0

1 10000010100

Sommare 3 significa spostarsi verso destra 3 volte. Quindi

Se l’alfabeto, così com’è, non basta, allora si genera un riporto, quindi

90 2

Es. 7 1

45

3 1

22

6 0

11

3 1

56 0

28 0

14 0

7 1

3

Il vantaggio dell’uso di macchine automatiche è duplice: la velocità è infinitamente più alta e

1

1

non ci sono possibilità di errore. 1

0

Problema: + e sono chiusi rispetto all’insieme , ma – e / no!

La divisione può però essere vista come un insieme di sottrazioni, quindi basterà capire come eseguire

l’operazione di sottrazione. Essa può essere vista come la somma algebrica di un numero positivo con un

numero negativo, quindi, ampliando a l’insieme di riferimento avremo risolto il problema.

(hanno lo stesso numero di elementi)

Il passaggio da a aumenta di un bit (dovuto al segno) la grandezza dell’informazione.

Notazione Modulo e Segno

ma ;

Se ora dovessi svolgere una sottrazione tra due numeri, come potrei conoscere il segno del risultato? Dovrei

sapere quale numero è il più grande. Sarebbe complesso e costoso utilizzare questo algoritmo, infatti non viene

utilizzato quasi mai al giorno d’oggi.

Complemento a 2

L’utilizzo del complemento a 2 facilita molto il procedimento.

La codifica di 0 deve esistere ed essere univoca e bisogna trasformare le sottrazioni in una somma aritmetica.

Ma per Dedekind potrei usare il complemento a 10.

Fissato l’operatore +, esiste una codifica per a, b e c che mi restituisca un risultato corretto?

dove è l’opposto di . In uno spazio algebrico non ci sono più le sottrazioni, ma le

somme algebriche. Devo introdurre il concetto di opposto.

dove si legge “bi complementare” e significa che inverto gli 1 con gli 0 e

viceversa:

Operazione di complementazione:

può essere rappresentato su n bit. Quindi

In si utilizzano metà delle codifiche per rappresentare i positivi e metà per i negativi, quindi i positivi

rappresentabili saranno come i negativi.

Se

Avendo rappresento un sottoinsieme di , se il numero in base 10 è positivo, allora la rappresentazione in

CP2 coincide con il modulo in binario naturale su n bit.

Se

Perché c’è ancora la sottrazione in fase di codifica? Il è qualcosa che sta all’esterno del nostro sistema di

riferimento poiché il peso massimo che può essere assunto da una cifra della codifica è . Questa

sottrazione introduce dunque l’effetto specchio.

ES. ?

?

Ho bisogno di almeno , perché quindi devo continuare l’algoritmo e aggiungo

uno 0.

PREMESSA

Il CP2 permette di rappresentare i numeri interi ed esiste una sola codifica per rappresentare ogni numero

intero, quindi è una rappresentazione non ridondante. Ciò permette una simmetria di rappresentazione: lo spazio

di rappresentazione è .

Dato e avendo n bit posso definire codifiche che staranno in uno spazio C avente base 2. Con queste

codifiche creo delle corrispondenze biunivoche con gli elementi di .

La trasformazione diretta di codifica si dice “c” e l’inversa di decodifica “ ”.

Il nostro obiettivo è quello di realizzare una macchina fisica in grado di eseguire almeno le operazioni di

addizione e sottrazione e che, accettando input decimali codifichi un codice binario e restituisca un risultato

decimale.

L’INSIEME

Il punto chiave della definizione del CP2 è il calcolo del CP2 opposto, tale che

Se dove sta a significare “in binario naturale su n bit”

Se

Considero e : l’unica differenza strutturale è la sottrazione di . Si dimostra che

ES. devo calcolare n ho bisogno di 5 bit

procedimento 1:

procedimento 2:

procedimento 3:

Si dimostra che le codifiche che derivano dalla trasformazione di numeri positivi hanno, come bit in posizione

più significativa uno 0, per i negativi è 1. Questo bit sarà il bit di segno.

1011: è un numero. Se fosse un binario naturale varrebbe 11. Se fosse un CP2 sarebbe un numero negativo. Se

voglio sapere quanto vale bisogna decodificarlo generando l’opposto con il complemento bit a bit e sommando

1, otterremmo 0101=5 quindi 1011= -5.

Questo per dire che l’elaborazione di un’informazione dipende dal contesto nel quale la si pone.

OPERAZIONI IN CP2

Dati come svolgere la somma ?

Osserviamo che la codifica del numero 2 in binario naturale coincide con la codifica del numero -2 in

complemento a 2. Questo non ha nessuna implicazione: è semplicemente una coincidenza, infatti la codifica in

binario naturale è un sistema di riferimento diverso dalla codifica in complemento a 2 e non ci sono relazioni

immediate o intuitive tra di esse.

Svolgiamo l’operazione

Non si possono sommare due elementi, che potrebbero essere vettori, di dimensioni diverse.

Come portare 10 a 4 bit? Basta dire che, se è il numero minimo di bit necessari è sufficiente estendere

con due zeri il binario naturale, che diverrà 0010. Poi utilizzerò questa codifica per i calcoli in CP2.

A riguardo, esiste questa regola: si considera il bit di segno e si ripropone alla sinistra tante volte quante sono

necessarie a completare la codifica in bit.

Ora però sorge un problema: noi disponiamo di soli 4 bit, mentre il risultato ottenuto ne necessita 5 per essere

rappresentato. Sulla nostra macchina fisica, che dispone di una rappresentazione a 4 bit visualizzeremo il

risultato 1001, che è la codifica di un numero negativo e quindi potrebbe essere il risultato corretto.

Genero l’opposto e sommo 1: . Questo è un numero positivo, ma io so che la

rappresentazione in CP2 di un numero positivo coincide con la rappresentazione in binario naturale del modulo

(svolgiamo così l’antitrasformazione, cioè la decodifica), quindi . Quindi il risultato complessivo è -7.

Svolgere la sottrazione

Devo generare ora genero l’opposto per

decodificarlo: . Quindi .

Es. 7=4+2+1

3=2+1 che è un numero negativo. Questo risultato è impossibile. Ciò significa

che il risultato non può essere rappresentato su 4 bit. Si dice che è avvenuto un trabocco o overflow. (un

esempio in base dieci potrebbe essere: 999 + 002 in 3 bit decimali).

Può esserci overflow quando la somma algebrica genera un risultato che non può essere rappresentato

attraverso il numero di bit stabilito: questa situazione si manifesta solo quando ho delle operazioni che

compongono segni concordi.

Abbiamo overflow quando i segno concordi degli operandi sono discordi da quello del risultato. Se si verifica

l’overflow il risultato su n bit non è corretto.

Es. Il risultato è quindi corretto: eseguo l’operazione di decodifica .

I BIT DI FLAG

Con questa regola svolgo addizioni, sottrazioni, moltiplicazioni, divisioni.

Siamo quindi in grado di costruire una calcolatrice tascabile. Ma un calcolatore è qualcosa di più.

Sarà necessaria un’unità aritmetico-logica (ALU). Essa svolge le 4 operazioni, ricevendo a e b come operandi e

restituendo un risultato

Questo dispositivo non solo restituisce il risultato, ma anche delle informazioni addizionali: l’overflow ad

esempio, indicato con un bit O, che sarà attivo e assumerà il valore 1 quando si sarà verificato un overflow. Ci

sono inoltre i cosiddetti “bit di flag”: il bit P di positività, che resta attivo quando il risultato è la codifica di un

numero positivo, il bit Z zero che si attiva quando il risultato è 0 e il bit N negative. Quindi la calcolatrice è in

grado di osservare il risultato e fornire altre informazioni. Questi 4 bit rendono la calcolatrice in grado di

eseguire dei programmi.

All’interno di un programma non ci saranno istruzioni di natura aritmetica: ci saranno istruzioni che modificano

il comportamento del programma stesso, per esempio: “ ”

L’hardware non è in grado di risolvere problemi logici di questa natura. Ma come procede allora il calcolatore?

Il punto chiave sono i bit di flag.

La condizione irresolubile può essere ricondotta ad un problema equivalente: che necessita

solamente di un’operazione di differenza e del bit P. Se il risultato ha generato la codifica di un numero positivo

la condizione è soddisfatta e si attiva il bit P. La macchina, osservando lo stato di un bit può acquisire potere

decisionale.

Se fosse “ ” basterebbe che non ci fosse un overflow e che il risultato fosse 0, cioè si attivasse il bit Z.

Il programma è computabile quando associato al programma c’è un algoritmo che lo descrive.

GLI INSIEMI E

Abbiamo quindi risolto i problemi di calcolo in e . Ma come fare ad estendere il campo d’azione agli altri

insiemi numerici?

Consideriamo

Fissato n e volendo rappresentazione un numero in ed non può essere infinita la parte frazionaria. Ma

allora non ha più senso parlare di e considereremo solo un sottoinsieme di . Quindi:

dove è la parte intera del numero considerato e è la parte frazionaria.

Comunque scelto un numero e messi a disposizione n bit dovrò creare un’approssimazione di questo

numero. L’errore di approssimazione sarà .

Bisognerà utilizzare un numero k di bit per la parte intera e un numero q di bit per la parte frazionaria, in modo

che . Osserviamo che:

Se avessi con scriverei:

Se questo numero dovessi moltiplicarlo per la virgola scomparirebbe. La virgola, quindi, in realtà non esiste.

Questa rappresentazione si dice “in virgola fissa”.

Se invece considerassi di sottrarre la parte intera al numero considerato otterrei . Ma se la

rappresentazione è posizionale e pesata possiamo riscrivere questo numero come somma di finiti termini:

Quindi ma qui è la parte intera, il resto è la parte frazionaria.

Quindi iterando il procedimento ottengo gli altri bit frazionari. Questo procedimento si dice algoritmo

di lunga moltiplicazione.

Se ora moltiplicassi per otterrei un numero intero e ridurrei il campo a .

Se k è scelto in modo sufficiente a rappresentare il numero intero allora q rappresenta l’errore:

Quindi l’errore diminuisce molto rapidamente, in modo esponenziale.

Es. è un numero razionale.

voglio rappresentarlo in virgola fissa. Rappresento 15 poi rappresento 33. Pongo

0.33 2

. 0.66 0

1.28 1

0.56 0

1.12 1

L’errore è inferiore a

La rappresentazione in virgola fissa viene utilizzata su sistemi dedicati (cip di lavatrici, centraline delle auto

ecc.) e non sui computer poiché questi devono poter lavorare su numeri molto piccoli o molto grandi, che

necessiterebbero di moltissimi bit con una rappresentazione in virgola fissa.

Per questo motivo è stato pensato un’altra rappresentazione, per spiegarla dobbiamo tornare ai numeri .

Vogliamo mantenere un errore relativo costante. Si usa la cosiddetta notazione scientifica.

dove sta per mantissa, per base ed per esponente.

Per rappresentare un numero in modo univoco si rappresenta una tripletta . Osserviamo che la base non

è necessaria ai fini dell’univocità, poiché la macchina fisica lavora solo in base 2, quindi la tripletta si riduce

alla coppia . Questo tipo di rappresentazione di dice “in virgola mobile” o “floating point”.

Pensiamo di dover rappresentare in virgola mobile .

Ho infinite possibilità: potrei trascriverlo come ma in infiniti altri modi cambiando l’esponente.

Dovendo rappresentare solo m ed e nella coppia è necessario scrivere il numero in forma canonica:

L’esponente e la mantissa sono numeri interi, per i quali uso il complemento a 2:

Un numero in virgola mobile su macchine a 32 bit ha 8 bit per rappresentare l’esponente e i restanti 24 (23 + 1

di segno) per la mantissa. In questo caso si parla di precisione singola. La doppia precisione rappresenta i

numeri su 64 bit di cui 12 bit per l’esponente.

L’elettronica soffre di questa rappresentazione: sommare due numeri significa portarli allo stesso esponente e

poi sommare le mantisse. Chiaramente è dispendioso.

All’interno dei computer c’è quindi la ALU, che lavora in virgola fissa, e la FPU, che lavora in virgola mobile.

In fisica, pur avendo a che fare con numeri molto grandi, si usa la virgola fissa per la sua rapidità, perché le

misurazioni richiedono immedi