In un certo senso evoluzione delle macchine a stati finiti, ma gli stati vengono visti come composizione di stati "atomici" e quindi le transizioni mutano solo parte dello stato.
http://www.daimi.au.dk/PetriNets
Hanno a disposizione una rappresentazione grafica intuitiva
Le unità delle reti di Petri sono:
Posti, Transizioni, Gettoni (e archi orientati). I gettoni vengono inseriti nei posti, gli archi connettono posti a transizioni (e vice versa). Un posto può essere attaccato ad una sola transizione, ma una transizione può essere attaccata a più posti.
Le reti di Petri sono la 5upla:
<P,T,F,W,m0>
dove:
P Insieme dei posti
T Insieme delle transizioni
F Relazioni di flusso (gli archi orientati)
W Funzione che associa un peso ad ogni flusso (non presente in tutte le versioni delle reti di Petri. Interi maggiori di zero)
m0 Numero iniziale di gettoni. Ogni posto ha dei gettoni (intero >= 0).
Pre(a) ovvero Preset(a) é un percorso predeterminato che porta al nodo a
Post(a) insieme dei nodi collegati con un flusso che partono da a
Comportamento dinamico
Si basa sull identificare quali sono le transizioni abilitate a scattare
Sono transizioni abilitate a scattare quelle il cui peso dei gettoni del posto é maggiore del peso dell'arco che congiunge con la transizione
La transizione t é abilitata nella marcatura M: M[t>
Lo scatto di una transizione t dalla marcatura M produce una nuova marcatura M'
Quando scatta una transizione per ogni posto in ingresso tolgo un numero di gettoni pari al peso dell'arco che conduce alla transizione e aggiungo il numero di gettoni pari agli archi in uscita che raggiungo posti che prima non erano presenti.
Nell'immagine: sulla sinistra un automa a stati finiti, sulla destra la corrispondente rete di Petri
Il peso degli archi non é specificato perché é banalmente 1
Alcuni dettagli: i gettoni NON si spostano vengono distrutti e ricreati.
Le reti di Petri sono NON-deterministiche (in alcuni casi più di una transizione potrebbe scattare e ne scatterà casualmente una delle tante che possono scattare.
Si consiglia di guardare 15 minuti di lezione dal minuto 20:00 della lezione corrispondente
Relazioni tra le transizioni (t1 e t2 nella marcatura M)
Sequenza (t1 e t2 sono in sequenza (nella marcatura M) se t1 é abilitato in M, t2 NON lo é, ma viene abilitato dallo scatto di t1 in M. In parole povere se t1 é attivabile e poi lo é t2)
Conflitto:
Strutturale: quando esiste un intersezione non vuota tra Pre(t1) e Pre(t2) ovvero quando hanno dei posti (precedenti) in comune.
Effettivo: se c'é un conflitto strutturale e il numero di gettoni nei posti comuni é sufficiente a fare scattare solo una qualsiasi delle transizioni, ma non entrambe (come strutturale, ma in più ci sono i gettoni)
Rilassata: t1 e t2 possono scattare in M, ma t1, t2 non é una sequenza ammissibile in M. Ovvero come l'effettivo, ma asimmetrico (potrebbe esserci un arco che permette l'attivazione in un senso)
Concorrenza: (quando non sono in conflitto)
Strutturale: quando l'intersezione fra i preset é nulla
Effettiva: Quando c'é intersezione fra i preset, ma ci sono abbastanza gettoni perché partano entrambe le transizioni (probabilmente in una transizione successiva ci sarà conflitto effettivo)
Insieme di raggiungibilità di una rete a partire da una certa marcatura M é il più piccolo insieme di marcature raggiungibili dalla marcatura M senza bisogno di aggiungere alcun token (il sistema si deve evolvere con i token già presenti nella marcatura M). Non é detto che sia identificabile (più che altro non é detto che sia finito).
Se la rete é limitata allora posso costruirne sempre un automa a stati finiti
Gradi di vitalità di una transizione
grado 0) la transizione é MORTA: se in qualunque caso é impossibile che dalla marcatura corrente verrà a scattare la transizione t in oggetto.
grado 1) Esiste almeno una marcatura raggiungibile in cui é abilitata
grado 2) Esiste almeno una sequenza ammissibile in cui posso fare scattare la transizione N (per qualsiasi N) volte
grado 3) Esiste una sequenza ammissibile in cui scatta infinite volte
grado 4) (é viva) in qualunque marcatura raggiungibile esiste una sequenza ammissibile in cui scatta.
Una rete si dice viva se tutte le sue marcature sono vive (tutte di grado 4).
Nell'esempio:
T0 é di grado 0, T1 di 1, T2 di 2, T3 di 3 e T4 di 4.
Perché T2 é di grado 2?
In effetti io posso fare scattare T3 N volte (quindi caricare P2 con N gettoni), ma poi faccio scattare T1 e non posso più tornare indietro (quindi un numero finito grande a piacere, ma non infinito!)! 
Nessun commento:
Posta un commento