Petri Hálók

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

%TOC{depth="2"}%

Elmélet

1.

Petri hálók diagnosztikai alkalmazásában a háló milyen (strukturális/dinamikus) tulajdonságát használjuk fel a megoldások keresésében és milyen a hipotézisekre vonatkozó konzisztencia kritériumokat alkalmazunk?
A T-invariánsokkal maszatolunk, de hogy itt konkrétan milyen tulajdonságokra gondol, az jó kérdés. A konzisztencia kritérium azt jelenti, hogy csak azokat a hipotéziseket fogadhatjuk el, amelyek konzisztensek a megfigyeléseinkkel. Kétféle diagnózis van, a konzisztencia bázisú, illetve az abduktív. Konzisztenciabázisúnál csak az a követelmény, hogy a hipotézisből ne következzen semmi olyan, ami a megfigyeléseinkkel ellentétes, míg abduktívnál a hipotézisből direktben következnie kell mindennek, amit megfigyeltünk. Vagyis kétféle konzisztencia feltétel van (Ψ⁺ és Ψ^- halmazok), az egyikre abduktív, a másikra konzisztencia bázisú a követelmény.

2.

Színezett Petri hálókban értelmezhetjük-e a T-invariáns fogalmát? Ha igen, mi a különbség a színezetlen Petri hálókhoz képest? Ha nem, mi az elvi szabály?
Igen, értelmezhetjük. Hogy mi a különbség? Rendes PN-ben tudjuk mi a T-invariáns. Színezettben ezzel szemben:

Ezen a helyen volt linkelve a t-inv.PNG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

3.

Petri hálónál ismétlődés (ismételhetőség) statikus v. dinamikus tulajdonság? Mi a (részleges) ismételhetőség feltétele, hogyan fejezhető ki a szomszédossági mátrixszal? (2p)
Statikus. Egy N Petri háló (részlegesen) ismételhető, ha létezik olyan M₀ kezdőállapot és M₀-ből induló σ tüzelési szekvencia, hogy minden (néhány) t ∈ T tranzíció végtelen sokszor tüzel σ-ban

4.

Mi a színezett Petri hálóban az őrfeltétel definíciója? A CPN mely eleméhez kapcsolódnak, hogyan értékelhetők ki, hogyan befolyásolják a háló működését? (2p)
Az őrfeltételek, vagy angol nevükön guard kifejezések a tranzíciókhoz tartozó, multi-halmazokon értelmezett logikai kifejezések. Az őrfeltétel nem teljesülése (a logikikai kifejezés kiértékelésekor kapott hamis eredmény) az adott tranzíció engedélyezettségének megvonását eredményezi. Kiértékeléskor a nyílt kifejezésben szerepló változókat a bemenő helyeken levő tokenek segítségével az összes lehetséges módon lekötjük, majd ezeket kiértékeljük, ha valamelyik lekötéssel az őrfeltétel igazzá válik, a tranzíció engedélyezetté válhat az adott lekötéssel.

5.

Mit tudunk egy korlátos Petri háló P- és T-invariánsairól?
Úgy véljük, semmit. Íme egy példa KÉP, ami korlátos és nincs neki se P se T invariánsa. Ugyanakkor másik példa is adható, aminek meg van P és T invariánsa, és korlátos.

6.

Mit jelent a Petri háló alosztályok kapcsán definiált asszimetrikus konfúzió fogalma?
Konfúzió: konkurens és konfliktusos. Asszimetrikus konfúzió: tüzelési szekvenciától függ, hogy konkurens és konfliktusos-e.

7.

Definiálható-e a színezett Petri hálókra az invariánsok fogalma? Ha igen, hogyan? Ha nem, miért nem?
Hát nyilván igen, mert vannak a slideokon, meghát ha kiterítjük sima PNné arra értelmezhető, akkor nyilván az eredeti szinesben is kell megfelelője legyen. De a hogyanra nem nagyon volt semmi irva. Annyi hogy hasonlóan mint a programok invariánsai (??) és a P-invre volt néhány példa hogy a M(P1)+M(P2)..... = token vagy tokenhalmaz. Annyi nehézséget jelent a T invariáns, hogy az azonos szinű tokenek még lehetnek különbözőek, ha az attribútumaik különböznek, míg a fekete-fehér PN-nél ez nem volt gond.

8.

Milyen kapcsolatban van egymással a Petri hálók élő és deadlock-mentes tulajdonsága?
L4 élő == élő => deadlock-mentes.

9.

Számítási komplexitás szempontjából melyik analízis módszer rendelkezik kedvezőbb tulajdonságokkal és miért: az elérhetőségi analízis vagy az invariáns analízis?
Elérhetőőség: exponenciális, invariáns: $O(n^{2})$ -es, tehát az invariáns

10.

A Petri hálók diagnosztikai alkalmazása melyik analízis módszeren alapul és miért pont azon?
A hibaterjedési mechanizmusokat (hiba, hibaállapot, szindróma) vizsgáljuk, és ehhez a T invariánsokra van szükség.

Igaz/Hamis

Igaz/ Hamis?	Kérdés	Magyarázat
Igaz	Ha egy PN biztos akkor egyúttal korlátos is..	Az egy korlátos PN-t nevezzük biztosnak.
Igaz	Ha egy PN megfordítható akkor tetszőleges M eleme R(N,M0) állapot visszatérő..
Igaz	Perzisztens PN-ben egy engedélyezett átmenet mindaddig engedélyezett marad, amíg nem tüzel..
Igaz	Ha egy PN élő akkor nincs benne olyan (nem izolált) hely amelyben egyetlen állapotban sincs token.
Igaz	Egy rendszer elérhetőségi gráfjának és fedési gráfjának topológiája csak akkor nem azonos, ha az w (omega) megjelenik állapotcímkeként.
Igaz	Ha egy tranzíció L3 élő akkor L2 élő és L1 élő is.
Igaz	A prioritás megőrzi a szinteken belüli nemdeterminizmust.
Igaz	Ha egy Petri háló megfordítható, akkor biztosan van legalább egy L3-élő tüzelése.
Igaz	Ha egy (N, M0) állapotgép élő, akkor N biztosan erősen (szigorúan) összefüggő, és M0-ban van legalább egy token.
Igaz	Az elérhetőségi gráfban (w) omega akkor jelenik meg címkeként, ha a tokenek száma minden határon túl nőni kezd.
Igaz	Az elérhetőségi gráf szélességi típusú bejárása a tranzíciók tüzelése mentén építi fel az állapotteret.
Igaz	Véges kapacitású Petri háló átalakítható kapacitáskorlát nélküli Petri hálóvá.	Az adminisztratív helyek bevezetésével.

Igaz	Nem korlátos Petri-hálóban nem létezhet minden helyet lefedő P-invariáns.	Ha a token szám a végtelenségig nő, azt akárhogy súlyozzuk, sose lesz annyi, mint a kezdőeloszlásban..
Igaz	Kiegészítő hely-transzformációval megvalósított kapacitáskorlátos hálóban a kapacitásos helyet és a hozzá tartozó adminisztrációs helyet lefedi egy P-invariáns.	Hisz az adminisztratív helyben annyi token van, amennyi felhasználatlan kapacitás, így a két helyben összesen annyi token van, mint az eredeti hely kapacitás korlátja.
Igaz	Ha egy háló L3 élő, akkor van benne L1 élő tranzíció.	Minden tranzíció L3 élő, ami magában foglalja az L1 élőséget is.
Igaz	Ha egy tranzíció halott, akkor nem jelenik meg a háló fedési fájában.
Hamis	Ha egy PN valamelyik állapota fedhető, akkor az már biztosan nem lehet visszatérő állapot.
Hamis	Ha egy helyből csak egy kisebb és egy nagyobb prioritású időzítetlen tranzícióba vezet él, akkor a kisebb prioritású tranzíció sosem lesz engedélyezett.	P. Ha a nagyobb prioritásunak nem teljesülnek az egyéb tüzelési feltételei.
Hamis	A tranzíció engedélyezett, ha létezik legalább egy olyan bemenő él, amelynek súlya nem több, mint az élhez kapcsolódó bemeneti helyen levő tokenek száma.
Hamis	A kimeneti helyek kapacitáskorlátja csak a tüzelés végrehajthatóságában játszik szerepet, az átmenet engedélyezettségében nem.
Hamis	Az elérhetőségi gráfban minden egyes él egyéni címkét kap.
Hamis	Egy élő PN elérhetőségi gráfja minden esetben tartalmaz legalább egy szigorúan összekötött komponenst.
Hamis	Az elérhetőségi gráf önmagában nem alkalmas egy véges állapotú rendszer élőségének bizonyítására. (feltéve, hogy M0 is adott).
Hamis	Ha egy PN L4 élő akkor korlátozottan fair (B-fair) is.	Az élőség nem biztosítja, hogy egy tranzíció valaha tüzelni fog..
Hamis	Ha egy PN-nek adott kezdőállapotból elindítva létezik L3 élő tüzelése akkor az L3 élő.	Az összes tranzíciónak L3 élőnek kell lennie ehhez.
Hamis	Egy élő PN P-invariánsai minden esetben lefedik a háló összes helyét.
Hamis	A prioritási szintek bevezetése a Petri hálókban nem módosítja a tüzelési feltételt.
Hamis	A prioritási szintek fogalma csak színezett Petri hálók esetén értelmezett.
Hamis	A prioritási szintek bevezetése módosíthatja a háló kezdő token eloszlását.
Hamis	Egy forrás vagy nyelő tranzíciót tartalmazó Petri háló csak akkor lehet élő és biztos, ha az elérhetőségi gráfja erősen összefüggő.	forrást és nyelőt ugyanis nem enged meg a szigorú összekötöttség!)
Hamis	Ha egy Petri hálónak van legalább egy L3-élő tüzelése, akkor a háló biztosan L2-élő is.
Hamis	Egy M állapotból kiindulva az elérhetőségi gráfban pontosan annyi rákövetkező csomópont található, amennyi az M állapotban engedélyezett tranzíciók száma.	(Lehet kevesebb is. Mondjuk ha két hely van, egyikből a másikba két különböző nevű tranzíción keresztül is lehet tüzelni. És a kezdőállapotban az első helyen van egy token. Ekkor az elérhetőségi G-ben M0-ből két él vezet a köv (1db) állapotba. tehát: nem pontosan hanem legfeljebb annyi rákövetkező! )
Hamis	Az állapotegyenlet csak az elérhetőségi gráf segítségével oldható meg, és csak exponenciális komplexitású algoritmus létezik hozzá.
Hamis	A prioritásos Petri hálók esetén a tranzakciók tüzelési sorrendje minden esetben determinisztikus.	Prioritási szinteken belül továbbra is nemdeterminisztikus.
Hamis	Erős és gyenge tüzelési szabály közt az a különbség, hogy az erős figyelembe veszi a tranzíciók prioritását, míg a gyenge nem.	Az erős figyelembe veszi a helyek kapacitás korlátait.
Hamis	Véges kapacitású Petri hálóban egy tranzíció mindig tüzelhet, ha az összes bemeneti helyén a bemenő éleknek megfelelő számú token van.	Az erős tüzelési feltétel szerint a kimenő helyek kapacitás korlátaira is figyelni kell.
Hamis	Ha egy hálóban vannak L0 élő (halott) tranzíciók, akkor a hálóban van deadlock.
Hamis	Ha létezik minden állapotot lefedő P-invariáns, akkor a háló nem lehet halott.
	Az állapottérben ciklikus működésű rendszerben biztosan található T-invariáns.
	Egy háló élősége egyértelműen megállapítható pusztán a T-invariánsok alapján.

TODO: powered by OmniPage OCR
Formázást javítottam, a spell check még hátravan -- Peti - 2007.06.26.

1.1-1. Mely állítások igazak a P-invariánsra?

1. Ha a P-invariánsok nem fedik lc háló minden egycs helyet. akkor a háló nem korlátos.
2. Ha egy Petri hálóban a helyek egy reszhalmazában a tokenek száma egy (végtelen)

tüzelési szekvenciában állandó, akkor biztosan létezik berme legalább egy P-invarians.

1. Pusztán a fedési grid- ismeretében nem hatarozhato meg egy Petri hálo minden P-invariánsa.
2. Kizárólag a szomszedossagi matrix ismerete alapjan meghatározhatók a halo P-invariánsai.

pont hamis

1.1-2. Mely állitások igazak az alábbi, korlatossággal, élőségi, illetve deadlockmentességgel kapcsolatos állitások közül? (12 pont)

1. Egy korlatos, éle, visszatérő állapottal rendelkező Petri hálóra igaz,

hogy minden tranziciója tüzelhető valamely visszaterö al lapotban.

1. Ha minden helyre igaz, bogy a szomszedossagi matrixban a hozzá tartozó sorban (esztepban)

az elemek összege 0, akkor a háló korlátos.

1. Egy adott kezdojeloles mellett deadlockmentcs halo L1-élő.
2. Ha egy (N,Mo) Petri haló minden tranzicioja vegtelen sokszor előfordul valamely L(N,Mo)

tüzelési szekvenciaban, akkor biztosan nines benne deadlock.

1.1-3. Mely állítások igazak tranziciók engedélyezettségére, illetve tüzelhetősegére?

1. Egy biztonságos Petri haloban egy tranzicio engedelyezett, ha minden bemeneti helye jelölt.
2. Ha egy helyböl egy kisebb es egy nagyobb prioritise időzítetlen tranzicioba egyarant vezet el,

akkor bármely tokeneloszlas eseten a nagyobb prioritású tranzició tüzel.

1. Ha egy tranzició adott tokeneloszlas esetén engedelyezett, akkor minden ebbol a

tokeneleszlasból tüzelhető tranzíció-szekvenciában a a tranzició tüzelhető.

Példák

-- adamo - 2006.06.10. -- András - 2006.06.13. -- Gegman - 2009.01.21.