Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
mal wieder ROBBDS und der verdammte Shannon
Hi Leuts!
Also ich hab folgendes Prob: ich kann zwar aus nem ausdruck den baum zeichnen , aber ich weiss nicht wie des mit dem shannon hinzukriegen sein soll. ich glaub ich vertu mich da immer wegen der variablenordnung … da kommen naemlich immer entweder sachen raus die noch reduzierbar sind oder der ausgangsausdruck verzweifel
Kann mir jemand anhand des Beispiels
(X1X4 + X1X2*X3) Variablenordnung : X4<X1<X2<X3
mal zeigen wie der shannon funzt ? das waere echt net, auch im hinblick darauf dass in der klausur ja leider nicht einfach der robbd verlangt wird sondern auch die entwicklung oder gar eine reduktion des ganzen mit dem angeblich (!!!) besprochenen Algorithmus. Also entweder hab ich vielzuviel party gemacht oder wir haben des net gehabt (den algorithmus mein ich)
Dangge im Vorraus!
fredator
F[SUB]|x4=1 [/SUB] = x1 + x1x2x3
F[SUB]|x4=0 [/SUB] = x1x2x3
F[SUB]|x4=1,x1=1 [/SUB] = 1
F[SUB]|x4=1,x1=0 [/SUB] = 0
F[SUB]|x4=0,x1=1 [/SUB] = x2*x3
F[SUB]|x4=0,x1=0 [/SUB] = 0
F[SUB]|x4=0,x1=1,x2=1 [/SUB] = x3
F[SUB]|x4=0,x1=1,x2=0 [/SUB] = 0
F[SUB]|x4=0,x1=1,x2=1,x3=1 [/SUB] = 1
F[SUB]|x4=0,x1=1,x2=1,x3=1 [/SUB] = 0
Schau dir dazu auf jeden Fall auch mal die Probeklausuren mit Musterlösung an. Da ist bei der robdd-Aufgabe eine Automatentabelle, die du ähnlich auch für eine solche Funktion bauen kannst. Du schreibst halt alle Kombinationen auf für die die Funktion eine 1 ergibt, die Spalten in der Reihenfolge der Variablenordnung. Dann ist das robdd-erstellen nicht mehr schwer. Im Beispiel:
x4 x1 x2 x3
0 1 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1Das robbd wird dann genauso erstellt wie in der Musterlösung. Ich glaub auch nicht, dass eine so komplexe Aufgabe drankommt dass das zu schwierig wird. Korrigiert mich bitte wenn ich falsch liege.
das schaut irgendwie einerseits recht verwirrend aus, andererseits könnte es diese seltsame F|X…*** formulierung irgendwo im skript erklären…
also wir hatten das so in der übung:
(links 1, rechts 0)
t: X4 → t1, t0
t1: X1 → 1, t10
(…)
t0: X1 → t01, 0
(…)
das gleiche findet man auf der otrs-homepage unter übungen, als musterlösung zur aufgabe 7. naja, ich komm zumindest auch auf einen ROBBD. denke, so falsch kann das dann gar nicht mehr sein 
@yves das ist shannon? oh dann hab ich den ja schon dauernt benutzt nur net gewusst wie das heisst 
Drager
hmm, das wär ein interessanter ansatz
ich hab ehrlich gesagt so direkt keine ahnung, was shannon oder sein entw.satz ist, diese t-schreibweise ist eben das ähnlichste, was mir zu dem obigen beitrag eingefallen ist.
wobei die weise, jedes mal den aktuellen (rest-)ausdruck hinzuschreiben vielleicht doch mal etwas übersichtlicher ist?
Könnte mal einer diese dumme ROBDD hier reinzeichenen, irgendwie bekomm ich des nämlich nie gebacken!!! Hoffe nur das er die ROBBD auslässt, die brechen mir sonst echt den Hals!
ich glaub leider , dass du mit ziemlicher wahrscheinlichkeit von ROBBDS in der pruefung ausgehen kannst …
so ich muss des etz mal nachrechnen
@tsunami: hm ich glaub ich hatte doch richtig mit dem shannon rumgedocktert aber irgendwie der baum der dabei rauskommt ist fuer mich nicht logisch: d ahaben wir ja erst mal den ausgangsausdruck stehen … und dann hat x4 und (not x4) den nachfolgeknoten x1 … ??? vor allem wuerde mich interessieren was ich dann tun soll ???
gruss fred
ich hab die Aufgabe von oben jetzt mal kurz nachgerechnet…
Ausdruck: X[sub]1[/sub]X[sub]4[/sub] + X[sub]1[/sub]X[sub]2[/sub]X[sub]3[/sub]
Reihenfolge: X[sub]4[/sub] < X[sub]1[/sub] < X[sub]2[/sub] < X[sub]3[/sub]
t-Schreibweise:
t: X[sub]4[/sub] → t[sub]1[/sub], t[sub]0[/sub]
t[sub]1[/sub]: X[sub]1[/sub] → 1, 0
t[sub]0[/sub]: X[sub]1[/sub] → t[sub]01[/sub], 0
t[sub]01[/sub]: X[sub]2[/sub] → t[sub]011[/sub], 0
t[sub]011[/sub]: X[sub]3[/sub] → 1, 0
Der ROBDD sieht bei mir dann so aus:
ja genau… meiner sieht genauso aus.
Im übrigen denke ich, dass die Shannon-Methode (die Variablen der Ordnung nach durchgehen und mit Werten im Audruck belegen) und der Algorithmus mit den t´s das selbe in grün ist…
@fred: versuch´s nochmal… der robdd is der gleiche egal nach welcher Methode. WIE man genau den robdd aus diesen Algorithmen erhält lässt sich hier durch Aufsätze schlecht erklären… 
das müsste dir halt mal einer vormachen…
Hilfe! Was soll ich den damit anstellen? :wand:
Das ROBBD von Yves bekomme ich eigentlich direkt wenn ich versuche den Ausdruck X4X1 + X1X2X3 zu zeichnen.
Aber eigentlich sollte ich das doch aus der Umformung oben erhalten, oder?
hm … also ich glaub es geht jetzt… einziges offenes problem ist die tatsache dass x4 sowohl im 0 als auch im 1 zweig auf x1 zeigt.
hiess es nicht wenn ein knoten den selben 0 und 1 nachfolgeknoten hat ist er redundant ? wenn ich dann von x4 aus auf x1 schau dann hab ich doch sowohl fuer x4=1 wie x4=0 x1 … aber kann dann x4 als wurzel des baums ueberhaupt redundant sein ??? ich weiss eben nicht genau
aber logisch ueberlegt: egal welchen wert unsere wurzel hat … der nachfolger x1 entscheidet eigentlich wies weiter geht . also koennte der baum genauso gut mit x1 beginnen und ohne x4 zurecht kommen oder nicht ??
gruss fred
@Maexle : dich muss bei den gleichungen die da stehen nur interessieren wo 1 oder 0 am schluss rauskommen … das heisst: dich interessieren die = varible + blabla gleichungen nicht weil sie nur zwischenschritte auf dem weg zu dem 1 oder 0 ergebnis sind … aus diesen kannst du dann direkt deinen baum zeichnen der dann vielleicht hoffentlich reduziert ist und schon beim ersten versuch gelingt …
fuer die leute die mich nicht kennen : ich bin dann der der bei der klausur sich die ganze zeit meldet und nach mehr schmierpapier fraegt gggg
@fredator, 14:26
nicht ganz…
nachdem du x4 hast entscheiden lassen, bewirkt x1 jeweils eine andere entscheidung… also so irgendwie…
jedenfalls kannst du nicht direkt mit x1 anfangen, weil das ja (je nach x4 davor) andere wege weitergehen würde. also ist es schon wichtig, dass x4 vorher drankommt. überleg mal, was passiert, wenn x4=1 egal wäre… dann müsstest du ja auf einmal x2 und x3 auch noch prüfen, was du dir so ja sparen kannst. (verstanden??)
ich hatte es bereits vermutet … aber ich war eben net sicher . hatte mich eh schon gewunder wie ich die zwei verschiedenen x1 haette zusammenfassen sollen ohne da im endeffekt nen groesserem baum rauszukriegen g
danke nochmal fuer die hilfe an alle die was dazu geschrieben habn!
gruss fred
yves hat zwar schon geantwortet, dass sie nicht redundant sind, hier nur nochmal kurz die begruendung: redundant ist ein knoten, wenn er DENSELBEN 0- und 1-nachfolgeknoten hat. das oben sind aber zwei verschiedene knoten, die zufaellig dieselbe variable pruefen …
hth,
-steppenwolf