Appunti Informatica

esempio: NOT A AND B OR C = (((NOT A) AND B) OR C)

semantica

AND : F(x,y) = 1 <—> x = Y = 1

F(x,y) =0 <—> x = Y = 0

OR : F(x,y) = 0 <—> x = Y = 0

F(x,y) = 1 <—> x = Y = 1

NOT: F(x) = 1 <--> x = 0

F(x) = 0 <—> x=1

Tavole di verità:

Un altro modo di rappresentare le operazioni booleane è tramite le mappe di Karnaugh:

Due espressioni sono equivalenti se hanno la stessa tavola della verità

TAUTOLOGIA: un’espressione che è sempre vera: A OR NOT A

CONTRADDIZIONE: un’espressione che è sempre falsa: A AND NOT A

Esistono dei Teoremi notevoli:

Teorema dell’identità o elemento neutro:

Teorema dell’elemento nullo:

Teorema di idempotenza:

Commutativa:

Associativa:

Inverso:

Distributiva:

Assorbimento o dominanza:

Leggi di DE Morgan: vantaggi:

1) + economico

2) + piccolo

3) - consumi

4) + veloce

CODIFICA DELL’INFORMAZIONE

Le informaizoni in informatica vengono trasmesse tramite dei bit, ovvero l’unità base

dell’informazione.

Anche il bit come ogni altra unità di misura ha i suoi multipli:

bit 0/1

nibble 4 bit

Byte 8 bit = 2^8 = 256

Word 16 bit

Kbyte 2^10 byte= 1024 byte

Mbyte 2^20 byte 10^6

≃

Gbyte 2^30 byte 10^9

≃

Tbyte 2^40 byte 10^12

≃

PetaByte 2^50 byte 10^15

≃

ExaByte 2^60 byte 10^18

≃

Ma che cosa possiamo codificare?

codifica dei caratteri

La codifica di un carattere, sono codifiche che avvengono per lo più su un solo byte. La codifica

standard dei caratteri è il codice ASCII (American Standard Code for Information Interchange), e

si divide in due tipi:

• codice ASCII standard, composto da 7 bit, per un totale di 128 (2^7) codici distinti, che

permettono di codificare caratteri alfanumerici (maiuscole, minuscole, cifre, punteggiatura)

• codice ASCII esteso, composto da 8 bit, per un totale di 256 (2^8) codici distinti. I primi 128

sono uguali al 7 bit, mentre i restanti sono per i caratteri speciali (à,é).

• UNICODE, un codice a 16bit, con circa 65 mila caratteri.

codifica di numeri naturali

La codifica dei numeri naturali è una codifica che ha due obbiettivi:

• permettere di rappresentare biunivocamente una porzione di numeri naturali

• eseguire correttamente le operazioni.

La codifica può avvenire secondo diverse basi p, che corrispondono al numero p di simboli.

Come già detto in precedenza, date un numero m di cifre posso rappresentare un numero p^m

di valori, e comprendendo lo zero, ho un range di cifre che vanno da 0 a p^m-1. Oppure

viceversa, dati un numero p di simboli, posso rappresentare al massimo m =logp valori.

Per la codifica dei numeri vengono utilizzate numerosi basi:

• base binaria

alfabeto: {0, 1}

• base ottale:

alfabeto: {0, 1, …, 7}

• base esadecimale

alfabeto: {0, …, 9, A, …, F}

• alfabeto decimale

alfabeto: {0, 1, …, 9} posso aggiungere o togliere zeri alle cifre più

significative e il numero non cambia.

conversioni

Visto che i numeri possono essere rappresentati secondo più basi, come facciamo a convertire un

numero da una base iniziale ad un altra?

Per far ciò vi sono delle tecniche di conversione:

• conversione da base 2 a base 10:

• conversione da base 8 a base 10:

• conversione da base 16 a base 10:

• conversione da base 10 a base 2:

Questo tipo di conversione può essere eseguito in due modi:

metodo delle sottrazioni successive

metodo delle divisioni successive:

• conversione da base 10 a base 8

• conversione da base 10 a base 16:

• conversione da base 2 a base 8:

dato che 8 = 2^3, uso una codifica indiretta (senza perdita)

• conversione da base 2 a base 16:

anche in questo caso, dato che 16 = 2^4, uso una codifica indiretta (senza perdite)

ora che abbiamo analizzato come convertire in numeri nelle varie basi, analizziamo ora come

eseguire le varie operazioni:

SOMMA DI NUMERI NATURALI

Per trattare al meglio queste somme dobbiamo introdurre la funzione XOR, ovvero la funzione

data da (A OR B) AND (NOT (A OR B)), infatti facendo la tabella della verità possiamo notare

che:

Da questo ragionamento escono due macchine che permettono di eseguire le somme:

• Semisommatore ad 1 bit: A + B = A xor B con riporto di (A+B)

• Sommatore completo ad un bit: A + B + R = A xor B xor C con carry AB + BC + AC

Combinando in questo modo un semisommatore e n-1 sommatori, si possono ottenere dei

sommatori a n bit.

NOTA BENE: prima di eseguire la somma però devo scrivere tutti e due i numeri sullo stesso

numero di bit, espandendoli o contraendoli (shift a dx o sx), aggiungendo bit 0 a volontà o

togliendo i bit nulli.

A volte però può succedere che vi sia un overflow:

Ho quindi un uno che sfora il numero di bit degli operandi. Se la macchina ha una cella di 6 bit,

per un intero l’uno viene perso e finisce nel carry. Ho quindi un overflow, infatti choose si nota il

risultato è sbagliato su 6 bit.

D’altronde con 6 bit posso rappresentare il range (0 - (2⁶ - 1)) = (0-63).

Quando vi è un overflow, il risultato richiede un it in più per essere rappresentato, mentre il

carry è quando il MSB (bit più significativo) viene perso.

SOTTRAZIONE DI NUMERI NATURALI

Le sottrazioni a numeri naturali ad un bit, sono molto simili simili alle somme a numeri naturali:

MOLTIPLICAZIONI DI NUMERI NATURALI

DIVISIONI DI NUMERI NATURALI

OPERAZIONI CON I NUMERI INTERI

Cerco una codifica che mi permetta di esprimere i numeri interi relativi.

CODIFICA CON RAPPRESENTAZIONE IN MODULO E SEGNO

I numeri interi relativi, hanno il segno, quindi per essere rappresentati, utilizzo una

rappresentazione in modulo e segno, ovvero aggiungo un bit per il segno:

• 0 se positivo

• 1 se negativo

Dati un numero n di bit ho n-1 bit per rappresentare i numeri positivi e altrettanti per i negativi,

quindi il range é: [-(2ⁿ⁻¹) +1 - 2ⁿ⁻¹-1].

Questa rappresentazione però ha due importanti problematiche:

• la doppia rappresentazione dello 0, infatti può essere rappresentato come 0000 o 1000

• problemi con i conti

CODIFICA CON COMPLEMENTO A UNO

Questa tecnica si basa sul fatto di complementare tutti i bit, invece del solo bit di segno, quindi:

Quindi anche in questo caso, come nella rappresentazione in modulo e segno, dati un numero n

di bit ho n-1 bit per rappresentare i numeri positivi e altrettanti per i negativi, quindi il range é:

[-(2ⁿ⁻¹) +1 - 2ⁿ⁻¹-1].

Ciò che cambia dalla vecchia codifica è che la somma risulta corretta, a meno del riporto.

Il problem che resta però è che lo zero può essere ancora rappresentato in due modi: 0000

oppure 1111

CODIFICA CON COMPLEMENTO A DUE

L’idea scaturita per la realizzazione di questa codifica è: cerco un

numero -A, tale che A + (-A) = 0, ovvero:

Se sommo 1 e perdo il riporto ottengo 0

Quindi ho capito che -A = (not A) + 1

conversione da c2 a decimale:

Per la conversione da c2 a decimale vi sono 2 tecniche:

• modo 1: converto il positivo:

• modo 2: assegno un peso negativo al MSB (most significant bit)

conversione da decimale a c2:

Per la conversione da decimale a c2 vi sono due tecniche:

• modo 1: converto il positivo:

• modo 2: trovo il numero di bit per cui -2ⁿ⁻¹ < A e poi converti sui restanti A + 2ⁿ⁻¹

i vantaggi della codifica a complemento a due sono che:

• facile identificazione dei negativi (bit di segno)

• ho una sola rappresentazione dello 0, infatti 0 = -0

• tutti i conti funzionano senza problemi

Con questa tecnica però si può riscontrare un nuovo problema, difatti ora il range è asimmetrico,

[-2ⁿ⁻¹, 2ⁿ⁻¹ -1], quindi se ad esempio abbiamo 8 bit, il range è [-128, +127], quindi la

complementazione non è chiusa, infatti se dovessimo codificare ad esempio:

Quindi con il complemento a due, nella somma, riporto e overflow non sono più equibalenti, infatti

quando sommo numeri discordi il risultato C è compreso tra i due e quindi è rappresentabile. Se il

risultato è positivo significa che avrò avuto un riporto

ESPANSIONE/CONTRAZIONE

Posso aggiungere e togliere tutti i bit he voglio, ma devo estendere il bit di segno

• se il numero è positivo non cambia nulla

• se il numero è negativo, il MSB vecchio avrà preso x, spostandolo aggiungo 2x, ma tolgo altri

2x con il nuovo MSB

Analogamente posso togliere quanti bit voglio purchè non cambi il bit di segno.

OPERAZIONI CON NUMERI FRAZIONARI

Trattiamo ora le operazioni con i numeri frazionari compresi tra 0 e 1

Per la conversione da base 10 a base 2, faccio i prodotti successivi, ovvero

moltiplico per 2 = shift a sinistra di 1 bit

NOTA, la periodicità è una proprietà della base in cui viene espresso il numero, ovvero:

per codificare cifre maggiori di 1, basta sommare la parte intera con la parte frazionale.

codifica di numeri in codice ottale/esadecimale

Ovviamente la codifica indiretta vale anche per i numeri frazionari

CODIFICA DEI NUMERI REALI

I numeri reali sono infiniti, quindi posso sperare di rappresentare solo un numero finito di reali.

Esistono due metodi per la rappresentazione dei numeri reali:

• virgola fissa (fixed point), giustapposizione della parte intera e della parte frazionaria. Il

numero di cifre delle due parti sono fissate a priori dalla posizione della virgola.

• virgola mobile (floating point): utilizza la notazione esponenziale (scientifica)

rappresentazione in virgola fissa

Nella rappresentazione in virgola fissa, si assume la posizione della virgola in un ben preciso

punto della sequenza, ovvero la parte intera su un numero m di bit, mentre la parte frazionaria

su un numero n di bit.

I vantaggi di questa tecnica sono che la somma si esegue come al solito, mentre gli svantaggi

sono che vi è un errore in percentuale grande per numeri piccoli.

Rappresentazione in virgola mobile

Si utilizza una notazione scientifica, ovvero:

Nel caso binario, m ed e, appartengono a due insiemi di valori, limitanti sia il range di valori

rappresentabile che la precisione con cui possono essere rappresentati.

Base 10, 2 cifre per e, 3 cifre per m; Otteniamo 7 regioni omogenee.

1) < -0.999 x 10⁹⁹

-0.999 x 10⁹⁹

2) tra e -0.100 x 10⁻⁹⁹

3) tra -0.100 x 10⁻⁹⁹ e 0

4) 0

5) tra 0 e 0.100 x 10⁻⁹⁹

6) tra 0.100 x 10⁻⁹⁹ e 0.999 x 10⁹⁹

7) > 0.999 x 10⁹⁹

Le regioni 1, 3, 5 e 7 non sono rappresentabili (lo zero è rap