2004 tavaszi Form ZH megoldása

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.

1.1

1.1-1.

1. IGAZ - egyedül a hurokélek okoznak gondot, egy szomszédossági mátrix számára ezek láthatatlanok
2. HAMIS - annyi sora van ahány TRANZÍCIÓ van és annyi oszlop ahány HELY (az élek száma nem is határozható meg egyértelműen a mátrixból - lásd hurokélek - ha ezek nincsenek, akkor a mátrix elemeinek abszolutértékes összege az élek száma)
3. HAMIS - a w(p,t) elem a tranzíció tüzelése által az adott helyre rakott/helyről elvett tokenek száma
4. IGAZ - nem csak korlátos hálóra igaz, de ez nem is számít

1.1-2.

1. HAMIS - lehet h rossz sorrendben deadlockba kerül a hálózat
2. HAMIS - lehet h más sorrendben tüzelve tokeneket termel a hálózat
3. IGAZ - mivel élő, ezért minden t tranzíció L1 élő bármilyen állapotból, ezért végig tudunk menni minden t tranzíción (mégha közben egyik-másikat többször is érintjük), és előbb utóbb vissza is jutunk egy olyan állapotba, ahol már jártunk (és onnantól volt már mindegyik tranzíció..) - ezt tudja vki egyszerűbben elmagyarázni?
4. HAMIS - ha ez az egyetlen T-Invariáns, akkor miért ne?

Példa /a-ra és /b-re:

Ezen a helyen volt linkelve a 1.1-2.a.JPG 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)

Itt t1-t2-t3 tüzelés minden tranzíciót lefed és visszatérünk a (3,0,0) kezdőállapotba, DE:

1. esetben a t1-t1 tüzelés után deadlock van
2. esetben t2-t2-t3 után határozottan nő a tokenek száma

1.1-3.

1. HAMIS - attól h van egy helyünk, ahol végtelen sok token van, simán lehet h egy másik tranzíció tüzelése az egészet megakasztja
2. HAMIS - a nem tüzelhető T-invariánsokat nem lehet leolvasni, sőt sem a háló, sem a mátrix nem konstruálható vissza a fedési gráfból
3. HAMIS - minden állapotnak meg kell jelennie a fedési gráfban, amit a háló elérhet
4. IGAZ - bár nem értemi miért kell kikötni h véges..

Ellenpélda /a-ra:

Ezen a helyen volt linkelve a 1.1-3.a.JPG 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)

Itt t1 tüzelhet amíg kedve tartja, így p1-ben végtelen sok számú token is lehet-> w megjelenik a fedési gráfban, DE ahogy t2 tüzel, t1 letiltódik és vége a mókának.

Ellenpélda/b-re:

Ezen a helyen volt linkelve a 1.1-3.b.JPG 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)

Itt a fedési gráf (0,0,0), de a t1-t2-t3 T-invariánst alkotnak, csak éppen nem végrehajthatók ebből a kezdőállapotból.

1.1-4.

1. IGAZ - definíció szerint, Alosztályok.ppt 23.dia
2. HAMIS - ha nem erősen összefüggő, simán lehet halott is az egész hálózat
3. IGAZ - mivel nincs forrástranzíció, és egy tranzíció sem termel tokent, végtelen nem jelenhet meg a fában --> véges
4. IGAZ - ha élő, akkor erősen összefüggő -> a kezdőállapot ismét elérhető (van irányított út) -> megfordítható

Ellenpélda /b-re:

Ezen a helyen volt linkelve a 1.1-4.b.JPG 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)

1.1-5.

N/A

1.2

1.2-1.

Free Choice, SM nem lehet mert van olyan tranzíció amiből több él indul ki, MG nem lehet mert pl p2ből több él indul ki, viszont egy helyből vagy csak egy él indul ki vagy ha több él, akkor mindegyik ezek közül egyedüli bemenő éle annak a tranzíciónak, ahova befut. Huhh. :)

1.2-2.

Marked Graph, mert minden helynek pontosan egy be- és kimeneti éle lesz.

1.2-3.

Élő, mert erősen összekötött és biztos, mert minden körön csak egy token van.

1.3

1. HAMIS - 210 halott állapot, emiatt az egész háló nem lehet élő.
2. HAMIS - 210 ben van egy elég nagy deadlock
3. IGAZ - a háló eljuthat a (1w1)-(211)-(110) ciklusba, itt pedig végtelen sokszor tüzelhet t6.
4. HAMIS - t7 tranzíció csak egyszer tüzelhet, L1 élő
5. IGAZ - létezik (22w) állapot a gráfban, ami fedi (221)-t
6. IGAZ - a (211) állapot fedi a (210) állapotot
7. HAMIS - (010)-ból ha t1 tüzel, t4 letiltódik, így a háló nem lehet perzisztens
8. HAMIS - megjelenik w az állapotokban
9. HAMIS - sajnos egyetlen állapotból sem érhető el újra a kezdőállapot, nemhogy mindegyikből...
10. HAMIS - mivel a háló nem korlátos, nincs olyan súlyfv, amire állandó lenne a súlyozott tokenösszeg
11. IGAZ - van legalább két ciklus is, az egyiket lásd a c. pontnál
12. HAMIS - minden állapotból elérhető az ominózus (210), innen viszont egyik másik sem (apropó, ugye ilyenkor 210 visszatérő?!)
13. IGAZ - minden ciklusban amiben t4 előfordul, ott van t6 is: (1w1)-(211)-(110) és (121)-(22w)-(122)
14. HAMIS - a (1w1)-(211)-(110) ciklusban van t5 de nincs t8

2.1

2.1-1.

B a helyes. Aki nem hiszi, járjon utána :)

2.1-2.

Martinez-Silva:

1	0	0	0	0	-1	1	0	1	0	-1
0	1	0	0	0	1	-1	-1	0	0	0
0	0	1	0	0	1	0	-2	0	0	0
0	0	0	1	0	0	2	0	0	0	-3
0	0	0	0	1	0	0	1	-1	0	1
első fázis
1	1	0	0	0	0	0	-1	1	0	-1
1	0	1	0	0	0	1	-2	1	0	-1
második fázis
1	1	0	0	1	0	0	0	0	0	0

és kész is, innen egyedül csak a

p1+p2+p5 a helyes... de... ilyen mo. meg nincs ?!

-===2.1-3.===

1	0	0	0	0	0	-1	1	1	0	0
0	1	0	0	0	0	1	-1	0	2	0
0	0	1	0	0	0	0	-1	-2	0	1
0	0	0	1	0	0	1	0	0	0	-1
0	0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	1	-1	0	0	-3	1
első fázis
1	1	0	0	0	0	0	0	1	2	0
1	0	0	1	0	0	0	1	1	0	-1
0	1	0	0	0	1	0	-1	0	-1	1
0	0	0	1	0	1	0	0	0	-3	0
második fázis
1	0	1	1	0	0	0	0	-1	0	0
1	1	0	1	0	1	0	0	1	-1	0
harmadik fázis
2	1	1	1	0	0	0	0	0	2	0
2	1	1	2	0	1	0	0	0	-1	0
negyedik fázis
6	3	3	5	0	2	0	0	0	0	0

vagyis T-Invariánsok:

(6,3,3,5,0,2) és (0,0,0,0,1,0)

a helyes válasz: D

2.1-4.

Élő, ha p1-ben vagy p2-ben van token, akkor a t1 és t2 tranzíciókkal egymásnak passzolgatják, és közben feltöltik p3 és p4 helyeket a végtelenségig, ezekből meg akkor tud tüzelni a t3 és t6 is (elveszik ekkor p1ből ill. p2ből a tokent), és ilyenkor egy darab token kerül p5-be. Ekkor t5 is tud tüzelni, majd t4-el visszakerül p4-be a token és az egész móka kezdődik előlről. Összefoglalva: ha p1 ben vagy p2 ben vagy p5 ben van token, akkor a háló élő, és ez igaz a kezdeti tokeneloszlásra.. (tud valaki valami frappánsabbat?!)

2.1-5.

Nem: p3 és p4 tokenjeinek száma korlátlanul nő, ha t1 és t2 felváltva tüzel.

2.2

Nagyon remélem ez mindenkinek megy ^_^

2.3

2.3-1.

A lift megérkezett a kívánt emeletre.

2.3-2.

Hiányzó élek:

• p2->t5 (z)
• p2->t4 (x,z)
• t3->p2 (x,z)
• t4->p2 (x,z)

2.3-3.

A kifejezés: (x,Inc(y))

2.3-4.

Ha a lift nem a földszinten állt meg, automatikusan lemegy a földszintre.

-- RGabo - 2006.04.02.