Esercizi di Ingegneria del Software II 0 Esercizi su Diagrammi di Flusso dei Dati Esercizio n



Scaricare 430.28 Kb.
17.11.2017
Dimensione del file430.28 Kb.

Esercizi di

Ingegneria del Software II

0 Esercizi su Diagrammi di Flusso dei Dati
Esercizio n. 1

Si scriva usando dei DFD la specifica di un sistema per il prelievo automatizzato di denaro contante (Bancomat) che possieda le seguenti caratteristiche:

Per poter utilizzare il sistema l'utente deve inserire una tessera magnetica e successivamente digitare il codice segreto e l'ammontare del prelievo desiderato in banconote da 50.000.

La tessera magnetica contiene i seguenti dati:

1) Il numero di conto corrente dell'utente

2) Il codice segreto

3) L'ammontare del prelievo massimo (Lit. 500.000)

4) La data dell'ultimo prelievo effettuato

5) L'ammontare dei prelievi gia' effettuati dall'utente il giorno stesso.

Il sistema deve verificare che il codice segreto digitato corrisponda a quello registrato sulla tessera, che l'ammontare del prelievo richiesto non sia tale da far superare il prelievo massimo consentito.

Qualora l'utente non digiti il codice corretto, il sistema gli permettera' di ridigitare il codice segreto. Qualora anche il secondo tentativo dovesse fallire il sistema deve trattenere la tessera ed azionare un opportuno allarme.
Per semplicita' si ipotizzi che il sistema abbia una disponibilita' di banconote infinita.
Soluzione:

Dove: Dati_in::={Tessera,Codice, Richiesta_prelievo}

Dati_out::={Messaggi}


Esplodendo la funzione BM:

Esplodendo Ripeti_codice:


Esplodendo la funzione Aggiorna_Tessera:




0 Esercizi su reti di Petri
Esercizio n. 1

Si modelli tramite una rete di Petri (anche con archi inibitori) il seguente frammento di codice (sequenziale) C-like


S1;

S2;

if (Cond1)

S3;

else {

S4;

while (Cond2)

do

S5

while (Cond3);

}
S6;
Soluzione:

Si ottiene per composizione delle reti che seguono:


Esercizio n. 2

Si definisca il meccanismo generale (detto interlock), ossia la sottorete che aggiunta ad una rete P/T permetta di stabilire un ordinamento negli scatti tra due transizioni t ed u, in modo tale che u possa scattare solo dopo che è scattata t.


Soluzione:

Le due transizioni vengono sequenzializzate.
Esercizio n. 3

Si modelli il seguente protocollo, di tipo stop and wait, con una rete di Petri. Una stazione trasmittente genera ed invia messaggi a una stazione ricevente tramite un canale di comunicazione. Una volta inviato un messaggio, la stazione trasmittente attende di ricevere dalla stazione ricevente un messaggio che indichi che il messaggio che aveva inviato è effettivamente giunto a destinazione. La stazione trasmittente passa poi alla generazione del prossimo messaggio. La stazione ricevente accetta messaggi uno alla volta provenienti dalla stazione trasmittente e le invia ogni volta un messaggio di corretta ricezione. Passa poi ad elaborare il contenuto del messaggio ricevuto e si pone in attesa del prossimo messaggio dalla stazione trasmittente.


Soluzione:


t1, generazione

t2, invio

t3, ricezione

t4, elaborazione

t6, invio ack
p1,p2 modellano la stazione trasmittente

p3, p4 modellano la stazione trasmittente

p5 il canale ricevente il messaggio

p6 il canale su cui viaggia il messaggio di ack


Esercizio n. 4

Si modifichi l'esempio di produttori/consumatori rappresentato in figura:



imponendo che tutti gli archi abbiano peso unitario e i posti capacita` unitaria, che la marcatura iniziale si componga di un token nel posto p1 e di un token nel posto p3 (tutti gli altri posti non sono marcati) e che il posto p5 sia sostituito da un'opportuna sottorete che modelli un canale di comunicazione tramite un buffer dato da una coda FIFO con 3 posizioni.

Indicare che tipo di rete si ottiene.
Soluzione:


E` una rete condizioni/eventi.

La transizione t2 scatta solo se il posto p51 e` vuoto, la transizione s1 scatta solo se p52 e` vuoto, s2 scatta se solo se p53 e` vuoto (si e` omesso di indicare gli archi inibitori).


Esercizio n. 5

Costruire la rete di Petri con archi di peso unitario equivalente alla seguente rete:




Soluzione:

t e` abilitata solo dopo che sono scattate t1, t2 e t3.

p1, p2 e p3 posti a capacita` unitaria.


Esercizio n. 6

Specificare mediante una rete di Petri un sistema di controllo semaforico sito all’incrocio tra due strade P e S. Il semaforo è inizialmente verde per coloro che provengono dalla strada P (e di conseguenza rosso per coloro che provengono dalla strada S). Quando una macchina proveniente dalla strada S arriva in prossimita` dell’incrocio viene rilevata da un apposito sensore e il semaforo diventa verde per chi proviene da S (e rosso per chi proviene da P). Il semaforo rimane verde fino a che un secondo sensore rileva una macchina proveniente dalla strada P che arriva in prossimita` dell’incrocio. A questo punto il semaforo ritorna allo stato iniziale.


Si suppone nullo il tempo di attraversamento dell’incrocio da parte delle autovetture.
Soluzione:



Esercizio n. 7

Si specifichi mediante una rete di Petri un sistema di controllo di un passaggio a livello composto da due sensori (S_in e S_out), una coppia di sbarre ed una coppia di luci intermittenti avente le seguenti caratteristiche:

- il passaggio di un treno in corrispondenza del sensore S_in provoca l’accensione delle luci lampeggianti e successivamente l’abbassamento delle sbarre;

- il passaggio del treno in corrispondenza del sensore S_out provoca lo spegnimento delle luci e l’innalzamento delle sbarre;

Si preveda infine la possibilità che venga azionato un segnale di emergenza E il cui effetto è quello di togliere la tensione al tratto di ferrovia controllato dal sistema.

Per semplicità si ipotizzi che il tempo che intercorre tra il passaggio di due treni sia maggiore del tempo necessario ad ogni treno per attraversare completamente il passaggio a livello.


Soluzione:


Esercizio n. 8

La seguente rete di Petri rappresenta un sistema con tre produttori (posti p1 e p2) e due consumatori (posti p3, p4) che scrivono e leggono da un buffer (p5) di capacita` limitata.



a) Indicare qual e` la rappresentazione matriciale di questa rete (compresa la matrice di incidenza della rete).

b) Per questa rete e` possibile stabilire l'abilitazione di una transizione sulla base delle informazioni contenute nella matrice di incidenza? (motivare la risposta)

c) Indicare quali sono le transizioni abilitate nella marcatura indicata.


Soluzione: a)

b) In questo caso e` possibile decidere correttamente sull'abilitazione di una transizione sulla base delle informazioni contenute nella sola C perche` la rete e` una rete pura (nessun posto e` sia di ingresso che di uscita per alcuna transizione).

c) Le transizioni abilitate nella marcatura m sono t2 e t3, poiche` m e` maggiore della seconda e terza colonna della matrice I, ma minore delle altre colonne di I.

Esercizio n. 9

Data la seguente rete di Petri (dove le transizioni sono indicate da rettangoli e i posti da cerchi):




a) Indicare qual e` la rappresentazione matriciale di questa rete (compresa la matrice di incidenza della rete).

b) Indicare se la sequenza:

t1 t2 t5 t6 t2

e` abilitata e se si` qual e` la marcatura raggiunta dopo lo scatto di tale sequenza.

c) Indicare se la rete puo` andare in deadlock.
Soluzione:

a)

| 1 |



| 1 |

m= | 0 |


| 0 |

| 0 |
| 1 0 0 0 0 0 |

| 0 1 0 0 0 0 |

I= | 0 0 1 1 1 1 |

| 0 0 0 1 0 0 |

| 0 0 0 0 0 1 |


| 0 0 0 1 0 0 |

| 0 0 0 0 0 1 |

O= | 1 1 0 0 0 0 |

| 0 0 1 0 0 0 |

| 0 0 0 0 1 0 |
| -1 0 0 1 0 0 |

| 0 -1 0 0 0 1 |

O-I= | 1 1 -1 -1 -1 -1 |

| 0 0 1 -1 0 0 |

| 0 0 0 0 1 -1 |
Dopo t1 t2:
| 0 |

| 0 |


m1= | 2 |

| 0 |


| 0 |
Dopo t5:
| 0 |

| 0 |


m2= | 1 |

| 0 |


| 1 |
Dopo t6:
| 0 |

| 1 |


m3= | 0 |

| 0 |


| 0 |
Dopo t2:
| 0 |

| 0 |


m4= | 1 |

| 0 |


| 0 |
c) La rete puo` andare in deadlock. Ad esempio, se dalla marcatura raggiunta scatta 5 non si ha piu` alcuna transizione abilitata.

0 Esercizi su specifiche algebriche
Esercizio n. 1

Specificare algebricamente il tipo di dato astratto insieme (privo di elementi ripetuti) di elementi del tipo Item.

La specifica del tipo di dato Set deve definisce le seguenti operazioni:

nulset per la creazione di un set vuoto, i

Insert per l'aggiunta di un elemento,

isemptyset per la verifica di insieme vuoto,

delete per la cancellazione,

member per la verifica di presenza di un dato elemento
Soluzione:
type Set [Item]

uses Item, Boolean,

syntax

NULSET : ? Set,

INSERT : Item ? Set ? Set,

ISEMPTYSET : Set ? Boolean,

DELETE : Item ? Set ? Set,

MEMBER : Item ? Set ? Boolean,

semantics

for all s in Set; i, e in Item;

ISEMPTYSET (NULSET) = true,

ISEMPTYSET (INSERT (i, s)) = false,

DELETE (i, NULSET) = NULSET,

DELETE (e, INSERT (i, s)) = if e = i

then s

else INSERT (i, DELETE (e, s)),

MEMBER (i, NULSET) = false,

MEMBER (e, INSERT (i, s)) = if i = e

then true

else MEMBER (e, s),



end Set.
La forma normale, costituita da applicazioni degli operatori nulset e insert, non è unica, dal momento che l'ordine di inserzione degli elementi non è rilevante. Inoltre, poichè nulla impedisce a un cliente di inserire più volte, mediante l'operazione insert, lo stesso elemento, può accadere che in un esemplare del tipo Set un valore sia duplicato.

Il secondo assioma per l'operatore delete assicura però che il tipo di dato si comporti, esternamente, come un set matematico, senza ripetizioni.

Infatti l'espressione member (e, delete (e, s) ) vale false, indipendente-mente dal numero di volte in cui l'elemento e era stato precedentemente inserito durante la costruzione di s.
Esercizio n. 2

Specificare mediante specifiche algebriche il tipo di dato astratto BAG (insieme con elementi ripetuti), caratterizzato dalle seguenti operazioni:



nulBAGper la creazione di un set vuoto, i

nsert per l'aggiunta di un elemento,

isemptyBAG per la verifica di insieme vuoto,

delete per la cancellazione,

member per la verifica di presenza di un dato elemento
Soluzione:

Identica alla precedente, tranne che per l'operazione DELETE:


type Bag [Item]

uses Item, Boolean,

syntax

NULBAG : ? Bag,

INSERT : Item ? Bag ? Bag,

ISEMPTYBAG : Bag ? Boolean,

DELETE : Item ? Bag ? Bag,

MEMBER : Item ? Bag ? Boolean,

semantics

for all s in Bag; i, e in Item;

ISEMPTYBAG (NULBAG) = true,

ISEMPTYBAG (INSERT (i, s)) = false,

DELETE (i, NULBAG) = NULBAG,

DELETE (e, INSERT (i, s)) = if e = i

then DELETE (e, s)

else INSERT (i, DELETE (e, s)),

MEMBER (i, NULBAG) = false,

MEMBER (e, INSERT (i, s)) = if i = e

then true

else MEMBER (e, s),



end Bag.
In questo caso le ripetizioni di un elemento all'interno della forma normale sono visibili esternamente in quanto, secondo questa definizione, member (e, s) darebbe false solo dopo che siano state fatte delle operazioni di delete in numero uguale a quello delle operazioni di insert precedentemente effettuate.

Esercizio n. 3

Specificare mediante specifiche algebriche il tipo di dato astratto BAG (insieme con elementi ripetuti), caratterizzato dalle seguenti operazioni:



- null, crea il bag vuoto;

- is_empty, test se bag vuoto;

- insert(E,B), inserisce l’elemento E nel bag B;

- del_one(E,B), cancella dal bag B la prima occorrenza dell’elemento E, se E appartiene a B, altrimenti lascia B inalterato;

- del_all(E,B), cancella dal bag B tutte le copie dell’elemento E (se esistono);

- size(B), fornisce il numero di elementi contenuti nel bag B;

- howmany(E,B), calcola il numero di elementi uguali a E presenti nel bag B;

- project(B,S), “proietta” il bag B sul set S, eliminando da B tutte le copie ripetute di uno stesso elemento.
Soluzione:
type Bag [Item]

uses Item, Boolean, Int,

syntax

NULL : ? Bag,

ISEMPTY : Bag ? Boolean,

INSERT : Item ? Bag ? Bag,

DEL_ONE : Item ? Bag ? Bag,

DEL_ALL : Item ? Bag ? Bag,

SIZE : Bag ? Int,

HOW_MANY: Item ? Bag ? Int ,

PROJECT: Bag ? Bag,

semantics

for all s in Bag; i, e in Item;

ISEMPTY (NULL ) = true,

ISEMPTY (INSERT (i, s)) = false,

DEL_ONE (i, NULL ) = NULL ,

DEL_ONE (e, INSERT (i, s)) = if e = i then s

else INSERT (i, DELETE (e, s)),

DEL_ALL (i, NULL ) = NULL ,

DEL_ALL (e, INSERT (i, s)) = if e = i then DEL_ALL (e, s)

else INSERT (i, DELETE (e, s)),

SIZE (NULL ) = 0,

SIZE (INSERT (i, s)) = 1 + SIZE(s),

HOW_MANY (i, NULL ) = 0,

HOW_MANY (e, INSERT (i, s)) = if i = e

then 1+HOW_MANY (e, s)

else HOW_MANY (e, s),

PROJECT(NULL ) = NULL,

PROJECT(INSERT (i, s))= if HOW_MANY(i,s)=0

then insert(i,PROJECT(s))

else PROJECT(s)

end Bag.

Esercizio n. 4

Data la specifica algebrica della struttura dati albero binario:



type Bintree [Item]

uses Item, Boolean,

syntax

emptytree: ? Bintree,

make: Bintree ? Item ? Bintree ? Bintree,

isemptytree: Bintree ? Boolean,

left: Bintree ? Bintree,

data: Bintree ? Item,

right: Bintree ? Bintree,

isin: Item ? Bintree ? Boolean,

semantics

for all l, r in Bintree; d, e in Item;

Isemptytree (emptytree) = true,



isemptytree (make (l, d, r)) = false,

left (emptytree) = emptytree,



left (make (l, d, r)) = l,

data (emptytree) = error,

data (make (l, d, r)) = d,

right (emptytree) = emptytree,



right (make (l, d, r)) = r,

isin (e, emptytree) = false,

isin (e, make (l, d, r)) = if d = e

then true



else isin (e, l) or isin (e, r),

end Bintree.

indicare la specifica formale dell'operazione di visita in ordine simmetrico, definendo un operatore inord da aggiungere a quelli del tipo di dato Bintree, che a partire da un albero produce una coda in cui gli elementi dell'albero sono inseriti nello stesso ordine in cui verrebbero toccati da tale visita.

Soluzione:

La specifica e` costituita da una parte sintattica, che dichiara il tipo dell'operatore inord, e una parte semantica, costituita da due assiomi:



syntax

INORD: Bintree ? Queue,

semantics

inord (emptytree) = newq,



inord (make (l, d, r)) = appendq (addq (inord (l), d), inord (r) )
Inserendo queste clausole nella specifica di Bintree occorre aggiungere, nell'elenco dei tipi citati nella parte uses, anche il nome del tipo Queue[Item] (vedi testo o fotocopie dei lucidi).

Esercizio n. 5

Specificare algebricamente il tipo di dati astratto albero binario di ricerca nel quale l'operatore di INSERT inserisce elementi minori o uguali alla radice nel sottoalbero sinistro ed elementi maggiori della radice nel sottoalbero destro.

Sia dato un operatore relazionale:

>: Item ? Item ? Boolean

per confrontare gli elementi.

L'uso del solo operatore INSERTpermette di ottenere alberi ordinati, a patto di non usare make (si veda esercizio 4) nella costruzione di un albero a partire dall'albero vuoto (make è un'operatore nascosto , cioè non a disposizione del cliente e viene asteriscato nella specifica).

Il tipo Bstree possiede due ulteriori operatori,cancel e max. MAX restituisce il massimo valore memorizzzato nell'albero. cancel permette di eliminare un elemento (non ha alcun effetto se l'elemento non è presente). La cancellazione deve preservare l'ordinamento dell'albero: cancellando l'elemento nella radice, se il sottoalbero sinistro è vuoto si restituisce il sottoalbero destro, se quello destro è vuoto si restituisce il sottoalbero sinistro, altrimenti si restituisce un albero con il massimo tra gli elementi del vecchio sottoalbero sinistro nella radice, con il vecchio sottoalbero sinistro privato del suo massimo elemento come nuovo sottoalbero sinistro, e con il sottoalbero destro uguale a quello vecchio.

Soluzione:

type Bstree [Item]

uses Item, Boolean,

syntax

emptytree: ? Bstree,

* make: Bstree ? Item ? Bstree ? Bstree,

isemptytree: Bstree ? Boolean,

left: Bstree ? Bstree,

data: Bstree ? Item,

right: Bstree ? Bstree,

isin: Item ? Bstree ? Boolean,

add: Item ? Bstree ? Bstree,

max: Bstree ? Item,

cancel : Item ? Bstree ? Bstree,

semantics



for all l, r in Bstree; d, e in Item;

Isemptytree (emptytree) = true,



isemptytree (make (l, d, r)) = false,

left (emptytree) = emptytree,



left (make (l, d, r)) = l,

data (emptytree) = error,

data (make (l, d, r)) = d,

right (emptytree) = emptytree,



right (make (l, d, r)) = r,

isin (e, emptytree) = false,

isin (e, make (l, d, r)) = if d = e

then true



else if d > e

then isin (e, l)

else ISIN (e, r),

ADD (e, emptytree) = make (emptytree, e, emptytree),

ADD (e, make (l, d, r)) = if d = e

then make (l, d, r)

else if d > e

then make (ADD (e, l), d, r)

else make (l, d, add (e, r) ),

MAX (emptytree) = error,

max (make (l, d, r)) = if isemptytree (r)

then d

else max (r),

cancel (e, emptytree) = emptytree,



cancel (e, make (l, d, r)) =

if d = e

then if isemptytree (l)

then r

else if isemptytree (r)

then l

else make (cancel (max (l), l), MAX (l), r)

else if d > e

then make (cancel (e, l), d, r)

else make (l, d, cancel (e, r) ),



end Bstree.

La definizione di isin è stata modificata tenendo conto dell'ordinamento dell'albero: quando l'elemento ricercato non coincide con quello nella radice, esso può appartenere al sottoalbero destro o sinistro solo se ne è rispettivamente maggiore o minore.


Esercizio n. 6

Si dia una specifica algebrica del tipo di dato astratto CODA_CON_PRIORITA' che abbia le seguenti operazioni:

- Create: ? CODA_PR

restituisce una coda (con priorità) vuota;

- Add(C,Elem,Pr): CODA_PRIOR ??ELEM ??Int ??CODA_PRIOR

restituisce una coda ottenuta aggiungendo a C l'elemento Elem con priorità Pr;

- First(C, Pr): CODA_PRIOR ?? Int ? ELEM

restituisce il primo elemento in coda avente priorità Pr (l'ultimo a essere stato inserito temporalmente, quindi in realta` funziona come uno stack);

- Tail(C, Pr): CODA_PRIOR ?? Int ? CODA_PRIOR

restituisce la coda C privata del primo elemento con priorità Pr.

- Occ(C, Pr): CODA_PRIOR ?? Int ? Int

restituisce il numero di elementi in C aventi priorità Pr.

- Delete(C, Pr): CODA_PRIOR ?? Int ? CODA_PRIOR

elimina da C tutti gli elementi di priorità Pr.


Soluzione:

type Pqueue [Item]

uses Item, Boolean, Int,

syntax

CREATE : ? Pqueue,

ADD : Pqueue??Item ? Int ? Pqueue,

FIRST: Pqueue? Int ? Pqueue,

TAIL: Pqueue? Int ? Pqueue,

DELETE : Pqueue? Int ? Pqueue,

OCC: Pqueue? Int ? Int ,

semantics

for all s in Pqueue; e in Item; i, i1 in Int;

FIRST (CREATE, i) = e,

FIRST (add(e,i,s), i1) = if i = i1

then e,

else FIRST (s, i1),

TAIL(CREATE) = CREATE,

TAIL (add(e,i,s) ) = s,

DELETE (CREATE, i) = CREATE,

DELETE (add(e,i,s), i1) = if i = i1

then DELETE(s,i1)

else ADD(e,i, DELETE (s,i1)),

OCC(CREATE,i) = 0,

OCC(add(e,i,s), i1) = if i = i1

then 1+OCC(s, i1)

else OCC(s, i1)

end Pqueue.
Esercizio n. 7

Modificare la specifica algebrica dell'esercizio 6, in modo che la struttura dati sia effettivamente una coda.


Esercizio n. 8

Si dia una specifica algebrica del tipo di dato astratto LISTA_DI_STACK (di interi) che abbia le seguenti operazioni:



- CreateL(N): Int ? LISTA_DI_STACK

restituisce una lista di N STACK vuoti;



- PushL(N, Elem,LS): Int ?? Int ? LISTA_DI_STACK ? LISTA_DI_STACK

restituisce una lista di stack ottenuta eseguendo una push di Elem nel n-esimo stack;



- PopL(N, LS): Int ? LISTA_DI_STACK ??LISTA_DI_STACK

restituisce una lista di stack ottenuta eseguendo una pop nel n-esimo stack;



- TopL(N, LS): Int ? LISTA_DI_STACK ??Int

restituisce l’elemento in cima al n-esimo stack.



- AddTop(LS): LISTA_DI_STACK ? Int

restituisce la somma degli elementi in cima ai singoli stack.


Si faccia uso del tipo STACK specificato a pag. 243 del libro di testo (Ghezzi et al.) o reperibile nelle fotocopie dei lucidi.
0 Esercizi su specifiche logiche e TRIO
Esercizio n. 1

Si specifichi mediante TRIO un antifurto per automobili radiocomandato avente le seguenti caratteristiche:

L’antifurto viene attivato/disattivato attraverso un segnale radio e l’uso di una chiave.

Per attivare l’antifurto è necessario rimuovere la chiave dall’apposita toppa e inviare il segnale radio.

Per disattivare l’antifurto è necessario inviare il segnale radio e inserire la chiave. Qualora il tempo intercorso tra queste due azioni sia superiore a 20 secondi l’antifurto aziona una sirena.

La sirena continuerà a suonare sino a che non viene inserita la chiave e comunque non oltre 3 minuti.


Soluzione:

Unita` di tempo: secondi

Alfabeto: chiave (vero se inserita), segnale (vero se inviato),

antifurto (vero se attivato), sirena (vero se azionata)

Per attivare l’antifurto è necessario rimuovere la chiave dall’apposita toppa e inviare il segnale radio.

?chiave ? segnale ? Becomes(antifurto)

Per disattivare l’antifurto è necessario inviare il segnale radio e inserire la chiave.



( (segnale ??WithinP(chiave,20)) (chiave ??WithinP(segnale,20)) )

?



Becomes(?antifurto)
Si utilizza WithinP perché Becomes(?antifurto) deve avvenire quando avviene il secondo evento. Attenzione perché se la chiave viene messa e tolta e poi viene lanciato il segnale, l'antifurto viene attivato. Se si vuole che la chiave rimanga inserita affinché parta l'antifurto:

( (segnale ??Et (t<20 ? Lastedei(chiave,t))) (chiave ??WithinP(segnale,20)) )

?



Becomes(?antifurto)
C'è un altro problema: se dopo che è stato attivato l'antifurto si reinserisce la chiave entro 20 secondi dall'ultima attivazione del segnale, la condizione chiave ??WithinP(segnale,20) potrebbe essere verificata anche se non viene dato un altro segnale. Quindi la formula va modificata come segue:

( (segnale ??Et (t<20 ? Lasted(chiave,t))

(chiave ??WithinP(segnale ??antifurto,20)) )

?



Becomes(?antifurto)
Qualora il tempo intercorso tra queste due azioni sia superiore a 20 secondi l’antifurto aziona una sirena:

((segnale ???WithinP(chiave,20) (chiave ???WithinP(segnale,20)))

? antifurto ??sirena
Mettendo il sse e il Becomes anche qua:

(segnale ???WithinP(chiave,20)) (chiave ???WithinP(segnale,20)))

? antifurto ? ?Becomes(sirena)
così si evita che la sirena possa essere attivata anche in altri casi.

La sirena continuerà a suonare sino a che non viene inserita la chiave e comunque non oltre 3 minuti:



Becomes(?sirena) ??chiave ⁄?Lasted(sirena, 180)

Esercizio n. 2

Si scriva la specifica TRIO del seguente sistema:

Un sistema d'allarme è costituito da due sensori S1 e S2 e da una sirena collegati ad una centralina di controllo.

La centralina di controllo attiva la sirena:

1) dopo 30 sec. dal ricevimento di un segnale da S1, a meno che in tale intervallo il sistema non venga disattivato;

2) non appena riceve un segnale da S2.

Una volta attivata la sirena resta in funzione fino a quando il sistema non viene disattivato e comunque per non più di 5 minuti.
Soluzione:

Unita` di tempo: secondi

Alfabeto: segnale1 (vero se ricevuto segnale S1),

segnale2 (vero se ricevuto segnale S2),

disattivazione (vero se sistema disattivato)

attiva_sirena (vero se sirena attivata),

La centralina di controllo attiva la sirena:

1) dopo 30 sec. dal ricevimento di un segnale da S1, a meno che in tale intervallo il sistema non venga disattivato

2) non appena riceve un segnale da S2

( Past(segnale1,30)??(WthinP(disattivazione),30)) ⁄?segnale2 )

?

Becomes(attiva_sirena)

Una volta attivata la sirena resta in funzione fino a quando il sistema non viene disattivato e comunque per non più di 5 minuti:



(disattivazione ⁄?Lasted(attiva_sirena, 300)) ??Becomes(?attiva_sirena)

Esercizio n. 3

Si scriva la specifica TRIO di un sistema di apertura/chiusura di un cancello composto da un ricevitore di segnali radio, una fotocellula ed un motore in grado di far aprire/chiudere il cancello.

Se il cancello è chiuso (o se si sta chiudendo), la ricezione del segnale radio provoca l'inizio dell'apertura del cancello . Una volta completata l'apertura, il cancello resta aperto per un 1 minuto, dopo di che inizia a chiudersi.

La cellula fotolelettrica invia un segnale ogni qualvolta un oggetto passa attraverso il cancello. L'effetto del segnale è il seguente:

Se il cancello è completemante aperto, la chiusura non può avvenire fintanto che il segnale proveniente dalla fotocellula non cessa; se il cancello si sta chiudendo l'effetto è analogo a quello provocato dal segnale radio.
Esercizio n. 4

Si specifichi in TRIO il seguente sistema di registrazione dei punteggi di un incontro di boxe:

Il sistema è composto da 3 coppie di pulsanti (A - B) e da due display di punteggio (D_A, D_B).

- Il sistema viene attivato dal segnale di inizio round e viene disattivato dopo 3 minuti dal segnale di fine round .

- Quando il sistema è attivo, ogni giudice usa una coppia di pulsanti. La pressione del pulsante A (B) indica che il giudice che l’ha premuto vuole assegnare 1 punto all’atleta A (B).

- Qualora almeno 2 giudici premano nello spazio di 1 secondo lo stesso pulsante il sistema assegna 1 punto all’atleta corrispondente.

- I display indicano il punteggio dei due atleti (inizialmente uguale a 0).

0 Esercizi su specifiche in Z
Esercizio n. 1

Si specifichi in Z un sistema di controllo accessi ad un parcheggio avente N posti macchina. L'accesso al parcheggio è consentito unicamente a coloro che sono in possesso di un apposito tesserino e purche' vi siano dei posti liberi nel parcheggio.

Si modellino in particolare le seguenti operazioni:

1) Richiesta di una tessera: Fornendo Nome e Cognome del nuovo utente il sistema provvede ad aggiornare l'elenco degli utenti e rilascia una tessera (modellabile attraverso un naturale) per l'accesso al parcheggio.

2) Ritiro di una tessera: permette di disabilitare una tessera, ossia cancellare il proprietario dall'elenco utenti.

3) Ingresso al parcheggio: permette ad un utente di entrare nel parcheggio facendo uso della tessera purchè vi siano ancora posti liberi.

4) Uscita dal parcheggio: permette di uscire dal parcheggio

Inoltre il sistema deve far si che NON sia possibile entrare due volte consecutive con la stessa tessera senza un'uscita intermedia.


Esercizio n. 2

Una società sportiva possiede 4 campi da tennis che affitta, previa prenotazione, per periodi di un'ora ai soci che ne facciano richiesta. I campi sono disponibili ogni giorno della settimana dalle ore 9.00 alle ore 21.00. Per poter effettuare una prenotazione è necessario fornire il numero di tessera dei giocatori. La prenotazione va a buon fine solo se esiste un campo disponibile per il giorno e l'ora richiesta e nessuno dei due prenotanti ha già superato la sua quota massima di prenotazioni fissata in 3 ore alla settimana.

Per semplicità si ipotizzi che:

1) Ogni campo venga prenotato dando il numero di tessera di solo 2 giocatori

2) Le ore di gioco iniziano all'inizio di ogni ora di orologio, ossia la prima ora prenotabile è quella che va dalle 9.00 alle 10.00 e l'ultima è quella che va dalle 20.00 alle 21.00.

3) Le prenotazioni possano essere effettuate solo per i giorni della settimana corrente, ossia le prenotazioni possano arrivare sino alla Domenica successiva.

Si specifichi in Z un tale sistema di gestione delle prenotazioni dei campi da tennis.

Ingegneria del Software
0 Esercizi su Convalida e Verifica

Esercizio n. 1

Si individi un'insieme di casi di test di dimensione minima secondo il criterio di copertura delle decisioni per la seguente procedura:


procedure DIVIDI (X, Y : INTEGER)

RIS, RESTO : INTEGER

POS_X, POS_Y : BOOL

begin

POS_X := TRUE;

POS_Y := TRUE;

READ(X);

READ(Y);

if X < 0 then

POS_X := FALSE;

X := -X;

end if

if Y < 0 then

POS_Y := FALSE;

Y := -Y;

end if

RIS := 0;

while X ≤ Y loop

X := X - Y;

RIS := RIS - 1;

end loop

if not (POS_X or POS_Y) then RESTO := -X

else RESTO = X

end if

WRITE(RIS);

WRITE(RESTO);

end --DIVIDI
Provare ad eseguire la procedura usando i casi di test individuati e si commentino i risultati.
Soluzione:
1. procedure DIVIDI (X, Y : INTEGER)

2. RIS, RESTO : INTEGER

3. POS_X, POS_Y : BOOL

4. begin

5. POS_X := TRUE;

6. POS_Y := TRUE;

7. READ(X);

8. READ(Y);

9. if X < 0 then

10. POS_X := FALSE;

11. X := -X;

12. end if

13. if Y < 0 then

14. POS_Y := FALSE;

15. Y := -Y;

16. end if

17. RIS := 0;

18. while X <= Y loop

19. X := X - Y;

20. RIS := RIS - 1;

21. end loop

22. if not (POS_X or POS_Y)

23. then RESTO := -X

24. else RESTO = X

25. end if

26. WRITE(RIS);

27. WRITE(RESTO);

28. end --DIVIDI
Il grafo associato risulta:


Per coprire il ramo dal nodo 22 al nodo 24 occorre che la condizione not(POS_X or POS_Y) sia falsa, quindi che X e Y siano entrambi negativi.

Caso 1: X<0

Y<0


|X|>|Y|

Con dati di test che soddisfano queste condizioni si coprono tutti gli archi tranne 9-13 e 13-16, e gli archi 18-19, 19-20, 20-18 (non si esegue il ciclo while) e 22-24, 24-25



Caso 2: X>=0

Y>=0


X<=Y

Eseguendo il ciclo una volta si esce dal while se:

X-Y > Y ovvero X>2Y

E` una condizione che non puo` verificarsi (non puo` essere X<=Ye X>2Y).


Quindi modificihiamo il caso 1, in modo che si percorra il ciclo while almeno una volta:

Caso 1': X<0

Y<0


|X|<=|Y|

Eseguendo il ciclo una volta si esce dal while se:

|X|-|Y| > |Y| ovvero |X|>|2Y|

Il secondo caso diventa:



Caso 2': X>=0

Y>=0


X>Y

(non esegue il ciclo, copre gli archi 9-13, 13-16, 22-24 e 24-25).


I casi 1' e 2' assicurano la copertura di tutti gli archi.

Il test sintetizzato puo` essere:

T::={(X=-1;Y=-2), (X=2; Y=1)}
L'esecuzione in corrispondenza del primo dato di test corrisponde ad un ciclo infinito (non si esce mai dal while), in quanto all'interno del ciclo il valore di X (diventato +1) viene decrementato di una quantita` negativa (-|Y|) e resta pertanto sempre minore di Y (diventato +2).

Esercizio n. 2

Si descriva il risultato di una esecuzione simbolica della seguente procedura indicando i valori dello stato del programma e della path condition dopo ogni istruzione nell'ipotesi di voler eseguire ogni comando del programma (ramo then) ed il ciclo while una volta.


1. function FATT (X: INTEGER):INTEGER

2. RIS: INTEGER;

3. POS_X, PARI_X: BOOL;

4. begin

5. POS_X := TRUE;

6. PARI_X := TRUE;

7. if X < 0 then

8. if X mod 2 <> 0 then

9. POS_X := FALSE;

10. PARI_X := FALSE;

11. end if

12. X := -X;

13. end if

14. RIS := 1;

15. while X > 0 loop

16. RIS := RIS *X;

17. X := X-1;

18. end loop

19. if not POS_X and not PARI_X

20. then RIS := -RIS end if

21. RETURN(RIS);

22. end --FATT


Soluzione:

Ambiente: X=valx, PC=true,

FATT,RIS,POS_X,PARI_X=undef



Esecuzione: istruzioni 5 e 6

Ambiente: X=valx, PC=true,

POS_X=true, PARI_X=true,

FATT,RIS=undef

Esecuzione: test 7: X < 0 ? Risposta utente: yes

Ambiente: X=valx, PC=valx<0,

POS_X=true, PARI_X=true,

FATT,RIS=undef

Esecuzione: test 8: X mod 2 <> 0 ? Risposta utente: yes

Ambiente: X=valx, PC=(valx<0) and (valx mod 2 <> 0),

POS_X=true, PARI_X=true,

FATT,RIS=undef

Esecuzione: istruzioni 9 e 10

Ambiente: X=valx, PC=(valx<0) and (valx mod 2 <> 0),

POS_X=false, PARI_X=false,

FATT,RIS=undef

Esecuzione: istruzioni 11 e 12

Ambiente: X= - valx, PC=(valx<0) and (valx mod 2 <> 0),

POS_X=false, PARI_X=false,

FATT,RIS=undef

Esecuzione: istruzioni 13 e 14

Ambiente: X= - valx, PC=(valx<0) and (valx mod 2 <> 0),

POS_X=false, PARI_X=false,

RIS=1, FATT=undef

Esecuzione: test 15: X > 0 ? vera perche` X=-valx e valx>0

Ambiente: X= - valx, PC=(valx<0) and (valx mod 2 <> 0),

POS_X=false, PARI_X=false,

RIS=1, FATT=undef

Esecuzione: istruzioni 16 e 17

Ambiente: X= - valx - 1, PC=(valx<0) and (valx mod 2 <> 0),

POS_X=false, PARI_X=false,

RIS= - valx, FATT=undef

Esecuzione: test 15: X > 0 ?

- valx - 1 > 0? ovvero |valx|>1?

Risposta utente: no

Ambiente: X= - valx,

PC=(valx<0) and (valx mod 2 <> 0) and (|valx|<=1),

POS_X=false, PARI_X=false,

RIS=1, FATT=undef



Esecuzione: test 20: not POS_X and not PARI_X ?

vera perche` POS_X = false and PARI_X = false



Ambiente: X= - valx,

PC=(valx<0) and (valx mod 2 <> 0) and (|valx|<=1),

POS_X=false, PARI_X=false,

RIS= - 1, FATT=undef



Esecuzione: istruzione 21

Ambiente: X= - valx,

PC=(valx<0) and (valx mod 2 <> 0) and (|valx|<=1),

POS_X=false, PARI_X=false,

RIS= - 1, FATT= - 1


La path condition risulta:

PC=(valx<0) and (valx mod 2 <> 0) and (|valx|<=1)


Un test che soddisfa questa condizione e`, ad esempio:

T = {(X=-1)}



Esercizio n. 3

Si trovi l'espressione regolare D-U associata al seguente programma. Cosa vi suggerisce tale risultato ?


program A

var X, Y, Z: Integer

begin

Read(X);

Read(Y);

if X >Y

then X:=X-1;

else Y:=Y-1;



fi

while X+Y > 0

do

X:= Y-Z

Z:= X+Y


Y:= Y-X

od

if Z > 0

then Z:= X+Y + Z

else Z:= X-Y -Z

fi

end
Soluzione:

Usi e definizioni per le variabili risultano:




program A

X

Y

Z

var X, Y, Z: Integer










begin










Read(X);

d







Read(Y);




d




if X >Y

u

u




then X:=X-1;

ud







else Y:=Y-1;




ud




fi










while X+Y > 0

u

u




do










X:= Y-Z

d

u

u

Z:= X+Y

u

u

d

Y:= Y-X

u

ud




od










if Z > 0







u

then Z:=X+Y+Z

u

u

ud

else Z:= X-Y -Z

u

u

ud

fi










end









L'espressione regolare per X risulta:

du (ud + ?) u ( duuu)* (u + u)

semplificabile in:

du (ud + ?) u ( duuu)* u
L'espressione regolare per Y risulta:

du (? + ud) u ( uuudu)* (u + u)

semplificabile in:

du (? + ud) u ( uuudu)* u


L'espressione regolare per Z risulta:

(ud)*u (ud + ud)

semplificabile in:

(ud)*u (ud + ud)


Ci sono possibili usi di Z senza che questa variabile sia stata definita.

Esercizio n. 4

Si esegua simbolicamente la seguente procedura, nell'ipotesi di voler eseguire ogni comando del programma (ramo then) ed il ciclo while una volta, mostrando come varia la path condition e il valore delle variabili. Cosa calcola la funzione A ?


function A ( N: Integer): Integer

var X, Y: Integer

begin

1. X:=N;


2. if N < 0

3. then

4. while N < 0 do

5. X:= X+2;

6. N:= N+1;

7. endwhile

8. endif

9. Y:=X;


10. return(Y);

end
Soluzione:

Ambiente: N=valn, PC=true,

X,Y,A=undef



Esecuzione: istruzione 1

Ambiente: N=valn, PC=true,

X= valn,

Y,A=undef

Esecuzione: test 2: N < 0 ? Risposta utente: yes

Ambiente: N=valn, PC=valn<0,

X= valn,

Y,A=undef

Esecuzione: test 4: N < 0 ? vera

Ambiente: N=valn, PC=valn<0,

X= valn,

Y,A=undef

Esecuzione: istruzioni 5 e 6

Ambiente: N=valn+1, PC=valn<0,

X= valn+2,

Y,A=undef

Esecuzione: test 4: N < 0 ?

valn+1<0 Risposta utente: no



Ambiente: N=valn+1, PC=(valn<0) and (valn+1>=0),

X= valn+2,

Y,A=undef

Esecuzione: istruzioni 9 e 10

Ambiente: N=valn+1, PC=(valn<0) and (valn+1>=0),

X= valn+2,

Y= valn+2,

A=valn+2


La path condition risulta:

PC=(valn<0) and (valn>=-1)

Un test (l'unico) che soddisfa PC e`:

T = {(N=-1)}


La funzione calcolata e`:

A(n)= valn+2*|valn|.



Esercizio n. 5
Si consideri il seguente programma che determina il valore minimo ed il valore massimo presente in una lista di N interi
program TROVA_MIN_E_MAX

var n, I, min, max : INTEGER

a : array[1.. MAX_INTEGER] of INTEGER;

begin


read(n);

for I in 1..N loop

read(a(i));

end loop

min:=0;

max:=0;


for I in 1..N loop

if a(i) < min then min := a(i);

if a(i) > max then max := a(i);

end loop

print(min);

print(max);

end loop
Determinare un insieme di dati di test che mostri come il programma, in alcuni casi, si comporti in modo anomalo. Spiegare come si dovrebbe modificare il programma per correggere l’errore.

Esercizio n. 6

Dire quali di queste affermazioni sono VERE (FALSE), giustificando brevemente le risposte date.

1) Un malfunzionamento rilevabile usando un qualunque insieme di dati di test selezionato in base al criterio di copertura dei comandi non è sempre rilevabile usando un insieme di dati di test selezionato in base al criterio di copertura delle decisioni.

2) Per individuare all’interno di un programma l’uso di una variabile non inizializzata non è necessario eseguire il programma.


Soluzione:

1) No, il criterio di criterio di copertura delle decisioni include quello di di copertura dei comandi.

2) Si`, e` sufficiente eseguire un'analisi statica del flusso delle variabili (analisi D-U-A).
Esercizio n. 7

Si consideri il seguente frammento di programma:


read(x, y);

while x > 0 and y < x do

x := x - 1;

if x >= 1 then y := y + x

enddo
Si calcoli lo stato dell’esecutore simbolico all’uscita del ciclo dopo la seguente computazione:

si entra nel ciclo while e si esegue il ramo then, si rientra nel ciclo while e si esegue il ramo then, si rientra nel ciclo while e non si esegue il ramo then, e infine si esce dal ciclo.

Si sintetizzi anche un caso di test corrispondente a questa computazione simbolica.
Soluzione:

Ambiente: x=undef, y=undef, PC=true

Esecuzione: istruzione read

Ambiente: x=valx, y=valy, PC=true

Esecuzione: test x > 0 and y < x ? Risposta utente: yes

Ambiente: x=valx, y=valy,

PC=valx > 0 and valy < valx



Esecuzione: x := x - 1

Ambiente: x=valx-1, y=valy,

PC=valx > 0 and valy < valx



Esecuzione: test x >= 1 ? Risposta utente: yes

Ambiente: x=valx-1, y=valy,

PC=valy < valx and valx>=2



Esecuzione: y := y + x

Ambiente: x=valx-1, y=valy+valx-1,

PC=valy < valx and valx>=2



Esecuzione: test x > 0 and y < x ? Risposta utente: yes

Ambiente: x=valx-1, y=valy+valx-1,

PC=valx >=2 and valy1 and valy<0



Esecuzione: x := x - 1

Ambiente: x=valx-2, y=valy+valx-1,

PC=valx >=2 and valy

Esecuzione: test x >= 1 ? Risposta utente: yes

Ambiente: x=valx-2, y=valy+valx-1,

PC=valx >=3 and valy

Esecuzione: y := y + x

Ambiente: x=valx-2, y=valy+2valx-3,

PC=valx >=3 and valy

Esecuzione: test x > 0 and y < x ? Risposta utente: yes
Ambiente: x=valx-2, y=valy+2valx-3,

PC=valx >=3 and valy

Esecuzione: x := x - 1

Ambiente: x=valx-3, y=valy+2valx-3,

PC=valx >=3 and valy

Esecuzione: test x >= 1 ? Risposta utente: no

Ambiente: x=valx-3, y=valy+2valx-3,

PC=valx >=3 and valy

and valx<4

Esecuzione: test x > 0 and y < x ? Risposta utente: no

la condizione è falsa se:


x<=0

oppure


y>=x
La path condition può avere due valori:

PC1=valx>=3 and valy

and valx<=3

ovvero:


PC1= valx=3 and valy<3
PC2=valx>=3 and valy and valy+valx>=0

ovvero:

PC2= valx=3 and valy<0 and valy>=-3



Esercizio n. 8

Si consideri il seguente programma:



program ese

var x,y,z : Integer;

read(x, y);



while x > 0 and y < x do

x := x - 1;

if x >= 1 then

begin

y := y + x;

z := y - x;

end

else



begin

y := y - x;

z:= x + z;

end



endif

enddo

print(z);



end ese
Si calcolino le espressioni D-U-A associate alle variabili x,y,z del programma. Si commenti il risultato ottenuto.
Soluzione:


program ese

X

Y

Z




var x,y,z : Integer;

a

a

a

read(x, y);

d

d




while x > 0 and y < x do

u

u




x := x - 1;

ud







if x >= 1 then

u







begin










y := y + x;

u

ud




z := y - x;

u

u

d

end










else










begin










y := y - x;

u

ud




z:= x + z;

u




ud

end










endif










enddo










print(z);







u

end ese









L'espressione regolare per X risulta:

adu(udu(uu+uu))u)*

L'espressione regolare per Y risulta:

adu(uduuuu)*

L'espressione regolare per Z risulta:

(ad)(d + ud)*u

Ci sono possibili usi di Z senza che questa variabile sia stata definita.









©astratto.info 2017
invia messaggio

    Pagina principale