Die Arbeit beschäftigt sich mit der Einbeziehung einer impulsbasierten Dynamik in eine Montagesimulation, d.h. neben Geometrie und Kinematik des simulierten Systems betrachten wir auch die Kräfte, die die Bewegungen innerhalb des Systems auslösen. Dabei kann es zur Interaktion zwischen den simulierten Objekten kommen, was die Erkennung solcher Kollisionen und die physikalisch möglichst korrekte Reaktion darauf notwendig macht. Die Arbeit gliedert sich gemäs den vier Phasen unserer Simulation. Im ersten Teil leiten wir Formeln zur Berechnung von Volumen, Schwerpunkt und Trägheitsmatrix von Polyedern her. Das zweite Kapitel beschäftigt sich mit der Entwicklung der Bewegungsgleichungen unserer Objekte und der Lösung der so erhaltenen Differentialgleichungen. Da dabei die Möglichkeit zur Interaktion zwischen den Objekten besteht, müssen wir solche Kontakte erkennen. Eine solche Kollisionserkennung, die mit Systemzuständen zu jeweils zwei festen Zeitpunkten arbeiten, ist das Thema des dritten Teils. Das vierte Kapitel schlieslich beschäftigt sich mit der Reaktion auf Kollisionen. Zu Beginn vergleichen wir mehrere mögliche Ansätze und erläutern die Entscheidung für eine impulsbasierte Methode. Anschliesend wird ein Verfahren zur Behandlung von beliebigen Mehrfachkontakten zwischen verschiedenen Objekten entwickelt. Der Anhang geht dann noch näher auf die Benutzerschnittstelle und insbesondere die Anbindung der Spacemouse (3D-Eingabegerät) ein.

In der vorliegenden Arbeit wurde eine Heuristik zur Bestimmung von symmetrischen Erweiterungen partieller Boolescher Funktionen entwickelt. Dabei wurden für die Spezifizierung der don't care-Menge die Symmetrien der Funktion derart ausgenutzt, daß die resultierende Erweiterung in einer möglichst kleinen Partition der Eingangsvariablen stark symmetrisch ist. Experimentelle Untersuchungen an ROBDD-Darstellungen für Benchmarkschaltungen haben gezeigt, daß sich mit Hilfe der vorgestellten Algorithmen die Größe der Darstellung sehr stark reduzieren läßt. Für viele ROBDD-basierte Anwendungen kann dadurch die Laufzeit, der Speicherverbrauch und die Güte der Schaltungsentwürfe erheblich verbessert werden.

Ein Algorithmus für das allgemeine geometrische Bewegungsplanungsproblem wird vorgestellt, welcher intuitiv leichte Probleme auch in Szenen mit vielen Freiheitsgraden schnell löst. Eine Divide-and-Conquer-Strategie dient zur Wegesuche, wobei der Konfigurationsraum nie explizit errechnet oder repräsentiert wird; sie greift auf eine Routine zur Kollisionserkennung zurück. Die elementaren Translationen und Rotationen, aus denen sich eine Bewegung zusammensetzt, werden getrennt durch ein effizientes Verfahren behandelt; Hüllkörper verringern dabei die Laufzeit in praktischen Beispielen dramatisch.

Wir betrachten das Wörterbuchproblem, wenn die Folge der Suchanfragen durch eine Markov-Kette modelliert werden kann (Anfragequelle mit Gedächtnis). Selbst-organisierende Datenstrukturen stellen eine Möglichkeit zur Behandlung dar, und erlauben die dynamische Anpassung an das Zugriffsverhalten. Für die Simple-k- und Batched-k-Nach-Vorne-Schieben- Regel werden Formeln fuer die erwartete Suchzeit hergeleitet. Es stellt sich heraus, daß bei abhängigen Zugriffen mit trägem Übergangsverhalten (Lokalität der Zugriffe) die Hierarchie der Heuristiken bzgl. der erwarteten Suchzeit genau umgedreht ist als bei unabhängigen Zugriffen. Weiter betrachten wir eine spezielle Folge abhängiger Zugriffe, um die Größe des Zustandsraums der Datenstruktur zu reduzieren. In diesem Fall können wir beliebige Vorwärts- Regeln miteinander vergleichen und stellen auch hier fest, daß die Rangfolge der Regeln genau umgekehrt ist, verglichen mit unabhängigen Zugriffen. Außerdem betrachten wir selbst-organisierende Suchbäume mit der Zur-Wurzel-Rotieren-Regel. Bei beliebiger vorgegebener stationärer Verteilung können Zugriffsfolgen mit Lokalität angegeben werden, so daß die erwartete Suchzeit beliebig nahe an 1 liegt.

Two general heuristic approaches to the geometric motion planning problem are considered. Both heuristics make use of efficient collision detection algorithms and combine motion planning with collision detection to speed up planning or to extend planning facilities. The first approach tries to speed up motion planning by ignoring all obstacles in the scene which do not contribute to the planned collision-free path. In order to obtain such a minimal scene the heuristic computes a collision-free path in a scene and checks the planned paths for collisions with ignored obstacles using standard collision detection algorithms. The heuristic thereby conserves qualitative features of the algorithms used like completeness, computation of most-secure, euclidian-shortest or time-optimal paths. It can be used with any kind of motion planning algorithms like classical ones, algorithms for dynamical environments or multiple moving objects. The advantages of the heuristic are shown for a complete algorithm handling 3-dimensional objects with two translational degrees of freedom using the configuration space approach of Lozano-Perez and Wesley. The second heuristic extends the facilities of algorithms for static environments by classifying the obstacles in the scene in fixed and movable obstacles forming a motion planning problem with many degrees of freedom. The complex problem is decomposed in a series of simple problems which can be solved efficiently by known algorithms and the solutions are combined to a solution for the whole problem. It is shown that together with a problem modification strategy the heuristic nearly always extends and never reduces the facilities of motion planning algorithms in static environments.

Wir untersuchen den Zusammenhang zwischen Baumersetzungen und dazu korrespondierenden Stringersetzungen. Jeder durch ein Baumersetzungssystem generierten Sprache wird durch sog. multilineare Interpretation eine Stringsprache zugeordnet. Wir zeigen, daß sich diese Stringsprachen durch eine natürliche Verallgemeinerung der kontextfreien Grammatiken, den gekoppelt-kontextfreien Grammatiken erzeugen lassen. Es wird weiter gezeigt, daß die Klasse der Tree-Adjoinining-Languages, die in der Computerlinguistik zur Zeit große Bedeutung findet, durch gekoppelt-kontextfreie Sprachen charakterisiert werden kann.

Der erste Teil der Arbeit beschäftigt sich mit den Problemen einer feineren Modellierung von Fehlern, der zweite mit der Miniaturisierung von Schaltkreisen. Die führt nämlich dazu, daßdie auf die Chips gebrannten Schaltungen immer umfangreicher werden. Weshalb wiederum die Algorithmen für Testgenerierung und Fehlersimulation immer mehr Zeit beanspruchen. Sie bedürfen daher einer Weiterentwicklung, um mit neuen Generationen von Schaltungen Schritt zu halten. Da Testen eine sehr zeitaufwendige Aufgabe ist stellt man die Laufzeit der Algorithmen gegenüber ihrem Speicherbedarf oft in den Vordergrund. Deshalb wurde deren hierarchischer Aufbau, der das Design großer Schaltungen erst ermöglicht, nicht genutzt. Die höheren Laufzeitkosten eines hierarchischen Algorithmus stufte man als zu teuer gegenüber dem daraus erhofften Platzgewinn ein. Ich will für die hierarchische Fehlersimulation zeigen, daßdie Laufzeitkosten gar nicht so hoch sind, wie bisher angenommen.