Petri verkko

Petri-verkko on Carl Petrin vuonna 1962 ehdottama  matemaattinen objekti, jota käytetään dynaamisten diskreettien järjestelmien mallintamiseen .

Se määritellään kaksiosaiseksi orientoiduksi multigrafiksi , joka koostuu kahdesta pisteestä - paikoista ja siirtymistä, jotka on yhdistetty kaarilla. Samantyyppisiä pisteitä ei voi yhdistää suoraan. Asemat voivat sisältää tarroja (merkkejä), jotka voivat liikkua verkossa. Tapahtuma on siirtymän laukaisu, jossa tarrat siirretään tämän siirtymän tulopaikoista lähtökohtiin. Tapahtumat tapahtuvat välittömästi tai eri aikoina, tietyissä olosuhteissa.

Petri-verkko on multigrafi, koska se mahdollistaa useiden kaarien olemassaolon graafin kärjestä toiseen. Koska kaaret ovat suunnattuja, tämä on suunnattu multigrafi. Graafin kärjet voidaan jakaa kahteen joukkoon (paikat ja siirtymät) siten, että jokainen kaari suunnataan yhden joukon elementistä (paikat tai siirtymät) toisen joukon elementtiin (siirtymät tai paikat); näin ollen tällainen graafi on kaksiosainen suunnattu multigrafi.

Alun perin kehitetty järjestelmien mallintamiseen rinnakkaisten vuorovaikutteisten komponenttien kanssa; Petri muotoili laskentajärjestelmän asynkronisten komponenttien viestinnän teorian pääsäännöt väitöskirjassaan "Automaattien kommunikaatio" [1] .

Dynamiikka

Petri-verkon toimintaprosessi voidaan esittää visuaalisesti saavutettavissa olevien merkintöjen kuvaajalla. Verkon tila määräytyy yksiselitteisesti sen merkinnällä - sirujen jakautumisella sijainnin mukaan. Graafin kärjet ovat sallittuja Petri-verkon merkintöjä, kaaret on merkitty liipaistuneella siirtymäsymbolilla. Jokaiselle jännitteelle siirtymälle rakennetaan kaari. Rakentaminen pysähtyy, kun saamme merkintöjä, joissa ei ole virittyvää siirtymää, tai merkintöjä, jotka sisältyvät kuvaajaan. Huomaa, että saavutettavien merkintöjen kuvaaja on automaatti.

Petri-verkkojen tyypit

Jotkut Petri-verkkotyypit:

• Temporaalinen Petri-verkko - siirtymillä on painoarvo, joka määrää vasteen keston (viiveen).
• Stokastinen Petri Net - viiveet ovat satunnaismuuttujia.
• Toiminnallinen Petri-verkko - viiveet määritellään joidenkin argumenttien funktioiksi, esimerkiksi nimikkeiden lukumäärä missä tahansa paikassa, joidenkin siirtymien tila.
• Värillinen (värillinen, maalattu) Petri-verkko  - tarrat voivat olla erityyppisiä, merkitty väreillä, etikettityyppiä voidaan käyttää argumenttina toiminnallisissa verkoissa.
• Estävä Petri-verkko — Estokaaret ovat mahdollisia, jotka estävät siirtymän laukaisun, jos syöttökohdassa on etiketti, joka liittyy estävän kaaren siirtymään.
• Hierarkkinen verkko - sisältää ei-välittömiä siirtymiä, joissa on sisäkkäisiä muita, mahdollisesti myös hierarkkisia verkkoja. Tällaisen siirtymän laukeaminen luonnehtii sisäkkäisen verkon koko elinkaaren päättymistä.
• WF verkko .
• Algebrallinen Petri-verkko .

Petri-verkkojen analyysi

Petri-verkon tärkeimmät ominaisuudet ovat:

• rajaus - tarrojen määrä verkon missä tahansa kohdassa ei voi ylittää tiettyä arvoa ;
• turvallisuus on rajoituksen erikoistapaus: ;
• pysyvyys - resurssien kuormituksen pysyvyys: vakio, missä  - merkkien lukumäärä -: nnessä paikassa,  - painokerroin;
• saavutettavuus - mahdollisuus verkon siirtymiseen yhdestä tietystä tilasta (jolle on ominaista nimikkeiden jakelu) toiseen;
• eloisuus - mahdollisuus laukaista mikä tahansa siirtymä simuloidun kohteen toiminnan aikana.

Näiden ominaisuuksien tutkiminen perustuu saavutettavuusanalyysiin. Petri-verkkojen ominaisuuksien analysointimenetelmät perustuvat saavutettavien (peittävien) merkintöjen kuvaajien käyttöön, verkon tilayhtälön ratkaisemiseen sekä paikkojen ja siirtymien lineaaristen invarianttien laskemiseen. Apuvähennysmenetelmiä käytetään myös Petri-verkon koon pienentämiseen sen ominaisuudet säilyttäen sekä hajottamista [2] , joka jakaa alkuperäisen verkon aliverkkoihin.

Universal Petri Net

Vuonna 1974 Tilak Ajerwala osoitti, että estävä Petri-verkko on universaali algoritmijärjestelmä. Kotovin monografiassa esitetään luonnos todistuksesta, jossa esitetään säännöt Minskyn laskuriautomaatin ohjelman koodaamiseksi estäjäverkolla . Peterson antaa esimerkkejä muista laajennetuista Petri-verkkojen luokista, jotka ovat universaali algoritmijärjestelmä: synkroninen ja prioriteetti. Eksplisiittisesti rakennetussa universaalissa Petri-verkossa [3] oli useita tuhansia pisteitä ja se pienennettiin hiljattain 56 kärkeen [4] .

Infinite Petri Nets

Äärettömät Petri-verkot otettiin käyttöön laskennallisten verkkojen todentamiseksi ja mahdollistamaan Petri-verkkojen ominaisuuksien määrittäminen säännöllisille rakenteille (lineaarinen, puumainen, neliö, kolmiomainen, kuusikulmainen ja hyperkuutio [5] ), jotka ovat mielivaltaisen kokoisia ja jotka on saatu muodostamalla tyypillisiä fragmentteja.

Katso myös

• Jonotusjärjestelmät
• Simulointi
• Näyttelijä malli
• valtion kone

Muistiinpanot

1. ↑ Peterson, 1984 , s. 11 "1.3. Petri-verkkojen teorian alkuperä.
2. ↑ Zaitsev D. A. Arkistoitu kopio 1. huhtikuuta 2022 Wayback Machinessa Petri-verkkojen koostumusanalyysi // Kybernetiikka ja järjestelmäanalyysi. - 2006, nro 1. - S. 143-154.
3. ↑ Zaitsev D. A. Arkistokopio , päivätty 1. huhtikuuta 2022 Wayback Machine Universal Petri Netissä, Cybernetics and System Analysis, nro 4, 2012, s. 24-39.
4. ↑ Zaitsev DA Arkistoitu 1. huhtikuuta 2022 Wayback Machinessa Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1-12.
5. ↑ Zaitsev D. A. Arkistoitu kopio 1. huhtikuuta 2022 Wayback Machinessa , Shmeleva T. R. Hyperkuution viestintärakenteiden verifiointi parametrisilla Petri-verkoilla, Cybernetics and System Analysis, nro 1, 2010, s. 119-128.

Kirjallisuus

• Peterson J. Petri-verkkojen teoria ja järjestelmämallinnus. - M .: Mir, 1984. - 264 s.
• Kotov V.E. Petri verkot. - M .: Nauka, 1984. - 160 s.
• Sleptsov A. I., Yurasov A. A. Joustavan automatisoidun tuotannon ohjausjärjestelmien suunnittelun automatisointi / B. N. Malinovsky. - Kiova: Teknika, 1986. - 160 s.
• Achasova SM, Bandman OL Rinnakkaisten laskentaprosessien oikeellisuus. - Novosibirsk: Nauka, 1990. - 253 s.
• Marakhovsky V. B., Rosenblum L. Ya., Yakovlev A. V. Rinnakkaisten prosessien simulointi. Petrin verkot. Kurssi järjestelmäarkkitehdeille, ohjelmoijille, järjestelmäanalyytikoille, monimutkaisten ohjausjärjestelmien suunnittelijoille . - Pietari: Ammattikirjallisuus, IT-valmistelu, 2014. - 400 s.

Linkit

• Koulutuskurssi MSTU. Bauman "CAD:n perusteet. Mallintaminen". Petri verkot . Petri-verkkojen analyysi
• Petri-verkot Automaatio- ja ohjausprosessien instituutin sivuilla.
• Petri-verkkoja ja tiukasti hierarkkisia verkkoja toteuttavien malliohjelmien lähdetekstit .