Definizione di informatica RAPPRESENTAZIONE … · 2017. 3. 6. · I numeri naturali maggiori o...

1

Programma

RAPPRESENTAZIONE DELL’INFORMAZIONE –  Rappresentazione dell’informazione. Modello generale dell’architettura del

calcolatore. Cenni sulla struttura della CPU. PROGRAMMAZIONE:

–  Il concetto di algoritmo. Il calcolatore come esecutore di algoritmi. –  Linguaggi ad alto livello. Sintassi e semantica di un linguaggio di

programmazione. Metodologie di programmazione strutturata. Principi fondamentali di progetto e sviluppo di semplici algoritmi.

2

Informatica (definizione formale dell’Association for Computing Machine ACM): è lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione, la loro teoria e analisi, il loro progetto, e la loro efficienza, realizzazione e applicazione. Algoritmo: sequenza precisa e finita di operazioni, comprensibili e perciò eseguibili da uno strumento informatico, che portano alla realizzazione di un compito.

Definizione di informatica

3

Calcolatore elettronico come risolutore di problemi

Calcolatori Elettronici come esecutori di algoritmi. Gli algoritmi vengono descritti tramite programmi, cioè sequenze di istruzioni scritte in un opportuno linguaggio comprensibile al calcolatore. Compito dell’esperto informatico: produrre algoritmi (cioè capire la sequenza di passi che portano alla soluzione del problema) e codificarli in programmi. Come viene rappresentata l’informazione in un calcolatore? Quali azioni è in grado di eseguire un calcolatore?

4

Rappresentazione dell’Informazione

L’informazione è qualcosa di astratto. Per poterla manipolare bisogna rappresentarla. Informazioni e dati. In un calcolatore i vari tipi di informazione (testi, figure, numeri, musica,…) si rappresentano per mezzo di sequenze di bit (cifre binarie). Bit è l’abbreviazione di Binary digIT, numero binario. Il bit è l'unità di misura elementare dell'informazione, ma anche la base del sistema numerico utilizzato dai computer. Può assumere soltanto due valori: 0 o 1.

5

Rappresentazione dell’Informazione

Quanta informazione può essere contenuta in una sequenza di n bit? L’informazione corrisponde a tutte le possibili combinazioni degli n bit ossia 2n

Esempio: n=2. 00 01 10 11 ATTENZIONE: Una stessa sequenza di bit può rappresentare informazione differente. Per esempio 01000001 rappresenta

–  l’intero 65 –  il carattere ‘A’ –  il colore di un puntino sullo schermo

6

Calcolatore e Informazione

testo"disegni"

immagini"numeri"musica"

..."

Calcolatore"

sequenze"di bit"

dispositivi di conversione!

OUT

IN

7

Rappresentazione del testo

Sequenze"00110000 00110001 00110010

... 00111001

... 01000001 01000010 01000011

... 01100001 01100010

...

Caratteri"0 1 2

... 9

... A B C

... a b

...

Caro amico,

01000011 01100001 01110010 01101111 00100000 01100001 01101110 01101001 01100011 01101111 00101100

Codifica ASCII (American Standard Code for Information Interchange) !Standard su 7 bit (il primo bit del byte sempre 0)!

8

Base dieci Cifre: 0, 1, 2, 3, 4, 6, 7, 8, 9 Rappresentazione posizionale (123)dieci significa 1×102 + 2×101 + 3×100

Base due Cifre: 0, 1 Rappresentazione posizionale (11001)due significa 1×24 + 1×23 + 0×22 + 0×21 + 1×20 (= 25)dieci

Rappresentazione dei numeri naturali (1)

9

Data una base β ≥ due

Ogni numero naturale N minore di β (N < β) è associato ad un simbolo elementare detto cifra


BASE CIFRE due 0 1 cinque 0 1 2 3 4 otto 0 1 2 3 4 5 6 7 sedici 0 1 2 3 4 5 6 7 8 9 A B C D E F

10

I numeri naturali maggiori o uguali a β possono essere rappresentati da una sequenza di cifre secondo la rappresentazione posizionale

Se un numero naturale N ≥ β è rappresentato in base β dalla sequenza di cifre:

allora N può essere espresso come segue:


an!1an!2…a1a0

β β β β β− − −

− −=

= = + + + + +∑a a a a a a1 1 2 2

1 2 2 1 00

...n i n n

i n ni

N

11

Data una sequenza di cifre in base β, a quale numero naturale corrisponde?


Sequenze"di simboli"(in base β)

Sequenze"di simboli"

(in base 10)"

N ?

6568"A0316"11012"

6 ·8 2 + 5 ·8 1 + 6 · 8 0 "10 ·16 2 + 0 ·16 1 + 3 ·16 0"1 ·2 3 + 1 ·2 2 + 0 ·2 1 + 1 ·2

0 "

430 "2563"

13"

1 2 1 0...n na a a a− −

12

Data la base β ed un numero naturale N, trovare la sequenza di cifre che rappresenta N in base β


Sequenze"di simboli"(in base β)

Sequenze"di simboli"

(in base 10)"

Nan!1an!2…a1a0

13

Esempio: da base 10 a base 2


inizio"

fine"

div 2!

div 2!

div 2!

div 2!

QUOZIENTE RESTO Rappresentazione 23 - 11 1 11*2+1 5 1 ((5*2)+1)*2+1 2 1 ((((2*2)+1)*2)+1)*2+1 1 0 (((((1*2)+0)*2)+1)*2)+1)*2+1 0 1 (((((1*2)+0)*2)+1)*2)+1)*2+1 (10111)due!

N = 23"

14

Sia mod il resto e div il quoziente della divisione intera Procedimento mod/div q0 = N Se q0 = 0 porre a0 = 0; altrimenti eseguire la seguente procedura iterativa:

a0 = q0 mod β q1 = q0 div β a1 = q1 mod β q2 = q1 div β ... fino a che qp è uguale a 0;

!

Il procedimento si arresta quando qp = 0 dove p è il numero di cifre necessario per rappresentare N in base β


15


Inizio q0 = N"

fine"

div β div β div β div β div β

QUOZIENTE RESTO q0 = N -

q1 = q0 / ß a0 q2 = q1 / ß a1 q3 = q2 / ß a2 q4 = q3 / ß a3 q5 = q4 / ß a4 q6 = q5 / ß a5 q7 = 0 a6

div β

N = a6 ·β 6 + a5 ·β 5 + a4 ·β 4 + a3 ·β 3 + a2 ·β 2 + a1 ·β 1 + a0 ·β 0

16


Potenza della base: 2p ↔ (100…00)due!

p!

00…00"p!

00…01"p!

11…11"p!

0" 1" 2p-1"…" "Intervallo di rappresentabilità con p bit"

p Intervallo 8 [0, 255] 16 [0, 65535] 32 [0, 4294967295]

17

Calcolatore lavora con un numero finito di bit   Supponiamo che p = 16 bit   A = 0111011011010101 (30421)

B = 1010100001110111 (43127)   A + B è maggiore di 2p-1(65535) quindi non è rappresentabile

su p bit, allora si dice che la somma ha dato luogo ad overflow   In generale, ci vogliono p+1 bit per la somma di due numeri di

p bit

A = 1111111111111111 (65535) B = 1111111111111111 (65535)

11111111111111110 (131070)


18

Numeri naturali - Cambio di base (1)

1!

Numeri"Naturali"

Rappresentazioni"base X"

Rappresentazioni"base Y"

2!

Trovare la rappresentazione in base 9 di (1023)cinque "1) Trasformo in base 10 ed ottengo 138"2) Applico il procedimento mod/div ed ottengo (163)nove"

Da base X a base Y

19

Casi particolari (potenze di 2)

Numeri naturali - Cambio di base (2)

Numeri"Naturali"

Rappresentazioni"base 2"

Rappresentazioni"base 8 o 16"

(657)otto"

( 110 101 111 )due!

(A03)sedici"

(1010 0000 0011)due!

(FFE4)sedici"

(1111 1111 1110 0100)due!

20

Numeri Interi (1)

"Ad esempio, per p = 4 si ha:"se "x = +0001 "(+1 in base dieci) "allora X = 0001"se "x = -0110 "(-6 in base dieci) "allora X = 1110"se "X = 0111 "allora x = +0111" (+7 in base dieci)"se "X = 1000 "allora x = -0000" "(-0 in base dieci)"

Modulo e segno X rappresentazione di x |x| modulo di x

Intervallo di rappresentabilità con p bit (doppia rappresentazione dello 0)"

[-(2p-1-1),+2p-1-1]""

• p = 4 [-7,+7]"• p = 8 [-127,+127]"• p = 16 [-32767,+32767]"

|x| se x ≥ 0 X =

2p-1 + |x| se x ≤ 0

X se X < 2p-1 x =

- (X - 2p-1) se X ≥ 2p-1

21

Numeri Interi (2)

Ad esempio, per p = 4 si ha:"se "x = +0001 "(+1 in base dieci) "allora X = 0001"se "x = -0110 "(-6 in base dieci) "allora X = 1001"se "X = 0111 "allora x = +0111" "(+7 in base dieci)"se "X = 1000 "allora x = -0111 " "(-7 in base dieci)"

X rappresentazione di x

Complemento a 1 Intervallo di rappresentabilità con p bit"(doppia rappresentazione dello 0)"

[-(2p-1-1), +2p-1-1]""

• p = 4 [-7,+7]"• p = 8 [-127,+127]"• p = 16 [-32767,+32767]"

|x| se x ≥ 0 X =

2p - 1 - |x| se x ≤ 0

X se X < 2p-1 x =

- (2p - 1 - X) se X ≥ 2p-1

22

Numeri Interi (3)

Ad esempio, per p = 4 si ha:"se "x = +0001 "(+1 in base dieci) "allora X = 0001"se "x = -0110 "(-6 in base dieci) "allora X = 1010"se "X = 0111 "allora x = +0111" "(+7 in base dieci)"se "X = 1000 "allora x = -1000" "(-8 in base dieci)"

X rappresentazione di x

Complemento a 2 Intervallo di rappresentabilità con p bit"

[-2p-1,+2p-1-1]""

• p = 4 [-8,+7]"• p = 8 [-128,+127]"• p = 16 [-32768,+32767]"

|x| se x ≥ 0 X =

2p - |x| se x < 0

X se X < 2p-1 x =

- (2p - X) se X ≥ 2p-1

23

Numeri Interi (3)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Calcolatore con interi su 4 bit!

0 +1 +2 +3 +4 +5 +6 +7 -8 -7 -6 -5 -4 -3 -2 -1

numero negativo ⇔ bit più significativo della rappresentazione uguale a 1

X x { }40,1

24

Numeri Interi (4)

-2 +1 -1

1110 0001 compl.!

a 2!Sommatore per!

naturali!1111

Operazioni su numeri!

Operazioni sulle rappresentazioni!

QUESTO è il motivo per cui i calcolatori rappresentano gli interi

in complemento a 2!

25

Numeri Interi (5)

Sommando due numeri interi si verifica un overflow quando i due numeri hanno lo stesso

segno ed il risultato ha segno diverso"!

7+5=12

0111 + 0101 ---------------- 1100 => -4

7-1=6

0111 + 1111 ---------------- 1 0110 => 6

Overflow Ok

26

Numeri Reali (1)

Sottoinsieme!discreto dei Numeri"

Razionali"

Sequenze"di bit"

0!

Densità che dipende dal numero di bit usati!

Overflow! Overflow!Underflow!

27

Numeri Reali – Virgola fissa (1)

q  Si usa un numero fisso di bit per la parte intera ed un numero fisso di bit per la parte frazionaria.

q  Sia r un numero reale da rappresentare

q  Di seguito, indichiamo con I(r) la parte intera e con F(r) la parte frazionaria di r

q  Siano p i bit utilizzati per rappresentare r e f i bit utilizzati per rappresentare la parte frazionaria F(r) di r. Allora

R = ap-f-1…a0a-1..a-f e r ap-f-12p-f-1+…. + a020 + a-12-1 … + a-f 2-f

q  La virgola non si rappresenta.

q  La parte intera I(r) si rappresenta con le tecniche note.

q  Per la parte frazionaria si usa il procedimento seguente:

28


f0 = F(r) Se f0 ≠ 0 eseguire la seguente procedura iterativa:

a-1 = I(f0 * 2) f1 = F(f0 * 2) a-2 = I(f1 * 2) f2 = F(f1 * 2) ... fino a che fj uguale a zero oppure si è raggiunta la precisione desiderata

Esempio:!p = 16 e f = 5 r = +331,6875

29


•  Dalla rappresentazione dei numeri naturali: 331 ⇔ 101001011;

QUOZIENTE RESTO 331 - 165 1 82 1 41 0 20 1 10 0 5 0 2 1 1 0 0 1

30


•  Parte frazionaria -> 1* 2-1 + 0*2-2 + 1*2-3 + 1*2--4 -> 0,5 + 0,125 + 0,0625 -> 0,6875

•  Dall’algoritmo precedente: 0,6875 ⇔ 0,1011 •  r = (+101001011,1011)due •  r = +10100101110110 ⇒ R = 0010100101110110

PRODOTTO I F 0.6875*2->1.375 1 0.375 0.375*2 -> 0.75 0 0.75 0.75*2 -> 1.5 1 0.5 0.5*2 -> 1 1 0

31


ERRORE DI TRONCAMENTO

Rappresentare r = 2.3 con f = 6.

Per esprimere r sono necessarie un numero infinito di cifre.

Ne abbiamo a disposizione solo 6. Quindi si opera un troncamento alla 6a cifra dopo la virgola.

Quindi, in realtà si rappresenta non r ma il numero r’ r’ = 10.010011 r’ = 2 + 2-2 + 2-5 + 2-6 = 2 + 0.25 + 0.03125 + 0.015625 = 2.296875

32

Numeri Reali – Virgola mobile (1)

CALCOLO DI FISICA ASTRONOMICA!me = 9 × 10-28 gr; msole = 2 × 10+33 gr ⇒ Intervallo di variazione ≈ 10+60. "Sarebbero quindi necessarie almeno 62 cifre, di cui 28 per la parte frazionaria. !!

Si hanno tante cifre perché l’intervallo da rappresentare è grande ⇒ !

TRUCCO: si separa l’intervallo di rappresentabilità dalla precisione, cioè dal numero di cifre. !

33


β= ± ⋅ er m m = mantissa; e = esponente "L’intervallo di rappresentabilità è fissato dal numero di cifre dell’esponente."

La precisione è fissata dal numero di cifre della mantissa.

Notazione Scientifica

Forma Standard (unicità della rappresentazione)!

3.14 "0.314 10+1 "31.4 10-1

Si fissa una forma standard.

34


IEEE 754-1985 (semplificata)!

, ,r s E F↔

s = codifica del segno (1 bit) F = numero naturale su M bit che codifica la mantissa E = numero naturale su K bit che codifica l’esponente

p = 32; K = 8; M = 23 (precisione semplice) p = 64; K = 11; M = 52 (precisione doppia)

r = s ( 1 + F 2 –M ) * 2 E

forma normalizzata: ±(1+F 2-M )⋅2+E "

“uno implicito” ⇒ lo zero non è rappresentabile"

35

La descrizione di un problema non fornisce in generale un modo per risolverlo La definizione del problema deve essere chiara e completa. Algoritmo: sequenza di passi che portano alla soluzione del problema Non tutti i problemi sono risolvibili attraverso l’uso del calcolatore (funzioni calcolabili).

»  Se il problema presenta infinite soluzioni »  Se è stato dimostrato che non esiste nessun algoritmo per risolvere il

problema. »  Anche se la non esistenza di un algoritmo non è stata dimostrata,

nessun algoritmo è stato ancora trovato.

Calcolatore come esecutore di algoritmi

36

Algoritmo: sequenza precisa (non ambigua) e finita di operazioni, che portano alla realizzazione di un compito. Le operazioni utilizzate appartengono ad una delle seguenti categorie: 1.  Operazioni sequenziali

Realizzano una singola azione. Quando l’azione è terminata passano all’operazione successiva.

2.  Operazioni condizionali Controllano una condizione. In base al valore della condizione, selezionano l’operazione successiva da eseguire.

3.  Operazioni iterative Ripetono l’esecuzione di un blocco di operazioni, finchè non è verificata una determinata condizione.

Algoritmo (1)

37

L’esecuzione delle azioni nell’ordine specificato dall’algoritmo consente di risolvere il problema."Risolvere il problema significa produrre risultati a partire da dati in ingresso"""""""L’algoritmo deve essere applicabile ad un qualsiasi insieme di dati in ingresso appartenenti al dominio di definizione dell’algoritmo (se l’algoritmo si applica ai numeri interi deve essere corretto sia per gli interi positivi che per gli interi negativi)"

Algoritmo (2)

dati"risultati"

algoritmo"

esecutore"

38

Metodo mod/div lo vogliamo applicare a qualunque numero naturale N e a qualunque base β leggi N e β; inizializza q(0) a N, i a 0 - ripeti finché (q(i) diverso da 0) a(i) = q(i) mod β; q(i+1)= q(i) div β; i=i+1; scrivi a(i)

Algoritmo (3)

39

Eseguibilità: ogni azione deve essere eseguibile dall’esecutore in un tempo finito

Non-ambiguità: ogni azione deve essere univocamente interpretabile dall’esecutore

Finitezza: il numero totale di azioni da eseguire, per ogni insieme di dati in ingresso, deve essere finito

Algoritmi equivalenti   hanno lo stesso dominio di ingresso   hanno lo stesso dominio di uscita   in corrispondeza degli stessi valori del dominio di ingressso producono gli

stessi valori del dominio di uscita   Due algoritmi equivalenti

–  Forniscono lo stesso risultato, ma possono avere diversa efficienza e possono essere profondamente diversi

Algoritmo (5)

40

Algoritmo (7)

Proprietà essenziali degli algoritmi: Correttezza:

–  un algoritmo è corretto se esso perviene alla soluzione del problema dato.

Efficienza: –  un algoritmo è efficiente se perviene alla soluzione nel modo più

veloce possibile (con la minore occupazione di memoria possibile), compatibilmente con la sua correttezza.

41

La formulazione testuale di un algoritmo in un linguaggio comprensibile ad un calcolatore è detta PROGRAMMA. Ricapitolando, per risolvere un problema:

-  Individuazione di un procedimento risolutivo

-  Scomposizione del procedimento in un insieme ordinato di azioni – ALGORITMO

-  Rappresentazione dei dati e dell’algoritmo attraverso un formalismo comprensibile al calcolatore: LINGUAGGIO DI PROGRAMMAZIONE

Qual è il linguaggio comprensibile dal calcolatore?

Programmazione

42

Esistono linguaggi a vari livelli di astrazione Linguaggio macchina sequenze di bit (difficile da leggere e capire)

0001001000110100 Linguaggio Assembler istruzioni macchina espresse con nomi

simbolici (dipendente dalla macchina) MOV AL 0x54

Linguaggi ad Alto livello indipendenti dalla macchina

int main() { … }

Livelli di astrazione dei Linguaggi

43

Perché non usare direttamente il linguaggio naturale? Il LINGUAGGIO NATURALE è un insieme di parole e di regole per combinare tali parole che sono usate e comprese da una comunità di persone

- non evita le ambiguità - non si presta a descrivere processi computazionali automatizzabili

Occorre una nozione di linguaggio più precisa. Un LINGUAGGIO di programmazione è una notazione formale che può essere usata per descrivere algoritmi. Si può stabilire quali sono gli elementi linguistici primitivi, quali sono le frasi lecite e se una frase appartiene al linguaggio.

Linguaggi di Programmazione (1)

44

Un linguaggio è caratterizzato da: SINTASSI - insieme di regole formali per la scrittura di programmi, che fissano le modalità per costruire frasi corrette nel linguaggio

SEMANTICA - insieme dei significati da attribuire alle frasi (sintatticamente corrette) costruite nel linguaggio

- a parole (poco precisa e ambigua) - mediante azioni (semantica operazionale) - mediante funzioni matematiche (semantica denotazionale) - mediante formule logiche (semantica assiomatica)

Linguaggi di Programmazione (2)

45

Definizione di linguaggio

Alfabeto V (lessico)

- insieme dei simboli con cui si costruiscono le frasi Universo linguistico V*

- insieme di tutte le frasi (sequenze finite) di elementi di V Linguaggio L su alfabeto V

- un sottoinsieme di V* Come definire il sottoinsieme di V* che definisce il linguaggio? Specificando in modo preciso la sintassi delle frasi del linguaggio TRAMITE una grammatica formale

46

Grammatica G = <V, VN, P, S> V insieme finito di simboli terminali VN insieme finito di simboli non terminali P insieme finito di regole di produzione S simbolo non terminale detto simbolo iniziale

Data una grammatica G, si dice Linguaggio LG generato da G l’insieme delle frasi di V

- Derivabili dal simbolo iniziale S - Applicando le regole di produzione P

Le frasi di un linguaggio di programmazione vengono dette programmi di tale linguaggio.

Grammatiche

47

GRAMMATICA BNF (Backus-Naur Form) è una grammatica le cui regole di produzione sono della forma

X ::= A X simbolo non terminale A sequenza di simboli (terminali e non terminali) Una grammatica BNF definisce quindi un linguaggio sull’alfabeto terminale V mediante un meccanismo di derivazione (riscrittura) A deriva da X perché esiste una regola (o una sequenza di derivazioni) capace di trasformare X in A X ::= A1 | A2 | unica regola che indica che la trasformazione è una alternativa fra A1, …, An …

An |

Grammatica BNF (1)

48

G = <V, VN, P, S>""V = {lupo, canarino, bosco, cielo, mangia, vola, canta} VN = {frase, soggetto, verbo, articolo, nome }!S = "frase!"Produzioni P"! !frase "::= "soggetto verbo .!! !soggetto "::= "articolo nome!! !articolo "::= "il "" " " "lo"! !nome "::= "lupo"" " " "canarino"" " " "bosco "" " " "cielo"" "verbo "::= "mangia"" " " "vola"" " " "canta"

"

Esempio: derivazione della frase "" " "“il lupo mangia.”"

"frase -> soggetto verbo. " -> articolo nome verbo.! -> il nome verbo.! -> il lupo verbo." -> il lupo mangia.""" "derivazione left-most"

Grammatica BNF (2)

49

Albero sintattico

frase!

soggetto! verbo!

articolo! nome!

mangia"lupo"il"

Albero sintattico: albero che esprime il processo di derivazione di una frase usando una data grammatica"Esistono programmi per generare analizzatori sintattici per linguaggi descritti con BNF " " ""

.

50

Gli analizzatori sintattici verificano che il programma sia sintatticamente corretto Ma un programma sintatticamente corretto non è garanzia che funzioni correttamente (cioè raggiunga l’obbiettivo per cui è stato scritto) La frase “il lupo vola” è sintatticamente corretta ma non è semanticamente corretta (non è significativa)

Sintassi e semantica

51

Sviluppo di un programma (approccio compilato): - editing: scrivere il testo e memorizzarlo su supporti di memoria permanenti - compilazione - linking - esecuzione

Compilatore: traduce il programma sorgente in programma oggetto

  ANALISI programma sorgente analisi lessicale analisi sintattica

  TRADUZIONE generazione del codice ottimizzazione del codice

Esempi: C, C++, Pascal…

Approccio compilato

52

Sviluppo di un programma (approccio interpretato):

- editing: scrivere il testo e memorizzarlo su supporti di memoria permanenti - interpretazione

  ANALISI programma sorgente analisi lessicale analisi sintattica

  ESECUZIONE ESEMPIO: Basic, JavaScript

Approccio Interpretato

53

Esistono linguaggi a vari livelli di astrazione Linguaggio macchina sequenze di bit (difficile da leggere e capire)

0001001000110100 Linguaggio Assembler istruzioni macchina espresse con nomi

simbolici (dipendente dalla macchina) MOV AL 0x54

Linguaggi ad Alto livello indipendenti dalla macchina

int main() { … }

Livelli di astrazione dei Linguaggi

54

Architettura di von Neumann (1946)!

Schema a blocchi di un semplice calcolatore

MEMORIA

PRINCIPALE

RETE di INTERCONNESSIONE

INTERFACCE

TRASDUTTORI

PROCESSORE

55

La memoria contiene dati e programmi (istruzioni) codificati in forma binaria Il processore ripete all’infinito le azioni seguenti :

• preleva una nuova istruzione dalla memoria •  la decodifica •  la esegue

L’esecuzione di un’istruzione può comportare »  Elaborazione e/o Trasferimento (memoria ↔ processore,

I/O ↔ processore)

Le periferiche permettono al calcolatore di interagire con il mondo esterno

Funzionamento

56

Struttura logica della memoria

OPERAZIONI 1.  LETTURA di UNA cella 2.  SCRITTURA di UNA cella

...

0 1 2 ...

... 2h-2 2h-1

k bit

•  2h celle di k bit ognuna •  Ogni cella ha un indirizzo

57

Istruzioni per il trasferimento di dati MOV Movimento (ricopiamento) PUSH Immissione di una word nella pila POP Estrazione di una word dalla pila IN Ingresso dati OUT Uscita dati

Istruzioni aritmetiche

ADD Somma (fra interi oppure naturali) SUB Sottrazione (fra interi oppure naturali) CMP Confronto (fra interi oppure naturali) MUL Moltiplicazione (fra naturali) DIV Divisione (fra naturali) IMUL Moltiplicazione (fra interi) IDIV Divisione (fra interi)

Istruzioni operative (1)

58

Istruzioni logiche NOT Not logico bit a bit AND And logico bit a bit OR Or logico bit a bit

Istruzioni di traslazione/rotazione

SHL Traslazione a sinistra SHR Traslazione a destra ROL Rotazione a sinistra ROR Rotazione a destra

Istruzioni operative (2)

59

Istruzioni di salto JMP Salto incondizionato Jcond Salto sotto condizione

Istruzioni per la gestione dei sottoprogrammi

"CALL Chiamata di sottoprogramma RET Ritorno da sottoprogramma

Istruzione di alt

"HLT Alt

Istruzioni di controllo

60

Le istruzioni sono codificate come sequenze di bit."

"

Formato delle istruzioni

codice operativo"

operandi"

Stringa di bit"

MOV" AL" Cella 51"

Codice Operativo! Operandi!

Esempio!

0000 0001 00110011

61

01000000 00010001 01000010 00010010 01100001 00010010 01010010

01000000 00010001 01000010

Esempio di programma (2)

memoria"

cpu" I/O"

bus"

(100) (101) (102)

(200) (201) (202)

62

Architettura di von Neumann (1946)!

Schema a blocchi di un semplice calcolatore

MEMORIA

PRINCIPALE

RETE di INTERCONNESSIONE

INTERFACCE

TRASDUTTORI

PROCESSORE

63

Struttura logica del processore (1)

Processore"

AX"Spazio di I/O"Spazio di Memoria"

AL"

Registri Generali"

IP"AH"

BX"BL" F"

BH"CX"

CL"CH"DX"

DL"DH"

Registri di Stato"

0"1"

65534"65535"

0"1"

65534"65535"

SP"Puntatore di Pila"

CLOCK"


AL"

Registri Generali"

IP"AH"

BX"BL" F"

BH"CX"

CL"CH"DX"

DL"DH"

Registri di Stato"

0"1"

65534"65535"

0"1"

65534"232-1


ALU"

232-2

64

Segnali digitali

Segnali analogici: più informazione, ma inaccurato sia il processo di generazione del segnale che il suo riconoscimento

65

Segnali digitali

Sistema digitale binario

Come si può definire il processore

Il processore è una Rete logica cioè un oggetto che trasforma segnali binari di ingresso in segnali binari di uscita Una rete logica è sempre unidirezionale Cos’è un segnale binario?

66

67

Segnali digitali

Segnali analogici: più informazione, ma inaccurato sia il processo di generazione del segnale che il suo riconoscimento

68

Segnali digitali

Sistema digitale binario

Rete logica

Una rete logica può essere divisa in tipi diversi a seconda del suo funzionamento Rete combinatoria: uscita esclusivamente funzione dell’ingresso - indicando con O un qualunque valore di uscita e con I un qualunque valore di ingresso O=f(I)

Rete sequenziale: l’uscita è funzione, oltre che dell’ingresso, anche dello stato; la rete conserva traccia in modo limitato della sequenza di ingresso

–  indicando con S lo stato O=f(I,S) Una rete logica può, in generale, essere costituita da un insieme di reti combinatorie e sequenziali interconnesse

69 70


Processore"


AL"

Registri Generali"

IP"AH"

BX"BL" F"

BH"CX"

CL"CH"DX"

DL"DH"

Registri di Stato"

0"1"

65534"65535"

0"1"

65534"65535"


CLOCK"


AL"

Registri Generali"

IP"AH"

BX"BL" F"

BH"CX"

CL"CH"DX"

DL"DH"

Registri di Stato"

0"1"

65534"65535"

0"1"

65534"232-1


ALU"

232-2

Struttura della ALU

La ALU è l’unità aritmetico-logica ed è in grado di eseguire le istruzioni aritmetiche e quelle logiche.

Che tipo di rete è e come funziona?

E’ composta da un insieme di Reti combinatorie

Vediamo meglio cosa è una rete combinatoria

71

Questa algebra fu sviluppata nel 1854 da George Boole, un matematico inglese dell'University College di Cork.

Algebra= Dati + operazioni L’algebra di Boole è definita su due soli elementi {0,1} Sono definite tre operazioni, tramite le cosiddette tabelle di verità (0=falso, 1=vero)

72

Algebra delle reti: Algebra di Boole (1)

73

Esempi di circuiti

A=Alto, B=Basso, -E<A,B<E

Anodo

Catodo

74

Porte Logiche

Le operazioni dell’algebra hanno un corrispondente immediato in termine di circuiti elementari o

Porte logiche

75

Algebra delle reti (2)

In ogni algebra, date le operazioni definite, posso costruire espressioni che rappresentano applicazioni successive delle operazioni sui dati

Espressione logica: qualunque combinazione ammissibile di variabili o costanti booleane combinate con gli operatori

Un’espressione può venire calcolata per ogni valore che può essere assegnato alle variabili booleane (2n configurazioni possibili se n sono le variabili)

y=f(x1, …, xn) il valore di y corrisponde al valore corrispondente assegnato nella tabella di verità

76

Algebra booleana: proprietà (3)

1 . x = x 0+x = x 0 . x = 0 1+x = 1 x . x = x x+x = x x . x = 0 x+x = 1 x . y = y . x x+y = y+x Commutatività (x.y)z = x(y.z) (x+y)+z = x+(y+z) Associatività x+y.z = (x+y)(x+z) x. (y+z) = x.y+x.z Distributività x . (x+y) = x x+ (x . y) = x Assorbimento x . y = x+y a+b = a . b De Morgan Vale il principio di dualità

77

Algebra booleana (4)

Prova De Morgan

78

Teorema di Shannon

Permette di passare dalla rappresentazione grafica ad una espressione algebrica

f(x1,..,xn) = xi f(x1,.., xi-1,1, xi+1...,xn) + ¬xi f(x1,.., xi-1,0, xi+1...,xn)

1≤ i≤n Dimostrazione (per induzione perfetta): n  Se xi = 0 allora il primo termine vale 0. Poiché ¬0=1, si ha f(x1,..,xn)

= f(x1,.., xi-1,0, xi+1...,xn), che è identicamente vera perché, per ipotesi, xi = 0.

n  Se xi = 1 allora il secondo termine vale 0. Poiché ¬1=0, si ha f(x1,..,xn) = f(x1,.., xi-1,1, xi+1...,xn), che è identicamente vera perché, per ipotesi, xi = 1.

79

Teorema di Shannon

Applichiamo il teorema più volte …

f(x1,..,xn) =

x1 f(1, x2,..,xn) + ¬x1 f(0,x2,...,xn) =

x1 (x2 f(1,1, x3..,xn) + ¬x2 f(1,0, x3..,xn)) + ¬x1 f(0,x2,...,xn)=

x1 x2 f(1,1, x3..,xn)+ x1 ¬x2 f(1,0, x3..,xn) + ¬x1 f(0,x2,...,xn)=

…..

x1 x2 …xn f(1,1, …,1) + x1 ¬x2 …xn f(1,0,1, …,1)+

x1 x2 … ¬xn f(1,1, …,0) + … + ¬x1 ¬x2 ¬x3 … ¬xn f(0,0,0, …,0)

80

Forme Canoniche

Dal teorema ottengo, per una funzione di n variabili booleane, una espressione costituita dalla somma di 2n termini prodotto

Il termine generico della somma si chiama mintermine ed è il prodotto di n variabili in parte dirette e in parte negate

•  f(x1,.., xn)= Σ mkf(k) => f(x1,.., xn)= Σ mk dove: •  mk = Π x (x0= ¬x, x1=x) mintermine

•  f(k) il valore f(α1,.., αn), con α1,.., αn

81

• f(x1,.., xn)= Σ mkf(k) = Σ mk dove: • mk = Π x (x0= ¬x, x1=x) mintermine

• f(k) è il valore f(α1,.., αn)

• un mintermine m si chiama anche implicante perché ogni volta che m vale 1 anche f vale 1

n

i=1

λ

i

2n-1

k=0

k|f(k)=1

Dal teorema ottengo, per una funzione di n variabili booleane, una espressione costituita dalla somma di 2n termini prodotto Il termine generico della somma si chiama mintermine ed è il prodotto di n variabili in parte dirette e in parte negate

Forme canoniche in somma di prodotti (SP)

82

Scrivere un’espressione in somma di prodotti per rappresentare la funzione con 3 ingressi la cui uscita vale 1 se e solo se il numero di variabili d’ingresso con valore 1 è pari y=f(x1,x2,x3)

0 0 0 1

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

0 1 2 3 4 5 6 7

m3

m0

m5

m6

y =m0+m3+m5+m6 =Σ(0,3,5,6)

f(x1,x2,x3) = x3 x2 x1+ x3x2x1 + x3 x2 x1 + x3x2 x1

x3 x2 x1 y

Esempio

83

• Sia f(x1,.., xn) = Σ mk

•  g(x1,.., xn) = Σ mk •  g= not f.

Infatti, g vale 0 quando f vale 1 (poiché mancano i mintermini) e viceversa

k|f(k)=1

k|f(k)=0

Forma canonica: prodotto di somme (PS) Prodotti di somme : dualità delle forme canoniche

84

• f(x1,.., xn) = Σ mk

•  f(x1,.., xn) = Π mk => f(x1,.., xn) = Π Μk Mk =

k|f(k)=0

k|f(k)=0

k|f(k)=0

n

i=1

| αi-1|

i Σ x Maxtermine – somma di tutte

le variabili o dirette o negate

Relazioni tra Minterm e Maxterm

Infatti per il Teorema di DeMorgan: M2 è il complemento di m2 e vice versa. Così Mi in generale è il complemento di mi.

85

y x y · x + = y x y x ⋅ = +

y x M 2 + = y x· m 2 =

i m M = i i i M m =

Esempio

y=f(x1,x2,x3) è 1 se e solo se il numero di variabili con valore 1 è pari

86

0 0 0 1

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

0 1 2 3 4 5 6 7

M2

M1

M4

M7

y =M1+M2+M4+M7 =Π(1,2,4,7)

f(x1,x2,x3) =(x3+x2+ x1)·(x3 + x2 + x1)·( x3 + x2 + x1 )·( x3 + x2 + x1)

x3 x2 x1 y

Sintesi di Reti Combinatorie

Nell’attività di progetto é necessario tenere conto sia delle prestazioni che del costo.

Necessità: rete logica il più veloce possibile. A parità di velocità é necessario ottimizzare il costo.

87

Sintesi di Reti Combinatorie

Costo: dipende dalla somma del numero di letterali e delle porte Velocità : dipende dal numero max di porte attraversato dal segnale

dall’ingresso all’uscita

Una funzione realizzata a partire da una espressione canonica in somme di prodotti ha il tipo in figura

•  numero di porte uguale al numero di mintermini +1 •  2 livelli La velocità è massima, il costo non è minimo

88

X0 ¬X1

X2

¬X0 X1 X2

X0 ¬X1 ¬X2

Y

Rete AND in OR

3+3+3+3=12

3

3

3

Sintesi di Reti Combinatorie Per diminuire il costo bisogna diminuire gli ingressi delle porte e/o diminuire le porte; siccome, data una tabella di verità, è possibile ricavare più espressioni equivalenti che la rappresentano e che possono avere costi differenti, devo cercare una

89

•  Espressione minimale: espressione nella quale non possono essere

eliminati né un letterale né un termine senza alterare la funzione rappresentata dall’espressione stessa.

•  Una espressione minimale è composta solo da implicanti principali

•  Implicante principale: implicante per il quale non è possibile eliminare un letterale dalla sua espressione ed ottenere ancora un implicante

•  Gli implicanti principali si vedono bene nelle Mappe di Karnaugh

90

Mappe di Karnaugh

0 1 2 3

Y

0 0 1

X0

1 X1

0 0 0 1 1 0 1 1

X0 X1 Y Tabella di verità

91

Mappe di Karnaugh

0 1 2 3

Y 0

0 1 X0

1 X1 0 1 4 5

Y 0

00 01 X1 X0

1 X2 3 2 7 6

11 10

0 1 4 5

Y

00 00 01

01 X3 X2

3 2 7 6

11 10

12 13 8 9

11 10

15 14 11 10

X1 X0

• Le caselle adiacenti corrispondono a configurazioni delle variabili di ingresso che differiscono di un solo bit • Anche le caselle sulle due colonne estreme (o sulla prima e l’ultima riga) sono da considerarsi adiacenti, come se la mappa fosse originariamente su una sfera

92

Mappe di Karnaugh

0 1 0 1

Y

00 00 01

01 X3 X2

1 0 1 0

11 10

0 0 0 0

11 10

0 0 0 0

X1 X0

(¬X3X0) 1 0 1 0

Y

00 00 01

01 0 1 0 1

11 10

0 0 0 0

11 10

0 0 0 0

(¬X3 ¬X0) X3 X2

X1 X0

0 1 0 1

Y

00 00 01

01 X3 X2

1 0 1 0

11 10

0 1 0 1

11 10

1 0 1 0

X1 X0

(X0) 1 0 1 0

Y

00 00 01

01 0 1 0 1

11 10

1 0 1 0

11 10

0 1 0 1

(¬X0) X3 X2

X1 X0

Mappe di Karnaugh Gli implicanti principali sono insiemi di k 1 collocati in caselle adiacenti, con k uguale ad una potenza di 2.

Alcuni implicanti principali coprono almeno un 1 non coperto da altri implicanti primi

Questi implicanti detti essenziali compaiono in ogni espressione minimale

Le espressioni minimali sono composte dagli essenziali più un sottoinsieme dei principali in modo che tutti gli 1 siano coperti senza ridondanze - in questo modo non posso togliere né lettere né termini

dall’espressione senza cambiare la funzione La velocità è ancora massima perché la rete è sempre a due livelli

93 94

Mappe di Karnaugh

1

Y

00 00 01

01 1 1 1

11 10

1 1

11 10

1 1

X1 X0

1 1 1

Y

00 00 01

01 1 1 1 1

11 10

1 1 1

11 10

1 1 X3 X2

X1 X0

1 1 1

Y

00 00 01

01 1 1

11 10

1 1 1

11 10

1 1

X1 X0

1 1

Y

00 00 01

01 1 1

11 10

1 1 1 1

11 10

1 1 1 1

X3 X2

X1 X0

X3 X2

X3 X2

95

Moduli combinatori

Reti combinatorie complesse –  Scomposizione delle reti in sottoreti –  Si rinuncia alla soluzione teoricamente ottima ottenibile

attraverso la minimizzazione delle reti a due livelli in somme di prodotti, a favore di una maggiore comprensibilità e gestibilità del progetto

–  Componenti standard –  Possibilità di usare componenti integrati che svolgono

precise funzionalità di carattere combinatorio

Altri operatori

Mediante il teorema di De Morgan è possibile dimostrare che qualsiasi espressione logica può essere espressa tramite due soli operatori

Infatti l’insieme degli operatori algebrici {+, ·,-} è funzionalmente ridondante L’insieme {+, -} e l’insieme {·, -} sono funzionalmente completi

96

NAND e NOR

Questi operatori si chiamano NAND e NOR

97

NAND e NOR

Le porte NAND e NOR permettono di realizzare qualunque funzione logica utilizzando un solo tipo di porta

98

Reti con solo porte NAND o NOR

Il passaggio da espressioni in forma SP a reti NAND risulta immediato tramite il teorema di De Morgan

Nello stesso modo da reti PS a NOR

–  z=ab+cd=ab+cd=(ab)(cd)=(a|b)|(c|d)

99 100

Moduli combinatori

Reti combinatorie complesse –  Scomposizione delle reti in sottoreti –  Si rinuncia alla soluzione teoricamente ottima ottenibile

attraverso la minimizzazione delle reti a due livelli in somme di prodotti, a favore di una maggiore comprensibilità e gestibilità del progetto

–  Componenti standard –  Possibilità di usare componenti integrati che svolgono

precise funzionalità di carattere combinatorio

101

Codificatore

Un codificatore (o coder) è un circuito che presenta p = 2n ingressi x e n uscite z.

Il comportamento della rete è specificato solo per quelle configurazioni con uno e un solo ingresso ad 1 e tutti gli altri a 0.

Se xi è l’ingresso posto ad 1, le uscite sono tali da codificare l’intero i in binario.

102

Codificatore

Realizzazione

103

Decodificatore

Un decodificatore (o decoder) è un circuito che presenta n ingressi e 2n uscite . Contrariamente al codificatore, tutte le configurazioni di ingresso sono possibili.

Il decoder realizza la funzione inversa del coder; infatti interpreta l’insieme delle 2n combinazioni di ingresso come un numero i espresso in codifica binaria, e pone ad 1 la i-esima linea di uscita, mantenendo a 0 tutte le altre.

104

Decodificatore

Decodificatore 2x22

Decodificatore

Data una tabella di verità con n ingressi e m uscite, un decodificatore nx2n e M porte OR con 2n ingressi permettono di realizzare la rete combinatoria (non a costo minimo) che la implementa.

105

Selettori: Multiplexer

Un selettore di ingresso (multiplexer) è un dispositivo che permette di selezionare uno degli n ingressi e presentarlo sull’unica uscita

Un multiplexer di ordine n è un circuito combinatorio con n ingressi x, un’unica uscita z, e k variabili di comando b con

106


Funzionamento –  Il multiplexer seleziona l’ingresso xi con i pari al valore delle

variabili di comando, interpretate secondo la codifica binaria, e pone il valore dell’uscita pari al valore di xi. In altre parole, le variabili di comando instradano uno degli ingressi verso l’unica uscita.

107 108


Esempio di Multiplexer di ordine 2


Il multiplexer può essere usato per sintetizzare una qualsiasi funzione combinatoria.

–  Basta collegare alle variabili di comando del multiplexer gli ingressi della funzione e agli altri ingressi del multiplexer costanti 1 e 0 a seconda della risposta della funzione per quella configurazione d’ingresso .

109

Selettori: Demultiplexer

Funzionamento –  Il funzionamento del demultiplexer consiste nell’instradare il

valore dell’unico ingresso x sull’uscita specificata dalle variabili di comando, mentre tutte le altre uscite rimangono a zero. L’ingresso viene instradato sull’uscita zp se e solo se il valore delle variabili di comando bk−1 · · · b0 rappresenta la codifica binaria dell’intero p.

110

111

Memorie ROM

Prima forma canonica. –  Per qualunque funzione con m ingressi richiede

•  Un numero di porte AND con m ingressi pari al numero di mintermini

•  Una porta OR con numero di ingressi pari al numero di porte AND

La figura seguente mostra una struttura regolare con la quale i collegamenti tra le uscite delle porte AND e gli ingressi della porta OR sono ottenuti attraverso contatti

–  Programmare il comportamento della rete equivale a fissare i contatti

Memorie ROM

Una rete con m ingressi e k uscite costituisce una ROM di M=2m posizioni (celle) di k bit ciascuna.

Le ROM (Read Only Memory) sono delle memorie non volatili di sola lettura. Questo significa che il loro contenuto informativo è stabilito una volta per tutte all’atto della fabbricazione.

Una ROM realizza una forma canonica

112

Memorie ROM

Nelle ROM è il costruttore che fa le connessioni in base alla matrice di bit desiderata

PROM (Programmable Real Only Memory) la matrice ha inizialmente tutti i punti di contatto tra righe e colonne.

–  Programmare un bit richiede la fusione del relativo fusibile in modo da inserire uno 0

113 114

Memorie ROM

EPROM (Erasable PROM) sono delle PROM che possono anche essere cancellate esponendo il chip (racchiuso in uno speciale case con una finestrella al quarzo) ad una forte luce ultravioletta.

EEPROM (o E2PROM) (Electrically Erasable

PROM) sono delle EPROM che hanno il vantaggio di poter essere cancellate applicando un opportuno voltaggio. In questo modo, rispetto alle EPROM, si aumenta la facilità d’uso e si diminuisce il costo del packaging del circuito.

115

Unità aritmetiche e logiche

Semisommatore

116


Sommatore completo

117


Sommatore completo una sintesi –  Mappe di Karnaugh corrispondenti

alla tabella di fianco

118


Somma di due numeri interi –  Emula il procedimento di somma con “carta e matita” –  Utilizzo del Sommatore Completo (Full Adder)

119

Registro Stack Pointer SP Registri di stato:

Instruction Pointer IP Flag register F !

"


CFZFSFOF

11 7 6 0

Carry Flag CF"Zero Flag ZF"SignFlag SF"Overflow Flag OF"

120


Siano tR e tS i tempi che un elemento FA richiede per calcolare il riporto e la somma

Caso peggiore per sommare un numero di n bit (riporto propagato a tutte le celle)

–  TR = n tR per il riporto Rn-1 –  TS = (n-1)tR + tS per il calcolo della somma

121


E’ possibile impiegare in modo iterativo il calcolo anticipato del riporto, costruendo reti a piu’ livelli

122


Esempio di costruzione di un’unità aritmetica Partendo dal sommatore, implementiamo la sottrazione

(esprimiano B in complemento a due) –  A-B=A+(-B)


Aggiungiamo della logica, per usare lo stesso sommatore sia per la somma che la sottrazione

123 124


Aggiungiamo della logica, per usare lo stesso sommatore sia per la somma che la sottrazione

Due risultati straordinari (overflow) • Si sommano due numeri positivi ed il risultato e’ negativo • Si sommano due numeri negativi ed il risultato e’ positivo

125


La tabella seguente riporta i risultati in corrispondenza di ogni combinazione di c1 cO R-1.

126


Quella che abbiamo fatto è una semplice ALU Possiamo estenderla con le operazioni logiche

–  però dobbiamo annullare gli effetti dei riporti

127


Aggiungiamo c2 e c3 per selezionare le operazioni logiche

128


Estendiamo ora la ALU con le operazioni logiche

Definizione di informatica RAPPRESENTAZIONE … · 2017. 3. 6. · I numeri naturali maggiori o...

Documents

Transcript of Definizione di informatica RAPPRESENTAZIONE … · 2017. 3. 6. · I numeri naturali maggiori o...