Übungsblatt 3

Übungsblatt 3 ist ab sofort im Übungsportal und auf der Vorlesungswebseite verfügbar. Die Abgabe ist am 24.6., so dass fast zwei Wochen Zeit für die Bearbeitung sind.

Für die noch folgenden Übungsblätter 4 und 5 werden wir es ebenfalls so machen, dass zwei Wochen Zeit zur Bearbeitung sind. D.h. die neuen Blätter kommen jetzt immer gleichzeitig mit dem Abgabetermin des jeweils letzten heraus.

Bei Fragen oder Unklarheiten zum aktuellen Blatt, bitte hier posten!

Viele Grüße,
Linus

Irgendwie verstehen wir das mit der Negation bei dem BDD wohl nicht so ganz. Zumindest bekommen wir ein anderes Ergebnis als die Mulö raus und schätzen, dass der Fehler hier liegen muss.. (oder in der Mulö =))

Viele Grüsse
Raphael & Ja4

Könnt ihr etwas konkreter werden? Was meint ihr mit "Negation"? Es geht um Aufgabe 2, nehme ich an?
Grüße, Linus

In der Lösung zu Exercise 1c) sind imho die DC-Spalten in der Tabelle durcheinander geraten.

Wieso sollen die DC-Spalten nicht stimmen? Das 'x' ist überall da, wo die entsprechende Funktion (f1, f2 oder f3) einen anderen Wert als g hat. Damit weiß man, dass die jeweilige Belegung von x1, x2, x3, g (mit der entsprechenden Funktion (f1, f2 oder f3) als g) niemals vorkommen kann; daher DC (don't care).

So, nochmal wegen dem BDD:

Folgende Vorgehensweisen habe ich versucht:
1) Teilterme, wie in der angegebenen Formel als OBDD dargestellt und minimiert. Dann diese kleineren OBDDs zusammengefuegt und verknuepft.
AND: Verknuepfen beim Pfad zur [1]
OR: Verknuepfen beim Pfad zur [0]

Hier bekam ich allerdings ein anderes, jedoch nicht unaehnliches Ergebnis zur Musterloesung raus. Ist die Vorgehensweise falsch?

2) kompletten Formel, wie sie ist unminimiert hinschreiben und dann minimieren (Schien mir zu aufwendig, habe ich deshalb nicht probiert, muesste aber gehen, an kleineren Beispielen getestet)

3) Formel minimieren mit boolscher Algebra. Klappt super, so kaeme ich auch auf das Ergebnis der Muloe.

Welche Vorgehensweisen waeren Erlaubt in der Klausur und funktioniert 1 ueberhaupt und ich habe hier nur einen noch nicht entdeckten Fehler gemacht?

Viele Gruesse
Raphael



1 mal bearbeitet. Zuletzt am 16.09.2011 15:16 von RaphaelS.

Wie man BDDs erstellt, ist eigentlich Stoff aus TI. Da kann man das auf jeden Fall in den Folien noch mal genauer nachgucken.

Aber hier noch mal in Kurzform, wie das geht:

Man malt einen Knoten mit der ersten Variable der Variablenordnung als Wurzel (hier b3). Davon gehen 2 Kanten aus; eine für 0 und eine für 1. Diese gehen zu jeweils einem Knoten der zweiten Variablenordnung (hier a3). An den a3 Knoten, der an der 0 Kante hängt, schreibt man sich die Formel noch mal hin, wo man allerdings überall b3 mit 0 ersetzt. Das gleiche macht man mit b3 und 1 an den a3 Knoten, der an der 1 Kante hängt. So könnte man immer weiter machen, bis man schließlich einen binären Baum hat, der das vollständige (nicht reduzierte) BDD wäre.

An einem Knoten wie dem a3 an der 0-Kante von b3 würde man dann sehen, dass alle Knoten (außer dem 1-Blatt) unter der 1-Kante von diesem a3 isomorph und redundant sind, so dass man sie beim Reduzieren des BDDs löschen kann und die 1-Kante direkt aufs 1-Blatt zeigen kann.

Wenn nicht gefordert ist, ein vollständiges BDD zu zeichnen, sondern ein reduziertes (R in ROBDD steht für reduziert), kann man aber auch gleich bei der Konstruktion sehen, dass die 1 Kante von diesem a3 aufs 1-Blatt führt. Denn die Formel, die man da ran schreibt, in der b3 bereits durch 0 und a3 durch 1 ersetzt ist lautet:

1 + 0 * (~b2*a2 + (b2*a2 + ~b2*~a2) * (~b1*a1))

Und weil da schon 1 + ... steht, weiß man, dass die ganze Funktion nur noch 1 sein kann, egal welche Werte b2,a2,b1 und a1 annehmen. Also kann man die Kannte gleich auf 1 ziehen.

Hoffe, das beantwortet die Frage.

Viele Grüße,
Linus

Ja, teilweise.

Was meine Idee war: dass ich quasi fuer jedes Monom ein ROBDD erstell und diese aneinander verkette.

Wir hatten leider keine BDDs damals in Ti... (WS2007)

Nunja, dann muesste ich also doch alles ersteinmal unreduziert hinschreiben, was bei dieser Aufgabe ja ein Riesengebilde ergibt?!

Viele Gruesse
Raphael

Hallo Raphael,

Deine Zerstückelungs-Methode würde ja nur funktionieren, wenn in den verschiedenen Monomen nicht die gleichen Variablen vorkommen. Sonst hast Du die Variablen ja in Deinem später zusammengesetzten BDD (UPDATE: pro Pfad von Wurzel zu einem Blatt) mehrfach drin. Diese Methode ist deshalb im allgemeinen nicht anwendbar.

Aber unreduziert hinschreiben musst Du es doch gerade NICHT, wie ich es im letzten Post beschrieben habe. Wenn Du siehst, dass für eine partielle Variablenbelegung schon 0 oder 1 rauskommt, kannst Du die Kante gleich zum 0- oder 1-Blatt ziehen. Wenn es aus meiner Beschreibung nicht ausreichend klar geworden ist, gehen wir das gerne am Montag in der Fragestunde noch mal durch. Sonst gibt es ja auch noch Folien und Aufzeichnungen früherer TI-Vorlesungen.

Viele Grüße,
Linus



1 mal bearbeitet. Zuletzt am 16.09.2011 17:42 von Linus F..

Ok Linus,

Vielen Dank erstmal, ich werde mir das nochmals ansehen. Ansonsten Montag ;)

Viele Gruesse
Raphael