Petri háló

A Petri-háló  egy matematikai objektum, amelyet dinamikus diszkrét rendszerek modellezésére használnak, Carl Petri javasolta 1962 - ben .

Úgy definiálható, mint egy bipartit orientált multigráf , amely kétféle csúcsból áll – pozíciókból és átmenetekből, amelyeket ívek kötnek össze. Az azonos típusú csúcsok közvetlenül nem kapcsolhatók össze. A pozíciók címkéket (jelölőket) tartalmazhatnak, amelyek mozoghatnak a hálózaton. Egy esemény egy átmenet kilövése, amelyben az átmenet bemeneti pozícióiról a címkék a kimeneti pozíciókra kerülnek. Az események azonnal vagy eltérő időpontokban, bizonyos feltételek mellett történnek.

A Petri-háló egy multigráf, mivel lehetővé teszi több ív létezését a gráf egyik csúcsától a másikig. Mivel az ívek irányítottak, ez egy irányított multigráf. A gráf csúcsai két halmazra oszthatók (pozíciók és átmenetek) oly módon, hogy minden ív egy halmaz eleméből (pozíciók vagy átmenetek) egy másik halmaz elemére (átmenetek vagy pozíciók) irányuljon; ennélfogva egy ilyen gráf egy bipartit irányított multigráf.

Eredetileg párhuzamosan kölcsönható komponensekkel rendelkező rendszerek modellezésére fejlesztették ki; Petri az "Automaták kommunikációja" című doktori értekezésében [1] fogalmazta meg a számítástechnikai rendszer aszinkron komponenseinek kommunikációs elméletének főbb rendelkezéseit .

Dinamika

A Petri-háló működési folyamata vizuálisan ábrázolható az elérhető jelölések grafikonjával. A hálózat állapotát egyértelműen a jelölése határozza meg - a chipek pozíció szerinti eloszlása. A gráf csúcsai a Petri-háló megengedett jelölései, az ívek a triggerelt átmenet szimbólummal vannak jelölve. Minden gerjesztett átmenethez egy ív épül. A konstrukció leáll, ha olyan jelöléseket kapunk, amelyekben nincs átmenet gerjesztve, vagy olyan jelöléseket kapunk, amelyeket a gráf tartalmaz. Vegye figyelembe, hogy az elérhető jelölések grafikonja egy automata.

Petri-hálók típusai

Néhány Petri-háló típus:

• Időbeli Petri-háló - az átmeneteknek súlya van, amely meghatározza a válasz időtartamát (késleltetés).
• Sztochasztikus Petri-háló – a késleltetések véletlen változók.
• Funkcionális Petri-háló - a késleltetések bizonyos argumentumok függvényeiként vannak definiálva, például a tetszőleges pozíciókban lévő címkék száma, egyes átmenetek állapota.
• Színes (színes, festett) Petri háló  - a címkék többféle típusúak lehetnek, színekkel jelölve, a címke típusa argumentumként használható funkcionális hálózatokban.
• Gátló Petri-háló – Lehetséges olyan gátló ív, amely megtiltja az átmenet elindítását, ha a gátló ív általi átmenethez társított bemeneti pozícióban címke található.
• Hierarchikus hálózat – olyan nem azonnali átmeneteket tartalmaz, amelyekbe más, esetleg hierarchikus hálózatok is beágyazódnak. Egy ilyen átmenet kiváltása a beágyazott hálózat teljes életciklusának kiteljesedését jellemzi.
• WF hálózat .
• Algebrai Petri-háló .

Petri-hálók elemzése

A Petri-háló főbb tulajdonságai:

• korlátoltság - a hálózat bármely pozíciójában lévő címkék száma nem haladhat meg egy bizonyos értéket ;
• a biztonság az elévülés speciális esete: ;
• perzisztencia - erőforrás terhelés állandósága: állandó, ahol - -edik pozícióban  lévő markerek száma ,  - súlyegyüttható;
• elérhetőség - a hálózati átmenet lehetősége egy adott állapotból (amelyet a címkék elosztása jellemez) a másikba;
• élénkség - a szimulált objektum működése során bármilyen átmenet kiváltásának lehetősége.

Ezen tulajdonságok vizsgálata elérhetőségi elemzésen alapul. A Petri-hálók tulajdonságainak elemzésére szolgáló módszerek az elérhető (fedő) jelölések grafikonjain, a háló állapotegyenletének megoldásán, valamint a pozíciók és átmenetek lineáris invariánsainak kiszámításán alapulnak. Kiegészítő redukciós módszereket is alkalmaznak a Petri-háló méretének csökkentésére, miközben megtartják tulajdonságait, és dekompozíciót [2] , az eredeti hálót alhálózatokra osztva.

Univerzális Petri Net

1974-ben Tilak Ajerwala kimutatta, hogy a gátló Petri-háló univerzális algoritmikus rendszer. Kotov monográfiájában a bizonyíték vázlatát adják meg, feltüntetve a Minsky -féle számlálóautomata programjának gátlóhálózat általi kódolásának szabályait . Peterson példákat ad a Petri-hálók egyéb kiterjesztett osztályaira, amelyek univerzális algoritmikus rendszer: szinkron és prioritás. Az explicit módon megszerkesztett univerzális Petri-háló [3] több ezer csúcsot tartalmazott, és a közelmúltban 56 csúcsra csökkentették [4] .

Végtelen Petri háló

A végtelen Petri-hálókat a számítási rácsok ellenőrzésére vezették be, és lehetővé tették a Petri-hálók tulajdonságainak meghatározását tetszőleges méretű, tipikus töredékek összeállításával kapott szabályos (lineáris, faszerű, négyzetes, háromszög-, hatszögletű és hiperkocka [5] ) szerkezetekre.

Lásd még

• Sorozati rendszerek
• Szimuláció
• Színész modell
• állapotgép

Jegyzetek

1. ↑ Peterson, 1984 , 11. o. „1.3. A Petri-háló elméletének eredete.
2. ↑ Zaitsev D. A. 2022. április 1-i archivált példány a Wayback Machine -nél Petri-hálók kompozíciós elemzése // Kibernetika és rendszerelemzés. - 2006, 1. sz. - S. 143-154.
3. ↑ Zaitsev D. A. Archív másolat , 2022. április 1-je, a Wayback Machine Universal Petri Net, Cybernetics and System Analysis, 2012. évi 4. szám, p. 24-39.
4. ↑ Zaitsev DA archiválva : 2022. április 1., a Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man and Cybernetics: Systems, 2013, 1-12.
5. ↑ Zaicev D. A. 2022. április 1-i archivált példány a Wayback Machine -nél, Shmeleva T. R. Hiperkocka kommunikációs struktúrák ellenőrzése parametrikus Petri-hálókkal, Cybernetics and System Analysis, 1. szám, 2010, 119-128.

Irodalom

• Peterson J. Petri-hálók elmélete és rendszermodellezés. — M .: Mir, 1984. — 264 p.
• Kotov V.E. Petri hálók. — M .: Nauka, 1984. — 160 p.
• Sleptsov A. I., Yurasov A. A. Vezérlőrendszerek tervezésének automatizálása rugalmas automatizált gyártáshoz / B. N. Malinovsky. - Kijev: Technika, 1986. - 160 p.
• Achasova SM, Bandman OL Párhuzamos számítási folyamatok helyessége. - Novoszibirszk: Nauka, 1990. - 253 p.
• Marakhovsky V. B., Rosenblum L. Ya., Yakovlev A. V. Párhuzamos folyamatok szimulációja. Petri hálók. Tanfolyam rendszertervezőknek, programozóknak, rendszerelemzőknek, komplex vezérlőrendszerek tervezőinek . - Szentpétervár: Szakirodalom, IT-előkészítés, 2014. - 400 p.

Linkek

• MSTU képzés. Bauman "A CAD alapjai. Modellezés". Petri hálók . Petri-hálók elemzése
• Petri hálók az Automatizálási és Irányítási Folyamatok Intézet honlapján.
• Petri-hálókat és szigorúan hierarchikus hálókat megvalósító mintaprogramok forrásszövegei .