Abstract:
Oftmals kann ein Problem erst dadurch gelöst werden, indem seine Komplexität reduziert wird. Erst diese Reduktion ermöglicht die Verwendung von Lösungsansätzen, die für weniger komplexe Problemstellungen existieren. Für 3d-Objekte ist die Skelettierung der Mechanismus, der die Objekte auf eine niedrigere Dimension abbildet und dadurch deren Komplexität reduziert.
Seit nunmehr 40 Jahren werden entsprechende Verfahren und darauf basierende Anwendungen entwickelt. In jüngster Zeit traten auf innovativen Forschungsgebieten innerhalb des Maschinenbaus, der Nanotechnologie, der Medizintechnik und nicht zuletzt der Computergrafik Probleme auf, die durch Skelettierung bewältigt wurden oder in naher Zukunft zu bewältigen sind.
Mit der vorliegenden Dissertation wird an den aktuellen Stand der Forschung angeknüpft und ein Skelettierungsverfahren vorgestellt, das nicht auf den bisher üblichen kartesischen Gittern, sondern auf den sogenannten kubisch-raumzentrierten Gittern operiert. Dadurch ergeben sich eine Vielzahl positiver Eigenschaften, sowohl unter topologischen als auch rechentechnischen Aspekten.
Die auf Gitterstrukturen basierenden Verfahren haben traditionell Schwierigkeiten, rotationsinvariante Skelette zu generieren. Diese Eigenschaft ist jedoch für eine Reihe von Applikationen wünschenswert. Eine Ausnahme bilden Verfahren, die zunächst ein Vektorfeld berechnen, das Abstoßungen vom Objektrand simuliert. Mithilfe dieser Strukturen können Skelettpunkte identifiziert werden, die von der Gitterstruktur unabhängig sind. Allerdings sind die Verfahren, die derartige Skelette erzeugen, extrem ineffizient: Bezogen auf die Anzahl der Objektgitterpunkte ist die Komplexität quadratisch. Deshalb ist ein weiterer Schwerpunkt dieser Arbeit, eine qualitativ hochwertige Approximation des Vektorfeldes in linearer Zeitkomplexität zu erzeugen. Die zusätzlichen Informationen, die aus diesen Vektorfeldern gewonnen werden, kommen innerhalb des ursprünglichen Skelettierungsverfahrens zum Einsatz, um die Vorteile beider Verfahren zu kombinieren.
Die auf diese Weise erzeugten eindimensionalen Skelettstrukturen der 3d-Objekte eignen sich für eine Vielzahl von Anwendungen. Drei Anwendungen, namentlich die Klassifizierung, die Segmentierung und die Manipulierung werden gezeigt. Für die Klassifizierung werden die erzeugten Skelette in eine Graphrepräsentation transformiert. Hierfür werden zwei Verfahren vorgestellt und darüber hinaus erläutert, wie die Graphrepräsentation optimiert und mit Attributen versehen werden kann. Insbesondere die Attributierung (z. B. mit Distanz- oder Krümmungsinformationen) ist von großer Bedeutung, da der Graph zunächst die Objektform nur grob abstrahiert und dadurch kein detaillierter Vergleich zwischen Objekten möglich wäre.
Für die Segmentierung und die Deformierung von 3d-Objekten besteht der wichtigste Beitrag dieser Dissertation darin, eine präzise Zuordnung zwischen Abschnitten des Graphen und Meshregionen durchzuführen, die erforderlich ist, um Änderungen an der Graphstruktur (Auftrennen oder Deformieren) direkt auf das Mesh übertragen zu können. Hierfür wird eine spezielle Datenstruktur präsentiert, die diese Zuordnung ermöglicht, ohne die Komplexität des Skelettierungsverfahrens zu verschlechtern. Ein breites Spektrum an Vorschlägen für zukünftige, auf dieser Dissertation aufbauende Forschungsthemen schließen die Arbeit ab.
Promotionsverteidigung David BrunnerPromotionsverteidigung David BrunnerPromotionsverteidigung David Brunner
Ralf Neubert "QBäume - Effizientes Retrieval von Graphen mit Hilfe von Strukturinvarianten"
Promotion zum Dr.-Ing.
Abstract englisch:
Transportation is one of the most vital services in modern society. It makes most of the other functions of society possible. Real transportation systems are so large and complex that in order to build the science of transportation systems it will be necessary to work in many areas, such as: Modeling, Optimization and Simulation. We are interested in solutions for the so-called fleet-sizing-and-allocation problem (FSAP). Fleet sizing and allocation problems are one of the most interesting and hard to solve logistic problems. A fleet sizing and allocation problem consists of two interdependent parts. The fleet sizing problem is to determine a number of transportation units that optimally balances service requirements against the cost of purchasing and maintaining the transportation units. The allocation problem is dealing with the repositioning of transportation units to serve future transportation demand.
To make the fleet sizing and allocation problem a little bit more tractable we concentrate on logistic systems with a special hub-and-spoke structure. We start with a very simple fleet sizing of one-to-one case. This case will cause us to focus attention on several key issues in fleet sizing. Afterwards, the generalization of the one-to-one system is the one-to-many system. As a simple example can serve the continuous time situation where a single origin delivers items to many destinations. For the case that items are produced in a deterministic production cycle and transportation times are stochastic. We also studied a hub-and-spoke problem with continuous time and stochastic demand. To solve this problem, based on Marginal Analysis, we applied queueing theory methods.
The investigation of the fleet-sizing-and-allocation problem for hub-and-spoke systems is started for a single-period, deterministic-demand model. In that the model hub has to decide how to use a given number of TU´s to satisfy a known (deterministic) demand in the spokes. We consider two cases:
1. Renting of additional TU´s from outside the system is not possible, 2. Renting of additional TU´s from outside the system is possible. For each case, based on Marginal Analysis, we developed a simple algorithm, which gives us the cost-minimal allocation. Since the multi-period, deterministic demand problem is NP-hard we suggest to use Genetic Algorithms. Some building elements for these are described.
For the most general situation we also suggest to use simulation optimization. To realize the simulation optimization approach we could use the software tool "Calculation Assessment Optimization System" (CAOS). The idea of CAOS is to provide a software system, which separates the optimization process from the optimization problem. To solve an optimization problem the user of CAOS has to build up a model of the system to which the problem is related. Furthermore he has to define the decision parameters and their domain. Finally, we used CAOS for two classes of hub-and-spoke system: 1. A single hub with four spokes, 2. A single hub with fifty spokes. We applied four optimizers - a Genetic Algorithm, Tabu Search, Hybrid Parallel and Hybrid Serial with two distributions (Normal Distribution and Exponential Distribution) for a customer interarrival times and their demand.
Abstract deutsch:
Der Entwurfsprozess informationsverarbeitender Systeme ist gekennzeichnet durch die Beschreibung von speichernden, verarbeitenden und übertragenden Komponenten auf unterschiedlichen Abstraktionsstufen. Sowohl für spezifische Anwendungsdomänen als auch für die jeweiligen Abstraktionsstufen wurden in der Vergangenheit Werkzeuge entwickelt, die den Systemdesigner von der Phase der Anforderungsspezifikation bis hin zu Implementierung und funktionaler Erprobung begleiten. Beim Entwurf komplexer Systeme im allgemeinen und eingebetteter Systeme im besonderen stellt sich zusätzlich das Problem der Wiederverwendung von Komponenten aus früheren Entwürfen, der Transformation des Entwurfswissens über die Grenzen der Abstraktionsstufen hinweg sowie die Integration einer variablen Anzahl domänenspezifischer Werkzeuge in den Entwurfsprozess. Voraussetzung eines korrekten Designs ist dabei die Anwendungsinvariante Integritätserhaltung aller beteiligten Entwurfsdaten unabhängig von ihrer Repräsentation. Nach der Diskussion des Integritätsbegriffs für konventionelle Informationssysteme und den nötigen Erweiterungen für eingebettete Systeme werden Verfahren zur Modellierung des Entwurfsprozesses vorgestellt, mit deren Hilfe eine der spezifischen Entwicklungsaufgabe optimal entsprechende Wissensbasis generiert und fortwährend neuen Anforderungen von Fremdwerkzeugen und Entwurfsverfahren angepasst werden kann. Sie erfordert vom Anwender keine Detailkenntnisse des zugrunde liegenden Datenmodells. Die Generierbarkeit der Wissensbasis und ihrer Werkzeuge beruht auf einem Metamodell, das sich auf eine erweiterbare Objektalgebra zur Struktur- und Verhaltensbeschreibung informationsverarbeitender Systeme stützt und in domänenspezifische Zielsysteme transformierbar ist.
Abstract englisch:
The design process of data processing systems is characterized by the description of storing, processing and transmitting components on different levels of abstraction. In the past tools have been developed for specific application domains as well as for the respective abstraction levels. They support the system designer from the stage of the requirements specification down to implementation and functional test. During the sketch of complex systems in general and embedded systems in particular, problems occur in the following areas: reusing the components from former drafts; transforming the design knowledge across the boundaries of abstraction levels; integrating a variable number of domain specific tools in the design process. The precondition for a correct design is the integrity preservation of all involved draft data no matter which sources such as databases, XML files or conventional HOST file systems provide them. After discussing the integrity term regarding conventional information systems and the extensions necessary for embedded systems, approaches for modelling the design process are presented. They help to generate a knowledge base which is optimally adjusted to a particular design task and can be continuously adapted to new requests coming from external tools and design processes. The user does not need detailed knowledge about the knowledge base's underlying data model. The capability of generating the knowledge base and its tools is based on a meta model. First, this model is based on an extensible object algebra applied when describing the structure and behaviour of data processing systems and second, the model is transformable into domain specific target systems.
Abstract:
Kleine Softwareunternehmen haben eine beachtliche wirtschaftliche Bedeutung in Deutschland. In der softwaretechnischen Forschung rücken sie zunehmend ins Blickfeld. Dieses Buch basiert auf mehrwöchigen Beobachtungen in fünf kleinen Softwareunternehmen und erzählorientierten Interviews mit 21 Softwareentwicklern. Das erhobene Datenmaterial gewährt Einblick in den Arbeitsalltag in diesen Unternehmen. Es hilft Ihnen zu verstehen, wie Arbeitsstile die Softwareentwicklung in kleinen Unternehmen prägen und wie sie gleichzeitig die Entwicklung der Unternehmen befördern können. Neben einer wissenschaftlichen Verortung der Fragestellung finden sie in diesem Buch eine Beschreibung und Auswertung des Datenmaterials, eine Diskussion der Ergebnisse und den Entwurf eines Prozesses, der an den Arbeitsstilen ansetzt und mit dem die Einführung von softwaretechnischen Methoden in kleinen Unternehmen gelingt.
Promotionsverteidigung Andrea SieberPromotionsverteidigung Andrea Sieber
Matthias, Kühnemann "Analyse, Laufzeitmodellierung und Optimierung paralleler MPI Programme"
Promotion zum Dr.-Ing.
Abstract:
Diese Promotion widmet sich der Entwicklung von Fehlermodellen für eingebettete, verteilte Multi-Prozessorsysteme. Diese werden zu einem hierarchischen Netzwerk zur Steuerung von Flugzeugen (Avionik) verbunden und mehr und mehr im Automotive Bereich eingesetzt. Hier gilt es höchste Sicherheitsstandards einzuhalten und maximale Verfügbarkeit zu garantieren. Marco Fischer integriert die Modellierung von möglichen Fehlern in den Entwurfsprozess. Auf Grundlage des π-Kalküls entwickelt er ein formales Fehlermodell, das eine einheitliche Modellierung von Fehlerfällen unterstützt. Dabei werden interessante Bezüge zur Bi- Simulation sowie zu Methoden des Modell Checkings hergestellt. Die theoretischen Ergebnisse werden an einem komplexen Beispiel anschaulich illustriert. So kann der Leser die Mächtigkeit des entwickelten Ansatzes nachvollziehen und wird motiviert, die entwickelte Methodik auf weitere Anwendungsfälle zu übertragen.
Promotionsverteidigung Marco FischerPromotionsverteidigung Marco Fischer
Abstract:
The modelling and design of todays DES (Distributed Embedded System) entails two major challenges. On the one hand, to cope with the inherent complexity and heterogeneity of DES, middleware solutions have been developed. This in turn led to the Modelling Problem of multi-layered DES, since current modelling approaches largely fail in supporting the modelling of more than two-layered systems in a concise way. On the other hand, there is the Reuse and Upgrade problem which is caused by the need for re-qualification and re-certification of safety critical DES after each system upgrade. Typically, such a system upgrade involves the exchange of one or several components in the system by other ones providing more functionality, i.e., extending the functionality of the original ones. This work addresses both challenges by developing a formal framework for the modelling of multi-layered DES and managing component extension, which is applicable to a wide range of development processes, development approaches, and specification and implementation notations. To achieve this, whilst taking into account the inherent concurrent and communication intensive nature of modern multi-layered DES, the π-calculus process algebra was chosen as the semantics foundation of the presented framework. In order to support the paradigm of layered DES, the work proposes abstract and concrete layers and the Integration-View. Thereby, applications modelled with abstractlayer constructs provide an inherent execution semantics based on π-calculus. An example from the domain of avionics shows how a hierarchy of layers and thus multi-layered DES can be described. The second major contribution of this work is the component extension relation which is based on the idea of component substitutability. Its semantic foundation are the three more general process extension relations in π-calculus named interface, cut-off, and closed extension. Thereby, interface extension captures static well-typing of processes, cut-off extension stipulates equivalent component behaviour as long as the new process functionality is not used, and closed extension permits the usage of the new process functionality in a disciplined manner, whilst ensuring equivalent behaviour at the original process interface. Last but not least, an important property of the process extension relations is that each weaker version is implied by the stronger versions.
Promotionsverteidigung Stefan FörsterPromotionsverteidigung Stefan Förster
