Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
45 Aufrufe

Hallo zusammen,

meine Frage bezieht sich auf den BDD in der Bonusklausur.

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

AusgewähltBDD besteht aus 4 Knoten oder weniger.
AusgewähltBDD 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

in BIN-AA von upubh upubh Lernwillige(r) (120 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
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)
von ufoxl ufoxl Lernwillige(r) (960 Punkte)  
0 0
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"?
...