In der vorliegenden Arbeit wird eine Datenstruktur zur Darstellung einer Booleschen Funktion "TVL-Tupel" präsentiert, die im Ergebnis einer Kombination der bekannten Datenstrukturen Entscheidungsgraph und Ternärvektorliste entsteht. Zuerst wird untersucht, wie lokale Phasenlisten sich als Elemente des Tupels eignen. Weiterhin wird die neue Dekompositionsart ("Tupel-Dekomposition") einer Boolesche Funktion in drei bzw. vier Teilfunktionen vorgestellt. Die Besonderheit der Teilfunktionen der Dekomposition besteht in ihrer Orthogonalität zueinander. Der Vorteil der Dekomposition von Funktionen mit einer hohen Anzahl von Konjunktionen besteht im geringeren Speicherplatzbedarf. Des weiteren wurden Algorithmen für Realisierung der Operationen entwickelt, die für eine Handhabung der zerlegten Funktionen erforderlich sind. Der detaillierte Vergleich der Berechnungszeiten für die Operationen erbringt den Nachweis, dass eine Verringerung des Zeitbedarfs als Folge der Zerlegung zu erwarten ist. Weiterhin bietet die Dekomposition einen Ansatz für den Entwurf von Algorithmen, die eine parallele Bearbeitung auf der Grundlage verteilter Rechentechnik zulassen. Die Erkenntnisse der Untersuchungen der Tupel-Dekomposition einschließlich der Verwendung der verteilen Verarbeitung können beispielsweise für die Suche der Variablenmengen der OR-Bi-Decomposition verwendet werden.

Techn. University, Diss., 2000--Darmstadt.

Gescannte und vektorisierte technische Zeichnungen werden automatisch unter Nutzung eines Netzes von Modellen in eine hochwertige Datenstruktur migriert. Die Modelle beschreiben die Inhalte der Zeichnungen hierarchisch und deklarativ. Modelle für einzelne Bestandteile der Zeichnungen können paarweise unabhängig entwickelt werden. Dadurch werden auch sehr komplexe Zeichnungsklassen wie Elektroleitungsnetze oder Gebäudepläne zugänglich. Die Modelle verwendet der neue, sogenannte Y-Algorithmus: Hypothesen über die Deutung lokaler Zeichnungsinhalte werden hierarchisch generiert. Treten bei der Nutzung konkurrierender Modelle Konflikte auf, werden diese protokolliert. Mittels des Konfliktbegriffes können konsistente Interpretationen einer kompletten Zeichnung abstrakt definiert und während der Analyse einer konkreten Zeichnung bestimmt werden. Ein wahrscheinlichkeitsbasiertes Gütemaß bewertet jede dieser alternativen, globalen Interpretationen. Das Suchen einer bzgl. dieses Maßes optimalen Interpretation ist ein NP-hartes Problem. Ein Branch and Bound-Algorithmus stellt die adäquate Lösung dar.

In der vorliegenden Arbeit wird eine Datenstruktur zur Darstellung einer Booleschen Funktion "TVL-Tupel" präsentiert, die im Ergebnis einer Kombination der bekannten Datenstrukturen Entscheidungsgraph und Ternärvektorliste entsteht. Zuerst wird untersucht, wie lokale Phasenlisten sich als Elemente des Tupels eignen. Weiterhin wird die neue Dekompositionsart ("Tupel-Dekomposition") einer Boolesche Funktion in drei bzw. vier Teilfunktionen vorgestellt. Die Besonderheit der Teilfunktionen der Dekomposition besteht in ihrer Orthogonalität zueinander. Der Vorteil der Dekomposition von Funktionen mit einer hohen Anzahl von Konjunktionen besteht im geringeren Speicherplatzbedarf. Des weiteren wurden Algorithmen für Realisierung der Operationen entwickelt, die für eine Handhabung der zerlegten Funktionen erforderlich sind. Der detaillierte Vergleich der Berechnungszeiten für die Operationen erbringt den Nachweis, dass eine Verringerung des Zeitbedarfs als Folge der Zerlegung zu erwarten ist. Weiterhin bietet die Dekomposition einen Ansatz für den Entwurf von Algorithmen, die eine parallele Bearbeitung auf der Grundlage verteilter Rechentechnik zulassen. Die Erkenntnisse der Untersuchungen der Tupel-Dekomposition einschließlich der Verwendung der verteilen Verarbeitung können beispielsweise für die Suche der Variablenmengen der OR-Bi-Decomposition verwendet werden.

Gescannte und vektorisierte technische Zeichnungen werden automatisch unter Nutzung eines Netzes von Modellen in eine hochwertige Datenstruktur migriert. Die Modelle beschreiben die Inhalte der Zeichnungen hierarchisch und deklarativ. Modelle für einzelne Bestandteile der Zeichnungen können paarweise unabhängig entwickelt werden. Dadurch werden auch sehr komplexe Zeichnungsklassen wie Elektroleitungsnetze oder Gebäudepläne zugänglich. Die Modelle verwendet der neue, sogenannte Y-Algorithmus: Hypothesen über die Deutung lokaler Zeichnungsinhalte werden hierarchisch generiert. Treten bei der Nutzung konkurrierender Modelle Konflikte auf, werden diese protokolliert. Mittels des Konfliktbegriffes können konsistente Interpretationen einer kompletten Zeichnung abstrakt definiert und während der Analyse einer konkreten Zeichnung bestimmt werden. Ein wahrscheinlichkeitsbasiertes Gütemaß bewertet jede dieser alternativen, globalen Interpretationen. Das Suchen einer bzgl. dieses Maßes optimalen Interpretation ist ein NP-hartes Problem. Ein Branch and Bound-Algorithmus stellt die adäquate Lösung dar.