25 - Petriho sítě (motivace, definice P/T Petriho sítě, metody analýzy, třídy Petriho sítí

Question 1

Definice sítě

Answer 1

Trojici N = (P, T , F ) nazýváme sítí (net), jestliže:

1. P a T jsou disjunktní konecˇné množiny
2. F ⊆(P ×T)∪(T ×P) je binární relace

P nazýváme množinou míst (places)
T nazýváme množinou pˇrechodu ̊ (transitions)
F nazýváme tokovou relací (flow relation)

Graf sítě​ je grafová reprezentace relace F, je to ​bipartitní orientovaný graf​ s množinou uzlů P ∪ T vrcholů

Pro všechny prvky x ∈ (P ∪ T)
•x = {y | yF x} se nazývá vstupní množinou (preset) prvku x
x• = {y | xF y} se nazývá výstupní množinou (postset) prvku x

Question 2

P/T Petriho síť

Answer 2

P/T Petriho síteˇ
❖ Definice 5: Šestici N = (P, T, F, W, K, M0) nazýváme P/T Petriho sítí
(Place/Transition Petri Net), jestliže:
1. (P,T,F)jekonecˇnásít’
2. W : F → N{0} je ohodnocení hran grafu urcˇující kladnou váhu každé hrany síteˇ
3. K : P → N ∪ {ω} je zobrazení urcˇující kapacitu každého místa
4. M0 : P → N ∪ {ω} je pocˇátecˇní znacˇení míst Petriho síteˇ takové, že ∀p ∈ P : M0(p) ≤ K(p)
Poznámka:
• •
N je množina N = {0,1,2,…}
•
Petriho sítí budeme dále rozumeˇt P/T Petriho sít’
ω znacˇí supremum množiny N s vlastnostmi:
1. ∀n∈N:n

Question 3

Analýza petriho sítí

Answer 3

základní pojmy
○ bezpečnost = místo p je bezpečné, pokud pro každé dosažitelné značení M platí M(p)<=1 (maximální “ohodnocení” (kapacita) je jedna)
○ omezenost = pro každé značení M platí M(p) <= k (kapacita žádného místa nepřesáhne k) - ​místo je omezené, pokud je k-bezpečné pro nějaké k
○ konzervativnost = Petriho síť nazýváme konzervativní, jestliže pro každý její stav platí, že celkový počet značek je konstantní - počet značek v síti je konstantní!
○ živost = ​značení M je živé, pokud pro všechny přechody t existuje značení M’ dosažitelné z M takové, že t je M’-proveditelný
Petriho síť je živá jestliže všechna značení z M0 jsou živá

● problém dosažitelnosti - je značení M dosažitelné z M​0
● problém pokrytí - existuje značení M’ dosažitelné z M takové, že M’ >= M

Question 4

Metody analýzy - strom dosažitelných značení

Answer 4

Strom dosažitelných značení
● konečná reprezentace množiny dosažitelných značení
● je to kořenový orientovaný strom, jehož kořenem je počáteční značení M0 a vrcholy tvoří n-tice popisující značky v jednotlivých místech, kde n = |P|

strom můžeme využít pro ověřování
○ bezpečnost
○ omezenost
○ konzervativnost 
○ pokrytí
○ živost
○ dosažitelnost

Question 5

Metody analýzy - P-invarianty

Answer 5

= Množina míst, jejichž počet značek se během provádění přechodů nemění

● vyznačují místa, jejichž značky se během provádění přechodů nemění T​
● je to řešení soustavy rovnic N​* x = 0
● i je P invariant a M je dosažitelné značení, pak platí M​0​* i = M * i
● N je síť s konečným počátečním značením M​0,​ pokud je pokryta P invarianty, pak
je omezená
● pokud i​1​a i​2​jsou P invarianty, pak také i​1​+ i​2​a z*i​1​jsou P invarianty

Question 6

Metody analýzy - T-invarianty

Answer 6

= Které přechody se musí kolikrát provést, aby se toto značení reprodukovalo

každá živá a omezená petriho síť je pokryta T invarianty

značí, které přechody by se musely počínaje určitým značením provést, aby se toto značení reprodukovalo

T invariant je realizovatelný, pokud existuje nějaké značení M ∈ [M​0>​ a výpočetní
posloupnost M … Mk, taková, že počty přechodů v posloupnosti odpovídají T invariantu