Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

ROBDDs
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> ROBDDs
 
Autor Nachricht
Tanye
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 06.11.2010
Beiträge: 24

BeitragVerfasst am: 12 Nov 2010 - 23:21:23    Titel: ROBDDs

Hi Very Happy

Hab ne Frage zu folgender Aufgabe :

Erstellen Sie mit folgender booleschen Funktion

f(x1, x2, x3) = x1 + (x2 · x3)

jeweils ein Reduced Ordered Binary Decision Diagram für die folgenden Variablenreihenfolgen:

i) x1, x2, x3
ii) x2, x1, x3
iii) x3, x2, x1

Was macht das fürn Unterschied bei i) zu z.B. ii) ? Ich hab den Baum zu i) gezeichnet ... Hab ne Wertetabelle gemacht mit x1,x2,x3 dazu f(x1,x2,x3) berechnet usw. ... aber ich check den Unterschied nicht , was spieltn die Reihenfolge fürne Rolle :S
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 13 Nov 2010 - 10:24:31    Titel:

Die Reihenfolge spielt eine Rolle für die Struktur des reduzierten Baumes. Natürlich ändert sich der Inhalt der Funktion nicht. Wie sehen denn deine Bäume jeweils aus?
Tanye
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 06.11.2010
Beiträge: 24

BeitragVerfasst am: 13 Nov 2010 - 13:18:26    Titel:

Hi ,

Ich hab dir mal abgetimmt wie mein ROBDD zu i) aussieht Smile

Danke für deine Antwort Very Happy

http://www.speedyshare.com/files/25165897/ROBDD.pdf
ingu
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.02.2006
Beiträge: 1003

BeitragVerfasst am: 13 Nov 2010 - 14:32:55    Titel:

hi,
das, was du gezeichnet hast, ist ein korrekter OBDD, aber kein ROBDD. Der ganz linke Pfad (x1 = 0, x2 = 0) führt immer zu 0 - oder anders formuliert: Das linke x3 hat identische Folgeknoten. Das kommt bei einem reduzierten OBDD nicht vor. Daher musst du dort den x2 = 0-Pfad direkt zu 0 zeichnen und nicht erst über x3 gehen.
Dasselbe gilt für den rechnten Pfad.

Wenn du den ROBDD für ii) zeichnen willst, beginnst du ganz oben statt mit x1 mit der Variablen x2. Danach kommt x1 und dann x3. Dann sieht der ROBDD natürlich - meist - anders aus. Bei komplexeren Funktionen ist eine geschickte Reihenfolge sehr wichtig, da der OBDD sonst schnell sehr unübersichtlich wird.
Tanye
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 06.11.2010
Beiträge: 24

BeitragVerfasst am: 13 Nov 2010 - 18:29:33    Titel:

Ach klar dass is mir garnicht aufgefallen Embarassed Dankeschön ! Very Happy
ingu
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.02.2006
Beiträge: 1003

BeitragVerfasst am: 13 Nov 2010 - 19:45:20    Titel:

Wenn dir das weiterhilft, ist es sicher sinnvoll, die Wertetabelle umzusortieren, denn das ändert ja an der Funktion nix.

Viele Wege führen nach Rom... Oft entwickelt man auch die Funktion nach einer Variablen. Das ist im Endeffekt die algebraische Form einer "Umsortierung". Das sähe dann so aus:

In dem Fall entwickelt man f zuerst nach x2, d. h. man unterteilt f in eine Disjunktion von 2 "Unterfunktionen"
[; f(x_1, x_2, x_3) = \overline{x_2} \cdot f_{\overline{x_2}}(x_1, x_3) + x_2 \cdot f_{x_2}(x_1, x_3) ;]
in denen die zu entwickelnde Variable nicht mehr als Argument auftaucht.

Man setzt also x_2 einmal 0 und einmal 1 - ganz einfach Wink Anschaulich gesprochen sind das die Funktionen, die du bekommst, wenn du in der Tabelle nur die Spalten x_1 und x_3 für x_2 = 0 bzw. 1 betrachtest.
[; f(x_1, x_2, x_3) = x_1 + (x_2 \cdot x_3) = \overline{x_2} \cdot (x_1) + x_2 \cdot (x_1 + x_3) ;]
Dann fängt man also mit dem Knoten x_2 an und wenn dieser 0 ist, realisiert man die Funktion x_1 und wenn dieser 1 ist, realisiert man x_1 + x_3.
Das führt man dann immer weiter und kann das gesamt Problem (fast schon rekursiv) in immer kleinere Unterfunktionen unterteilen bis man nur noch 0 und 1 hat.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> ROBDDs
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum