TI Uebungsblatt 04 - WS14/15 PDF

Preview

Summary

Das 4. Übungsblatt bei Prof. Dr. Stefan Kowalewski aus dem WS14/15...

Description

Aachen, 04. November 2014 ¨ 2, ECTS: 6 SWS: V4/ U

Professor Dr.-Ing. Stefan Kowalewski Hendrik Simon, M.Sc. Igor Kalkov, M.Sc.

Einfu ¨ hrung in die Technische Informatik WS 2014/2015 Blatt 4: OBDD Die L¨osungen k¨onnen vor der Global¨ ubung am 11.11.2014 abgegeben werden. Bitte bearbeiten Sie die Aufgaben ohne (⋆) in Lerngruppen und geben Sie nur eine geheftete L¨osung ¨ wird in der Global¨ ubung vorgerechnet. pro Lerngruppe ab. Das gesamte Ubungsblatt Aufgabe 1: OBDDs Gegeben sei das folgende OBDD (Variablenordnung x0 < x1 < x2 < x3 ): x0 x1

x1 x2 x3

x2

x2 x3

x3

x3

x3

0

x2 x3

x3

x3

1

a) Minimieren Sie das OBDD soweit wie m¨oglich und geben Sie jeden Schritt an. In einem Schritt d¨ urfen Sie mehrere Transformationen des gleichen Typs (entweder Verj¨ungung oder Elimination) anwenden. Geben Sie zu jedem Schritt den Transformationstyp an. b) Ist das Ergebnis minimal? Begr¨ unden Sie Ihre Antwort. Aufgabe 2: Reduzierte OBDDs ur die Funktion f (y2 , y1 , x2 , x1 ) = (x1 ⊕ y1 )(x2 ⊕ y2 ) auf. Eins a) Stellen Sie zwei ROBDDs f¨ mit der Variablenordnung x1 < x2 < y1 < y2 , und eins mit der Ordnung x1 < y1 < x2 < y2 . 1

b) Geben Sie die Anzahl der Nichtterminalknoten f¨ ur die beiden Darstellungen an. c) Verallgemeinern Sie das Ergebnis und betrachten Sie die Funktionen fn (yn , ..., y1 , xn , ..., x1 ) = Vn (x ⊕ y ), n ∈ N \ {1}. Begr¨unden Sie, warum die Variablenordnung x1 < y1 < x2 < i i=1 i y2 < ... < xn < yn f¨ ur diese Funktionen immer ein kleineres ROBDD ergeben wird, als die Ordnung x1 < x2 < ... < xn < y1 < y2 < ... < yn . Aufgabe 3: Erfullbarkeit von ROBDDs ¨ Beschreiben Sie eine Methode, um an einem ROBDD die Erf¨ullbarkeit seiner Funktion nachzuweisen. Aufgabe 4: Gleichheit von Booleschen Funktionen (⋆) Nehmen Sie an, Sie h¨ atten eine Methode um festzustellen, ob eine boolesche Funktion erf¨ ullbar ist. Legen Sie dar, wie Sie diese Methode nutzen k¨onnen, um die Gleichheit zweier Funktionen f und g zu zeigen.

2...