BDD Bonusklausur 2022

Question

Hallo zusammen,

meine Frage bezieht sich auf den BDD in der Bonusklausur.

Wie bestimme ich die maximale/ minimale Knotenzahl bzw. was ist damit gemeint?

BDD besteht aus 4 Knoten oder weniger.

BDD besteht aus 3 Knoten oder mehr.

Die Aussagen obendrüber sind als richtig angegeben in der Musterlösung, allerdings frage ich mich ob diese Aussagen einzeln betrachtet sich nicht ausschließen?

Wären Sie in einem Satz geschrieben würde es meiner Meinung nach nur stimmen.

LG

upubh

Answer 1

Hi,

die maximale Knotenanzahl zu bestimmen ergibt nicht so wirklich Sinn (theoretisch könnte man Knoten mit gleicher Bedeutung unendlich oft vervielfachen und hätte immer noch ein Diagramm mit der gleichen Aussage vorliegen)

Die minimale Knotenanzahl (für eine bestimmte Variablenreihenfolge) bestimmst du indem du das BDD aufstellst. (Das BDD ist so definiert, dass es für die gleiche Variablenreihenfolge immer die minimale Anzahl an Knoten hat und gleich aussieht)

Da die Anzahl der Knoten des BDDs (und damit auch die minimale Anzahl) aber von der Reihenfolge der Variablen abhängt kann es einen Unterschied machen in welcher Reihenfolge diese dastehen.
[mgl. Variablenreihenfolgen bei den Var. x,y,z: (x,y,z), (x,z,y), (y,z,x), (y,x,z), (z,x,y) oder (z,y,x)]

in der hier verlinkten Aufgabe (BIN-AA) bspw. müssten wenn c oben steht 5 Knoten zustande kommen.

Vielleicht wurden deshalb in der Bonusklausur auch die beiden Formulierungen mit "4 oder weniger" sowie "3 oder mehr", damit Leute die die Reihenfolge anders gewählt hatten keinen Nachteil haben (Aber keine Garantie, ich hab die Aufgabe nicht wirklich angeschaut & auch nicht vorliegen).
Wie man jetzt auf die minimale Anzahl der Knoten kommt ohne alle BDDs aufzuzeichnen?:
Schau dir die Wahrheitstabelle an und versuche Abhängigkeiten zu finden
(in der Aufgabe BIN-AA siehst du dass wenn A 1 ist nur B entscheidet, ob am Ende "0" oder "1" herauskommt. Daraus kann man schließen, dass man hier das eine C nicht braucht)

Ich hoffe das hilft weiter

Grüße

Constantin
(Tutor)

Comments

Daraus ergibt sich noch eine kleine Frage von meiner Seite:
Wie ist die Definition eines BDDs?
Ist ein BDD ein (immer) minimaler Baum oder kann ein BDD auch nicht minimale sein, also wie du beschrieben hast, durch z.B. replizieren eines Knotens oder einfach der "Ausgangsbaum"?