| come viene definita una rete di petri? | la rete viene definita tramite una tupla [P,T,F,W,M0]
P : insieme dei posti
T : insieme delle transizioni
F : relazione di flusso
W : funzione che associa un peso ad ogni flusso
M0 : marcatura iniziale(assegnamento dei gettoni) |
| quale è la differenza di un conflitto strutturale e effettivo? | due transizioni si dicono in conflitto strutturale quando l'insieme intersezione dei due preset non è vuoto(hanno almeno un posto in comune nel preset)
due transizioni si dicono in conflitto se in un posto che è preset comune di t1 e t2 ci sono gettoni minori della somma dei requisiti per fare scattare entrambe le transizioni |
| quali sono le varie tipologie di relazioni che possono coinvolgere le transizioni in una rete di petri? | - relazione di sequenza
- relazione di conflitto
- relazione di concorrenza |
| cosa significa che due transizioni sono in una relazione di sequenza? | due transizioni sono in sequenza se:
M [ t1>∧¬M [ t2>∧M [ t1t2>.
ovvero se la transizione t2 viene abilitata dallo scatto di t1 nella marcatura M |
| quando due transizioni sono in relazione di conflitto?
quali tipi di conflitto esistono? | - conflitto strutturale : se l’intersezione dei due preset non è vuota e quindi hanno posti in ingresso in comune
- conflitto effettivo : se sono entrambe abilitate in una marcatura M ed esiste un posto in ingresso in comune ai due preset tale per cui il numero di gettoni in quel posto è minore della somma dei pesi dei due flussi che vanno dal posto alla transizione |
| quando due transizioni si dicono in relazione di concorrenza?
quali tipi di concorrenza esistono? | concorrenza strutturale ⟺Pre(t1)∩Pre(t2)=∅
concorrenza effettiva in una marcatura M⟺
- M [ t1>∧M [ t2>
- ∀p∈Pre(t1)∩Pre(t2)M(p)≥W(⟨p,t1⟩)+W(⟨p,t2⟩)
in altre parole
- M abilita sia t1 che t2.
- Per ogni posto p che è pre-condizione sia di t1 che di t2, M contiene almeno il numero di token richiesto per abilitare entrambe le transizioni. |
| come viene definito l'insieme di raggiungibilità R di una rete di petri P/T a partire da una marcatrura M? | è il più piccolo insieme di marcature tale che:
- M∈R(P/T,M)
M fa parte delle marcature raggiungibili
- M′∈R(P/T, M) ∧ ∃t∈T M′ [ t > M" )
allora M″∈R(P/T,M)
se M' fa parte delle marcature raggiungibili e esiste una transizione che da M' mi porta in M" allora M" fa parte delle marcature raggiungibili da M |
| cosa significa che una rete di petri è limitata? | una rete di petri R si dice limitata se:
∃k∈ℕ, ∀M′!∈R P/T, M), ∀p∈PM′ ( p ) ≤ k
cioè se esiste un numero naturale k tale per cui per ogni marcatura M′ raggiungibile da M, per ogni posto p all’interno della rete il numero di gettoni in quella marcatura raggiungibile è minore o uguale di k
— ovvero se è possibile porre un numero finito tale per cui dopo qualsiasi evoluzione non esista alcun posto che possiede un numero di gettoni maggiore di k allora è possibile affermare che la rete è limitata. |
| quali sono i possibili gradi di vitalità di una transizione? | grado 0 (o morta): non è abilitata in nessuna marcatura appartanente all’insieme di raggiungibilità, quindi qualunque evoluzione avvenga nella rete, la transizione non portà mai scattare (non è sempre un aspetto negativo)
- grado 1: esiste almeno una marcatura raggiungibile a partire da M
in cui la transizione è abilitata;
- grado 2: per ogni numero n naturale escluso lo zero esiste almeno una sequenza di scatti ammissibile a partire da M in cui la transizione scatta n volte, ovvero è possibile far scattare la transizione un numero n grande a piacere di volte;
- grado 3: esiste una sequenza di scatti ammissibile a partire da M
per cui la transizione scatta infinite volte;
- grado 4 in qualunque marcatura raggiungibile esiste una sequenza ammissibile in cui è possibile far scattare la transizione almeno una volta, di conseguenza può scattare infinite volte in qualunque situazione ci si trovi (ovvero in qualunque marcatura).
In questo caso si dice che la transizione è viva in maniera assoluta. |
| quando una rete si dice pura?
quando una rete si dice viva? | 1) quando per ogni transizione hanno preset e postset disgiunti
2) quando tutte le transizioni della rete sono vive |
| come è possibile convertire la rete di petri in figura in una rete di petri con archi senza peso? | tramite un posto globale collegato a tutte le transizioni.
questo consente di proibire qualsiasi altra transizione fino a quando siano scattate sia t0 che t1 tramite il singolo gettone globale |
| che cosa sono le reti C/epsilon?
e a cosa servono | sono reti particolari in cui ogni posto può contenere un massimo di 1 gettone e tutti gli archi hanno peso 1
possono essere utili per poter fornire una visualizzazione più immediata del comportamento della rete,
ogni rete può essere convertita in una corrispondente C/epsilon |
| quando una rete si dice conservativa rispetto ad una funzione H? | si dice conservativa rispetto ad H se e solo se:
∀M′∈ R(P/T,M) ∑p∈P H(p) M′(p) = ∑p∈P H(p) M(p).
ovvero se
per ogni marcatura M′ raggiungibile dalla marcatura iniziale data una certa marcatura e una funzione H, si dice che la rete è conservativa se la sommatoria dei gettoni di ogni posto (quest’ultimi pesati attraverso la funzione H) è costante per qualunque marcatura raggiungibile. |
| quale relazione esiste fra conservatività e limitatezza di una rete?
la dimostrazione? | - limitata:
esiste un k tale che ogni posto non ha mai piu di k gettoni
- conservativa:
se qualsiasi marcatura pesata è costante
una rete conservativa è necessariamente limitata non necessariamente il contrario.
dimostrazione:
Assumendo che ∑p∈PH(p)M(p)=k
allora
∀M′∈ R(P/T,M) ∑p∈P H(p) M′(p) = k. |
| quando una rete si dice strettamente conservativa? | quando è conservativa(se la sommatoria dei gettoni di ogni posto (quest’ultimi pesati attraverso la funzione H) è costante per qualunque marcatura raggiungibile.)
e per di più la funzione che assegna il peso ai posti è unitaria H = 1
BISOGNA STARE ATTENTI A NON CONSIDERARE LE TRANSIZIONI MORTE |
| cosa si intente per stato base di una rete?
quando la rete si dice reversibile? | per stato base di una rete si intende se da qualsiasi marcatura della rete è possibile raggiungere la marcatura in oggetto.
Una rete si dice reversibile se la marcatura iniziale è anche uno stato base della rete |
| quali sono le possibili tecniche di analisi di una rete di petri? | tecniche dinamiche :
- albero delle marcature raggiungibili
- grafo di copertura delle marcature raggiungibili
tecniche statiche :
- identificazione p-invarianti
- identificazione t-varianti |
| quando una marcatura si dice morta? | una marcatura si dice morta se, data la sua marcatura minima M(il minor numero di gettoni nel preset per abilitarla) questa non è copribile dalla marcatura corrente |
| quando nella costruzione dell'albero di copertura omega non compare | si può dire limitata |
| quando una rete si può dire binaria? | quando nel corrispettivo albero di copertura compaiono solo 0 e 1 |
| quando una transizione di una rete si può dire morta? | quando nel corrispettivo albero di copertura la transizione non compare |
| se nell'albero di copertura esiste un nodo corrispondente alla marcatura che copre M allora è possibile affermare che M è raggiungibile? | non necessariamente, l'esistenza di una copertura è condizione necessaria ma non sufficiente ad affermare che M sia raggiungibile |
| che cosa sono i p-invarianti e quale è il loro scopo? | un P-invariante è un insieme di posti tale per cui, indipendentemente da come i gettoni vengono spostati tra i posti della rete, il numero totale di gettoni in quei posti rimane lo stesso
possono essere utilizzati per l'analisi statica:
- determinare la raggiungibilità di una marcatura
- determinare se una rete è conservativa(quando un p-invariante ha solo pesi positivi) |
| quale correlazione esiste fra un posto e un p-invariante? | un p-invariante con tutti pesi >= 0 è detto semi positivo
- un posto si dice limitato (nel numero di gettoni che può contenere) se nel p-invariante corrispettivo ha un peso > 0
- se per ogni posto esiste un p-invariante in cui è positivo allora la rete si dice limitata |
| a che cosa serve l'algoritmo di Farkas? | l'algoritmo di Farkas viene utilizzato nell'ambito di p invarianti:
predilige la ricerca di basi minime per un sistema di equazioni, privilegiando quelle semipositive
n = righe
m = colonne
C = matrice di incidenza |
| quale differenza intercorre fra p-invarianti e t-invarianti? | Gli T-invarianti sono vettori che identificano sequenze di transizioni che, se attivate, riportano la rete di Petri dalla marcatura m ad m
le sequenze di scatti negli t-invarianti:
- si possono ripetere ciclicamente
- portano alla marcatura di partenza
consentono l'affermazione ulteriore:
Se una rete è limitata e copribile da T-invarianti, allora è dimostrabile che è anche viva. |
| quale formula per trovare gli t-invarianti? | Partendo dall’equazione m′=m+Cs
poniamo il vincolo m′=m in quanto la sequenza deve tornare alla marcatura iniziale. Le soluzioni del sistema sono quindi: Cs=0
la sequenza di scatti trovata è tale da riportare un sistema da una marcatura M a se stessa |
| a cosa servono i controllori con specifica a stati proibiti?
un esempio in cui sono utili? | servono per poter porre delle forzature o delle restrizioni alla rete con lo scopo di poter rispettare un certo invariante
un caso è il poter garantire l'utilizzo in mutua esclusione di una risorsa per esempio lettori e scrittori |
| quale è la differenza sostanziale fra p-invarianti e controllori? | nonostante il concetto sia molto simile:
un p invariante pone una condizione di uguaglianza con la combinazione di marcature di una rete
un controllore pone una condizione di minore o uguale
controllore LM <= b
p invariante LM = b |
| che formula si usa per calcolare le righe da aggiungere alla matrice di incidenza Cs dato un controllore? | Cc = −L Cs
dove:
- Cs è la matrice di incidenza del sistema originale
- L è il vincolo desiderato, un vettore 0 nei posti non interessati N numero di gettoni da vincolare nei posti interessati;
- Cc matrice che si vuole trovare |
| che formula si usa per calcolare la marcatura iniziale del posto controllore Pc? | M0c = b − L M0s
dove:
- M0c marcatura iniziale del posto controllore
- b vincolo numerico
- L vettore dei pesi del vincolo imposto dal controllore
- M0s marcatura iniziale del sistema |
| che cosa sono le reti con priorità e quali sono i loro difetti? | nelle reti a priorità Ad ogni transizione è associata una priorità: quando in una marcatura n transizioni sono abilitate, la scelta della prossima da far scattare è determinata dalla sua priorità.
- rischio di creare di cicli infiniti;
- si perde la località di decisione della abilitazione di una transizione |
| aggiungi un posto di controllo per la mutua esclusione in: | questo |
| conoscendo le matrici I, O cosa mi può far dire se una transizione è abilitata? | la transazione jesima è abilitata in una marcatura (vettore m) se e solo se la colonna jesima della matrice di input è miniore o uguale al m |
| cosa succede allo scatto di una transizione al vettore della marcatura m? | si crea un nuovo vettore m' dato da m - [][j]I + [][j]O
oppure viene sommato il vettore [][j] della matrice C |
| la matrice c è utile per poter calcolare l'abilitazione di una transizione? | no, al contrario è utile per calcolare la matrice risultante da uno scatto |
| in quale modo un p-invariante dimostra che una rete sia conservativa e/o limitata? | Nel caso in cui un P-invariante abbia tutti i pesi maggiori di zero allora h(vettore pesi) ≡ H(funzione del p-invariante) : la rete sarebbe quindi conservativa e quindi anche limitata.
dove:
H è una funzione H:P→ℕ∖0
P è l'insieme di indici del p-invariante |
| data la matrice C di un sistema, come si estraggono i p invarianti? | tramite l'algoritmo di farkas, affiancando alla matrice di incidenza C la matrice identità corrispettiva, si combinano linearmente le righe per ottenere dei vettori semipositivi
queste basi saranno i p invarianti |
| quali affermazioni si possono fare osservando questo albero di raggiungibilità ?
cosa non è possibile affermare? | - la rete è viva poichè vengono attivate tutte le possibili transizioni
- la rete è reversibile poichè da qualsiasi marcatura è raggiungibile un qualsiasi altra marcatura
- se la rete fosse illimitata allora non sarebbe possibile elencare tutti i nodi dell'albero |
| cosa significa che una marcatura ne copre unaltra? | una marcatura M copre M' se per ogni posto di M la marcatura in quel posto è maggiore o uguale a M'(p) |
| cosa consentono di fare i grafi di copertura delle reti in più rispetto ai grafi di raggiungibilità? | consentono di analizzare anche reti illimitate tramite l'utilizzo di stati simbolici, per le marcature. questi utilizzano omega per esprimere un valore arbitrario in un posto |
| quali affermazioni si possono fare conoscendo il grafo di copertura delle reti? | - se ω non compare mai nell’albero di copertura la rete è limitata
- una rete di Petri è binaria se nell’albero di copertura compaiono solo 0 e 1
- una transizione è morta (0-viva) se non compare mai come etichetta di un arco |
| data una marcatura M è sufficiente l'applicazione della formula Cs=0 per trovare tutti gli t invarianti ammissibili? | no, gli t-invarianti trovati non tengono conto della marcatura di partenza data che viene persa nella formula originale M' = M+Cs.
gli ogni t-invariante trovato deve essere testato se compatibile con la matrice di partenza |
