2006. január 18. vizsga
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
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
Tartalomjegyzék
2.5 Feladat
Az eredeti példaábra:
Az egy gráftranszformáciüs lépéssel elérhető modellek, piros a régi elemeket jelöli, a zöld az újakat:
2.5.1
Az egyes gránsztranszformációs szabály az eredeti modell "bal" és "jobb" oldalára is illeszthetjük, ennek az eredménye az első két ábra.
A kettes szabály sehol sem alkalmazható, mivel nincs olyan place, amihez kapcsolodik person is meg gift is (gondolom az a P person akart lenni...)
A harmas szabalynal csak egy olyan place van, amihez kapcsolodik box, de gift nem, ezt az illesztest mutatja a harmadik abra.
2.5.2
Az egyes szabaly ket illesztesi lehetosege (jobb ill baloldali illesztes) kolcsonosen kizarja egymast, mivel a kozepso P1 place-tol elveszik a persont, igy a masik mar nem fog illeszkedni.
Egyes szabaly utan csak akkor alkalmazhatjuk a kettest , ha az elso szabalyt a modell bal oldalra illesztjuk, es csak ekkor kerul egy place-hez egy gift es egy person
Egyes szabaly utan a harmas alkalmazhato: ha az egyes szabalyt a bal oldalra illesztjuk, akkor a P4 es P3 helyre is illesztheto lesz a harmas, de ha jobb oldalra illesztjuk, akkor az az eredetileg jo P3 helyet elrontja es uj jot sem hoz letre, tehat ezutan nem johet a harmas
Kettes szaballyal nem kezdhetunk, lasd elozo 2.5.1es feladat.
Harmas utan egyes alkalmazhato: a P3ra illeszkedo harmas szabaly alkalmazasa utan az egyest az abra bal oldalara minden tovabbi nelkul illeszthetjuk, de a jobb oldali illesztest elrontja a harmas a box giftre valo cserejevel.
Harmas utan kettes : ugyan a harmas utan a P3 helynel lesz gift, de nem lesz person, igy nem alkalmazhato.
Harmas utan harmas : mivel csak a P3ra illesztheto a harmas, sajat lehetoseget rontja el, tehat nem illesztheto.
Osszefoglalva, a fuggetlen graftranszformacios lepesek: csak a bal oldalra illesztett egyes es a harmas fuggetlen egymastol, mivel ebben az esetben a sorrend mindegy, minden mas esetben az egyik szabaly nem alkalmazhato.
2.6 Feladat
Adottak az alábbi logikai függvények: (sum 6p)
[math] f := \neg(y \vee x) \vee (\neg x \wedge z ) [/math]
[math] g := (\neg z \vee \neg y ) \wedge ( x \vee \neg z ) [/math]
[math] m := f \wedge g [/math]
2.6.1 Határozza meg az f, g, m logikai függvényeket ROBDD alakban! Az m függvény kiszámítását közvetlenül az ROBDD-ken értelmezett műveletekkel végezze el! Az m függvénynek az f és g függvények ROBDD-jéből történő kiszámítása is kell!
Először is átalakítjuk az első kifejezést a De Morgan szabállyal, hogy rendes konjunktív alakban legyen, mert úgy kisebb ROBBD ábrát kapunk majd. Ekkor tehát [math] f := ( \neg y \wedge \neg x ) \vee ( \neg x \wedge z ) [/math]
A ROBDD redukált és rendezett a változók sorrendjét tekintve, ezért keresnünk kell egy olyan változósorrendet, amelyet mindkét, az f és a g ROBDD diagramjában is használni fogunk, és lehetőleg minél kisebb méretű gráfot eredményez. Nyilván akkor lesz a gráf kisebb, ha elsőnek olyan változó szerint vizsgáljuk, amely közvetlen levélbe vezet, vagyis ahol egy változó alapján dönteni tudunk, hogy a kifejezés értéke igaz lesz, avagy hamis.
Ilyen pl. f esetében az x, hiszen annak 1 értéke esetén egész biztosan hamis lesz a kifejezés értéke. Igen ám, de ez g-ben nem teszi lehetővé rögtön a döntést, mert x igaz és hamis volta még nem határozza meg egyértelműen a g kifejezés logikai értékét. Itt a z változó volna a nyerő, hiszen annak hamis értéke esetén a g kifejezés biztosan igazra értékelődik ki.
Y egész biztosan nem jó választás kezdő változónak, hiszen az eredményezné mindkét esetben a legnagyobb döntési fát!
A feladat innentől tehát kétféleképp megoldható, ám tudnunk kell, hogy bármely megoldási utat választjuk is, az egyszerűsítések után a végeredmény egyértelmű kell, hogy legyen, hiszen minden logikai kifejezéshez, és így f-hez, g-hez és a kettejük konjunkciójának (azaz m-nek) is pontosan egy-egy ROBDD gráf feleltethető meg.
Válasszuk most első változóként az x-et, második nyilván a z lesz (hiszen az y-nal továbbra is csak felesegesen növelnénk a fát), a harmadik pedig az y.
F, G előállítása:
A ROBDD előállítása úgy történik, hogy vesszük az első változót, és behelyettesítünk a kifejezésbe először 0-t (baloldali ág), majd 1-et (jobb oldali ág), és megnézzük mi az eredmény. Ha egyből ki tudjuk értékelni a logikai kifejezést, mint pl. az f kifejezésben x=1 esetén a jobb ágon, akkor örülhetünk, mert azt nem kell tovább vizsgálni. Ha nincs így, akkor vesszük a fentebb meghatározott sorrend szerinti következő változót, és elvégezzük ugyanezt a vizsgálatot. A fa legfeljebb 3 mélységű lehet, hiszen 3 változónk van, és legrosszabb esetben egy 3 mélységű teljes fát kaphatnánk, ha a lehető legrosszabb sorrendbe állítottuk volna fel a változókat. Így azonban a 2^3 csomópont helyett mindössze 5-öt kaptunk az f kifejezésre, tehát jól látszik, hogy valóban sikerült tömörítenünk a kifejezést (ti. az igazságtábla 2^3=8 elemet tartalmaz, mi pedig 5 csomóponttal leírtuk ugyanezt a függvényt).
A G ROBBD-jének előállítása hasonlóan történik, az első ábrát nyomon követve látható, hogy x=1, z=1 esetén még mindig nem tudunk dönteni a kifejezés logikai értékéről, csak y kiértékelése után.
m = f /\ g előállítása:
Ha megvan a két ROBDD, és a kettőnek a gyökértől számítva azonosak a változók sorrendjei, akkor a két gráf csomópontjainak direkt szorzatát véve (lásd formális nyelvek: két nyelv metszete = véges automaták állapotainak direkt szorzata) éppen a kívánt BDD-t kapjuk, ami viszont sajnos még egyszerűsítésre szorul.
A direkt szorzat képzése szemléletesen úgy működik, hogy vesszük mindkét ROBDD gyökerét, és rátesszük az ujjunkat. Aztán mindkét ROBDD-n nyomon követjük a változók értékadását: az első, majd második stb. változó 0 illetve 1 értéke esetén hova kerülünk F ill. a G ROBDD-jében, és ezeket egy közös változónévpárral jelölt csomópontba felírjuk.
Pl. a kezdő (X,X - melynek jelentése X változót vizsgáljuk az F ROBDD-jében, és szintén X változót a G ROBDD-jében) változópár vizsgálatakor x=1 hatására a (0,z) párt kell vizsgálnunk, hiszen az F ROBDD-jében x igaz esetén már biztosan hamis lesz a kifejezés értéke, míg G ROBDD-jében a z vizsgálatára térünk át. Ha mindkét ROBDD-ben levélhez, azaz 0,0 0,1 1,0 vagy 1,1 -hez értünk, akkor azt az ágat nem kell tovább vizsgálni, hiszen az alapján már el tudjuk dönteni a két kifejezés között értelmezett műveletet, azaz jelen esetben, mivel a feladat m = f /\ g -t kérdezi, az ÉS műveletet.
Az egyszerűsítés folyamata, eredmény ROBDD előállítása:
- Ha x változónak 0 és 1 értéke esetén is ugyanazon y változó vizsgálatára térünk át, azaz a kifejezés értéke az x változótól független, akkor x-et egyszerűen elhagyhatjuk a BDD-ből (x szülőjéből a nyíl a gyerekébe, azaz y-ba mutat, őt magát pedig törölhetjük)
- Ha a BDD-ben van több ugyanolyan címkéjű csomópont, azokat összevonhatjuk, természetesen megtartva a kimenő/bemenő nyilakat.
A példánkban (lásd 2. ábra) a nagy karikával jelölt rész helyére 0-t írhatunk, hiszen minden részfája hamis eredményre vezet. Vigyázat: ha pl. nem m = f /\ g, hanem m = f \/ g lenne a feladat, akkor nem hagyhatnánk el ezt az egész részfát, hiszen a jobb alsó részen 0,1 és 0,0 nem lenne azonos! Tudniillik 0 /\ 1 = 0, 0 /\ 0 = 0, azonban 0 \/ 1 = 1, 0 \/ 0 = 0.
Ezenkívül összevonhatunk minden =0 -val jelölt levelet, valamint ha több is lenne, akkor az =1 -gyel jelölt leveleket is.
Végül egyszerűsítsük a csomópontok címkéit, és csak a változók neveit tüntessük fel egy példányban, a vessző utáni másik változónevet / logikai konstanst nem szükséges kiírni. A végeredmény, azaz az f és g kifejezések konjunkciójának megfelelő ROBDD gráf a 3. ábrán látható.
-- NeoXon - 2006.05.28.
