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. +more 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). +more 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í: # více přechodů může být uschopněno současně a libovolný může odpálit, # žádný přechod není nutno odpálit - odpalují se dle libosti mezi časy 0 až nekonečno nebo vůbec nikdy. +more 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 (S,T,F,M_0,W)\. , kde (viz Desel a Juhás) * S je konečná množina míst. +more * T je konečná množina přechodů. * F je konečná množina hran, kde žádná hrana nemůže spojovat dvě místa nebo dva přechody, formálněji: F \subseteq (S \times T) \cup (T \times S). * M_0 : S \to \mathbb{N} je počáteční označkování, kde v každém místě s \in S je n \in \mathbb{N} teček. * W : F \to \mathbb{N^+} je množina vážených hran, které přiřazuje každé hraně f \in F nějaké číslo 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

[url=http://www.informatik.uni-hamburg.de/TGI/PetriNets/]Svět Petriho sítí - anglicky[/url] * [url=http://citeseer.ist.psu.edu/cs?q=Petri+net]Citace v CiteSeeru - anglicky[/url]

Kategorie:Výpočetní modely