fondamenti di informatica
parte 4
appunti per il D.U. in Ingegneria
Informatica, di Telecomunicazioni
e di Meccanica, a.a.1999-2000
di
anna maria carminelli gregori
fondamenti di informatica 1 parte
4 D.U.
1
<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
fondamenti di informatica 1 parte
4 D.U.
2
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 logicomatematico 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 difondamenti
algebra
ci introducono
anche:
di informatica
1 parte
4 D.U.
3
...
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’ la seguente:
fondamenti di informatica 1 parte
4 D.U.
4
and => e inoltre
if (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: ...
fondamenti di informatica
1 parte
4 D.U.
5
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 True=vero e
False=falso rappresentati da 0 per False e 1
per True.
fondamenti di informatica 1 parte
4 D.U.
6
Il significato
degli operatori logici del C e C++ e’ il
seguente:
Negazione not
! => opposto di
Prodotto logico and && => e inoltre
Somma logica or
|| => oppure
Le costanti logiche True=Vero=1 e
False=Falso=0 (che puo’ assumere ogni
variabile e/o espressione logica) sono
tipiche dell’ algebra
di
Boole.
fondamenti di informatica 1 parte
4 D.U.
7
Algebra di Boole
L’ 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.
fondamenti di informatica 1 parte
4 D.U.
8
True e False
sono le 2 uniche costanti logiche dell’ algebra
di Boole con valori: False = 0 True =1
Le 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 1 o 0.
Sulle 2 entita’ 1 e 0 si possono introdurre le 3
operazioni basilari
dell’ algebra di Boole.
fondamenti di informatica 1 parte
4 D.U.
9
Operazioni di base dell’
algebra sono:
il prodotto logico,
la somma logica,
la complementazione o negazione.
La definizione di ogni operazione avviene
tramite una tabellina: in quelle del prodotto e
della somma compaiono 2 variabili
indipendenti ed 1 variabile dipendente che
contiene il risultato; in quella della negazione
la variabile indipendente e’ solo una.
fondamenti di informatica 1 parte
4 D.U.
10
Tabelline di Prodotto e
Somma
X
0
1
0
1
Y
0
0
1
1
XY
0
0
0
1
con X e Y var. indipend. e X Y var. dipend.
X
0
1
0
1
Y
0
0
1
1
X+Y con X e Y var. indipend. e X+Y var. dipend.
0
1
ARITMETICA ELEMENTARE, MA PARTICOLARE
1
perche’ 1 e’ il tetto oltre il quale non si va !!!
1
fondamenti di informatica 1 parte
4 D.U.
11
Tabellina di negazione e …
funzioni elementari !
A
0
1
not (A)=Ā
1
0
con A var. indipend. e not(A) var. dipend.
not (A) e’ indicata anche con A barrato
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.
fondamenti di informatica 1 parte
4 D.U.
12
Significato logico delle
operazioni booleane (esempi)
 Operazione logica congiunzione = and = ‘e inoltre’
 Piove Ho soldi Prendo taxi
 X
Y
XY
 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
fondamenti di informatica 1 parte
4 D.U.
13
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
fondamenti
di informatica
1 parte che sia b=c=true
4 D.U.
14
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.
fondamenti di informatica 1 parte
4 D.U.
15
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 // potrebbe anche essere >1 ?
#define False 0
Le variabili logiche sono intere e si puo’ usarle
normalmente: ES. int ripeti = True; cfr. ripeleg
Stabilito che True = 1 si capisce il significato
del ciclo infinito while(1) ed anche alcune
condizioni cosi’ poste: if (ch=getchar()) fai(bip);
…. O NO ? Se NO cfr. in program6 Tasto.cpp16
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, switch4
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.)
fondamenti di informatica 1 parte
4 D.U.
17
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;
fondamenti di informatica 1 parte
4 D.U.
18
Significato delle variabili
automatiche e statiche
Meo 1 lez.33
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.
fondamenti di informatica 1 parte
4 D.U.
19
Static => protezione
Tutte 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.
Una var. globale (o esterna) static e’ visibile
e usabile all’ interno delle funzioni definite nello
stesso file sorgente in cui essa e’ definita, ma
diventa invisibile
ad altri file, a sua protezione
fondamenti di informatica 1 parte
4 D.U.
20
Conclusione per menu()
Per salvare il valore di n letto solo la prima volta
bisogna dichiarare n non solo int ma anche
static e quindi scrivere menu 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 0
if (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 */
fondamenti di informatica 1 parte
return n; }
4 D.U.
21
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 solo le Proprieta’ delle operazioni
logiche. In primis: l’ operatore + si dice duale
dell’ operatore . l’ elemento 0 duale dell’
elemento 1 e vale la seguente legge di dualita’:
da qq. identita’ booleana se ne puo’ trarre un’
altra per dualita’ sostituendo a ogni operatore e
agli elementi 0 e 1 i rispettivi duali.
fondamenti di informatica 1 parte
4 D.U.
22
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
fondamenti di informatica 1 parte
4 D.U.
23
Proprieta’ delle operazioni
dell’ Algebra di Boole
3)

4)

5)

doppia negazione:
not (not A) = A
distributiva del prodotto:
A (B+C) = AB + AC
distributiva della somma:
A+(BC) = (A+B)(A+C) (piove o (fa freddo e inoltre
c’e’ vento) = (piove o fa freddo) e inoltre (piove o c’e’ vento))
6) assorbimento
 AA = A
A+A = A
7) proprieta’ del complemento: A+Ā =1
fondamenti di informatica 1 parte
4 D.U.
24
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.
25
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’
fondamenti di informatica 1 parte
4 D.U.
26
Tabelle di verita’ delle
Operazioni fondamentali
Meo 1 lez.9 e
seg.
che sono: not

or

and

xor
or esclusivo

nand
and negato

nor
or negato
Per le tabelle ed i corrispondenti circuiti
elementari (detti porte logiche) vedere il
lucido tratto dal
Bishop ed esteso.
fondamenti di informatica 1 parte
4 D.U.
27
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.
fondamenti di informatica 1 parte
4 D.U.
28
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.
fondamenti di informatica 1 parte
4 D.U.
29
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
fondamenti di informatica 1 parte
4 D.U.
30
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 fondamenti
inoltre
E sono vere.
di informatica 1 parte
4 D.U.
31
L’ espressione booleana di f
e’ quindi: f(A,E) = AĒ + AE
Questo 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 valore VERO e’ costruito dall'
analisi di tutti i possibili valori attribuibili alle
variabili che si evidenziano bene nella tabella
della verita’...)
fondamenti di informatica 1 parte
4 D.U.
32
Semplificazione
L’ espressione ottenuta puo’ poi essere
tradotta in un circuito logico equivalente:
prima pero’ 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.
fondamenti di informatica 1 parte
4 D.U.
33
Esempio:
A
E
U
f
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
0
1
0
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.
fondamenti di informatica 1 parte
4 D.U.
34
Semplificazione
L' espressione booleana corrispondente e’:
f= ĀĒŪ + ĀĒU + AĒU + AEU
1a espressione da
semplificare
1o 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
fondamenti di informatica 1 parte
4 D.U.
35
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).
fondamenti di informatica 1 parte
4 D.U.
36
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);
fondamenti di informatica 1 parte
4 D.U.
37
o …
La semplificazione si ottiene
anche usando la proprieta’ di assorbimento:
A+A = A;
AA = A
o 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.
fondamenti
di informatica 1 parte
4 D.U.
38
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.
fondamenti di informatica 1 parte
4 D.U.
39
Decodificatori
Per 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.
fondamenti di informatica 1 parte
4 D.U.
40
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_
fondamenti di informatica 1 parte
4 D.U.
41
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.
fondamenti di informatica 1 parte
4 D.U.
42
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
0
Dalla prima riga della tabella si deduce: USC.0 = ĀĒ
quindi il DECODIFICATORE prima visto come una
scatola nera contiene al suo interno circuiti formati da
porte anche NOR: in una di queste entrano i segnali A
di informatica 1 parte
ed E (teorema di de fondamenti
Morgan).
4 D.U.
43
Sintesi di circuiti
Si 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
fondamenti di informatica 1 parte
logiche)
4 D.U.
44
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.
fondamenti di informatica 1 parte
4 D.U.
45
Flip-Flop Set-Reset = FF_SR
Circuito 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...
E’ detto anche multivibratore bistabile …
Domanda: che tipo di circuito e’ ?
fondamenti di informatica 1 parte
4 D.U.
46
Q= STATO del SISTEMA
circuito: 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
fondamenti di informatica 1 parte
4 D.U.
47
FF_SR: 8 situazioni possibili
= 4 input X 2 stati





X
0
1
0
1
Y NOR(X+Y)
0
1
0
0
1
0
1
0
S R Q_ora Q_poi
0
0
0
0
0
1
0 S=R=0 no modifiche
1 Q_poi=Q_ora
1
1
0
0
0
1
1 S=1 forza Q_poi a 1
1
 0
 0
1
1
0
1
0 R=1 forza Q_poi a 0
0





 1 1
0
0 o 1 Ambiguita’ da
 1 1
1
0 o 1 togliere con
modifiche nella struttura (FF tipo D o48JK)
La Dipendenza dal tempo
deve 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.
fondamenti di informatica 1 parte
4 D.U.
49
Memorie
I 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.
fondamenti di informatica 1 parte
4 D.U.
50
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

+ usate
Legenda: il simbolo

 significa dell’ ordine di
chip o …
“centopiedi”
fondamenti
di informatica 1
4 D.U.
parte
51
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 “ “
.
+volte
1) ROM, 2) PROM, 3) EPROM
fondamenti di informatica 1 parte
4 D.U.
52
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 ?
fondamenti di informatica 1 parte
4 D.U.
53
Array
E’ un tipo di variabile composta, strutturata
Importante 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
54
dichiarata al compilatore la sua dimensione.
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 indice
float 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
int c[3][3][3] array tridimensionale di tipo intero
(3 matrici di 3 righe e 3 col.: necess. 3 indici).
fondamenti di informatica 1 parte
4 D.U.
55
Meo 2 lez.2
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;
fondamenti di informatica 1 parte
4 D.U.
56
Creazione-stampa di vettori
Il 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 cop (non inizializzato) viene
letto con la procedura leggi che fa la lettura
degli elementi di un vettore uno dopo l’ altro; la
sua copia e’ realizzata nella procedura copia, la
visualizzazione nelle procedure scrivi e riscrivi;
in tutti i sottoprogrammi il passaggio di vettori
(e array in generale)
e’ fatto
per indirizzo.
fondamenti di informatica
1 parte
4 D.U.
57
Il nome del vettore e’
Meo 1 lez. 37
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
fondamenti di informatica 1 parte
SI !!!
4 D.U.
58
Altri esempi: statisti, tabel...
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
1 parte
visualizzazione. fondamenti di4informatica
D.U.
59
Progetto logico: continua
Come si individua 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’]++;
fondamenti di informatica 1 parte
(come sopra).
4 D.U.
60
La visualizzazione
Si 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 logico
fare il programma monoblocco prima e poi
strutturato a moduli.
X DOMANI !!!
fondamenti di informatica 1 parte
4 D.U.
61
Non confondere stringhe
costanti con tabelle di caratteri
La stringa char *pst= “buonino”; e’ costante. ll
C 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
fondamenti di informatica 1 parte
soluzione.
4 D.U.
62
Es. char riga[40];
Ogni elemento della tabella riga e’ di tipo char
e quindi disponibile a contenere un 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?
fondamenti di informatica 1 parte
4 D.U.
63
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’
??
fondamenti di informatica 1 parte
4 D.U.
64
};
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.
fondamenti
di informatica 1 parte
4 D.U.
65
Esempi
char *ps2,*ps1 = “stringa12”;
char s1[10], str[10]=“abcdefghi”;
strcp(ps2,ps1); // oppure strcp(ps2, str);
strcp(s1,str); // oppure strcp(s1,ps1);
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 fondamenti
procedure:
renderlo tutto
di informatica 1 parte
4 D.U.
66
modulare!
Meo 2 lez. 2
Array a 2 dimensioni
il 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 ;
la matrice e’ memorizzata per righe, una riga di
seguito all’ altra: l’ indirizzo del primo elemento
della seconda riga = indirizzo primo elemento
1 parte
della prima riga fondamenti
+ n.odi4informatica
colonne*
lungh.elementi
D.U.
67
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 indice
float 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++)
fondamenti di informatica 1 parte
4 D.U.
68
 for (int j=0; j<3; j++)
f[i][j]=0.0;
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
ottiene 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 *(mat+M)
contiene l’ indirizzo
alla
sua
seconda
riga.
fondamenti di informatica 1 parte
4 D.U.
69
Perche’ mat+M ?
Data la matrice mat[N][M] l’ elemento i-esimo
della prima riga e’ trovato dal compilatore
sommando all’indirizzo della sua prima riga la
lunghezza di un elemento moltiplicata per (i1);=> dato che l’indirizzo alla prima riga di mat
e’ *mat se si assume 1 come lunghezza di un
elemento allora *(mat +M) e’ l’indirizzo della
seconda riga di mat, *(mat +2*M) e’ l’indirizzo
della terza riga di mat e cosi’ via.
NOTA: *(mat +1) e’ l’indirizzo del secondo el. della
prima riga di mat, *(mat +2) del terzo e cosi’ via!
fondamenti di informatica 1 parte
4 D.U.
70
Aritmetica dei puntatori
Meo 1 lez.38
La NOTA 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.
Invece nel caso di float mat[N][M] matrice di
N righe ed M colonne, *(mat +1) e’ l’indirizzo
del secondo elemento della prima riga ossia
punta all’ elemento successivo al primo che
pero’ e’ scostato di almeno 4byte dal primo
elemento.
Quindi: il riferimento
e’ all’
elemento-tipo
non al byte!
fondamenti
di informatica
1 parte
4 D.U.
71
Precisazioni ed esercizi
Quando 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 program7.
Provare a fare procedure per: eseguire il
prodotto, la somma di matrici, data una matrice
costruirne la trasposta
...
fondamenti di informatica 1 parte
4 D.U.
72