Petriho síť

Petriho síť je matematická reprezentace diskrétních distribuovaných systémů. Petriho síť graficky reprezentuje strukturu distribuovaného systému jako orientovaný bipartitní graf s ohodnocením. Taková Petriho síť má dva druhy uzlů označované jako místa a přechody a orientované hrany spojující místa s přechody. Petriho sítě byly vytvořeny roku 1962 Carlem Adamem Petrim v jeho disertační práci.

Příklad Petriho sítě v pohybu

Základní Petriho sítě

Petriho sítě obsahují místa, přechody a hrany. Hrany jsou pouze mezi místy a přechody, nikoliv mezi dvěma místy nebo dvěma přechody. Místa, ze kterých vedou hrany do přechodu, jsou nazývána vstupní místa tohoto přechodu; místa, do kterých vedou hrany z přechodu, jsou nazývána výstupní místa tohoto přechodu.

Místa mohou obsahovat libovolný počet teček (někdy též značek nebo tokenů; anglicky: tokens). Rozložení značek mezi místy v síti je nazýváno značení (anglicky: marking). Přechody mohou tečky ze vstupních míst takzvaně odpalovat (anglicky: firing) do míst výstupních. Přechod je uschopněn (anglicky: enabled) a může odpálit, pokud je v každém ze vstupních míst alespoň tečka. Když přechod odpálí, odebere tečky z jeho vstupních míst, provede nějaké výpočetní úlohy, a vloží zvolený počet teček do každého výstupního místa. Tento proces činí automaticky v každém jednotlivém kroku.

Výpočet Petriho sítě je nedeterministický. Což znamená následující:

1. více přechodů může být uschopněno současně a libovolný může odpálit,
2. žádný přechod není nutno odpálit – odpalují se dle libosti mezi časy 0 až nekonečno nebo vůbec nikdy. Je tedy možné, že se neodpálí vůbec nic.

Protože je odpalování nedeterministické, Petriho sítě jsou vhodné pro modelování souběžného chování distribuovaných systémů.

Formální definice

Petriho síť je pětice ${\displaystyle (S,T,F,M_{0},W)\!}$, kde (viz Desel a Juhás^[1])

• ${\displaystyle S}$ je konečná množina míst.
• ${\displaystyle T}$ je konečná množina přechodů.
• ${\displaystyle F}$ je konečná množina hran, kde žádná hrana nemůže spojovat dvě místa nebo dva přechody, formálněji: ${\displaystyle F\subseteq (S\times T)\cup (T\times S)}$.
• ${\displaystyle M_{0}:S\to \mathbb {N} }$ je počáteční označkování, kde v každém místě ${\displaystyle s\in S}$ je ${\displaystyle n\in \mathbb {N} }$ teček.
• ${\displaystyle W:F\to \mathbb {N^{+}} }$ je množina vážených hran, které přiřazuje každé hraně ${\displaystyle f\in F}$ nějaké číslo ${\displaystyle n\in \mathbb {N^{+}} }$ označující kolik teček je odebráno z místa tímto přechodem, nebo alternativně: kolik teček je přechodem produkováno a vloženo do každého výstupního místa.

Existuje mnoho variant formálních definic – některé nemají vážené hrany, ale povolují více hran mezi stejným místem a přechodem, což je koncepčně shodné s jednou hranou s váhou rovnou počtu těchto hran z původní definice.

Odkazy

Reference

Související články

• Konečný automat
• Sekvenční obvod

Externí odkazy

• Obrázky, zvuky či videa k tématu Petriho síť ve Wikimedia Commons
• Svět Petriho sítí – anglicky
• Citace v CiteSeeru – anglicky