Fondamenti di informatica 1 parte 4 D.U.1 fondamenti di informatica parte 4 appunti per il D.U. in...

fondamenti di informatica 1 parte 4 D.U.

1

fondamenti di informatica parte 4

appunti per il D.U. in Ingegneria Informatica, di Telecomunicazioni e di Meccanica, a.a. 2000-2001dianna maria carminelli gregori


2

Prima di proseguireancora qualche riflessione utile.E’ gia’ stato detto che lo schema di flusso puo’

essere di notevole aiuto quando la logica del programma da costruire non e’ semplice. Altrimenti puo’ bastare indicare gli obiettivi nel linguaggio naturale (pseudocodice).

Se nel tema dell’ esame (scritto) gli obiettivi sono posti con la stesura stessa (come appare anche dal testo successivo che rappresenta la 4a domanda dell’ esame del 17.10.2000) lo schema di flusso non occorre e non e’ richiesto.


3

Tema del 17.10.2000Scrivere in C o C++ un programma,

strutturato in sottoprogrammi, che letti da tastiera 3 dati numerici, positivi e ciascuno <1

_ ne valuti il minimo e il massimo;_ se il minimo e’ inferiore a 0.25 proceda a

moltiplicare per 1.1 i dati e a rivalutarne il minimo e il massimo, ripetendo tali operazioni fintantoche’ il minimo risulti maggiore o uguale a 0.25;

(segue)


4

Tema ..._ visualizzi sul video o i dati modificati, o la stringa ”Non occorre modificare i valori letti”;

_ (memorizzi in una tabella in Memoria Centrale e) visualizzi sul video i dati originali.

N.B. E' SCONSIGLIATO L' USO DI VARIABILI GLOBALI.

L’ uso delle tabelle sara’ mostrato +oltre quindi nell’ ultima domanda attualmente e’ considerata solo la richiesta di visualizzazione.


5

Considerazioni e ...I 3 dati numerici, sono positivi e ciascuno

<1: per memorizzarli occorreranno 3 variabili di tipo …. Di questi 3 dati si deve valutare il minimo e il massimo, NON l’ ordinamento !

Per valutare il minimo occorre considerare una variabile dello stesso tipo dei dati e chiamarla per esempio min. Per il massimo la variabile dello stesso tipo sara’ max.

La rivalutazione del minimo implica un procedimento iterativo che si puo’ realizzare con una funzione contenente la frase while.


6

… svolgimento: Il main deve leggere i 3 valori, attivare una funzione che calcoli il

minimo, un’ altra che calcoli il massimo, se il minimo e’ inferiore

a 0.25 deve attivare una funzione che rivaluti minimo e massimo, e poi c’e la memorizzazione e la visualizzione:

main(){/* Inizio Modulo principale */ float a, b, c, min, max;

/*Parte esecutiva*/ clrscr(); cout <“\n dammi i 3 float: “; cin >> a >> b >> c; min = minimo(a, b, c); // passaggio per valore max = massimo(a, b, c); // “ “ “ if(min<0.25){max=rivaluta(&min, &a, &b, &c); // indirizzi !

visual(a,b,c);} /*else memovis (a,b,c);*/ cin >> " "; return 0;}


7

… e la funzione minimo ?Eccola … (e analoga sara’ la funzione massimo:)float minimo(float a, float b, float c){float mi; // si puo’ usare min ?!?cout<<“\nCon i dati: ”<<a<<“ “<<b<<“ “<<c;if (a<b && a< c) mi=a;else if (b<a && b<<c) mi=b;else mi = c;cout <<“\n il minimo e’:”<< mi; <<endl;return mi; //la funz. ha in piu’ le visualizzazioni...}


8

Alla funzione rivaluta i parametri sono passati per indirizzo quindi:

float rivaluta (float *m, float *x1, float *y1, float *z1) // m, x1, y1, z1 sono puntatori a float: per lavorare sui valori puntati occorre usare l’ operatore *

{float ma=0;//var. locale usata per restituire il massimo

while (*m < 0.25){*x1= unoeun*(*x1); *y1= unoeun*(*y1);*z1=unoeun*(*z1); *m=minimo(*x1,*y1,*z1);} ma=massimo(*x1, *y1, *z1); // *x1,… valori !!! return ma;}


9

CAPIRE BENE E completareil programma con le direttive al

precompilatore (per es. #define unoeun 1.1), i prototipi dei sottoprogrammi, la funzione

massimo, la procedura visual che mancano, le costanti …

farlo girare;dopo l’ introduzione delle tabelle

realizzare anche la procedura memovis.


10

<condizione>Nella sintassi delle frasi if, while et similia

compare una condizione o asserzione logica che puo’ essere vera (True) o falsa (False). Sono due possibili valori di stato che vengono assunti da una qualsiasi asserzione logica nel caso che essa si verifichi o no. Potendo contrassegnare un’ asserzione logica con un identificatore di variabile, questa assumera’ il valore vero se l’ asserzione logica si verifica, falso in caso contrario. Pero’ il significato della variabile diventa quello di una variabile logica


11

Il discorso quindi si apre verso una nuova direzione che e’ la

logica, trattata da molteplici studiosi ed autori gia’ nel periodo greco-romano (1 es. Aristotele)

La logica matematica studia i possibili mezzi matematici atti a descrivere la logica delle proposizioni. Tra i suoi studiosi c’ e’ per esempio il filosofo Leibnitz. Un logico-matematico molto importante e’ George Boole che nel 1847 publico’ un trattato di logica matematica che da lui prese il nome di Algebra di Boole.

A questo tipo di algebra ci introducono anche: ...


12

Gli operatori logici del C e C++ :

Negazione not !Prodotto logico and &&Somma logica or ||Il loro significato sara’ chiarito proprio dall’

algebra di Boole ed anche dall’ esempio seguente che puo’ facilitarne l’ introduzione. L’ es. si riferisce al prg. While1 che converte minuscole in maiuscole. La frase if che li’ si usa e’ simile alla seguente:


13

&& = and => e inoltreif (car>=‘a’) {if (car<=‘z’) putchar (car+’A’-’a’) }else putchar (car);Significato di questa frase: se car e’ compreso

nell’intervallo a-z allora scrivi car dopo averlo convertito in maiuscolo se no scrivilo cosi’ come e’. Con gli operatori logici la frase puo’ essere cosi’ riscritta:

if ((car>=‘a’) && (car<=‘z’)) putchar (car+’A’-’a’) else putchar (car); Si deduce dunque che: ...


14

il collegamento tra espressioni relazionali

puo’ avvenire con operatori logici in modo da costruire espressioni logiche.

Preciso significato logico dell’ operatore && di collegamento nell’esempio precedente:

se car >’a’ e inoltre car < ‘z’ allora convertilo.L’ espressione car >’a’ && car < ‘z’ e’ di

tipo logico. Il C e C++ non prevedono alcun tipo di dato logico, ma lo fanno corrispondere al tipo int con i 2 valori False (=Falso) e True (=Vero) rappresentati da 0 per False e 1 per True.


15

Il significatodegli operatori logici del C e C++ e’ il

seguente:Negazione not ! => opposto diProdotto logico and && => e inoltreSomma logica or || => oppureLe costanti logiche True=Vero=1 e

False=Falso=0 (che puo’ assumere ogni variabile e/o espressione logica) sono tipiche dell’ algebra di Boole.


16

Algebra di BooleL’ idea di G. Boole era quella di automatizzare

il ragionamento. Punto di partenza del suo discorso sono le proposizioni con significato di osservazioni e/o ‘asserzioni logiche’. Es. Oggi piove; Prendo un taxi; Sono ricco; Socrate e’ un uomo; .…Di ciascuna di queste si puo’ dire che e’ vera o falsa. (Quali altre non hanno questo significato? Per es. le ingiunzioni: Non uscire!)

Ad ogni asserzione logica si puo' associare una variabile a 2 valori (binaria) contenente uno dei 2 valori Vero o Falso, (True , False), 1 o 0. Si tratta delle variabili booleane o logiche.


17

True e Falsesono le 2 uniche costanti logiche dell’ algebra

di Boole con valori: False=0 True 0 posta = 1Le variabili booleane o logiche sono simili alle

variabili numeriche usate nell’ algebra classica, ma possono assumere solo questi 2 valori ossia sono binarie. Oggetto dell’ algebra di Boole sono insiemi di variabili con nomi diversi e contenenti False = 0 o True =1.

Sulle 2 entita’ 0 e 1 si possono introdurre le 3 operazioni basilari dell’ algebra di Boole.


18

Operazioni di base dell’ algebra sono:

il prodotto logico o congiunzione = and , la somma logica o disgiunzione = or ,la complementazione o negazione = not. La definizione di ogni operazione avviene

tramite una tabellina: in quelle del prodotto e della somma compaiono due variabili indipendenti ed una variabile dipendente che contiene il risultato; in quella della negazione la variabile indipendente e’ solo una come la variabile dipendente.


19

Tabellina di Prodotto (congiunzione = and )

X Y X Y con X e Y var. indipend. e X Y var. dipend. 0 0 0 1 0 0 0 1 0 1 1 1

Tabellina di Somma (disgiunzione = or ) X Y X+Y con X e Y var. indipend. e X+Y var. dipend. 0 0 0 1 0 1 ARITMETICA ELEMENTARE, MA PARTICOLARE 0 1 1 perche’ 1 e’ il tetto oltre il quale non si va !!! 1 1 1


20

Tabellina di negazione e … funzioni elementari !

A not (A)=Ā con A var. indipend. e not(A) var. dipend. 0 1 not (A) e’ indicata anche con A barrato 1 0 ossia A negato o -A

Ogni operazione puo’ essere considerata come una funzione elementare di 1 o 2 variabili

G.Boole, evidenziando la correlazione tra le var. binarie e le proposizioni logiche associabili ad esse, sottolinea come anche le operazioni booleane su tali proposizioni logiche assumono un significato logico.


21

Significato logico delle operazioni booleane (esempi)

Operazione logica congiunzione = and = . = ‘e inoltre’ Piove Ho soldi Prendo taxi X Y X Y (come in algebra e’ omesso il . ) 0 0 0 1 0 0 0 1 0 1 1 1 Oper. logica complementazione Fa freddo Non Fa freddo se la var. vale 1 il risultato e’ 0 A not (A)=Ā “ “ “ “ 0 “ “ “ 1 0 1 1 0


22

Operazioni algebriche ==>operazioni logiche

Operazione logica disgiunzione = or = + = ‘oppure’ Piove Fa fresco Metto impermeabile X Y X + Y 0 0 0 1 0 1 0 1 1 1 1 1

Altro esempio: sia b = oggi piove ed e’ tempo brutto; c = oggi e’ tempo bello; se b = true (=1) deve essere c = false (=0) e viceversa, e

poi non puo’ essere che sia b=c=true


23

Conclusioni:1a conclusione: l’ A.d.B. definisce operazioni di

tipo matematico che permettono di interpretare operazioni logiche;

2a conclusione: gli operatori dell’ A.d.B. possono effettuare automaticamente le proposizioni logiche tipiche dell’ intelligenza umana … primo passo verso la programmazione logica (Prolog);

3a conclusione: data la semplicita’ dell’ A.d.B. e’ possibile l’ automazione dei suoi calcoli con circuiti elettronici.


24

Come si traducono le operazioni dell’ A.d.B. in C++

Si definiscono le costanti True e False. In C e C++ la definizione puo’ avvenire in diversi modi dei quali uno usa la direttiva al precompilatore:

#define True 1 // in C basta che sia positiva 0#define False 0Le variabili logiche sono intere e si puo’ usarle

normalmente: ES. int ripeti = True; cfr. ripelegStabilito che True = 1 si capisce il significato

del ciclo infinito while(1) ed anche alcune condizioni del tipo: if (ch=getchar()) cout<< “ch”; …. O NO ? Se NO cfr. in program5 Tasto.cpp


25

Gli operatori logici del C e C++ (come gia’ visto) collegano le variabili logiche o le

espressioni relazionali e permettono di ottenere cosi’ un’ espressione logica.

Complementazione not !Prodotto logico and &&Somma logica or ||Es. di uso in while2.Con questi operatori o simili, ma di uguale significato,

il C, C++ e gli altri linguaggi di programmazione come il Pascal, il Basic, ... possono essere usati per costruire programmi con analisi di tipo logico (per es. gli Expert System per le diagnosi automatiche.)


26

A proposito della variabile logica da usare in switch4

Quando la funzione menu() viene attivata nella frase switch e’ giusto che richiami la funzione leggi(n) in quanto n deve dirottare il controllo al caso ennesimo; invece quando la funzione menu() viene attivata nelle 2 funzioni di elaborazione non occorrera’ una nuova lettura purche’ n sia ancora disponibile. Questo e’ il punto: n e’ ancora disponibile? NO se in menu non si dichiara:

static int n;


27

Significato delle variabili automatiche e statiche

In C e C++ ogni variabile e’ caratterizzata oltre che dal tipo dalla classificazione rispetto alla sua allocazione in memoria ed alla sua durata. Le variabili finora trattate sono chiamate automatiche perche’ iniziano ad esistere (sono allocate in memoria) quando la funzione in cui sono definite e’ attivata e “spariscono” all’ uscita dalla funzione, non conservando il loro valore tra una attivazione e l’ altra. Per conservarlo devono essere dichiarate static: senza questo attributo sono automatiche.

Meo 1 lez.33Meo 1 lez.33


28

Static => protezioneTutte la variabili (locali o globali) definite

static sono create ed inizializzate prima che il main inizi l’ esecuzione e sono distrutte solo al termine dell’ esecuzione del main program: la loro inizializzazione e’ eseguita una sola volta, se manca sono inizializzate a 0.

Anche una var. globale (o esterna) puo’ essere dichiarata static: in tal caso diventa visibile e usabile solo all’ interno delle funzioni definite nello stesso file sorgente in cui essa e’ definita, ma diventa invisibile ad altri file, a sua protezione.


29

Conclusione per menu()Per salvare il valore di n letto solo la prima volta

bisogna dichiarare n static (non solo int) e quindi scrivere menu cosi’ (come in switch5):

int menu (int attiva) /* attiva param. formale di tipo logico che deve essere True solo al primo richiamo e False ai richiami successivi*/

{static int n; // n inizializzata a 0if (attiva) leggi(&n) /*se attiva = True in n va il

valore digitato che resta immutato fino a nuova lettura che non si verifica se attiva = False */

return n; }


30

A.d.B. e dualita’L’ A.d.B. si puo’ definire in modo molto

rigoroso introducendo il concetto di reticolo caro ai matematici. In questo approccio elementare si introdurrano le Proprieta’ degli elementi, degli operatori logici e delle operazioni logiche.

a) l’ elemento 0 si dice duale dell’ elemento 1, l’ operatore + duale dell’ operatore . e vale la seguente legge di dualita’:

b) da qq. identita’ booleana se ne puo’ trarre un’ altra per dualita’ sostituendo i rispettivi duali agli elementi 0 e 1 ed a ogni operatore.


31

c) proprieta’ delle operazioni logiche: si dimostrano con le

tabelle di verita’ e sono estensibili a n variabili.1) associativa della somma: (A+B)+C = A+(B+C)NOTA: la somma di 2 o piu’ variabili assume il valore

0 solo se tutte la var. sono 0 e assume 1 negli altri casi

2) associativa del prodotto: (A B)C = A(BC)NOTA: il prodotto di 2 o piu’ variabili assume il val. 1

solo se tutte la var. sono 1 e assume 0 negli altri casi


32

Proprieta’ delle operazioni dell’ Algebra di Boole

3) doppia negazione: not (not A) = A 4) distributiva del prodotto: A (B+C) = AB + AC5) distributiva della somma: A+(BC) = (A+B)(A+C) (piove o (c’e’ vento e

inoltre fa freddo) = (piove o c’e’ vento) e inoltre (piove o fa freddo))

6) assorbimento AA = A A+A = A7) proprieta’ del complemento: A+Ā =1


33

Proprieta’ fondamentali & Legge di de Morgan:

not (A+B) = not(A)not(B) il negato della somma logica = prodotto dei negati (ossia il negato di piove o fa fresco = non piove e inoltre non fa fresco)

duale: not(AB) = not(A) + not(B)Legge di de Morgan estesa: (chiarisce la dualita’ )se in un’ espressione booleana si sostituisce

ogni variabile col suo complemento, ogni operatore + con l’operatore prodotto, ogni operatore prodotto con l’operatore + si ottiene il complemento dell’ espressione data.


34

Applicazione alla legge di de Morgan duale che e’:not(AB) = not(A) + not(B) (il negato del

prodotto = somma dei negati) Se in not(AB) (1o menbro) si sostituisce A con not(A), B con not(B) e l’ operatore . con +

si ottiene: not(not(A) + not(B)) ossia il complemento di

not(A) + not(B) (2o menbro) che e’ uguale a not(AB)!! quindi il complemento di not(AB)=AB,

o come si indichera’ tra 2 diapo, nand(AE) = (Ā+Ē).


35

Operazioni algebriche ==> circuiti logici

Come si e’ gia’ visto, ogni operazione eseguibile su variabili booleane (somma, prodotto, complementazione ed altre da questa deducibili) puo' essere definita tramite una tabella con variabili indipendenti e dipendenti detta tabella di verita’ .

E per ciascuna di queste tabelle di verita' esiste il corrispondente circuito elementare …=>Importanza delle tabelle di verita’


36

Tabelle di verita’ delle Operazioni fondamentali

che sono: not or and ed anche: xor or esclusivo nand and negato nor or negatoPer le relative tabelle ed i corrispondenti

circuiti elementari (detti porte logiche) vedere il lucido tratto dal Bishop ed esteso da dove appare: nand(AE) = (Ā+Ē); nor(AE) = ĀĒ.

Meo 1 lez.9 e seg.

Meo 1 lez.9 e seg.


37

Realizzazione circuitale del calcolo binario

Per rappresentare grandezze binarie si usa di norma la tensione elettrica come grandezza di riferimento con valori convenzionali: alto =1 basso =0.

Un circuito elettronico elementare che rappresenti un’ operazione dell A.d.B. e’ detto porta (gate). Esso riceve in ingresso uno o due impulsi elettrici da 1 o da 2 punti di ingresso e fornisce 1 uscita nel punto di uscita: le tensioni sui 2 punti di ingresso rappresentano i valori delle variabili indipendenti; la tensione sul punto di uscita il valore della variabile dipendente.


38

Grafici dei circuiti elementari = porte

I simboli dei circuiti elementari sono nel lucido tratto dal Bishop: si riconoscano le varie operazioni trattate per es. AB (ossia A and B) come e’ rappresentata ? e A+B ?

In ogni circuito elettronico di E.E. sono utilizzate le porte.

I circuiti logici ottenuti combinando le porte logiche corrispondono a funzioni dell’ A.d.B.

Esercizio: scrivere in C o C++ 3 funzioni per attuare xor= or esclusivo, nand = and negato, nor= or negato e nominarle oresc, andne, orne.


39

Funzioni di variabili booleane Con solo 2 valori discreti (e non un' infinita'

di valori continui come 0.001, 0.011, 0.111 … 0.990 ...) anche le Funzioni dell’ A.d.B. si possono rappresentare in forma tabellare.

Per esempio siano 2 variabili booleane A, E col significato di: A = oggi piove; E = ho l' ombrello; la funzione f(A,E) (col

significato di: f(A,E) = esco in auto), si potra' scrivere cosi’: A E f(A,E) 0 0 0 oggi piove=ho l’ombrello=esco in auto=falso 1 0 1 “ “ vero “ “ falso “ “ “ vero 0 1 0 etc. 1 1 1


40

Tabelle di verita' delle f(x,y)La tabella precedente e' la tabella di verita'

della funzione f(A,E). La sua espressione booleana si costruisce "elencando" tutte le condizioni che portano f(A,E) ad assumere valore VERO.

Nell’ esempio: f(A,E) e’ vera (ossia esco in auto) se A e’ vera e inoltre E e’ falsa (oggi piove e non ho l’ ombrello) oppure se A e’ vera e inoltre E e’ vera (oggi piove e inoltre ho l’ ombrello). ANCHE: f(A,E) e’ vera se: A e’ vera e inoltre Ē e’ vera oppure se A e inoltre E sono vere.


41

L’ espressione booleana di f e’ quindi: f(A,E) = AĒ + AE = A(Ē+E) = AQuesto e’ il modo di costruire l’ espressione

booleana di una qualunque funzione f(X,Y,Z …) dove X, Y, Z… sono variabili booleane

(L’ "elenco" di tutte le condizioni che portano f ad assumere SOLO il valore VERO =1, e’ costruito con le righe della tabella di verita’ in cui f=1: su ogni riga le variabili sono legate da operatori and mentre le righe sono legate da operatori or).


42

SemplificazioneL’ espressione ottenuta puo’ poi essere

tradotta in un circuito logico equivalente: se pero’ non e’ semplice e’ meglio semplificarla applicando le fondamentali proprieta’ dell' algebra di Boole.

Si arriva ad un' espressione booleana semplificata che si traduce in un circuito logico piu’ semplice e quindi piu’ economico di quello che si otterrebbe utilizzando l' espressione non semplificata.


43

Esempio:

A E U f 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1

A parole: f e’ VERA se A,E,U

sono tutte FALSE oppure se A e E sono FALSE e inoltre U e’ VERA oppure se A,E,U sono tutte VERE oppure se A e inoltre U sono VERE e inoltre E e’ FALSA.


44

Semplificazione

L' espressione booleana corrispondente e’: f= ĀĒŪ + ĀĒU + AĒU + AEU 1a espressione

da semplificare1o passo ĀĒŪ + ĀĒU = ĀĒ (Ū+U) = ĀĒ proprieta’

dist. del prodotto e del complemento (U+ Ū)=1 2o passo AĒU + AEU = AU(E+Ē) = AU proprieta’

dist. del prodotto e del complemento (E+Ē)=1 Quindi: f= ĀĒ + AU f

...

...


45

Il circuito corrispondente(molto piu’ semplice di quello relativo all’

espressione non semplificata) e’ elementare:i 2 segnali A e U entrano direttamente in una

porta and mentre i segnali A e E prima di entrare in una porta and devono essere complementati o possono entrare direttamente in una porta nor. Riflettere su questo: per quale legge ? Le uscite delle 2 porte and e nor entrano poi in una porta OR da cui esce il segnale risultante, valore della f(A,E,U).


46

Conclusioni:i circuiti logici che si ottengono combinando le

porte logiche, corrispondono a funzioni dell' algebra booleana ciascuna caratterizzata da una Tabella di Verita’ e rappresentata da un' espressione.

L’ espressione si semplifica usando le relazioni fondamentali, per es. la proprieta’ distributiva del prodotto: A(B+C) = AB + AC;

o la proprieta’ distributiva della somma: A+(BC) = (A+B)(A+C); (fa freddo o (nevica e piove))

o …


47

La semplificazione si ottieneanche usando la proprieta’ di assorbimento:A+A = A;AA = Ao le leggi di de Morgan, di dualita’ … Si otttengono cosi’ i Circuiti logici Combinatori che hanno la

caratteristica di essere "smemorati": i valori di uscita sono funzione dei soli valori di

ingresso in un dato istante.


48

Altro tipo di circuiti logici sono i circuiti sequenziali

con memoria: i valori di uscita sono funzione dei valori di ingresso e dello Stato del circuito.

Per Stato di un sistema si intende in generale il valore della situazione in cui il sistema si trova.

Esempio del prof. Mezzalama e’ il sistema "apriporta” a 2 Stati: porte aperte-porte chiuse e relativi comportamenti diversi.

Esempio tipico di Circuiti Combinatori e’ il Decodificatore; di Circuiti Sequenziali e’ il Registro di Memoria detto Flip-Flop.

Tutti questi Circuiti si trovano nella CPU di E.E.


49

DecodificatoriPer la conversione dei dati da un formato all'

altro sono necessari appositi DECODIFICATORI.

Un semplice esempio di DECODIFICATORE elementare e’ formato da un circuito con 2 morsetti di ingresso (su cui scrivere un codice da 0 a 3) e 4 morsetti di uscita di cui solo uno deve essere attivo in un certo istante. Il codice scritto sui 2 morsetti di ingresso indica il morsetto di uscita che si vuole rendere attivo nell' istante considerato. Queste sono le specifiche del circuito DECODIFICATORE.


50

L’ esempio di decodificatore

presentato appare inizialmente come una scatola nera qui sotto rappresentata che per ogni segnale di input ha un segnale di output.

A _____ ______0_ ______1_ E _____ ______2_ ______3_


51

Sui morsetti di ingresso si scrive un codice con:

segnale su: A E 0 0 basso su A basso su E 0 1 " " " alto " " 1 0 alto " " basso " " 1 1 " " " alto " "Dei morsetti di uscita solo uno deve essere

attivo in un cero istante.Il circuito attua quattro funzioni booleane

distinte.


52

Per ciascuna funzione booleana di uscita

si puo’ scrivere una tabella di verita’. Per es. per l'uscita 0 si ha: A E USC.0

0 0 1 0 1 0 1 0 0 1 1 0Dalla prima riga della tabella si deduce: USC.0 = ĀĒ

quindi il DECODIFICATORE prima visto come una scatola nera contiene al suo interno anche porte nor: in una di queste entrano i segnali A ed E (teorema di de Morgan).


53

Sintesi di circuitiSi e’ arrivati alla sintesi del circuito USC.0

tramite l' ispezione della tabella della verita’ che descrive la funzione logica USC.0 per ogni combinazione di valori delle due variabili A e E. E' questa una tecnica usata per la sintesi di circuiti combinatori semplici; la sintesi di ogni circuito combinatorio complesso si ottiene con la descrizione delle funzioni (= operazioni) che il circuito stesso deve realizzare. La descrizione viene espressa in un linguaggio simile ad un linguaggio di programmazione. (Corso di Reti logiche)


54

Perche’ ?L’ispezione delle tabelle di verita’ che

descrivono funzioni logiche per ogni combinazione di valori delle variabili di ingresso, diventa pesante all’ aumentare del numero N delle variabili. Il numero delle righe di una tabella di N var. e’ pari a 2N (num. di combinazioni diverse) ossia di tipo esponenziale e quindi al crescere di N (= 10, 20, 30 ...) si deve usare un altro metodo.


55

Flip-Flop Set-Reset = FF_SRCircuito elementare di memoria che

memorizza un BIT = BInary digiT = cifra binaria => informazione elementare

E’ realizzato con 2 porte nor retroazionate come si vede nel grafico fornito tratto da Meo, Mezzalama dove Q indica lo stato attuale del circuito.

E’ detto anche multivibratore bistabile …Domanda: che tipo di circuito e’ ?


56

Q= STATO del SISTEMA circuito FF_SR : o 0 o 1

Se in ingresso S = R = 0 risulta se Q=0 allora not(Q)=1 e Q restera’ 0 in uscita se Q=1 allora not(Q)=0 e Q restera’ 1 Il RISULTATO e’ diverso pur avendo lo stesso

ingresso: cio’ dipende dallo STATO del circuito => il valore di uscita e’ funzione dell’ ingresso e inoltre dello STATO del circuito … sequenziale


57

Altre situazioni: Se in ingresso S = 1 (SET) e R = 0 risulta: se attualmente Q=0 allora nor(QS)=0=not(Q) quindi Q = nor(not(Q)R) diventa 1; 0 0

invece se Q=1 allora nor(QS) = 0 = not(Q) quindi Q = nor(not(Q)R) resta 1. Se in ingresso S = 0 e R =1 (RESET) risulta:se attualmente Q=0 allora nor(QS)=1=not(Q)

quindi Q = nor(not(Q)R) resta 0; ed anche se Q=1 nor(QS) = 0 = not(Q) quindi Q=nor(not(Q)R) diventa 0. In definitiva: ...

0 1


58

FF_SR: 8 situazioni possibili = 4 input X 2 stati attuali (Q_ora)

X Y nor(X+Y) 0 0 1 1 0 0 0 1 0 1 1 0

S R Q_ora Q_poi 0 0 0 0 S=R=0 no modifiche 0 0 1 1 Q_poi=Q_ora 1 0 0 1 S=1 forza Q_poi a 1 1 0 1 1

0 1 0 0 R=1 forza Q_poi a 0 0 1 1 0

1 1 0 0 o 1 Ambiguita’ da 1 1 1 0 o 1 togliere con

modifiche nella struttura (FF tipo D o JK)


59

La Dipendenza dal tempodeve essere introdotta in tutti i circuiti

collegandovi il segnale di clock come ingresso ulteriore: e’ il segnale periodico che cadenza il funzionamento dei circuiti e permette la sincronizzazione di tutte le operazioni.

Es. i Flip-Flop non sono usati singolarmente, ma generalmente aggregati a gruppi di 4 o di 8 (=byte) o di 32 (registro). Le linee portanti l’ informazione entrano in porte and col segnale di clock: le uscite delle porte and diventano gli ingressi dei Flip-Flop => Tutti FF sono temporizzati nello stesso modo e sono attivi solo quando e’ attivo il segnale di clock.


60

MemorieI Flip-Flop vengono usati negli elementi di

memoria di E.E. ossia nella RAM e nei registri della CPU.

La memoria principale o C.M. di E.E. (composta con circuiti denominati RAM =Random Access Memory) ha come parametri significativi il tempo di ciclo TC e la capacita’ C (dimensione).

TC = intervallo tra la richiesta di un dato da parte della CPU e la fine della risposta della memoria che torna allo stato di ricezione.


61

SRAM e DRAM:sono 2 tipi di circuiti. TC 10 nsec

SRAM = Static RAM C << C(DRAM) + veloci, ma + costose e

. + voluminose TC 50 nsec

DRAM = Dinamic RAM C 16 Milioni di bit / chip

+ usateLegenda: il simbolo significa dell’ ordine di; il chip e’ … il “nostro centopiedi”


62

ROM (Read Only Memory)

Circuiti con informazione memorizzata in modo permanente

1) programmabili 1 sola volta in fabbrica Tipi 2) “ “ “ “ dall’ utente 3) cancellabili e riprogrammabili “ “ .

+volte1) ROM, 2) PROM, 3) EPROM


63

Emulazione della C.M.Della C.M. di E.E. fu detto (parte 1) che nel

Modello di von Neumann la memoria e’ di tipo lineare ossia: successione di locazioni (posizioni, celle, byte, parole) numerate (e quindi indirizzabili) sequenzialmente !

Problema1: sua emulazione con un programma in C e C++.

Problema2: memorizzare le tavole dell’ A.d.B.Soluzione: utilizzo di tabelle o array o altro ?


64

ArrayE’ un tipo di variabile composta, strutturataImportante perche’ permette di:mantenere in memoria un insieme di elementi

omogenei (dello stesso tipo, detto tipo base);tutti presenti contemporaneamente, posti in

memoria consecutivamente a partire da un indirizzo iniziale, ma accessibili in modo casuale o diretto usando la loro posizione;

accessibili +volte tramite appositi indici interi che in C e C++ assumono uno tra i valori compresi in un dato intervallo a partire da 0 (a cui corrisponde il primo elemento dell’ array);

Richiede un’ opportuna definizione in cui sia dichiarata al compilatore la sua dimensione.


65

Esempi di definizione di array o tabelle a + dimensioni in C++

int a[5] array monodimensionale o vettore di 5 componenti intere memorizzabili in:

a[0], a[1], a[2], a[3], a[4]. Necessario 1 indicefloat f[2][3] array bidimensionale o matrice

di 2 righe e 3 colonne memorizzabili in:f[0][0], f[0][1], f[0][2], (tipo base=float)f[1][0], f[1][1], f[1][2] Necessari 2 indiciint c[2][3][4] array tridimensionale di tipo intero

(4 matrici di 2 righe e 3 col.: necess. 3 indici).


66

Possibili inizializzazioni: In fase di compilazione:float f[5] = {0.0, 1.0, 2.0, 3.0, 4.0};int g[100] = {7}; // si inizializza solo g[0]=7; int dedo [] = { 2, 3};//inizializzazione obbligatoria:

NON c’ e’ dimensione => il compilatore la calcola automaticamente in base al numero di valori di inizializzazione: UNico caso ammesso senza dimension.

In fase di esecuzione con cicli a ripetizione nota:es. for (i=0; i<5; i++) f[i] = (float) i ; for (i=0; i<100; i++) g[i] = 0;// g azzerata


67

Creazione-stampa di vettoriIl primo esempio d’uso di vettori e’ in program6

il prg. creastatab.cpp dove si notano i vettori tab e cop dichiarati di MAX componenti o elementi. Il vettore tab e’ creato nel main con un for mentre in cop (non inizializzato) sono letti, con la procedura leggi, e sempre con un for, i valori degli elementi del vettore, uno dopo l’ altro; la sua copia e’ fatta nella procedura copia, la visualizzazione nella procedura scrivi;

in tutti i sottoprogrammi il passaggio di vettori (e array in generale) e’ fatto per indirizzo.


68

Il nome del vettore e’sinonimo dell’ indirizzo del primo elemento del

vettore => Si puo’ scrivere: float ris[10]; float *p; p=ris; /*oppure*/ p=&ris[0]; // cfr. tabel

ris e’ un puntatore, ma costante perche’ sigillato a puntare sempre allo stesso vettore.

Es. char* puni =“sono un’ idea”; // puni e’ inizializzato con l’ indirizzo di s, ma poi avendo: puni =“punto un oggetto”; // a puni si assegna un altro indirizzo: quello di p.

Non si puo’ mai invece modificare l’ indirizzo in ris, il contenuto SI !!!

Meo 1 lez. 37Meo 1 lez. 37


69

Esempi in.../duinf2000/program6 PROBLEMA: calcolare la frequenza di caratteri

alfabetici contenuti in una frase terminante col punto. Alla fine: visualizzare tutte le frequenze !=0

Progetto logico: n.o caratteri alfabeto ingl. =26;n.ocontatori di frequenza=26=n.oelementi vett.

da inizializzare a zero; int freq[26]={0,0,… 0};lettura e calcolo: fintantoche’ il carattere

letto non e’ il punto, aggiungi 1 all’ elemento che indica la frequenza del carattere letto; poi fai la visualizzazione.


70

Progetto logico: continuaCome si puo’ individuare questo elemento? Nel vettore freq[26] si trova tramite l’ indice intero

corrispondente nel codice ASCII al carattere letto, ma: ‘A’=65; … ‘Z’=90; ‘a’=97; … ‘z’= 122 Occorre fare un cambiamento di scala ossia riportare i

valori dei codici ASCII nell’ intervallo 0-25 => per i caratteri minuscoli basta fare: car_letto - ‘a’;

e poi incrementare il contatore freq [car_letto- ‘a’]++; invece per i maiusc. occorre prima convertirli a

minus. con: car_letto = car_letto - ‘A’ + ‘a’ (cfr. while1) e incrementare il contatore freq [car_letto-‘a’]++; (come sopra).


71

La visualizzazioneSi puo’ fare con un for dove la var. di controllo

e’ ancora il codice ASCII del carattere:for (char ch = ‘a’; ch<=‘z’; ch++) if (freq(ch- ‘a’) != 0)cout << “\nIl car.”<< ch <<“ha la frequenza:

” << freq[ch- ‘a’];Con questo progetto logicofare il programma monoblocco prima e poi

strutturato a moduli. X DOMANI !!!


72

Non confondere stringhe costanti con tabelle di caratteriLa stringa char *pst= “buonino”; e’ costante. C

e C++ la vedono come una sequenza di caratt. terminanti con \0 . Essa non e’ copiata in pst: a pst e’ assegnato l’ indirizzo del suo primo car. b.

Dovendo leggere o inizializzare una stringa di caratteri qualunque e’ responsabilita’ del programmatore riservarle adeguato spazio in memoria. Una tabella (vettore) di caratteri puo’ servire a questo scopo, ma non e’ l’ unica soluzione.


73

Es. char riga[40];Ogni elemento della tabella riga e’ di tipo char

e quindi disponibile a contenere un carattere. Per assegnare una stringa di caratteri ad una

tabella ci sono varie possibilita’: leggercela da tastiera (e per un es. di cio’ vedere il prg. Leggiora in program6) oppure occorre copiare la stringa carattere per carattere …

Come? Cfr. diapo seguente! Ma intanto: per la lettura di tutti i caratteri blanc compresi, in leggiora si usa la funz. del C++ get(char*,...) collegata al flusso cin ossia cin.get(char*,... ). (In C cio’ si ottiene con la funz. gets() ).


74

Copiare stringhe: oltre il prg. creastatab ecco la proc. strcp

void strcp(char *s, char *t) /* s, t: puntatori a carattere e quindi a stringa; la proc. strcp copia la stringa puntata da t in quella puntata da s */

{ while ((*s=*t) != ‘\0’) /*fintantoche’ il contenuto di t assegnato alla cella puntata da s e’ diverso da ‘\0’ (=fine stringa) fai*/

s++; t++}; // + sintetica ?!{while (*s++=*t++);// perche’ manca !=‘\0’ ??};


75

Come si scrive una procedura?L’ esempio precedente vuole mostrare anche

questo: fissati i parametri formali del sottoprogramma basta scrivere il suo corpo usandoli in modo corretto e coerente col progetto logico fatto.

La procedura strcp potra’ essere attivata da qualunque altro modulo usando come parametri effettivi o puntatori a stringa o nomi di vettori contenenti caratteri (cfr. es.)

Visti gli esempi sostituire in creastatab alla proc. copia la proc. strcp.


76

Esempichar *ps2,*ps1 = “stringa12”;char s1[10], str[10]=“abcdefghi”;strcp(str,ps1);//si puo’ strcp(ps2, s1)? Meglio NOstrcp(s1,str); // strcp(ps1,s1) puo’ dare errore;Ricordare il significato del nome di un vettore(!)

(sinonimo dell’ indirizzo) e che le array sono sempre trasmesse tra moduli per indirizzo come indicato nel programma tabel. Nel programma statisti invece si usano vettori nel main e in 2 o 3 procedure: renderlo tutto modulare!


77

Array a 2 dimensioniil nome della matrice e’ sinonimo dell’ indirizzo

del primo elemento della matrice di indici [0][0] che e’ anche l’ indirizzo del vettore prima riga;

l’ elemento i-esimo della prima riga e’ trovato dal compilatore sommando a questo indirizzo la lunghezza di un elemento moltiplicata per i-1 ;

la matrice e’ memorizzata per righe, una riga di seguito all’ altra: l’ indirizzo del primo elemento della seconda riga = indirizzo primo elemento della prima riga + n.o colonne* lungh.elementi

Meo 2 lez. 2Meo 2 lez. 2


78

Esempi di definizione di array o tabelle a + dimensioni in C+

int a[5] array monodimensionale o vettore di 5 componenti intere memorizzabili in:

a[0], ... a[4]. Necessario 1 indicefloat f[2][3] array bidimensionale o matrice

di 2 righe e 3 colonne memorizzabili in:f[0][0], f[0][1], f[0][2], (tipo base=float)f[1][0], f[1][1], f[1][2]. Necessari 2 indici: es.for (int i=0; i<2; i++) for (int j=0; j<3; j++) f[i][j]=0.0;


79

I nomi delle matrici sono indirizzi di riferimento e si possono

considerare come puntatori a "vettori di puntatori” alle varie righe.

Ecco perche’ il contenuto di un elemento si puo’ ottenere tramite una doppia operazione di indirezione fatta sull’ indirizzo ad esso relativo.

Per esempio, se float mat[N][M] e’ una matrice, *mat contiene l’ indirizzo alla prima riga di mat mentre **mat contiene il valore del suo primo elemento. Inoltre….


80

Le matrici sono memorizzate per righe

con l’ indirizzo iniziale di una matrice (il suo

nome) che identifica anche l’ indirizzo del primo puntatore del vettore righe ossia il puntatore alla sua prima riga; in questa visione esterna delle matrici l’ indirizzo iniziale+1 (+una riga) identifica il puntatore alla seconda riga e cosi’ di seguito come appare dall’ es. tabmat1.C

Se MAT = FFE2 allora *MAT = FFE2 **MAT = valore del primo elemento.


81

Come si trovano gli elementi?Dentro la matrice mat[N][M] l’ elemento Mesimo

della prima riga e’ trovato dal compilatore sommando all’indirizzo della sua prima riga la lunghezza di un elemento moltiplicata per (M-1);=> dato che l’indirizzo alla prima riga di mat e’ *mat se si assume 1 come lunghezza di un elemento allora: *(mat +1) e’ l’indirizzo del secondo el. della prima riga di mat, *(mat +2) del terzo e cosi’ di seguito fino a *(mat +M) che e’ l’indirizzo della seconda riga di mat, *(mat +2*M) che e’ l’indirizzo della terza riga di mat e cosi’ via.


82

Aritmetica dei puntatoriLa diapo precedente introduce all’ aritmetica dei

puntatori. Se char *p e’ un puntatore a una stringa di caratteri, *(p+1) punta al secondo carattere della stringa ossia al byte seguente il primo. Nel caso di float mat[N][M] matrice di N righe ed M colonne, internamente alla matrice *(mat +1) e’ l’indirizzo del secondo elemento della prima riga ossia punta all’ elemento successivo al primo (scostato da esso di almeno 4byte), ma esternamente alla matrice *(mat +1) e’ l’indirizzo della seconda riga .

Quindi: il riferimento e’ all’ elemento-tipo non al byte!

Meo 1 lez.38Meo 1 lez.38


83

Precisazioni ed eserciziQuando si usa un array a 2 dimensioni in un

modulo deve essere specificato il numero delle colonne dell’ array (necessario perche’ il compilatore possa calcolare gli indirizzi di inizio delle varie righe), mentre il numero delle righe e’ ininfluente e puo’ essere omesso.

Esempi nei prg. mat, tabmat, … in... duinf2000/ program7. Provare a fare procedure per: eseguire il prodotto, la somma di matrici, data una matrice costruirne la trasposta …e completare il tema in diapo 3-4.

Fondamenti di informatica 1 parte 4 D.U.1 fondamenti di informatica parte 4 appunti per il D.U. in...

Documents

Transcript of Fondamenti di informatica 1 parte 4 D.U.1 fondamenti di informatica parte 4 appunti per il D.U. in...