Übung BDD

• ROBDD für die Zählfunktion

  count_≥k(x₁,…, x_n) : = let s = x₁ + ... + x_n in s≥k

• obere Schranke für Anzahl der BDD für n Variablen mit k Knoten ( 2^{Anzahl der Bits})

  vergleiche mit Anzahl Boolescher Funktionen von n Variablen, Schlußfolgerung?

• Bsp. ROBDD-Operation
• Anzahl der Überdeckungen eines Schachbretts (w×h) durch Dominos (2×1):

  Modellierung (Formel), Implementierung mit obdd