Ingegneria del software - Appunti

Ingegneria del Software: reti di Petri

1 D EFINIZIONE DI SISTEMA

In generale, si definisce sistema un insieme di componenti interconnessi, selezionati secondo i confini che, sotto

un certo punto di vista, separano la realtà di interesse dall’ambiente circostante. Ciò presuppone la scelta dei

componenti interni al sistema e la selezione delle entità esterne che sono importanti rispetto a quest’ultimo.

Nel campo dell’ingegneria, come nelle scienze sociali, la definizione dei sistemi costituisce un principio

fondamentale. Si tratta di un’attività di modellazione: la realtà di interesse è sintetizzata secondo un certo grado

di astrazione e corrisponde alle sole caratteristiche rilevanti rispetto all’analisi che si vuole condurre.

Secondo Kristen Nygaard (autore del primo linguaggio di programmazione a oggetti, Simula 67) e Petter

Handlykken, un sistema è la porzione del mondo che una persona (o un gruppo di persone) sceglie di considerare,

in un certo momento e per una qualche ragione, come un complesso di componenti distinti. Ciascun componente

è caratterizzato dalle sue proprietà rilevanti e dalle azioni che lo mettono in relazione con gli altri.

NOTA - La definizione di Nygaard e Handlykken non menziona direttamente il comportamento esibito dai sistemi e il ruolo

dell’ambiente che li interagisce con essi.

2 E

LEMENTI DI TEORIA DEI GRAFI

2.1 Grafi e cammini (orientati)

Un grafo (orientato o diretto) è una struttura formata da un insieme di vertici (o nodi) e da un

insieme di archi orientati. Tali insiemi sono così definiti:

Un cammino (orientato) da a in un grafo , è una sequenza non nulla di vertici (con

), non necessariamente distinti, e di archi orientati che li collegano.

Un grafo G si definisce connesso se e solo se ogni sua coppia di vertici è collegata da un cammino, ovvero se e

solo se .

Un grafo G si definisce fortemente connesso (o forte) se e solo se ogni sua coppia di vertici è connessa da un

cammino orientato, cioè se .

Un cammino costituisce un ciclo (orientato) in un grafo G se i nodi iniziale e finale di

coincidono, cioè se e solo se e .

2.2 Classi particolari

Un grafo cui è associato un nodo iniziale è definito come una tripla di elementi .

Un grafo si definisce bipartito se identifica due sottoinsiemi distinti di nodi e ed è tale per cui gli elementi di

un sottoinsieme sono collegati, attraverso gli archi, esclusivamente agli elementi dell’altro. In simboli:

NOTA - La definizione e le proprietà dei cammini si applicano indistintamente ai grafi bipartiti, considerati nella forma

.

2.3 Isomorfismo

Due grafi e si dicono isomorfi se esiste una relazione biunivoca (o biiettiva)

tra i vertici di e tale che, se due nodi sono collegati da un arco , lo

stesso vale per e . 1

3 D P

AGLI AUTOMI A STATI FINITI ALLE RETI DI ETRI

Gli automi a stati finiti costituiscono un modello per descrivere il comportamento di sistemi semplici o dei

componenti che ne fanno parte, attraverso l’identificazione degli stati e delle operazioni che competono a

ciascuno.

Il modello è particolarmente indicato per descrivere il comportamento di componenti distinti, ma risulta

insufficiente rispetto alle situazioni di concorrenza che possono interessare i sistemi (specialmente i sistemi

distribuiti). Tali situazioni richiedono una descrizione che consideri i componenti a un livello di astrazione più alto,

poiché questi ultimi non sono sempre indipendenti tra loro rispetto alle operazioni che effettuano.

In realtà, è possibile superare il problema definendo un automa i cui stati corrispondano a situazioni globali,

anziché a stati locali. Ciascuno stato, in altre parole, sarebbe costituito da una tupla di situazioni inerenti ai singoli

componenti.

Tuttavia, la soluzione comporta due problematiche:

 il numero degli stati composti corrisponderebbe al prodotto degli stati locali di ciascun componente, perciò

la complessità dell’automa (specie nella rappresentazione grafica) crescerebbe in modo significativo;

 l’identità dei singoli componenti risulterebbe confusa, poiché andrebbe persa la rappresentazione specifica

degli stati locali e del “ciclo di vita” di ognuno.

4 R P

ETI DI ETRI

La teoria delle reti di Petri (definita nei primi anni Sessanta dal tedesco Carl Adam Petri) riguarda un formalismo

per la descrizione concettuale (attraverso grafi bipartiti) e matematica del comportamento dei sistemi

(distribuiti).

Si tratta, sostanzialmente, di un’estensione del modello degli automi a stati finiti, che meglio si presta alla

rappresentazione dei processi che caratterizzano un sistema, degli eventi e delle variazioni di stato che ne

determinano l’evoluzione e il comportamento esibito.

Il modello delle reti di Petri, articolato in posti (o stati) e transizioni (o eventi), ben evidenzia il comportamento

sequenziale delle componenti di un sistema e la natura concorrenziale di quest’ultimo nel complesso.

4.1 Reti e Net System

Una rete (orientata) è definita come una tripla di elementi tali che:

L’elemento rappresenta l’insieme dei posti, l’insieme delle transizioni, l’insieme delle relazioni di flusso che

collegano i posti alle transizioni e le transizioni ai posti.

NOTA - Nella rappresentazione grafica delle reti di Petri, i posti e le transizioni costituiscono i vertici del grafo bipartito,

mentre le relazioni di flusso corrispondono agli archi.

Si definisce Net System una tupla di elementi , cioè una rete alla quale è associato un

caso iniziale , corrispondente alle condizioni (ai posti) che son