Nächste Seite:
Operationen mit ROBDDs (Plan)
Aufwärts:
Binäre Entscheidungsgraphen (ROBDDs)
Vorherige Seite:
Eigenschaften von ROBDDs
Beispiele, Einfluß der Variablenordnung
Bestimme das ROBDD für
(
a
1
∧
b
1
)∨(
a
2
∧
b
2
)∨(
a
3
∧
b
3
)
für
a
1
>
b
1
>
a
2
>
b
2
>
a
3
>
b
3
für
a
1
>
a
2
>
a
3
>
b
1
>
b
2
>
b
3
Funktionen mit exponentieller ROBDD-Größe für
jede
Variablenordnung: Bryant 1991
hidden weighted bit function
f
(
x
1
,…,
x
n
) =
let
s
=
x
1
+ … +
x
n
in if
s
= 0
then 0 else
x
s
(das mittlere Bit bei) integer multiplication
für Ordnung
y
2n
> … >
y
1
betrachte Informationsfluß (Anzahl der Kanten) zw.
{
y
2n
,…,
y
n+1
}
und
{
y
n
,…,
y
1
}
.
(
http://www.cs.cmu.edu/~bryant/pubdir/ieeetc91.pdf
)
2014-07-06
