Graph Komponente

22/10/2013 - 12:07 von Hans-Peter Diettrich | Report spam
Bei der Analyse von Programmen bin ich über ein Problem gestolpert,
nàmlich wie eine komplexe binàre Entscheidung (logischer Ausdruck, if
statement) in einem Graphen gefunden werden kann. Anders als die
regulàren Komponenten (Block, single entry, single exit) hat so eine
Komponente genau 2 Ausgànge, die den möglichen Ergebnissen True und
False entsprechen.

Gibt es einen Algorithmus, der zur Erkennung solcher Komponenten
benutzbar ist?

Andernfalls hàtte ich eine Prozedur, die das leisten sollte. Es fehlt
nur ein Beweis, daß diese Prozedur (bzw. der Algorithmus) richtig
funktioniert. Könnte mir jemand dabei helfen?

TIA
DoDi
 

Lesen sie die antworten

#1 Christian Gollwitzer
23/10/2013 - 00:56 | Warnen spam
Am 22.10.13 12:07, schrieb Hans-Peter Diettrich:
Bei der Analyse von Programmen bin ich über ein Problem gestolpert,
nàmlich wie eine komplexe binàre Entscheidung (logischer Ausdruck, if
statement) in einem Graphen gefunden werden kann. Anders als die
regulàren Komponenten (Block, single entry, single exit) hat so eine
Komponente genau 2 Ausgànge, die den möglichen Ergebnissen True und
False entsprechen.



Tut mir leid, ich versteh nahezu kein Wort:"In einem Graphen gefunden
werden?". Möchtest Du vielleicht aus einer Wahrheitstabelle einen
möglichst kompakten Booleschen Ausdruck berechnen? Das leistet der
Quine-Mc-Clusky-Algorithmus, der wird u.U. auch von Compilern zur
Codeoptimierung eingesetzt.

Christian

Ähnliche fragen