Search

Zur Analyse der Phospholipase D3 wurden molekularbiologische, zellbiologische und biochemische Methoden eingesetzt. Außerdem wurde ein anti-PLD3-Antikörper experimentell etabliert, der den kurzen N-Terminus spezifisch detektiert. Nach der bisherigen, geringen Studienlage handelt es sich bei der Phospholipase D3 um ein Membranprotein, welches maßgeblich mit dem Endoplasmatischen Retikulum assoziiert ist (Munck et al. 2005), wobei neuere Studien auf eine Verbindung mit Lysosomen weisen (Palmieri et al. 2011). In dieser Arbeit kann gezeigt werden, dass PLD3 zellulär in Endosomen/Lysosomen lokalisiert ist. PLD3 wird proteolytisch in Lysosomen gespalten, wobei N- sowie C-terminale PLD3-Fragmente neu beschrieben werden konnten. Die Phospholipase D3 besteht in vitro überwiegend in der löslichen, luminalen Form. Weiterhin kann gezeigt werden, dass PLD3 an verschiedenen Positionen der AS-Sequenz mit unterschiedlichen Zuckertypen N-glykosidisch konjugiert ist. PLD3 wird nicht über Mannose-6-Phosphat-Reste sortiert. Auch dem potentiellen N-terminalen Tyrosin-Sortierungsmotiv kommt nur eine untergeordnete Rolle bezüglich des lysosomalen PLD3-Transportes zu und es werden alternative Transportmechanismen diskutiert. Zur Analyse einer potentiellen katalytischen Funktion von PLD3 als Phospholipase D wurde ein Enzym-Aktivitäts-Assay etabliert, welcher eine mögliche pH-Abhängigkeit der Aktivität berücksichtigt. Unter Testbedingungen kann eine enzymatische Aktivität von PLD3 im neutralen Milieu nachgewiesen werden. Die Phospholipase D3 wurde mit dem Retromer-Komplex in Verbindung gebracht (Breusegem und Seaman 2014). Passend kann gezeigt werden, dass PLD3 mit einer essentiellen Untereinheit des Retromer-Komplexes endosomal kolokalisiert, wodurch eine funktionelle Beteiligung der Phospholipase D3 bei der Formierung und Abschnürung retrograder Vesikel denkbar ist. Durch die PLD3-Überexpression in neuronalen Zellen können die APP-Gesamtlevel teils signifikant reduziert werden, in Zusammenschau mit der Analyse von PLD3-Kockout-Zellen ist der Einfluss auf das APP-Volllängenprotein jedoch als mäßig zu werten. PLD3 hat eher einen Effekt auf die proteolytische Prozessierung von APP, wobei die nicht-amyloidogene Spaltung gefördert und insgesamt geringere zelltoxische Abeta-Mengen generiert werden könnten. Außderdem wurde die murine Variante der wichtigsten PLD3-Patientenmutation (PLD3-V232M) mikroskopisch analysiert. Diese zeigt sich unter Überexpression, abweichend vom Wildtyp, überwiegend ER-lokalisiert. Ein pathologischer Transport mit konsekutivem Funktionsverlust von PLD3-V232M könnte eine zellbiologische Erklärung für die beschriebene Assoziation mit der Spätform des M. Alzheimer (Cruchaga et al. 2014) sein.

The first part of the thesis contains pseudo-polynomial algorithms for integer linear programs (ILP). When certain parameters of an ILP are fixed, that is, they are treated as constants in the running time, it is possible to obtain algorithms with a running time that is pseudo-polynomial in the entries of the ILP’s matrix. We present a tight pseudo-polynomial running time for ILPs with a constant number of constraints. Furthermore, we study an extension of this model to MILPs (linear programs that contain both fractional and integer variables). Then we move to n-fold ILPs, a class of ILPs with block structured matrices. We present the first algorithm for n-folds, which is near-linear in the dimensions of the ILP. The second part is about scheduling in non-identical machine models, more precisely, restricted allocation problems. Here a set of jobs has to be allocated to a set of machines. However, every job has a subset of machines and may only be assigned to a machine from this subset. We consider the objectives of minimizing the makespan or maximizing the minimum load. We study the integrality gap of a particularly strong linear programming relaxation, the configuration LP, for variations of this problem. The integrality gap can be seen as a measure of strength of an LP relaxation. A local search technique can be used to bound this value. However, the proofs are generally non-constructive, i.e., they do not give an efficient approximation algorithm right away. We derive better upper bounds on the integrality gap of the problems Restricted Assignment, Restricted Santa Claus, and Graph Balancing. Furthermore, we give the first (constructive) quasi-polynomial time approximation algorithm for Restricted Assignment with an approximation ratio strictly less than 2. Der erste Teil der Thesis umfasst pseudopolynomielle Algorithmen für ganzzahlige lineare Programme (ILP). Wenn bestimmte Parameter eines ILPs fixiert sind, d.h. sie werden in der Laufzeit als Konstanten betrachtet, dann ist es möglich Algorithmen zu entwerfen, deren Laufzeit pseudopolynomiell in dem größten absoluten Wert eines Eintrags der Matrix des ILPs ist. Ein Ergebnis, das wir präsentieren, ist eine scharfe Schranke für die pseudopolynomielle Laufzeit, die nötig ist um ein ILP mit konstant vielen Bedingungen zu lösen. Danach befassen wir uns mit n-fold ILPs, eine Klasse von ILPs, deren matrix eine Blockstruktur besitzt. Wir geben den ersten Algorithmus für n-folds an, dessen Laufzeit gleichzeitig nahezu linear in der Dimension des ILPs ist. Der zweite Teil handelt von nicht-identischen (heterogenen) Maschinen Modellen, genauer gesagt restricted allocation problems. Hier soll eine Menge von Jobs auf eine Menge von Maschinen verteilt werden. Jeder Job darf aber nur auf bestimmte Maschinen zugewiesen werden. Wir betrachten als Zielfunktionen sowohl die Minimierung des Makespans als auch die Maximierung der minimalen Last einer Maschine. Wir untersuchen den integrality gap einer besonders starken LP Relaxierung, dem Konfigurations LP, für Variationen dieses Problems. Der integrality gap kann als Maß für die Stärke einer LP Relaxierung gesehen werden. Über ein Argument mittels einer lokalen Suche wird dieser Wert beschränkt. Jedoch sind die Beweise typischerweise nicht konstruktiv, d.h. sie implizieren nicht direkt effiziente Approximationsalgorithmen. Wir beweisen neue obere Schranken an den integrality gap für die Probleme Restricted Assignment, Restricted Santa Claus und Graph Balancing. Desweiteren präsentieren wir den ersten (konstruktiven) Quasipolynomialzeit Approximationsalgorithmus für das Restricted Assignment Problem mit Approximationsrate echt kleiner als 2.

Many approaches have been suggested for automatic pedestrian and car detection to cope with the large variability regarding object size, occlusion, background variability, aspect and so forth. Current state-of-the-art deep learning-based frameworks rely either on a proposal generation mechanism (e.g., "Faster R-CNN") or on the inspection of image quadrants / octants (e.g., "YOLO" or "SSD"), which are then further processed with deep convolutional neural networks (CNN). In this thesis, the Discriminative Generalized Hough Transform (DGHT), which operates on edge images, is analyzed for the application to automatic multi-scale and multi-object pedestrian and car detection in 2D digital images. The analysis motivates to use the DGHT as an efficient proposal generation mechanism, followed by a proposal (bounding box) refinement and proposal acceptance or rejection based on a deep CNN. The impact of the different components of the resulting DGHT object detection pipeline as well as the amount of DGHT training data on the detection performance are analyzed in detail. Due to the low false negative rate and the low number of candidates of the DGHT as well as the high classification accuracy of the CNN, competitive performance to the state-of-the-art in pedestrian and car detection is obtained on the IAIR database with much less generated proposals than other proposal-generating algorithms, being outperformed only by YOLOv2 fine-tuned to IAIR cars. By evaluations on further databases (without retraining or adaptation) the generalization capability of the DGHT object detection pipeline is shown.

Pipe-and-Filter (P&F) is a well-known and often used architectural style. However, to the best of our knowledge, there is no P&F framework which can model and execute generic P&F architectures. For example, the frameworks Fastflow, StreamIt, and Spark do not support multiple input and output streams per filter and thus cannot model branches. Other frameworks focus on very specific use cases and neglect type-safety when interconnecting filters. Furthermore, an efficient parallel execution of P&F architectures is still an open challenge. Although some available frameworks can execute filters in parallel, there is much potential for optimization. Unfortunately, most frameworks have a fixed execution strategy which cannot be altered without major changes. In this thesis, we present our generic and parallel P&F framework TeeTime. It is able to model and to execute arbitrary P&F architectures. Simultaneously, it is open for modifications in order to experiment with the P&F style. Moreover, it allows to execute filters in parallel by utilizing the capabilities of contemporary multi-core processor systems. Extensive lab experiments show that TeeTime imposes a very low and in certain cases even no runtime overhead compared to implementations without framework abstractions. Moreover, several case studies from research and industry show TeeTime’s broad applicability and extensibility. We provide a replication package containing all our experimental data and code to facilitate the verifiability, repeatability, and further extensibility of our results. Furthermore, we provide reference implementations for TeeTime in Java and in C++ as open source software on https://teetime-framework.github.io.

In this thesis, we consider the Parallel Task Scheduling problem and several variants. This problem and its variations have diverse applications in theory and practice; for example, they appear as sub-problems in higher dimensional problems. In the Parallel Task Scheduling problem, we are given a set of jobs and a set of identical machines. Each job is a parallel task; i.e., it needs a fixed number of identical machines to be processed. A schedule assigns to each job a set of machines it is processed on and a starting time. It is feasible if at each point in time each machine processes at most one job. In a variant of this problem, called Strip Packing, the identical machines are arranged in a total order, and jobs can only allocate neighboring machines with regard to this total order. In this case, we speak of Contiguous Parallel Task Scheduling as well. In another variant, called Single Resource Constraint Scheduling, we are given an additional constraint on how many jobs can be processed at the same time. For these variants of the Parallel Task Scheduling problem, we consider an extension, where the set of machines is grouped into identical clusters. When scheduling a job, we are allowed to allocate machines from only one cluster to process the job. For all these considered problems, we close some gaps between inapproximation or hardness result and the best possible algorithm. For Parallel Task Scheduling we prove that it is strongly NP-hard if we are given precisely 4 machines. Before it was known that it is strongly NP-hard if we are given at least 5 machines, and there was an (exact) pseudo-polynomial time algorithm for up to 3 machines. For Strip Packing, we present an algorithm with approximation ratio (5/4 +ε) and prove that there is no approximation with ratio less than 5/4 unless P = NP. Concerning Single Resource Constraint Scheduling, it is not possible to find an algorithm with ratio smaller than 3/2, unless P = NP, and we present an algorithm with ratio (3/2 +ε). For the extensions to identical clusters, there can be no approximation algorithm with a ratio smaller than 2 unless P = NP. For the extensions of Strip Packing and Parallel Task Scheduling there are 2-approximations already, but they have a huge worst case running time. We present 2-approximations that have a linear running time for the extensions of Strip Packing, Parallel Task Scheduling, and Single Resource Constraint Scheduling for the case that at least three clusters are present and greatly improve the running time for two clusters. Finally, we consider three variants of Scheduling on Identical Machines with setup times. We present EPTAS results for all of them which is the best one can hope for since these problems are strongly NP-complete. In dieser Thesis untersuchen wir das Problem Parallel Task Scheduling und einige seiner Varianten. Dieses Problem und seine Variationen haben vielfältige Anwendungen in Theorie und Praxis. Beispielsweise treten sie als Teilprobleme in höherdimensionalen Problemen auf. Im Problem Parallel Task Scheduling erhalten wir eine Menge von Jobs und eine Menge identischer Maschinen. Jeder Job ist ein paralleler Task, d. h. er benötigt eine feste Anzahl der identischen Maschinen, um bearbeitet zu werden. Ein Schedule ordnet den Jobs die Maschinen zu, auf denen sie bearbeitet werden sollen, sowie einen festen Startzeitpunkt der Bearbeitung. Der Schedule ist gültig, wenn zu jedem Zeitpunkt jede Maschine höchstens einen Job bearbeitet. Beim Strip Packing Problem sind die identischen Maschinen in einer totalen Ordnung angeordnet und Jobs können nur benachbarte Maschinen in Bezug auf diese Ordnung nutzen. In dem Single Resource Constraint Scheduling Problem gibt es eine zusätzliche Einschränkung, wie viele Jobs gleichzeitig verarbeitet werden können. Für die genannten Varianten des Parallel Task Scheduling Problems betrachten wir eine Erweiterung, bei der die Maschinen in identische Cluster gruppiert sind. Bei der Bearbeitung eines Jobs dürfen in diesem Modell nur Maschinen aus einem Cluster genutzt werden. Für all diese Probleme schließen wir Lücken zwischen Nichtapproximierbarkeit und Algorithmen. Für Parallel Task Scheduling zeigen wir, dass es stark NP-vollständig ist, wenn genau 4 Maschinen gegeben sind. Vorher war ein pseudopolynomieller Algorithmus für bis zu 3 Maschinen bekannt, sowie dass dieses Problem stark NP-vollständig ist für 5 oder mehr Maschinen. Für Strip Packing zeigen wir, dass es keinen pseudopolynomiellen Algorithmus gibt, der eine Güte besser als 5/4 besitzt und geben einen pseudopolynomiellen Algorithmus mit Güte (5/4 +ε) an. Für Single Resource Constraint Scheduling ist die bestmögliche Güte eine 3/2-Approximation und wir präsentieren eine (3/2 +ε)-Approximation. Für die Erweiterung auf identische Cluster gibt es keine Approximation mit Güte besser als 2. Vor unseren Untersuchungen waren bereits Algorithmen mit Güte 2 bekannt, die jedoch gigantische Worst-Case Laufzeiten haben. Wir geben für alle drei Varianten 2-Approximationen mit linearer Laufzeit an, sofern mindestens drei Cluster gegeben sind. Schlussendlich betrachten wir noch Scheduling auf Identischen Maschinen mit Setup Zeiten. Wir entwickeln für drei untersuche Varianten dieses Problems jeweils einen EPTAS, wobei ein EPTAS das beste ist, auf das man hoffen kann, es sei denn es gilt P = NP.

This thesis concerns repetitive structures in words. More precisely, it contributes to studying appearance and absence of such repetitions in words. In the first and major part of this thesis, we study avoidability of unary patterns with permutations. The second part of this thesis deals with modeling and solving several avoidability problems as constraint satisfaction problems, using the framework of MiniZinc. Solving avoidability problems like the one mentioned in the past paragraph required, the construction, via a computer program, of a very long word that does not contain any word that matches a given pattern. This gave us the idea of using SAT solvers. Representing the problem-based SAT solvers seemed to be a standardised, and usually very optimised approach to formulate and solve the well-known avoidability problems like avoidability of formulas with reversal and avoidability of patterns in the abelian sense too. The final part is concerned with a variation on a classical avoidance problem from combinatorics on words. Considering the concatenation of i different factors of the word w, pexp_i(w) is the supremum of powers that can be constructed by concatenation of such factors, and RTi(k) is then the infimum of pexp_i(w). Again, by checking infinite ternary words that satisfy some properties, we calculate the value RT_i(3) for even and odd values of i.

Visual programming languages based on node-link diagrams are supposedly easy to use and to understand. This is only true, however, if the diagram elements are properly placed - a tedious and time-consuming process if done manually. Automatic graph layout algorithms alleviate users from that burden. Since even visual languages usually cannot make do without text, it follows that layout algorithms need to properly support textual labels. That is what this work is all about. We start by examining how enough space can be reserved for textual labels to be properly placed without overlaps. We then look at how users place comments in diagrams to establish relations to diagram elements. Our aim is to infer those, in order to take them into account during layout. We finally look at the negative implications of too much text: large diagrams and too much information. Different label management strategies dynamically change the text of labels, thus changing their size and, optionally, the amount of text displayed. All of the techniques are evaluated according to aesthetic criteria, and most are also validated through user studies.

Modelle haben sich zu Dokumentationszwecken bewährt, existieren in der Praxis aber oftmals losgelöst voneinander. Durch die wachsende Komplexität in den Unternehmen reicht jedoch eine getrennte Betrachtung nicht mehr aus. Das Zusammenspiel der Unternehmensbestandteile muss bei Entscheidungen berücksichtigt werden. Eine Enterprise Architecture (EA) eignet sich zur Herstellung einer übergreifenden Sichtweise. Wobei hauptsächlich aggregierte Inhalte enthalten sind, die manuell erstellt werden. Damit ist die EA ein weiteres Datensilo. Durch das Fehlen detaillierter Informationen in der EA sind außerdem die Möglichkeiten einer ganzheitlichen Analyse begrenzt. Die vorliegende Arbeit entwickelt daher ein Gesamtkonzept, um Detailinhalte zu vernetzen und übergreifende Analysen zu ermöglichen. Insbesondere werden auch Datenwerte (z.B. Kosten) einbezogen. Eine Indirektstufe kann die Teilmodelle lose verknüpfen. Zugleich dient ein einfaches EA-Vokabular als neutrale Begriffsschicht. Mithilfe der Technologien des Semantic Web entsteht so eine integrierte Datenbasis. Sie positioniert sich als Ebene oberhalb der Datenquellen. Anschließend kann eine übergreifende Analyse erfolgen, in der alle Inhalte kombiniert werden. Zur Konkretisierung des Ansatzes fokussiert sich die Arbeit auf die Ableitung des Bedarfs an Handlungen. Mit der Importance-Performance-Analyse wird ein Verfahren aus dem Qualitätsmanagement von Dienstleistungen entliehen und auf die EA-Analyse übertragen. Die Berechnung basiert auf flexibel zu beschreibenden Kennzahlen, bei deren Definition das EA-Vokabular verwendet wird. Als Ergebnis werden Gesamtratings für alle Untersuchungsobjekte ausgewiesen. Sie sagen etwas über einen Handlungsbedarf und die Dringlichkeit aus. Auch die Analyse basiert auf Technologien des Semantic Web. Als Nachweis der Realisierbarkeit wurde der Ansatz in einem Prototyp umgesetzt. Außerdem wird ein praxisnaher Anwendungsfall einer Digitalisierungsinitiative bei einer Versicherung skizziert.

In dieser Dissertation wird ein Handelssystem beschrieben und evaluiert, welches rückläufige Tendenzen nach Überreaktionen in Finanzmärkten analysiert und ausnutzt. Hierfür werden Fehlbewertungen über ein neues Verfahren stochastisch modelliert, um den tatsächlichen Wert eines Finanzprodukts von irrationalen Kursbewegungen zu separieren -- die Analyse von Realmarktdaten offenbart langfristige Gleichgewichtsniveaus, zu dessen Rückkehr untersuchte Kursprozesse tendieren. Verzögerte Wechselwirkungen zwischen unterschiedlichen Finanzprodukten helfen zusätzlich, Überreaktionen zu erkennen. Erkenntnisse der Martingal- und Portfoliotheorie werden bei der Definition des Handelssystems mit dem Ziel kombiniert, identifizierte Fehlbewertungen in gleichmäßige Gewinne zu überführen. Auf diese Weise wird ein nachhaltiger und sicherheitsorientierter Vermögensaufbau begünstigt. Um möglichst präzise Aussagen über den Erfolg des Handelssystems treffen zu können, werden Simulationen auf künstlichen und realen Kursdaten untersucht. Ausgewählte Performance- und Risikomaße werden dabei einerseits modellbasiert ausgewertet, um den Einfluss einzelner Zeitreiheneigenschaften akkurat bestimmen zu können. Andererseits werden Realmarktdaten genutzt, um einen unverfälschten Blick über den tatsächlichen Erfolg der theoretischen Überlegungen zu ermöglichen. Für die Evaluation werden Finanzmarktdaten von Aktien, Rohstoffen und Wechselkursen im Bereich von 1968 bis 2018 untersucht. Die abschließende finanzwirtschaftliche Auswertung offenbart an einem umfassenden Beispiel, dass das Handelssystem in der Dekade von 2008 bis 2018 stetige Gewinne bei einem moderaten Risiko generiert hätte. Mean-reversion is a fundamental term in finance market analysis that refers to the assumption of an equilibrium in asset prices that is superimposed with overreactions. This dissertation describes and evaluates a trading system that exploits mean-reverse price tendencies in finance markets. Under the assumption of mispricings, a stochastic model is developed to separate fair price levels from irrational price movements. Analysis results reveal long-term balances in the probed market data. Delayed interdependencies between asset classes are utilized to improve the identification of overreactions. Methods of the martingale and portfolio theory are combined to convert these mispricings into steady returns with the objective to depict a sustainable and security-oriented trading system. Simulations on artifical and real quote data are combined to generate precise statements over the success of the trading system. On the one hand, performance and risk measures are evaluated in a model-based approach to quantify the influence of crucial time series properties. On the other hand, results on real market data allow unbiased performance and risk statements. The evaluation is based on finance market data of stocks, resources and foreign exchanges in the period of 1968 and 2018. Next to an isolated analysis of trading results for single instruments, the performance of a portfolio of mixed asset classes is reviewed. A final evaluation from 2008 to 2018 depict steady returns over the whole decade. As a diversified asset composition smoothes equity requirements, the examined portfolio succeeds in a further risk reduction.

Reactive systems interact with their environment by reading inputs and computing and feeding back outputs in reactive cycles that are also called ticks. Often they are safety critical systems and are increasingly modeled with highlevel modeling tools. The concepts of the corresponding modeling languages are typically aimed to facilitate formal reasoning about program constructiveness to guarantee deterministic output and are explicitly abstracted from execution time aspects. Nevertheless, the worst-case execution time of a tick can be a crucial value, as it decides the frequency in which the system can interact with its surroundings. An excessive tick Worst Case Execution Time (WCET) can lead to lost inputs or tardy reaction to critical events. Thus, the modeler has to make sure that the timing behaviour of the system under development meets the specifications. This thesis proposes a general approach to interactive timing analysis, which enables the feedback of detailed timing values directly in the model representation to support timing aware modeling. The concept is based on a generic timing interface that enables the exchangeability of the modeling as well as the timing analysis tool for the flexible implementation of varying tool chains. This aims at enhancing the comparability of tools and facilitates the sharing of benchmark model suites. The introduced approach is applicable not only to dataflow-based systems, but also to state-based systems. The latter is enabled by a concept for communicating analysis requests and responses for arbitrary code parts instead of a restriction to function granularity. The proposed timing analysis approach includes visual highlighting and modeling pragmatics features to guide the user to WCET hotspots for timing related model revisions. The approach is practically evaluated with an open-source Eclipse-based example implementation for the modeling language SCCharts, which includes a user study. Reaktive Systeme interagieren mit ihrer Umgebung, indem sie in Zyklen, sogenannten Ticks, Eingaben einlesen und Ausgaben errechnen und zurückgeben. Meistens sind reaktive Systeme sicherheitskritisch. Sie werden typischerweise in spezialisierten Modellierungstools entworfen und die dazugehörigen Modellierungssprachen sind auf die formale Analyse der Konstruktivität optimiert, die eindeutige Ausgaben garantiert. Dies wird unter anderem durch eine bewusste Abstraktion von Laufzeitaspekten erreicht. Dennoch ist die maximale Laufzeit eines Ticks ein bedeutender Aspekt, denn sie bestimmt die mögliche Interaktionsfrequenz zwischen Umwelt und System und damit die Rechtzeitigkeit von Reaktionen. Dementsprechend muss bei der Systementwicklung darauf geachtet werden, dass die Spezifikationen bezüglich der maximalen Ausführungszeit eines Ticks gewahrt bleiben. In dieser Arbeit wird ein genereller Ansatz der interaktiven Ausführungszeitanalyse vorgeschlagen, der diese Aufgabe durch die Anzeige aktueller und detaillierter Zeitwerte in der Modelldarstellung erleichtert. Das Konzept hierzu beruht auf einer übergreifenden Schnittstelle, über die wechselnde Modellierungs- und Analysewerkzeuge flexibel miteinander verbunden werden können, welches Vergleiche und die Wiederverwendung von Testmodellen erleichtert. Der vorgestellte Ansatz ist sowohl für datenflussbasierte als auch für zustandsbasierte Systeme geeignet. Dies wird durch das Konzept ermöglicht, dass anstelle von Funktionen beliebige Codeabschnitte unter Analyse gestellt werden können. Der vorgeschlagene Ansatz umfasst zusätzlich die optische Hervorhebung von zeitkritischen Modellbereichen und den Einsatz von Konzepten aus der Modellierungspragmatik. Das Konzept wurde praktisch mit einer Eclipse-basierten Implementierung in Open-Source-Software ausgewertet; dies schließt die Anwendung in einer Benutzerstudie ein.

In this thesis a series of novel algorithms for high quality restoration of coherent images is introduced. This task cannot be solved with established methods for the restoration of incoherent images. These algorithms focus on the correction of images in coherent imaging systems with a-priori known aberrations. The new wavefront correction algorithms achieve a significantly higher restoration quality than any previously known technique. The algorithms in this thesis are based on latest advances in optimization algorithms, particularly projections onto convex sets, proximal optimization and fractal self-similarity. Convergence and performance of the individual algorithms are analyzed in detail in various scenarios on real and simulated images. The evaluation also deals with the impact of noise on the restoration quality. Practical application of the new algorithms on microscopic images of diverse biological and human samples, as well as shadowgraph images of plankton acquired with a laboratory setup prove their efficiency. The new algorithms also have promising future applications in other areas, for example in adaptive optics and astronomy. In dieser Thesis werden mehrere neue Algorithmen für eine qualitativ hochwertige Restaurierung von kohärenten Bildern vorgestellt. Diese Aufgabe kann mit den bekannten Methoden für die Restaurierung von nicht kohärenten Bildern nicht gelöst werden. Die neuen Algorithmen sind auf die Wiederherstellung von Bildern in kohärenten Abbildungssystemen, bei denen die Aberrationen a-priori bekannt sind, ausgerichtet. Sie dienen der Korrektur der Wellenfront und erreichen eine wesentlich höhere Qualität der Bildrekonstruktion als sämtliche vorbekannte Verfahren. Die Algorithmen in dieser Thesis basieren auf neuesten Optimierungsalgorithmen, wie Projektionen in konvexe Sets, proximale Optimierung und fraktaler Ähnlichkeit. Die Konvergenz und Leistung der einzelnen Algorithmen wird ausführlich in unterschiedlichen Szenarien mit simulierten und realen Bildern untersucht. Eine praktische Erprobung der neuen Algorithmen an mikroskopischen Aufnahmen von unterschiedlichen biologischen und humanen Proben, wie auch an Aufnahmen vom Shadowgraph, bestätigt ihre Effizienz. Die neuen Algorithmen haben vielversprechende künftige Anwendungen, auch in anderen Gebieten, z.B. in der adaptiven Optik und der Astronomie.

The area of graph drawing is concerned with positioning the elements of a graph on a canvas such that the resulting drawing is well-readable by humans and aids their execution of certain tasks. While known methods are usually well-studied from a theoretical perspective, both their applicability to graphs from practice and their integration into tools from practice are not always satisfactory. This is due to various reasons, for instance, due to known methods usually solving well-defined, self-contained problems that do not cover all of the bits and pieces that must be considered in practice. There, the diagrams the graphs originate from often comprise more than just simple nodes and simple edges, they tend to be messy and complex, and existing methods regularly compute drawings with poor compactness. This thesis is concerned with improving the well-known layer- based layout approach, originally proposed by Sugiyama et al., and devotes special attention to the requirements of data flow diagrams. It presents new methods for the approach’s layer assignment and coordinate assignment steps, and it identifies and illustrates research tasks that are essential to further better the situation in practice.

Vergleich des Adhäsionsverhaltens verschiedener Staphylococcus aureus Stämme von Patienten mit Granulomatose mit Polyangiits und Normalkontrollen an einer immortalen nasalen Epithelzelllinie (RPMI 2650 Zelllinie)

The detection of geometric primitives such as points, lines and arcs is a fundamental step in computer vision techniques like image analysis, pattern recognition and 3D scene reconstruction. In this thesis, we present a framework that enables a reliable detection of geometric primitives in images. The focus is on application in man-made environments, although the process is not limited to this. The method provides robust and subpixel accurate detection of points, lines and arcs, and builds up a graph describing the topological relationships between the detected features. The detection method works directly on distorted perspective and fisheye images. The additional recognition of repetitive structures in images ensures the unambiguity of the features in their local environment. We can show that our approach achieves a high localization accuracy comparable to the state-of-the-art methods and at the same time is more robust against disturbances caused by noise. In addition, our approach allows extracting more fine details in the images. The detection accuracy achieved on the real-world scenes is constantly above that achieved by the other methods. Furthermore, our process can reliably distinguish between line and arc segments. The additional topological information extracted by our method is largely consistent over several images of a scene and can therefore be a support for subsequent processing steps, such as matching and correspondence search. We show how the detection method can be integrated into a complete feature-based 3D reconstruction pipeline and present a novel reconstruction method that uses the topological relationships of the features to create a highly abstract but semantically rich 3D model of the reconstructed scenes, in which certain geometric structures can easily be detected. Die Detektion von geometrischen Primitiven wie Punkten, Linien und Bögen ist ein elementarer Verarbeitungsschritt für viele Techniken des maschinellen Sehens wie Bildanalyse, Mustererkennung und 3D-Szenenrekonstruktion. In dieser Arbeit wird eine Methode vorgestellt, die eine zuverlässige Detektion von geometrischen Primitiven in Bildern ermöglicht. Der Fokus liegt auf der Anwendung in urbanen Umgebungen, wobei der Prozess nicht darauf beschränkt ist. Die Methode ermöglicht eine robuste und subpixelgenaue Detektion von Punkten, Linien und Bögen und erstellt einen Graphen, der die topologischen Beziehungen zwischen den detektierten Merkmalen beschreibt. Die Detektionsmethode kann direkt auf verzeichnete perspektivische Bilder und Fischaugenbilder angewendet werden. Die zusätzliche Erkennung sich wiederholender Strukturen in Bildern gewährleistet die Eindeutigkeit der Merkmale in ihrer lokalen Umgebung. Das neu entwickelte Verfahren erreicht eine hohe Lokalisierungsgenauigkeit, die dem Stand der Technik entspricht und gleichzeitig robuster gegenüber Störungen durch Rauschen ist. Darüber hinaus ermöglicht das Verfahren, mehr Details in den Bildern zu extrahieren. Die Detektionsrate ist bei dem neuen Verfahren auf den realen Datensätzen stets höher als bei dem aktuellen Stand der Technik. Darüber hinaus kann das neue Verfahren zuverlässig zwischen Linien- und Bogensegmenten unterscheiden. Die durch das neue Verfahren gewonnenen zusätzlichen topologischen Informationen sind weitgehend konsistent über mehrere Bilder einer Szene und können somit eine Unterstützung für nachfolgende Verarbeitungsschritte wie Matching und Korrespondenzsuche sein. Die Detektionsmethode wird in eine vollständige merkmalsbasierte 3D-Rekonstruktionspipeline integriert und es wird eine neuartige Rekonstruktionsmethode vorgestellt, die die topologischen Beziehungen der Merkmale nutzt, um ein abstraktes, aber zugleich semantisch reichhaltiges 3D-Modell der rekonstruierten Szenen zu erstellen, in dem komplexere geometrische Strukturen leicht detektiert werden können.

Safety-critical systems are a subclass of reactive systems, a dominating class of computer systems these days. Such systems control the airbags in our cars, the flaps of an aircraft, nuclear power plants or pace makers. Software for these systems must be reliable. Hence, a language and tooling is needed that allows to build and maintain reliable software models. Furthermore, a reliable compiler is required to obtain decent machine-understandable and executable code from highly abstract models. This thesis presents SCCharts, a Statecharts-based synchronous and visual modeling language for specifying and designing safety-critical systems and for deriving their implementations. It elaborates on why a control-flow oriented and synchronous language is desirable and how incremental language features are chosen to flatten learning curve. It presents an interactive incremental model transformation based compilation approach termed SLIC. It shows how SLIC helps in supporting both, the modeler and the tool smith for building reliable models and maintaining a reliable compiler, respectively. A SLIC-based compiler for SCCharts including its high-level model transformations is presented. Furthermore, practicality aspects of the KIELER SCCharts language and tooling implementation complete the considerations to validate the proposed approach. Sicherheitskritische Systeme sind eine Unterklasse von reaktiven Systemen, welche heutzutage eine der wichtigsten und größten Klasse von Computersystemen darstellt. Solche Systeme kontrollieren die Airbags unserer Autos, die Landeklappen eines Passagierflugzeugs, Kernkraftwerke oder Herzschrittmacher. Software für solche Systeme muß absolut zuverlässig sein. Daher werden Computersprachen und Werkzeuge benötigt, die es erlauben, zuverlässige Softwaremodelle zu erstellen und zu warten. Weiterhin braucht es zuverlässige Kompiler, die aus solchen abstrakten Modellen korrekten maschinenlesbaren und ausführbaren Code erzeugen. Mit SCCharts präsentiert diese Arbeit eine zustandsmaschinenbasierte und synchrone Modellierungssprache für den Entwurf und zur Implementierung sicherheitskritischer Systeme. Es wird betrachtet, warum sich dafür eine kontrollflußorientierte und synchrone Sprache besonders gut eignet und welche Wahl inkrementeller Sprachbestandteile die Lernkurve senken können. Die Arbeit zeigt, wie ein als SLIC bezeichneter, interaktiver, inkrementeller und auf Modelltransformationen basierender Kompilierungsansatz sowohl dem Modellierer dabei helfen kann, zuverlässige Modelle zu erstellen, als auch den Werkzeugentwickler darin unterstützt, einen zuverlässigen Kompiler bereit zu stellen. Es wird ein auf SLIC basierender SCCharts Kompiler inklusive seiner high-level Modelltransformationen vorgestellt. Weiterhin wird der vorgestellte Ansatz mit Hilfe der beispielhaft umgesetzten KIELER SCCharts Sprach- und Werkzeugimplementierung auf seine Praktikabilität hin überprüft.

In this thesis we investigate properties of integer linear programs (ILPs) and their algorithmic use. Our main focus are ILP-formulations that come from concrete algorthmic problems like the bin packing problem or the scheduling problem on identical machines. Especially for this kind of ILPs we study structural properties as well as properties for their sensitivity. As a result, we are able to answer open algorithmical questions in the area of approximation and parameterized complexity. In the context of sensitivity we analyze how much an ILP solution has to be adjusted when the parameters of the ILP change. There is a classical results by Cook et al. which gave bounds for that question when optimal solutions are considered. However, in this thesis we investigate the sensitivity of ILPs when approximate solutions are allowed, i.e. solutions that differ by a factor of at most (1+ \epsilon) from the optimum value. We could apply the obtained results to the online bin packing problem, when an approximation guarantee with ratio $1+ \epsilon$ has to be fulfilled and repacking of already assigned items (limited by the so called migration factor) is allowed. In the context of structural results, we prove the existence (assuming the ILP is feasible) of solutions of a certain class of ILPs with a certain simplified structure. Specifically, in this thesis, we prove structure properties for ILPs that arise from formulations of bin packing or scheduling problems and natural generalization of those formulations. Based on the those structure properties, we develop an efficient approximation scheme for the scheduling problem on identical machines with a running time of 2^{\tilde{O}(1/\epsilon)} + poly}(n) and furthermore, we develop a structure theorem, which is applied to the bin packing problem when the number of different item sizes d is bounded. In dieser Dissertation werden Eigenschaften von ganzzahligen linearen Programmen (engl. integer linear programs, kurz: ILPs) untersucht. Von Interesse sind dabei hauptsächlich ILP-Formulierungen, welche sich aus dem Kontext von algorithmischen Problemstellungen ergeben, wie beispielsweise dem Bin Packing-Problem und dem Scheduling-Problem auf identischen Maschinen. Insbesondere für diese ILPs zeigen wir Strukturaussagen, sowie Aussagen über die Sensitivität und können so offene algorithmische Fragestellungen im Bereich von Approximation und parametrisierter Komplexität lösen. Im Kontext von Sensitivitätsaussagen wird untersucht, inwiefern Lösung des ILPs angepasst werden können, wenn sich die Parameter des ILPs leicht ändern. Ein klassisches Resultat von Cook u.a. gibt dabei für optimale Lösungen des ILPs Abschätzungen an. In dieser Arbeit betrachten wir Abschätzungen für die Senstivität wenn approximative Lösungen erlaubt sind, d.h. Lösungen deren Zielfunktionswert höchstens um einen Faktor 1+ \epsilon über dem optimalen Zielfunktionswert liegt. Diese Ergebnisse konnten wir auf das Online-Bin Packing-Problem anwenden, wenn eine approximative Lösung mit Güte 1+ \epsilon erreicht werden soll und in beschränktem Maße Items umgepackt werden dürfen. Im Kontext von Strukturaussagen wird in dieser Dissertation die Existenz von ILP-Lösungen bewiesen, welche eine bestimmte vereinfachte Struktur aufweisen. Insbesondere, konnten wir Strukturaussagen für ILPs entwickeln, welche sich aus Formulierungen des Bin Packing-Problems ergeben bzw. natürliche Verallgemeinerungen dieser Formulierung. Dadurch ist es uns zum einen gelungen ein effizientes Approximationsschemata für das Scheduling-Problem auf identischen Maschinen mit einer Laufzeit von 2^{\tilde{O}(1/\epsilon)} + poly(n) zu entwicklen und außerdem konnten wir eine Strukturaussage entwickeln, welche unter anderem Anwendung im Bin Packung-Problem fand, wenn die Anzahl der unterschiedlichen Itemgrößen d beschränkt ist.

In this thesis, we consider the parallelisation and application of SAT and CP solvers. In the first chapter, we consider SAT, the decision problem of propositional logic. We discuss details of the implementations of SAT solvers, and show how to improve upon existing sequential solvers. Furthermore, we discuss the parallelisation of these solvers with a focus on the communication of intermediate results within a parallel solver. The second chapter is concerned with Contraint Programing (CP) with learning. Contrary to classical Constraint Programming techniques, this incorporates learning mechanisms as they are used in the field of SAT solving. We present results from parallelising CHUFFED, a learning CP solver. In the final chapter, we discuss Sorting Networks, which are data oblivious sorting algorithms. Their independence of the input data lends them to parallel implementation. We consider the question how many parallel sorting steps are needed to sort some inputs, and present both lower and upper bounds for several cases.

Since the advent of Next Generation Sequencing (NGS) technology, the amount of data from whole genome sequencing has been rising fast. In turn, the availability of these resources led to the tapping of whole new research fields in molecular and cellular biology, producing even more data. On the other hand, the available computational power is only increasing linearly. In recent years though, special-purpose high-performance devices started to become prevalent in today’s scientific data centers, namely graphics processing units (GPUs) and, to a lesser extent, field-programmable gate arrays (FPGAs). Driven by the need for performance, developers started porting regular applications to GPU frameworks and FPGA configurations to exploit the special operations only these devices may perform in a timely manner. However, applications using both accelerator technologies are still rare. Major challenges in joint GPU/FPGA application development include the required deep knowledge of associated programming paradigms and the efficient communication both types of devices. In this work, two algorithms from bioinformatics are implemented on a custom hybrid-parallel hardware architecture and a highly concurrent software platform. It is shown that such a solution is not only possible to develop but also its ability to outperform implementations on similar- sized GPU or FPGA clusters in terms of both performance and energy consumption. Both algorithms analyze case/control data from genome- wide association studies to find interactions between two or three genes with different methods. Especially in the latter case, the newly available calculation power and method enables analyses of large data sets for the first time without occupying whole data centers for weeks. The success of the hybrid-parallel architecture proposal led to the development of a high- end array of FPGA/GPU accelerator pairs to provide even better runtimes and more possibilities.

Introduction: Late enhanced multi-slice computed tomography (leMDCT) introduced for the visualization of late enhancement (LE) indicating intramyocardial fibrosis in Hypertrophic Cardiomyopathy (HCM) leaves the left-ventricular (LV) cavity with low contrast at the time of scanning. With regard to potentential risk stratification we analysed whether leMDCT-datasets additionally allow for volumetric LV assessment. Methods: We prospectively included HCM-patients to perform leMDCT (64 slice-CT) followed by the gold standard, cardiovascular magnetic resonance (CMR) with late gadolinium enhancement (LGE) (1.5T). Dye was injected 7 minutes (Iopromid; 150mL) in leMDCT and 12 minutes (Gadolinium; 15mL 0.15mmoL/kgBW) in LGE-CMR before scanning. After creating three groups (0=no, 1=borderline and 2=sufficient LV-contrast) all reconstructed short cardiac axis views were manually and semiautomatically assessed and correlated with regard to LV muscle mass (MM) and other prognostically relevant volumetric parameters. Results: Mean age was 64.2±14 years of age. The three groups of varying contrast differed in weight and body mass index (p

Profiling refers to the process of collecting useful information or patterns about something. Due to the growth of the web, profiling methods play an important role in different applications such as recommender systems. In this thesis, we first demonstrate how knowledge graphs (KGs) enhance profiling methods. KGs are databases for entities and their relations. Since KGs have been developed with the objective of information discovery, we assume that they can assist profiling methods. To this end, we develop a novel profiling method using KGs called Hierarchical Concept Frequency-Inverse Document Frequency (HCF-IDF), which combines the strength of traditional term weighting method and semantics in a KG. HCF-IDF represents documents as a set of entities and their weights. We apply HCF-IDF to two applications that recommends researchers and scientific publications. Both applications show HCF-IDF captures topics of documents. As key result, the method can make competitive recommendations based on only the titles of scientific publications, because it reveals relevant entities using the structure of KGs. While the KGs assist profiling methods, we present how profiling methods can improve the KGs. We show two methods that enhance the integrity of KGs. The first method is a crawling strategy that keeps local copies of KGs up-to-date. We profile the dynamics of KGs using a linear regression model. The experiment shows that our novel crawling strategy based on the linear regression model performs better than the state of the art. The second method is a change verification method for KGs. The method classifies each incoming change into a correct or incorrect one to mitigate administrators who check the validity of a change. We profile how topological features influence on the dynamics of a KG. The experiment demonstrates that the novel method using the topological features can improve change verification. Therefore, profiling the dynamics contribute to the integrity of KGs.

The functional logic programming paradigm combines the two most important fields of declarative programming, namely functional and logic programming, in an integrated way to allow the concise notation of high-level programs. However, the variety of syntactic constructs and conciseness of programs may also impact their efficiency. To reduce the syntactic complexity of functional logic languages, a typical compilation scheme incorporates a normalization phase to subsequently replace complex constructs by simpler ones until a minimal language subset is reached. The efficiency of normalized programs can then be improved by means of different optimization techniques. A very powerful optimization technique is the partial evaluation of programs. Partial evaluation basically anticipates the execution of certain program fragments at compile time and computes a semantically equivalent program, which is usually more efficient at run time. Since partial evaluation is a fully automatic optimization technique, it can also be incorporated into the normal compilation scheme of programs. In this work we consider the language Curry as a representative of the functional logic programming paradigm. We develop a formal representation of the normalization process of Curry programs into a kernel language, while respecting the interference of different language constructs. We then define the dynamic semantics of this kernel language, before we subsequently develop a partial evaluation scheme and show its correctness and termination. Due to the previously described normalization process, this scheme is then directly applicable to arbitrary Curry programs. Furthermore, the implementation of a practical partial evaluator is sketched based on the partial evaluation scheme, and its applicability and usefulness is documented by a variety of typical partial evaluation examples. Das Paradigma der funktional-logischen Programmierung kombiniert die beiden wichtigsten Bereiche der deklarativen Programmierung, die funktionale und die logische Programmierung, um ausdrucksstarke Programme zu entwickeln. Jedoch erschweren die Vielzahl syntaktischer Konstrukte und der hohe Abstraktionsgrad auch die Übersetzung in effiziente Zielprogramme. Zur Reduktion der syntaktischen Komplexität beinhalten gängige Kompilierungsschemata eine Normalisierungsphase, in der komplexe Konstrukte schrittweise durch einfachere ersetzt werden, bis eine minimale Teilsprache erreicht wird. Die Effizienz normalisierter Programme kann dann mittels verschiedener Optimierungstechniken verbessert werden. Eine sehr mächtige Technik ist hierbei die partielle Auswertung, bei der zur Kompilierungszeit die Ausführung bestimmter Programmteile simuliert wird, um so ein semantisch äquivalentes Programm zu berechnen, das zur Laufzeit üblicherweise effizienter ausgeführt wird. Da die partielle Auswertung eine vollautomatische Optimierung darstellt, kann sie zudem in bestehende Kompilierungsschemata eingebunden werden. Diese Arbeit betrachtet die Sprache Curry als Repräsentanten für das funktional-logische Programmierparadigma. Zunächst wird eine formale Darstellung der Normalisierung von Curry-Programmen entwickelt, um die korrekte Transformation unterschiedlicher Sprachkonstrukte festzulegen. Für die resultierende Kernsprache wird dann deren dynamische Semantik definiert, um darauf aufbauend ein grundlegendes Schema zur partiellen Auswertung zu entwickeln und dessen Korrektheit und Terminierung zu zeigen. Aufgrund der Normalisierung eignet sich dieses Schema bereits zur partiellen Auswertung beliebiger Curry-Programme. Des Weiteren wird die Implementierung eines praktischen partiellen Auswerters skizziert und dessen Anwendbarkeit und Vorteilhaftigkeit anhand einiger typischer Beispiele demonstriert.

In dieser Arbeit wurde ein Recirculating Aquaculture Respirometre System (RARS) technisch entwickelt und die Einsatzmöglichkeiten in verschiedenen metabolischen Studien an Fischen unter Einbeziehung der Futtermittelverwertung evaluiert. Kapitel 1 stellt das RARS und die eingebauten online Messgeräte vor. Die Funktionalität des RARS wurde durch einige Beispielmessungen an Regenbogenforellen (Oncorhynchus mykiss) und Steinbutt, (Scophthalmus maximus) gezeigt. Im Kapitel 2 wurden über 8 Wochen das Wachstum, der Korpulenz-Faktor und die Proteinkatabolismus-Raten von juvenilen Steinbutt, bei drei verschiedenen CO2-Konzentrationen (5, 26, 42 mg l-1) im Haltungswasser untersucht. Es zeigte sich, dass die Fische, welche unter der höchsten CO2-Konzentration gehalten wurden, eine 3-fache Proteinnutzung im Energiestoffwechsel aufwiesen, verglichen mit Tieren, die bei den niedrigsten Konzentrationen gehalten wurden. Schlussendlich waren die Wachstumseinbußen und die Verringerung des Korpulenz-Faktors beim Steinbutt bei erhöhten CO2-Konzentrationen maßgeblich durch eine abnehmende Futteraufnahme bedingt. Im Kapitel 3 wurde das RARS erfolgreich zur Erfassung des Sauerstoffverbrauchs, des Proteinkatabolismus als Ammoniak-Quotient (AQ) und den Energiehaushalt von Regenbogenforellen bei variierendem Protein- und Sauerstoffangebot eingesetzt. Die Ergebnisse der vorliegenden Arbeit zeigen, dass reproduzierbare Umwelt-Manipulationen (CO2, O2 und Temperatur) für verschiedene Aquakultur-Verfahren simuliert und über die installierte Messtechnik überwacht, sowie durch das Computersystem des RARS aufgezeichnet werden konnten. Die verwendete Messtechnik für O2 und NH3/NH4+ arbeitete zufriedenstellend und die generierten Daten eigneten sich für die Berechnung von Stoffwechselraten inklusive des Anteils des Proteins am Energiestoffwechsel.

Life. Much effort is taken to grant humanity a little insight in this fascinating and complex but fundamental topic. In order to understand the relations and to derive consequences humans have begun to sequence their genomes, i.e. to determine their DNA sequences to infer information, e.g. related to genetic diseases. The process of DNA sequencing as well as subsequent analysis presents a computational challenge for recent computing systems due to the large amounts of data alone. Runtimes of more than one day for analysis of simple datasets are common, even if the process is already run on a CPU cluster. This thesis shows how this general problem in the area of bioinformatics can be tackled with reconfigurable hardware, especially FPGAs. Three compute intensive problems are highlighted: sequence alignment, SNP interaction analysis and genotype imputation. In the area of sequence alignment the software BLASTp for protein database searches is exemplarily presented, implemented and evaluated. SNP interaction analysis is presented with three applications performing an exhaustive search for interactions including the corresponding statistical tests: BOOST, iLOCi and the mutual information measurement. All applications are implemented in FPGA-hardware and evaluated, resulting in an impressive speedup of more than in three orders of magnitude when compared to standard computers. The last topic of genotype imputation presents a two-step process composed of the phasing step and the actual imputation step. The focus lies on the phasing step which is targeted by the SHAPEIT2 application. SHAPEIT2 is discussed with its underlying mathematical methods in detail, and finally implemented and evaluated. A remarkable speedup of 46 is reached here as well. Das Leben. Sehr viel Aufwand wird getrieben um der Menschheit einen Einblick in dieses faszinierende und komplexe, aber fundamentale Thema zu erlauben. Um Zusammenhänge zu verstehen und Folgen ableiten zu können hat der Mensch begonnen sein Genom zu sequenzieren, d.h. seine DNA zu bestimmen um daraus Informationen, z.B. in Bezug auf Erbkrankheiten folgern zu können. Der Prozess der DNA-Sequenzierung sowie die darauffolgenden Analysen sind schon allein wegen der riesigen Datenmengen eine Herausforderung für aktuelle Rechensysteme. Laufzeiten von über einen Tag für die Analyse einfacher Datensätze sind üblich, selbst wenn der Prozess bereits auf einem Computercluster ausgeführt wird. Diese Arbeit zeigt, wie dieses gängige Problem im Bereich der Bioinformatik mit rekonfigurierbarer Hardware, speziell FPGAs, angegangen werden kann. Es werden drei rechenintensive Themengebiete hervorgehoben: Sequenzalignment, SNP-Interaktionsanalyse und Genotyp-Imputation. Beispielhaft wird im Bereich des Sequenzalignments die Software BLASTp für die Suche in Proteinsequenzdatenbanken vorgestellt, implementiert und evaluiert. Die SNP-Interaktionsanalyse wird mit drei Verfahren zur vollständigen Suche von Interaktionen inklusive des dazugehörigen statistischen Tests vorgestellt: BOOST, iLOCi und die Messung der Transinformation. Alle Verfahren werden auf FPGA-Hardware implementiert und evaluiert, mit einer bestechenden Beschleunigung im dreistelligen Bereich gegenüber Standard-Rechnern. Das letzte Gebiet der Genotyp-Imputierung ist ein zweiteiliges Verfahren bestehend aus dem Phasing und der eigentlichen Imputation. Der Schwerpunkt liegt im Phasing-Schritt, der mit dem SHAPEIT2-Tool adressiert wird. SHAPEIT2 wird ausführlich mit den zugrunde liegenden mathematischen Methoden diskutiert, und schließlich implementiert und evaluiert. Auch hier wird ein beachtlicher Speedup von 46 erreicht.

The ever-increasing complexity of in silico experiments in computational science is reflected in the growing complexity of the simulation software enabling these experiments. However, computational scientists rarely employ state-of-the-art software engineering methods, which negatively affects their productivity as well as the reliability of their scientific results. To tackle this challenge, this book introduces the Sprat Approach, which hierarchically integrates multiple domain-specific languages to facilitate the cooperation of scientists from different disciplines and to support them in creating well-engineered software without extensive software engineering training. To evaluate the Sprat Approach, it is applied to the implementation of the Sprat Marine Ecosystem Model in an exploratory case study. The Sprat Marine Ecosystem Model is a novel end-to-end ecosystem model based on population balance equations. In order to evaluate the Sprat Model, it is parametrized for the eastern Scotian Shelf ecosystem with its intertwined direct and indirect fish stock interactions, which previously could not be modeled satisfactorily. The simulation results described in this book provide new insights into the main drivers of regime shifts in marine ecosystems.

Software systems are complex, as they must cover a diverse set of requirements describing functionality and the environment. Software engineering addresses this complexity with Model-Driven Engineering ( MDE ). MDE utilizes different models and metamodels to specify views and aspects of a software system. Subsequently, these models must be transformed into code and other artifacts, which is performed by generators. Information systems and embedded systems are often used over decades. Over time, they must be modified and extended to fulfill new and changed requirements. These alterations can be triggered by the modeling domain and by technology changes in both the platform and programming languages. In MDE these alterations result in changes of syntax and semantics of metamodels, and subsequently of generator implementations. In MDE, generators can become complex software applications. Their complexity depends on the semantics of source and target metamodels, and the number of involved metamodels. Changes to metamodels and their semantics require generator modifications and can cause architecture and code degradation. This can result in errors in the generator, which have a negative effect on development costs and time. Furthermore, these errors can reduce quality and increase costs in projects utilizing the generator. Therefore, we propose the generator construction and evolution approach GECO, which supports decoupling of generator components and their modularization. GECO comprises three contributions: (a) a method for metamodel partitioning into views, aspects, and base models together with partitioning along semantic boundaries, (b) a generator composition approach utilizing megamodel patterns for generator fragments, which are generators depending on only one source and one target metamodel, (c) an approach to modularize fragments along metamodel semantics and fragment functionality. All three contributions together support modularization and evolvability of generators.

Automotive software is mainly concerned with safety critical systems and the functional correctness of the software is very important. Thus static software analysis, being able to detect runtime errors in software, has become a standard in the automotive domain. The most critical runtime error is one which only occurs sporadically and is therefore very difficult to detect and reproduce. A reason for such an error is e. g., a race condition. The introduction of multicore hardware enables an execution of the software in real parallel. Hence, the risk of critical race conditions increases. This thesis introduces the MEMICS software verification approach. In order to produce precise results, MEMICS works based on the formal verification technique, bounded model checking. The internal model is able to represent an entire automotive control unit, including the hardware configuration as well as real-time operating systems like AUTOSAR and OSEK. The proof engine used to check the model is a newly developed interval constraint solver with an embedded memory model. MEMICS is able to detect common runtime errors, like e. g., a division by zero, as well as concurrent ones, like e. g., a critical race condition.

In many enterprises, the number of deployed applications is constantly increasing. Those applications - often several hundreds - form large software landscapes. The comprehension of such landscapes is frequently impeded due to, for instance, architectural erosion, personnel turnover, or changing requirements. Furthermore, events such as performance anomalies can often only be understood in correlation with the states of the applications. Therefore, an efficient and effective way to comprehend such software landscapes in combination with the details of each application is required. In this thesis, we introduce a live trace visualization approach to support system and program comprehension in large software landscapes. It features two perspectives: a landscape-level perspective using UML elements and an application-level perspective following the 3D software city metaphor. Our main contributions are 1) an approach named ExplorViz for enabling live trace visualization of large software landscapes, 2) a monitoring and analysis approach capable of logging and processing the huge amount of conducted method calls in large software landscapes, and 3) display and interaction concepts for the software city metaphor beyond classical 2D displays and 2D pointing devices. Extensive lab experiments show that our monitoring and analysis approach elastically scales to large software landscapes while imposing only a low overhead on the productive systems. Furthermore, several controlled experiments demonstrate an increased efficiency and effectiveness for solving comprehension tasks when using our visualization. ExplorViz is available as open-source software on www.explorviz.net. Additionally, we provide extensive experimental packages of our evaluations to facilitate the verifiability and reproducibility of our results. In vielen Unternehmen nimmt die Anzahl der eingesetzten Anwendungen stetig zu. Diese Anwendungen - meist mehrere hunderte - bilden große Softwarelandschaften. Das Verständnis dieser Softwarelandschaften wird häufig erschwert durch, beispielsweise, Erosion der Architektur, personelle Wechsel oder sich ändernde Anforderungen. Des Weiteren können Ereignisse wie Performance-Anomalien häufig nur in Verbindung mit den Anwendungszuständen verstanden werden. Deshalb wird ein möglichst effizienter und effektiver Weg zum Verständnis solcher Softwarelandschaften in Verbindung mit den Details jeder einzelnen Anwendung benötigt. In dieser Arbeit führen wir einen Ansatz zur live Trace Visualisierung zur Unterstützung des System- und Programmverständnisses von großen Softwarelandschaften ein. Dieser verwendet zwei Perspektiven: eine Landschaftsperspektive mit UML Elementen und eine Applikationsperspektive, welche der 3D Softwarestadtmetapher folgt. Unsere Hauptbeiträge sind 1) ein Ansatz, genannt ExplorViz, um live Trace Visualisierung von großen Softwarelandschaften zu ermöglichen, 2) ein Überwachungs- und Analyseansatz, welcher in der Lage ist die große Anzahl an Methodenaufrufen in einer großen Softwarelandschaft aufzuzeichnen und zu verarbeiten und 3) Anzeige- und Interaktionskonzepte für die Softwarestadtmetapher, welche über klassische 2D Anzeige und 2D Eingabegeräten hinausgehen. Umfassende Laborexperimente zeigen, dass unser Überwachungs- und Analyseansatz für große Softwarelandschaften elastisch skaliert und dabei nur einen geringen Overhead auf den Produktivsystemen erzeugt. Des Weiteren demonstrieren mehrere kontrollierte Experimente eine gesteigerte Effizienz und Effektivität beim Lösen von Verständnisaufgaben unter Verwendung unserer Visualisierung. ExplorViz ist als Open Source Anwendung verfügbar unter www.explorviz.net. Zusätzlich stellen wir umfangreiche Pakete für unsere Evaluierungen zur Verfügung um die Nachvollziehbarkeit und Wiederholbarkeit unserer Ergebnisse zu ermöglichen.

This thesis presents approximation algorithms for geometric packing and scheduling problems. First, improved AFPTAS for the Bin Packing Problem (BP) and its generalization, the Variable-sized Bin Packing Problem (VBP), are explained. Our algorithms have to solve the unbounded variant of the Knapsack Problem (KP) and of the Knapsack Problem with Inversely Proportional Profits (KPIP) as subproblems. In the normal 0-1 variant of KP, an item can be chosen only once. In the bounded variant, an individual bounded number of copies can be taken of every item. The unbounded variant (UKP) allows for an infinite number of copies of every item. KPIP is a generalization of KP in which we have not only one, but several knapsack sizes. The profit of an item is inversely proportional to the size of the knapsack into which it has been packed. This makes it non-trivial to choose the knapsack size that maximizes the profit over all knapsack sizes. Similar to KP, there are the 0-1, the bounded, and the unbounded variant of KPIP. We first present FPTAS for every of the three variants of KPIP. They are faster than the natural approach to separately solve for every knapsack size the corresponding Knapsack Problem. Second, we present an FPTAS for UKP that is faster and needs less storage space than previously known algorithms. Finally, we combine the approaches of the KPIP and of the UKP FPTAS to get an FPTAS for the Unbounded KPIP that has again a better time and space complexity. All these results improve the running time for our BP and VBP algorithms. As a corollary, we also improve the running time for a Strip Packing AFPTAS. Finally, we consider Scheduling on Unrelated Machines of which we study the special case with a constant number K of machine types: one job has the same processing time on every machine of the same type. We present a PTAS for this special case. The algorithm has a better running time than the previously known algorithm for general (but constant) K. Diese Dissertation stellt Approximationsalgorithmen für geometrische Packungs- und Ablaufplanungsprobleme (Packing and Scheduling Problems) vor. Zuerst werden verbesserte AFPTAS für das Behälterproblem (Bin Packing, BP) und seine Verallgemeinerung, das Behälterproblem mit verschiedenen Behältergrößen (Variable-sized Bin Packing, VBP), erklärt. Unsere Algorithmen müssen die unbeschränkte (unbounded) Variante des Rucksackproblems (Knapsack Problem, KP) und des Rucksackproblems mit invers proportionalen Profiten (Knapsack Problem with Inversely Proportional Profits, KPIP) als Unterprobleme lösen. Bei KP gibt es die Varianten 0-1, beschränkt und unbeschränkt. KPIP ist eine Verallgemeinerung des Rucksackproblems mit mehreren Rucksackgrößen, die in dieser Dissertation eingeführt wird. Wie bei KP gibt es bei KPIP ebenfalls die Varianten 0-1, beschränkt und unbeschränkt. Wir stellen zuerst FPTAS für alle drei Varianten von KPIP vor. Sie sind schneller als der natürliche Ansatz, für jede Rucksackgröße das entsprechende Rucksackproblem einzeln zu lösen. Danach stellen wir ein FPTAS für UKP vor, das schneller ist und weniger Speicherplatz benötigt als zuvor bekannte Algorithmen. Schließlich kombinieren wir den Ansatz für KPIP und für das unbeschränkte KPIP, um ein FPTAS für die unbeschränkte Variante von KPIP zu erhalten, das wiederum eine kleinere Zeit- und Speicherkomplexität besitzt. All diese Resultate verbessern die Laufzeit unserer BP- und VBP-Algorithmen. Als Korollar verbessern wir außerdem die Laufzeit eines AFPTAS für das geometrische Zuschnittproblem (Strip Packing). Schließlich betrachten wir das Ablaufplanungsproblem auf heterogenen Maschinen (Scheduling on Unrelated Machines), bei dem wir den Spezialfall mit einer konstanten Anzahl K an Maschinentypen untersuchen: Eine Aufgabe (Job) hat auf jeder Maschine desselben Typs die gleiche Ausführungszeit. Wir stellen für diesen Spezialfall ein PTAS vor. Der Algorithmus ist schneller als das zuvor bekannte Verfahren für allgemeines (aber konstantes) K.

The problem addressed in this thesis is the extrinsic calibration of embedded multi-camera systems without overlapping views, i.e., to determine the positions and orientations of rigidly coupled cameras with respect to a common coordinate frame from captured images. Such camera systems are of increasing interest for computer vision applications due to their large combined field of view, providing practical use for visual navigation and 3d scene reconstruction. However, in order to propagate observations from one camera to another, the parameters of the coordinate transformation between both cameras have to be determined accurately. Classical methods for extrinsic camera calibration relying on spatial correspondences between images cannot be applied here. The central topic of this work is an analysis of methods based on hand-eye calibration that exploit constraints of rigidly coupled motions to solve this problem from visual camera ego-motion estimation only, without need for additional sensors for pose tracking such as inertial measurement units or vehicle odometry. The resulting extrinsic calibration methods are referred to as "eye-to-eye calibration". We provide solutions based on pose measurements (geometric eye-to-eye calibration), decoupling the actual pose estimation from the extrinsic calibration, and solutions based on images measurements (visual eye-to-eye calibration), integrating both steps within a general Structure from Motion framework. Specific solutions are also proposed for critical motion configurations such as planar motion which often occurs in vehicle-based applications. Diese Arbeit beschäftigt sich mit der extrinsischen Kalibrierung von Mehrkamerasystemen ohne überlappende Sichtbereiche aus Bildfolgen. Die extrinsischen Parameter fassen dabei Lage und Orientierung der als starr-gekoppelt vorausgesetzten Kameras in Bezug auf ein gemeinsames Referenzkoordinatensystem zusammen. Die Minimierung der Redundanz der einzelnen Sichtfelder zielt dabei auf ein möglichst großes kombiniertes Sichtfeld aller Kameras ab. Solche Aufnahmesysteme haben sich in den letzten Jahren als hilfreich für eine Reihe von Aufgabenstellungen der Computer Vision erwiesen, z. B. in den Bereichen der visuellen Navigation und der bildbasierten 3D-Szenenrekonstruktion. Um Messungen der einzelnen Kameras sinnvoll zusammenzuführen, müssen die Parameter der Koordinatentransformationen zwischen den Kamerakoordinatensystemen möglichst exakt bestimmt werden. Klassische Methoden zur extrinsischen Kamerakalibrierung basieren in der Regel auf räumlichen Korrespondenzen zwischen Kamerabildern, was ein überlappendes Sichtfeld voraussetzt. In dieser Arbeit werden alternative Methoden zur Lagebestimmung von Kameras innerhalb eines Mehrkamerasystems untersucht, die auf der Hand-Auge-Kalibrierung basieren und Zwangsbedingungen starr-gekoppelter Bewegung ausnutzen. Das Problem soll dabei im Wesentlichen anhand von Bilddaten gelöst werden, also unter Verzicht auf zusätzliche Inertialsensoren oder odometrische Daten. Die daraus abgeleiteten extrinsischen Kalibrierverfahren werden in Anlehnung an die Hand-Auge-Kalibrierung als Eye-to-Eye Calibration bezeichnet. Es werden Lösungsverfahren vorgestellt, die ausschließlich auf Posemessdaten basieren und den Prozess der Poseschätzung von der eigentlichen Kalibrierung entkoppeln, sowie Erweiterungen, die direkt auf visuellen Informationen der einzelnen Kameras basieren. Die beschriebenen Ansätze führen zu dem Entwurf eines Structure-from-Motion-Verfahrens, das Poseschätzung, Rekonstruktion der Szenengeometrie und extrinsische Kalibrierung der Kameras integriert. Bewegungskonfigurationen, die zu Singularitäten in den Kopplungsgleichungen führen, werden gesondert analysiert und es werden spezielle Lösungsstrategien zur partiellen Kalibrierung für solche Fälle entworfen. Ein Schwerpunkt liegt hier auf Bewegung in der Ebene, da diese besonders häufig in Anwendungsszenarien auftritt, in denen sich das Kamerasystem in oder auf einem Fahrzeug befindet.

As shown previously by Fuhrmann, there are several concepts for increasing the productivity of MDE by improving the practical handling of models. The automatic layout of graph-based models is a key enabler in this context. However, there is a striking contrast between the abundance of research results in the field of graph layout methods and the current state of graphical modeling tools, where only a tiny fraction of these results are ever adopted. This thesis aims to bridge this gap on three separate levels: specialized layout algorithms, configuration management, and software infrastructure. Regarding layout algorithms, here we focus on the layer-based approach. We examine its extension to include ports and hyperedges, which are essential features of certain kinds of graphs, e.g. data flow models. The main contribution is the handling of constraints on the positioning of ports, which is done mainly in the crossing minimization and edge routing phases. Hyperedges are represented with normal edges, simplifying their handling but introducing inaccuracies for counting crossings. A final extension discussed here is a sketch-driven approach for simple integration of user interactivity. An abstract layout is the selection of a layout algorithm with a mapping of its parameters to specific values. We discuss a new meta model allowing to specify the structure of a graph as well as its abstract layout and its concrete layout, i.e. positioning data computed by the layout algorithm. This forms a basis for efficient management of layout configurations. Furthermore, we investigate an evolutionary algorithm for searching the solution space of abstract layouts, taking readability criteria into account for evaluating solutions. The software infrastructure developed here targets the connection of arbitrary diagram viewers (front-ends) with arbitrary graph layout algorithms (back-ends). The main challenge is to find suitable abstractions that allow such generality and at the same time keep the complexity as low as possible. We discuss a possible realization based on the Eclipse platform, which is used by several modeling tools, e.g. the Graphical Modeling Framework. A web-based survey has been conducted among users of the layout infrastructure in order to evaluate to what extent the stated goals have been met. The overall feedback collected from this survey is very positive. Wie bereits von Fuhrmann gezeigt, kann die Produktivität modellgetriebener Softwareentwicklung durch zahlreiche Konzepte zur Verbesserung der praktischen Handhabung von Modellen erhöht werden. Dabei ist das automatische Layout graphenbasierter Modelle ein zentraler Schlüssel. Allerdings gibt es einen bemerkenswerten Kontrast zwischen der Fülle an Forschungsergebnissen im Bereich des Graphen-Layout und dem aktuellen Stand graphischer Modellierungswerkzeuge, bei denen nur ein kleiner Teil dieser Ergebnisse übernommen wird. Das Ziel dieser Arbeit ist diese Lücke auf drei separaten Ebenen zu überbrücken: spezialisierte Layout-Algorithmen, Verwaltung von Konfigurationen und Software-Infrastruktur. Im Bezug auf Layout-Algorithmen liegt der Schwerpunkt auf dem Layer-basierten Ansatz. Wir untersuchen dessen Erweiterung zur Unterstützung von Ports und Hyperkanten, was wesentliche Bestandteile bestimmter Arten von Graphen sind, z.B. Datenflussmodelle. Der Hauptbeitrag ist die Einbeziehung von Bedingungen für die Positionierung von Ports, vor allem während der Kreuzungsminimierung und der Kantenführungsphase. Hyperkanten werden durch normale Kanten repräsentiert, was deren Verarbeitung vereinfacht aber Ungenauigkeiten beim Zählen von Kreuzungen verursacht. Als letzte Erweiterung betrachten wir einen Sketch-basierten Ansatz für die einfache Integration von Nutzerinteraktivität. Ein abstraktes Layout ist die Auswahl eines Layout-Algorithmus zusammen mit einer Abbildung seiner Parameter auf konkrete Werte, während ein konkretes Layout Positionsdaten beschreibt, die von einem Algorithmus berechnet wurden. Wir diskutieren ein neues Metamodell, mit dem sowohl die Struktur als auch das abstrakte sowie das konkrete Layout eines Graphen spezifiziert werden kann. Dies bildet eine Grundlage für die effiziente Verwaltung von Layout-Konfigurationen. Zudem untersuchen wir einen evolutionären Algorithmus für die Suche im Lösungsraum abstrakter Layouts, wobei zur Bewertung von Lösungen Ästhetikkriterien ausgewertet werden. Die in dieser Arbeit entwickelte Software-Infrastruktur hat als Ziel, beliebige Graphen-basierte Diagramme (front-ends) mit beliebigen Layout-Algorithmen (back-ends) zu verbinden. Die größte Herausforderung dabei ist das Finden geeigneter Abstraktionen, die eine solche Allgemeingültigkeit erlauben und gleichzeitig die Komplexität so niedrig wie möglich halten. Wir betrachten eine mögliche Realisierung, die auf Eclipse basiert, eine von vielen Modellierungswerkzeugen verwendete Plattform. Eine Web-basierte Umfrage wurde unter Nutzern der Layout-Infrastruktur durchgeführt, um zu untersuchen inwieweit die gesteckten Ziele erfüllt worden sind. Die allgemeine Resonanz zu dieser Umfrage ist sehr positiv.

Mit der Veröffentlichung der ersten PISA-Ergebnisse Ende 2001 in Deutschland ("PISA-Schock") wurden Diskussionen laut, den Unterricht mit neuen Ideen und innovativen Ansätzen zu reformieren. Parallel hierzu ist in den letzten dreizehn Jahren in Deutschland die Anzahl an Wettbewerben in der Schullandschaft stark angestiegen. Trotz vieler teilnehmenden Schulen wurden allerdings nur wenige wissenschaftliche Studien durchgeführt, die die Möglichkeiten und Potenziale von Wettbewerben im Unterricht untersucht haben. Erst Ende 2006 fand im Hamburger Körber-Forum die Fachtagung "Wozu Schülerwettbewerbe? Impulse für Bildung und Lernen" statt, die eine breitere und systematischere Diskussion über die Bedeutung von Wettbewerben in Schulen und Unterricht initiierte. In dieser Arbeit werden zwei Informatikwettbewerbe des Instituts für Informatik der Christian-Albrechts-Universität zu Kiel - der Movingart-Wettbewerb in der Sekundarstufe I und die Software-Challenge in der Sekundarstufe II - in Hinblick auf die Frage untersucht, ob und inwieweit sie geeignete Werkzeuge der Unterrichtsentwicklung darstellen. Die Ergebnisse der dazu durchgeführten Studien zeigen, dass beide Wettbewerbe in ihrer Struktur und Durchführung neue und wichtige Impulse für den Unterricht liefern: Kompetenzförderung sowie besonders starke Motivation der Schülerinnen und Schüler, vertiefte Einblicke in Inhalte und Methoden der Informatik, fächerübergreifende Zusammenarbeit sowie die Ermöglichung von binnendifferenzierter- und wissenschaftspropädeutischer Arbeit im Unterricht. Beide Wettbewerbe können damit einen wichtigen Beitrag zur Steigerung der Unterrichtsqualität leisten und bieten mithin teilnehmenden Schulen einen erheblichen pädagogischen Mehrwert. Es ist zu vermuten, dass zukünftige Unterrichtswettbewerbe, die sich in ihrer Entwicklung an den wesentlichen Konstruktionsmerkmalen von Movingart und der Software-Challenge orientierten, zu ähnlichen Verbesserungen der Unterrichtsqualität beitragen. When the first PISA-results were published in Germany in the end of 2001 "PISA-Shock", many discussions started about reforming teaching with the help of new ideas and innovative approaches. Around the same time, the number of competitions in German schools started to grow immensely. Although many schools have taken part in such competitions, we are lacking studies investigating their potential. Only as recent as 2006, a scientific meeting was held at the Körber-Forum in Hamburg called "Why competitions for pupils? Impulses for education and learning", which initiated a wider and more systematic discussion about the meaning of competitions at school and in teaching. Two competitions in computer science - the Movingart-Competition for the lower secondary school ages and the Software Challenge for the senior years, both organized by the computer science department of Kiel University - are investigated in this dissertation as to whether and how far they represent useful tools in the development of teaching. The findings show that both competitions offer new and important impulses for teaching in its structure and its organization: pupils develop more competences, their motivation rises, and they get deeper insights into the subject; teachers start cooperations across different subjects and receive more options for adapting their teaching to invidual pupils. Thus, both competitions offer a great contribution to improve the quality of teaching and strongly offer the schools taking part an increased educational benefit. It is to be presumed that new future competitions for schools which are constructed in the same or a comparable way as Movingart and Software-Challenge will contribute in a similar improving way to the quality of teaching.

The tracking of deforming objects and the reconstruction of deformation in image sequences is one of the current research areas in computer vision. In contrast to rigid scenes, which can be analyzed and reconstructed very well, general deformations come with an infinite number of sub-movements and ways to parametrize them, which makes it very difficult to formulate discrete tracking goals. In contrast to the classic reconstructions based on color data alone, the combination of depth and color video provides tracking algorithms with a data foundation with less room for ambiguities, but also requires new algorithmic approaches to handle different entities and to exploit the available data. This thesis discusses an Analysis by Synthesis (AbS) scheme as an approach to the deformation tracking problem, a method that differs in many key aspects from common reconstruction schemes. It is demonstrated that AbS based deformation reconstruction can reconstruct complex deformations, deal with occlusions and self-occlusions, and can also be used for real-time tracking.

Classic graph algorithms are usually presented and analysed in imperative programming languages. Imperative programming languages are well-suited for the description of a program flow, in which the order in which the operations are performed is important. One common example of such a description is the successive, typically destructive modification of objects. This kind of iteration often occurs in the context of graph algorithms that deal with a certain kind of optimisation. In functional programming, the order of execution is abstracted and problem solutions are described as compositions of intermediate solutions. Additionally, functional programming languages are referentially transparent and thus destructive updates of objects are discouraged. The development of purely functional graph algorithms begins with the decomposition of a given problem into simpler problems. In many cases the solutions of these partial problems can be used to solve different problems as well. What is more, this compositionality allows exchanging functions for more efficient or more comprehensible versions with little effort. An algebraic approach with a focus on relation algebra as defined by Tarski is used as an intermediate step in this dissertation. One advantage of this approach is the formality of the resulting specifications. Despite their formality, the resulting expressions are still readable, because the algebraic operations have intuitive interpretations. Another advantage is that the specification is executable, once the necessary operations are implemented. This dissertation presents the basics of the algebraic approach in the functional programming language Haskell. Using this foundation, some exemplary graph-theoretic problems are solved in the presented framework. Finally, optimisations of the presented implementations are discussed and pointers are provided to further problems that can be solved using the above methods. Klassische Graphalgorithmen werden üblicherweise in imperativen Programmiersprachen beschrieben und analysiert. Imperative Programmiersprachen eignen sich gut, um Programmabläufe zu beschreiben, in welchen die Reihenfolge der Operationen wichtig ist. Dies betrifft insbesondere die schrittweise, in der Regel destruktive Veränderung von Objekten, wie sie häufig im Falle von Optimierungsproblemen auf Graphen vorkommt. In der funktionalen Programmierung abstrahiert man von einer festen Berechnungsreihenfolge und beschreibt Problemlösungen als Kompositionen von Teillösungen. Ferner sind funktionale Programmiersprachen referentiell transparent, sodass destruktive Veränderungen nur bedingt möglich sind. Die Entwicklung rein funktionaler Graphalgorithmen setzt bei der Zerlegung der bestehenden Probleme in einfachere Probleme an. Oftmals können Lösungen dieser Teilprobleme auch in anderen Situationen eingesetzt werden. Darüber hinaus erlaubt es diese Kompositionalität, einzelne Funktionen mit wenig Aufwand durch effizientere oder verständlichere Fassungen auszutauschen. Als Zwischenschritt in der Entwicklung wird in dieser Dissertation ein algebraischer Ansatz basierend auf der Relationenalgebra im Sinne von Tarski verwendet. Ein Vorteil dieses Ansatzes ist die Formalität der entstehenden Spezifikationen. Trotz ihrer Formalität bleiben die entstehenden Ausdrücke oft leserlich, weil die algebraischen Operationen anschauliche Interpretationen zulassen. Ein weiterer Vorteil ist, dass Spezifikationen ausführbar werden, sobald bestimmte Basisoperationen implementiert sind. In dieser Dissertation werden Grundlagen einer Implementierung des algebraischen Ansatzes in der funktionalen Programmiersprache Haskell behandelt. Ausgehend hiervon werden exemplarisch einige Probleme der Graphentheorie gelöst. Schließlich werden Optimierungen der vorgestellten Implementierungen und weitere Probleme, welche mit den obigen Methoden lösbar sind, diskutiert.

Application-level monitoring of continuously operating software systems provides insights into their dynamic behavior, helping to maintain their performance and availability during runtime. Such monitoring may cause a significant runtime overhead to the monitored system, depending on the number and location of used instrumentation probes. In order to improve a system's instrumentation and to reduce the caused monitoring overhead, it is necessary to know the performance impact of each probe. While many monitoring frameworks are claiming to have minimal impact on the performance, these claims are often not backed up with a detailed performance evaluation determining the actual cost of monitoring. Benchmarks can be used as an effective and affordable way for these evaluations. However, no benchmark specifically targeting the overhead of monitoring itself exists. Furthermore, no established benchmark engineering methodology exists that provides guidelines for the design, execution, and analysis of benchmarks. This thesis introduces a benchmark approach to measure the performance overhead of application-level monitoring frameworks. The core contributions of this approach are 1) a definition of common causes of monitoring overhead, 2) a general benchmark engineering methodology, 3) the MooBench micro-benchmark to measure and quantify causes of monitoring overhead, and 4) detailed performance evaluations of three different application-level monitoring frameworks. Extensive experiments demonstrate the feasibility and practicality of the approach and validate the benchmark results. The developed benchmark is available as open source software and the results of all experiments are available for download to facilitate further validation and replication of the results.

Diese Arbeit zeigt, wie semantische Technologien (Sprachen und Werkzeuge) genutzt werden können, um Eisenbahn-Infrastrukturen zu modellieren und zu verifizieren. Dazu wurde ein semantisches Domänen-Modell entworfen und implementiert, das sowohl die Elemente von Eisenbahn-Infrastrukturen und deren Eigenschaften als auch die Beziehungen dieser Elemente untereinander darstellen kann. Zur Modellierung wurde die Web Ontology Language (OWL) in Kombination mit der Semantic Web Rule Language (SWRL) verwendet. Im Rahmen der Arbeit wurden Planungsrichtlinien von Eisenbahn-Infrastrukturen analysiert und exemplarisch in SWRL formalisiert. So wurde es ermöglicht, konkrete Eisenbahn-Infrastruktur-Planungsdaten in Instanzen des semantischen Domänenmodells zu transformieren, um diese Instanzen hinsichtlich ihrer Konformität mit Planungsrichtlinien zu verifizieren. Dieser Prozess wird anhand mehrerer Beispiele veranschaulicht. Ein weiterer Teil der Arbeit befasst sich mit einem Verfahren, mit dem Eisenbahn-Ingenieure bei der Suche nach Fehlern in Planungsdaten unterstützt werden können. Während OWL- und SWRL-Reasoner lediglich eine allgemeine Eingrenzung von Fehlern im zu verifizierenden Modell ermöglichen, wird durch Verwendung des in dieser Arbeit vorgestellten Konzepts der Semantic Constraints eine Eingrenzung auf konkrete fehlerhafte Axiome in Bezug auf die modellierten Planungsrichtlinien realisiert. Das Konzept basiert auf der Regelsprache SWRL und ermöglicht die Formulierung von Bedingungen, die dazu verwendet werden, Eisenbahn-Infrastruktur-Elemente in Form von OWL-Individuen zu überprüfen. Verstoßen einzelne Individuen gegen eine Bedingung, wird diese systematisch reduziert, um die Ursachen für den Verstoß gegen die Bedingung und die damit zusammenhängende Planungsrichtlinie zu ermitteln. In der Diskussion wird die Vergleichbarkeit des vorgestellten Ansatzes mit aktuell verwendeten XML-basierten Verfahren untersucht. Die Arbeit schließt mit einem Ausblick auf mögliche Weiterentwicklungen der vorgestellten Verfahren ab.

Current spoken dialogue systems are often criticised because they lack natural behaviour. In this thesis, a model to facilitate the development of user-friendly dialogues for information and control systems (e.g. travel-booking or smart room control systems) is created in order to address this problem. This also includes a study about the users' preferences, the classification of utterances according to intention and answer type and the development of a dialogue engine that can process dialogues based on this model. The developed model describes the dialogue flow and the combination of questions, answers and the resulting actions. Features like mixed initiative, open-ended questions, subdialogues and adaptable phrasings of system utterances lead to more natural dialogues and increase the usability of dialogue systems while linguistic datatypes, abstract question descriptions in connection with answer types and language generation methods enormously facilitate the definition of such dialogues for the developer. The separation of dialogue model and dialogue engine makes possible the reuse of base functionalities und prevents the mixing of execution logic and dialogue knowledge. The engine contains dialogue acts to classify user utterances and to prevent ambiguities as well as language understanding modules to identify the user's goal. In addition, it infers the next dialogue step under consideration of the specified dialogue behaviour. By implementing the Natural Dialogue System (NADIA), that runs the XML-based model, the functionality is proven. Aktuelle Sprachdialogsysteme haben oftmals den Ruf unnatürlich und nutzerunfreundlich zu sein. In dieser Dissertation wird diese Kritik adressiert und ein Modell zur einfacheren Entwicklung von nutzerfreundlichen Dialogen realisiert. Der Fokus liegt hierbei auf Informations- und Steuersystemen (z.B. Reisebuchungs- oder Raumsteuerungssysteme). Das entwickelte Dialogmodell beschreibt den Dialogablauf und somit das Zusammenwirken von Fragen, Antworten sowie den resultierenden Aktionen. Es trägt durch Fähigkeiten wie gemischter Initiative, offenen Fragen, Subdialogen sowie adaptierbaren Formulierungen von Systemäußerungen zu natürlicheren Dialogen bei und erhöht so die Nutzbarkeit von Dialogsystemen. Linguistische Datentypen, abstrakte Fragebeschreibungen in Verbindung mit Antworttypen sowie Sprachgenerierungsverfahren vereinfachen die Definition solcher Dialoge dabei enorm. Die Trennung zwischen Dialogmodell und Dialogengine ermöglicht die Wiederverwendbarkeit von Basisfunktionalitäten und verhindert die Vermischung von Ausführungslogik und Dialogwissen. Die Engine beinhaltet Dialogakte zur Klassifizierung von Nutzeraussagen und zur Vermeidung von Ambiguitäten, Module zum Sprachverstehen und leitet außerdem den nächsten Dialogschritt anhand der Definition des Dialogverhaltens ab. Durch die Implementierung des Natural Dialogue System (NADIA), welches als Dialogengine das XML-basierte Modell ausführt, wird abschließend die Funktionsfähigkeit nachgewiesen.

Due to ongoing increases in carbon dioxide (CO2) concentrations in the atmosphere, the world’s climate is changing at an unprecedented rate, leading to rising global mean air and water temperatures. When atmospheric CO2 dissolves in seawater, ocean pH declines, causing an acidification of the ocean. These altered environmental conditions are highly probable to have severe impacts on marine organisms by affecting their performance and survival. When environmental stress is increasing, some species can migrate to habitats with more favourable conditions, others have to adapt to changing conditions. Whether species will be able to adapt fast enough to keep pace with changing environments will be one decisive factor for population persistence. In this thesis, a prime model organism, the three-spined stickleback Gasterosteus aculeatus, was used to study ecological and evolutionary effects of rising water temperatures and ocean acidification on marine fish populations. Rising temperatures are likely to stress marine species, dependent on their thermal tolerance. Thermal stress can alter immune functions of organisms, thereby increasing the susceptibility to infectious diseases. By combining the effects of elevated temperature and bacterial infection in a common garden experiment, the influence of thermal stress on evolutionary trajectories of disease resistance in three-spined stickleback populations could be investigated (chapter II). Environmental stress negatively impacted life-history traits and pathogen resistance of sticklebacks. Furthermore, thermal stress reduced genetic differentiation between populations by releasing cryptic within-population variation. While life-history traits showed positive genetic correlations between temperatures and genotype by environment interactions (GxE), thermal stress led to negative genetic correlations in disease resistance, showing that evolutionary responses in altered environments can be hard to predict from prevailing conditions. Rising temperatures, on the other hand, promote the development of many parasites and pathogenic bacteria, increasing the risk of infection and diseases during summer. To understand infection patterns in relation to water temperature, the parasite and bacterial communities of marine fish species were investigated over a period of two years (chapter I). Temporarily elevated water temperatures resulted in increased macroparasite and bacterial diversities in marine fish species. In addition, some parasite groups showed a forward shift and extension in infection peaks, following warmer spring seasons. This shows that even subtle changes in seasonal temperatures can have an effect on the epidemiology and phenology of parasites as well as opportunistic pathogens. Increased virulence of pathogens at higher temperatures in combination with immune-compromised hosts can have far fetching consequences for marine ecosystems. Next to rising ocean temperatures, marine organisms have to cope with ocean acidification. It has been shown, that elevated CO2 concentrations negatively impacted fish development and survival, particularly in early developmental stages. A powerful mechanism to mediate the effects of global change is transgenerational acclimation. By acclimating parents and offspring to different CO2 concentrations, within- and transgenerational effects of ocean acidification on life-history traits of marine sticklebacks were studied (chapter III). Exposure to elevated CO2 concentrations led to an increase in clutch size in adults as well as increased juvenile survival and growth rates. Transgenerational effects could be found for juvenile growth and for otolith characteristics, suggesting that parental acclimation can modify ocean acidification effects. To summarize, three-spined sticklebacks cope better with ocean acidification than with rising ocean temperatures. Transgenerational acclimation enables sticklebacks to respond quickly to environmental changes and provides time for genetic evolution, as long-term adaptive mechanism, to catch up. The high tolerance to fluctuations in water chemistry and temperature as well as the substantial amount of standing genetic variation suggest that stickleback populations can adapt fast enough to changing environmental conditions. Durch stetig ansteigende Kohlenstoffdioxid-Konzentrationen (CO2) ändert sich das weltweite Klima mit rasanter Geschwindigkeit und Luft- und Wassertemperaturen steigen. Wenn sich atmosphärisches CO2 im Meerwasser löst, sinkt der pH-Gehalt des Meeres und führt zu einer Versauerung des Ozeans. Diese veränderten Umweltbedingungen können schwerwiegende Folgen für die Leistungsfähigkeit und das Überleben von Meeresbewohner haben. Wenn der Umweltstress ansteigt, können einige Arten in Habitate mit geeigneteren Bedingungen ausweichen, andere wiederum müssen sich an die veränderten Umweltbedingungen anpassen. Ob Lebewesen in der Lage sind, sich schnell genug an die sich ändernde Umwelten anzupassen, wird ein entscheidender Faktor für das Bestehen von Populationen sein. Um ökologische und evolutionäre Effekte des globalen Wandels auf marine Fischpopulationen zu untersuchen, wurde ein hervorragend geeigneter Modellorganismus, der Dreistachlige Stichling Gasterosteus aculeatus, für diese Arbeit verwendet. Abhängig von der thermalen Toleranz, können ansteigende Temperaturen Stress in marinen Lebewesen hervorrufen. Thermaler Stress kann Immunfunktionen von Organismen beeinflussen und dadurch die Anfälligkeit für Infektionskrankheiten erhöhen. Durch die kombinierten Effekte von erhöhter Temperatur und bakterieller Infektion in einem „common garden“ Experiment, konnte der Einfluss von thermalem Stress auf evolutionäre Mechanismen der Pathogenresistenz bei Stichlings-populationen untersucht werden (Kapitel II). Umweltstress beeinträchtigte Fitnesskomponenten und Pathogenresistenzen bei Stichlingen. Zudem führte thermaler Stress zu reduzierter genetischer Differenzierung zwischen Populationen. Während Fitnesskomponenten eine positive genetische Korrelation zwischen Temperaturen zeigten, führte thermaler Stress zu einer negativen genetischen Korrelation für Krankheitsresistenz. Ausgehend von vorherrschenden Bedingungen scheinen evolutionäre Antworten auf veränderte Umwelten schwer vorhersagbar. Ansteigende Temperaturen begünstigen andererseits die Entwicklung von vielen Parasiten und pathogenen Bakterien und erhöhen dadurch das Risiko für Infektionen und Krankheiten während des Sommers. Um temperaturbedingte Infektionsmuster zu verstehen, wurden die Parasiten- und Bakteriengemeinschaften von marinen Fischarten in einem Zeitraum von zwei Jahren untersucht. Kurzzeitig ansteigende Wassertemperaturen verursachten erhöhte Makroparasiten- und Bakteriendiversitäten in marinen Fischarten. Zusätzlich zeigten einige Parasitengruppen eine Verschiebung und Ausdehnung des Infektionshöhepunkts durch wärmere Frühlingsmonate. Bereits kleine Änderungen in saisonalen Temperaturen können die Epidemiologie und die Phänologie von Parasiten, als auch von opportunistischen Pathogenen, beeinflussen. Erhöhte Pathogenvirulenz durch ansteigende Temperaturen kombiniert mit immungeschwächten Wirten kann zu weitreichenden Konsequenzen für marine Ökosysteme führen. Neben ansteigenden Wassertemperaturen, müssen marine Lebewesen auch mit Ozeanversauerung umgehen. Es wurde bewiesen, dass erhöhte CO2 Konzentrationen die Entwicklung und das Überleben von Fischen beeinträchtigt. Ein wirkungsvoller Mechanismus, um die Effekte des globalen Wandels zu mildern, ist transgenerationale Akklimatisierung. Durch das Akklimatisieren von Eltern und Nachwuchs an verschiedene CO2 - Konzentrationen, konnten inner- und trans-generationale Effekte von Ozeanversauerung auf marine Stichlinge untersucht werden (Kapitel III). Erhöhte CO2 - Konzentrationen führten zu vergrößerten Eigelegen bei den Eltern, als auch zu erhöhten Überlebens- und Wachstumsraten bei den Juvenilen. Transgenerationale Effekte konnten für juveniles Wachstum und für Otolithencharakteristiken bestätigt werden und lassen darauf schließen, dass elterliche Akklimatisierung die Auswirkungen von Ozeanversauerung verändern können. Zusammenfassend ist zu erwähnen, dass der Dreistachlige Stichling mit Ozeanversauerung besser umgehen kann, als mit ansteigenden Meerestemperaturen. Zudem ermöglicht transgenerationale Akklimatisierung, Stichlingen auf Umweltveränderungen schnell zu reagieren, bevor genetische Evolution, als Langzeitanpassungsmechanismus, übergreift. Die hohe Toleranz für schwankende Wasserchemie und Temperatur, als auch die erhebliche Menge an dauerhafter genetischer Varianz ermöglicht Stichlingspopulationen sich schnell genug an die sich verändernde Umweltbedingungen anzupassen.

Advancements in production and display techniques allowed for novel displays to emerge that project a high-resolution light field for static poster content and video content, as well. These displays allow a full parallax, hence an audience can perceive a stereoscopic view of a scene without special glasses, which adjusts to the observer's position. The application of such displays are public places where the audience does not wear special glasses and is not restricted in movement. The rendering, storage, and transfer of the large amount of data required by those displays is a challenge. The image data for a static poster display is about 200 GB and the data rate for video displays are to be expected two to four orders of magnitude higher than HDTV. In this work the challenges are met by utilising DIBR to reduce the amount of data at the very beginning, during rendering. A fraction of the full amount of colour and depth images are rendered and used to interpolate the full data set. The rendering with state of the art ray tracers is described and a novel method to render image data for full parallax displays using OpenGL is contributed, that addresses some shortcomings of previous approaches. For static poster displays a scene based representation for image interpolation is introduced, which efficiently utilises multi-core processors and graphics hardware for parallelization, found on modern workstations. The introduced approach implements lossy compression of the input data, and handles arbitrary scenes, using a novel BNV selection algorithm. For video displays the real-time constraint does not allow for a costly interpolation or scene analysis. Hence, a novel approach is presented that uses a basic and computational inexpensive interpolation, and combines the interpolation results of different image representations without introducing prominent artefacts.

Diese Arbeit betrachtet die zentralen Schritte eines Sequenzierungsprozesses und zeigt auf, wie diese modelliert und optimiert bzw. neu gestaltet werden können, um ein performanteres und qualitativ besseres Alignment von Short Read Daten umzusetzen. Hierzu wird für die Modellierung von Short Reads ein Model hergeleitet, aus dem sich Formeln ableiten lassen, die sehr gute Abschätzungen über die zu erwartenden Ergebnisse eines Sequenzierungsprozesses zulassen. Es werden die Eigenschaften einer Sequenzierung wie die Coverage-Verteilung, Null-Coverage- Verteilung, Contig-Längen-Verteilung, N50 und Contig-Anzahl durch Formeln nachgebildet. Weiterhin wird ein Algorithmus zum Alignment von Reads an ein Referenzgenom entwickelt. Der Fokus wird auf die statistischen Eigenschaften der Eingabedaten gelegt. Es wird der Schwerpunkt darauf gelegt, dass die Operationen durch die Zugriffszeiten von Arbeitsspeicher und Festplatten den Algorithmus nicht ausbremsen und die Prozessoren optimal genutzt werden. Es wird gezeigt, dass der entwickelte Algorithmus sowohl mehr Reads alignt als auch eine niedrigere Falsch-Positiv Rate als der Referenzalgorithmus Bowtie2 hat und dabei die Laufzeit deutlich unter der des Referenzalgorithmus liegt. Zur Verbesserung der Eingabedaten wird eine Erweiterung des SHREC Algorithmus zur Fehlerkorrektur vorgestellt. Hierbei wird der Speicherbedarf durch Verwendung von Patricia Tries stark reduziert, wodurch größere Read-Sets verarbeitet werden können. Weiterhin wird die essentielle Parameterwahl von SHREC automatisiert, da sie für normale Anwender sehr schwierig zu bestimmen ist. Es wird gezeigt, dass diese Erweiterungen zu einer deutlichen Fehlerreduktion in den Reads führen. Um den wachsenden Datenmengen gerecht zu werden, werden Cloud-Dienste analysiert und ein Kommunikations-Benchmark vorgestellt. Dieser hilft, die tatsächlich vorliegende Kommunikationsstruktur zu analysieren und vor der Ausführung eines kommunikationsintensiven Algorithmus zu entscheiden, wie die Verteilung von Aufgaben auf die verschiedenen Recheneinheiten zu erfolgen hat.

Capacity management is a core activity when designing and operating distributed software systems. It comprises the provisioning of data center resources and the deployment of software components to these resources. The goal is to continuously provide adequate capacity, i.e., service level agreements should be satisfied while keeping investment and operating costs reasonably low. Traditional capacity management strategies are rather static and pessimistic: resources are provisioned for anticipated peak workload levels. Particularly, enterprise application systems are exposed to highly varying workloads, leading to unnecessarily high total cost of ownership due to poor resource usage efficiency caused by the aforementioned static capacity management approach. During the past years, technologies emerged that enable dynamic data center infrastructures, e. g., leveraged by cloud computing products. These technologies build the foundation for elastic online capacity management, i.e., adapting the provided capacity to workload demands based on a short-term horizon. Because manual online capacity management is not an option, automatic control approaches have been proposed. However, most of these approaches focus on coarse-grained adaptation actions and adaptation decisions are based on aggregated system-level measures. Architectural information about the controlled software system is rarely considered. This thesis introduces a model-driven online capacity management approach for distributed component-based software systems, called SLAstic. The core contributions of this approach are a) modeling languages to capture relevant architectural information about a controlled software system, b) an architecture-based online capacity management framework based on the common MAPE-K control loop architecture, c) model-driven techniques supporting the automation of the approach, d) architectural runtime reconfiguration operations for controlling a system’s capacity, e) as well as an integration of the Palladio Component Model. A qualitative and quantitative evaluation of the approach is performed by case studies, lab experiments, and simulation.

Software timing behavior measurements, such as response times, often show high statistical variance. This variance can make the analysis difficult or even threaten the applicability of statistical techniques. This thesis introduces a method for improving the analysis of software response time measurements that show high variance. Our approach can find relations between timing behavior variance and both trace shape information and workload intensity information. This relation is used to provide timing behavior measurements with virtually less variance. This can make timing behavior analysis more robust (e.g., improved confidence and precision) and faster (e.g., less simulation runs and shorter monitoring period). The thesis contributes TracSTA (Trace-Context-Sensitive Timing Behavior Analysis) and WiSTA (Workload-Intensity-Sensitive Timing Behavior Analysis). TracSTA uses trace shape information (i.e., the shape of the control flow corresponding to a software operation execution) and WiSTA uses workload intensity metrics (e.g., the number of concurrent software executions) to create context-specific timing behavior profiles. Both the applicability and effectiveness are evaluated in several case studies and field studies. The evaluation shows a strong relation between timing behavior and the metrics considered by TracSTA and WiSTA. Additionally, a fault localization approach for enterprise software systems is presented as application scenario. It uses the timing behavior data provided by TracSTA and WiSTA for anomaly detection. Die Analyse von Zeitverhalten wie z.B. Antwortzeiten von Software-Operationen ist oft schwierig wegen der hohen statistischen Varianz. Diese Varianz gefährdet sogar die Anwendbarkeit von statistischen Verfahren. In dieser Arbeit wird eine Methode zur Verbesserung der Analyse von Antwortzeiten mit hoher statistischer Varianz vorgestellt. Der vorgestellte Ansatz ist in der Lage, einen Teil der Varianz aus dem gemessenen Zeitverhalten anhand von Aufrufsequenzen und Schwankungen in der Nutzungsintensität zu erklären. Dadurch kann praktisch Varianz aus den Messdaten entfernt werden, was die Anwendbarkeit von statistischen Analysen in Bezug auf Verlässlichkeit, Präzision und Geschwindigkeit (z.B. kürzere Messperiode und Simulationsdauer) verbessern kann. Der Hauptbeitrag dieser Arbeit liegt in den zwei Verfahren TracSTA (Trace-Context-Sensitive Timing Behavior Analysis) und WiSTA (Workload-Intensity-Sensitive Timing Behavior Analysis). TracSTA verwendet die Form des Aufrufflusses (d.h. die Form der Aufrufsequenz, in die ein Methodenaufruf eingebettet ist). WiSTA wertet die Nutzungsintensität aus (z.B. Anzahl gleichzeitig ausgeführter Methoden). Dies resultiert in kontextspezifischen Antwortzeitprofilen. In mehreren Fall- und Feldstudien wird die Anwendbarkeit und die Wirksamkeit evaluiert. Es zeigt sich ein deutlicher Zusammenhang zwischen dem Zeitverhalten und den von TracSTA und WiSTA betrachteten Einflussfaktoren. Zusätzlich wird als Anwendungsszenario ein Ansatz zur Fehlerlokalisierung vorgestellt, welcher von TracSTA und WiSTA bereitgestellte Antwortzeiten zur Anomalieerkennung verwendet.

Nowadays, the security of information systems is of crucial importance. The large number of detected security vulnerabilities in many systems indicates that new methods for developing secure systems are necessary. These require an appropriate formal foundation. A widely used approach revolves around the notions noninterference and information flow. They allow to express and analyze the absence of illegal information flows and covert channels. In this thesis, the framework of noninterference for state-based asynchronous systems is extended and enriched with new techniques in order to gain a deeper understanding and a broader applicability. As a result, a formal foundation for developing secure systems is obtained. First, new results for the notion of intransitive noninterference are obtained. In particular, a complete characterization by unwinding relations makes the development of a polynomial-time verification algorithm possible in the first place. Second, the previous noninterference definitions are extended with support for policies changing during execution. To capture all resulting security requirements, a new theory of so-called dynamic noninterference is developed and compared to previous approaches. The applicability of this framework is demonstrated by several examples and a complex case study of a distributed dynamic access control system. Third, algorithmic problems are examined, in particular with regard to the question of decidability and complexity of the analyzed security definitions. New undecidability results for some of the present security definitions are obtained, and new efficient algorithms for the verification of both the previously existing and in this thesis developed different notions of noninterference are established.

The focus of this thesis is on the study of repetitive structures in words, a central topic in the area of combinatorics on words. The results presented in the thesis at hand are meant to extend and enrich the existing theory concerning the appearance and absence of such structures. In the first part we examine whether these structures necessarily appear in infinite words over a finite alphabet. The repetitive structures we are concerned with involve functional dependencies between the parts that are repeated. In particular, we study avoidability questions of patterns whose repetitive structure is disguised by the application of a permutation. This novel setting exhibits the surprising behaviour that avoidable patterns may become unavoidable in larger alphabets. The second and major part of this thesis deals with equations on words that enforce a certain repetitive structure involving involutions in their solution set. Czeizler et al. (2009) introduced a generalised version of the classical equations u^l = v^mw^n that were studied by Lyndon and Schützenberger. We solve the last two remaining and most challenging cases and thereby complete the classification of these equations in terms of the repetitive structures appearing in the admitted solutions. In the final part we investigate the influence of the shuffle operation on words avoiding ordinary repetitions. We construct finite and infinite square-free words that can be shuffled with themselves in a way that preserves square-freeness. We also show that the repetitive structure obtained by shuffling a word with itself is avoidable in infinite words.

Many SaaS providers nowadays want to leverage the cloud's capabilities also for their existing applications, for example, to enable sound scalability and cost-effectiveness. This thesis provides the approach CloudMIG that supports SaaS providers to migrate those applications to IaaS and PaaS-based cloud environments. CloudMIG consists of a step-by-step process and focuses on two core components. (1) Restrictions imposed by specific cloud environments (so-called cloud environment constraints (CECs)), such as a limited file system access or forbidden method calls, can be validated by an automatic conformance checking approach. (2) A cloud deployment option (CDO) determines which cloud environment, cloud resource types, deployment architecture, and runtime reconfiguration rules for exploiting a cloud's elasticity should be used. The implied performance and costs can differ in orders of magnitude. CDOs can be automatically optimized with the help of our simulation-based genetic algorithm CDOXplorer. Extensive lab experiments and an experiment in an industrial context show CloudMIG's applicability and the excellent performance of its two core components.

In recent years, underwater imaging has gained a lot of popularity partly due to the availability of off-the-shelf consumer cameras, but also due to a growing interest in the ocean floor by science and industry. Apart from capturing single images or sequences, the application of methods from the area of computer vision has gained interest as well. However, water affects image formation in two major ways. First, while traveling through the water, light is attenuated and scattered, depending on the light's wavelength causing the typical strong green or blue hue in underwater images. Second, cameras used in underwater scenarios need to be confined in an underwater housing, viewing the scene through a flat or dome-shaped glass port. The inside of the housing is filled with air. Consequently, the light entering the housing needs to pass a water-glass interface, then a glass-air interface, thus is refracted twice, affecting underwater image formation geometrically. In classic Structure-from-Motion (SfM) approaches, the perspective camera model is usually assumed, however, it can be shown that it becomes invalid due to refraction in underwater scenarios. Therefore, this thesis proposes an adaptation of the SfM algorithm to underwater image formation with flat port underwater housings, i.e. introduces a method where refraction at the underwater housing is modeled explicitly. This includes a calibration approach, algorithms for relative and absolute pose estimation, an efficient, non-linear error function that is utilized in bundle adjustment, and a refractive plane sweep algorithm. Finally, if calibration data for an underwater light propagation model exists, the dense depth maps can be used to correct texture colors. Experiments with a perspective and the proposed refractive approach to 3D reconstruction revealed that the perspective approach does indeed suffer from a systematic model error depending on the distance between camera and glass and a possible tilt of the glass with respect to the image sensor. The proposed method shows no such systematic error and thus provides more accurate results for underwater image sequences.

Scientific workflows are one important means in the context of data-intensive science for reliable and efficient scientific data processing in distributed computing infrastructures such as Grids. A common trend is to adapt existing and established business workflow technologies instead of developing own technologies from scratch. This thesis provides a model-driven approach for scientific workflow engineering, in which domain-specific languages (DSLs) tailored for a certain scientific domain are used for scientific workflow modeling, and automated mapping techniques for technical execution are developed and evaluated. The Business Process Model and Notation (BPMN) is thereby used at the domain-specific layer and the Web Services Business Process Execution Language (BPEL) at the technical layer. The implementation uses the Eclipse Modeling Framework (EMf) and is evaluated in three application scenarios.

Increasing CO2 concentrations in the atmosphere make it necessary to reduce the anthropogenic greenhouse gas emission. One option is the capture and storage of CO2 in the deep underground. If leakages from these storage reservoirs occur, monitoring methods need to be available for early detection. Stable carbon isotopes were used to test an early warning monitoring approach during a field experiment, where 800 kg of CO2 were injected in the underground. Additionally, the influence of increased CO2 concentrations on microorganisms present in aquifers and soil has been investigated up to the proteomic level. Ansteigende CO2-Konzentrationen in der Atmosphäre machen es erforderlich, dass die anthropogene Treibhausgasemission reduziert wird. Eine Möglichkeit ist das Abtrennen und Speichern von CO2 im tiefen Untergrund. Im Falle einer CO2 Leckage aus diesen Speicherreservoiren müssen Monitoringmethoden für eine frühzeitige Detektion zur Verfügung stehen. Stabile Kohlenstoffisotope wurden zur Erprobung eines Monitoringkonzeptes während eines Feldversuches verwendet, bei dem 800 kg CO2 in den Untergrund injiziert wurden. Zusätzlich wurde der Einfluss erhöhter CO2-Konzentrationen auf Mikroorganismen untersucht, die in Grundwasserleitern und im Boden vorkommen.

The overall goal of this study is to analyze and evaluate the long-term effects of sheep grazing intensity on yield performance, herbage quality, species diversity and specie composition in grassland ecosystems in Inner Mongolia, and then to provide efficient practices preventing grassland degradation.

Heute wird für konzeptuelle Modellierung sowohl die Unified Modeling Language (UML) als auch auch die OWL 2 Web Ontology Language (OWL 2) verwendet. Beide Sprachen entstammen verschiedenen Technologieräumen und setzen unterschiedliche Schwerpunkte. In dieser Arbeit wird untersucht, ob und wie sich konzeptuelle Modelle, die in der einen Sprache geschrieben sind, in konzeptuelle Modelle, die in der anderen Sprache geschrieben sind, überführen lassen. Dadurch würden für ein Modell Verfahren und Software-Werkzeuge beider Technologieräume verfügbar. Für die automatische Transformation wurde – anders als bei bisherigen Arbeiten – eine Herangehensweise gewählt, die von konkreter Syntax bzw. XML-Serialisierung abstrahiert und auf Ebene der Metamodelle von UML und OWL arbeitet. So lässt sich unabhängig von einzelnen Beispielmodellen zeigen, welche Modellelemente transformiert werden können und welche nicht. Für eine Vielzahl von Modellierungskonzepten wird eine formale Beschreibung gegeben und untersucht, wie sich das jeweilige Konzept mit UML bzw. OWL repräsentieren lässt. In den Fällen, in denen die Semantiken der Repräsentationen in beiden Sprachen hinreichend ähnlich sind, um – unter Beibehaltung der Semantik – eine Transformation durchführen zu können, werden die Transformationen ausführlich sowohl als Freitext als auch formal in Form deklarativer QVT-R-Transformationsregeln beschrieben. Da sich diese Regeln nur auf Elemente der Metamodelle beziehen, sind die Transformationen unabhängig von einzelnen Modellen (Instanzen dieser Metamodelle). Dadurch, dass die Transformationen in beide Richtungen vollständig und formal in QVT-R aufgeschrieben vorliegen, lassen sich die Überlegungen nachvollziehen und bei Bedarf schnell an einzelnen Beispielen testen. In dieser vollständigen und formalen Beschreibung unterscheidet sich diese Arbeit von anderen Arbeiten, die solche Beschreibungen nicht oder nur in Fragmenten enthalten. Während sich in UML beschriebene Datenmodelle bis auf wenige Einschränkungen (abstrakte Typen, bestimmte Arten der Generalisierung, Erweiterung durch Stereotypen) relativ gut mit Ontologien darstellen lassen, ist die Transformation allgemeiner OWL-Ontologien in UML-Datenmodelle nicht immer möglich. So stellt z.B. die automatische Klassifizierung von Objekten eine Schwierigkeit dar. Aber selbst in diesen Fällen ist oft eine Transformation möglich, wie bei Kardinalitätsbeschränkungen, die innerhalb von Vererbungsbeziehungen auftreten. Ein Anwendungsbeispiel aus der Praxis der Deutschen Zentralbibliothek für Wirtschaftswissenschaften (ZBW) zeigt, wie gut sich die Transformationsregeln auf konkrete Modelle anwenden lassen und so ohne große Verluste einen Wechsel von einem Technologieraum zum anderen möglich machen.

This thesis is a comparative experimental and theoretical work focused on the mechanical properties of Bombyx mori silk on macroscopic and molecular levels. We did study the response of silk to a mechanical perturbation by monitoring changes of the microscopic structure in the crystalline regions as well as the molecular dynamics of the amorphous phase. In order to achieve this goal \insitu scattering experiments were performed: synchrotron X-ray radiation and cold neutrons were used as probes of the structure and dynamics, respectively. Much attention was devoted to the less studied temporal evolution of the surveyed phenomena. Accordingly our stretching experiments covered several time intervals, ranging from fractions of a second up to several days. Because such environmental parameters as temperature and humidity strongly influence the thermo-mechanical properties of silk the measurements were done at controlled environmental conditions and were repeated at several humidities. The theoretical analysis of our experimental data resulted in the development of a set of interrelated viscoelastic, structural and dynamical models. These models allow to describe the behaviour of stretched silk in the examined range of forces and elongations over almost the whole range of humidity. Particularly, they help to clarify the basic principles of the viscoelastic linear and non-linear behaviour of silk as well as the geometrical and structural aspects of the elongation in the crystalline regions. Generally, a link between the macroscopic viscoelastic behaviour and the mechanism at the molecular length scales has been established. With our experimental techniques and analyses we could separate the mechanical properties of the crystalline region of silk from those of the amorphous part, as well as show their interplay. In our opinion, interesting novel results were also obtained concerning the long-time mechanical relaxation of silk and molecular diffusion processes. Both phenomena exhibit definitive memory effects and can be well described by the models based on fractional calculus. Despite the fact that these phenomena belong to very different temporal and spacial levels the fractional characteristics of these phenomena are very similar. Die vorgelegte Arbeit ist eine komparative theoretische und experimentelle Untersuchung der mechanischen Eigenschaften von Bombyx mori Seide auf makroskopischer und auf molekularer Ebene. Die Reaktion der Seide auf mechanische Einwirkungen wurde erforscht mittels der Beobachtung der Variationen der mikroskopischen Struktur der kristallinen Regionen und der Molekulardynamik der amorphen Phase. Zu diesem Zweck wurden insitu Streuungsexperimente durchgeführt, bei denen die Struktur mittels Synchrotronstrahlung erkundet wurde. Hingegen wurden die molekulardynamischen Eigenschaften der amorphen Phase mittels Neutronenstreuung untersucht. Besonderes viel Aufmerksamkeit widmeten wir den noch wenig erforschten Aspekten der zeitlichen Entwicklung der vorliegenden Phänomene. Dementsprechend wurden unsere Dehnungsexperimente auf mehreren Zeitskalen durchgeführt, mit Dauern von einigen Sekunden bis zu einigen Tagen. Auch wurden unsere Experimente in einer streng kontrollierten Umgebung durchgeführt, da die Temperatur und die Feuchtigkeit der Umgebung die mechanischen Eigenschaften der Seide stark beeinflussen. Um den Einfluß des Wassergehaltes auf die mechanischen Eigenschaften der Seide genauer zu untersuchen wurden die Messungen bei verschiedenen Feuchtigkeiten wiederholt. Aus der theoretischen Analyse unserer experimentalen Ergebnisse resultierte eine Reihe von zusammenhängenden, viskoelastischen, strukturellen und dynamischen Modellen. Dies erlaubte uns das Verhalten von gedehnten Seidenfasern in den untersuchten Kraft-Dehnungs-Bereichen effektiv zu beschreiben. Insbesonders ermöglichte es uns sowohl die Grundprinzipien des linearen und nicht linearen viskoelastischen Verhaltens von Seide als auch die geometrischen und strukturellen Aspekte der Dehnung der kristallinen Bereiche zu klären. Generell konnte der Zusammenhang zwischen dem makroskopisch-viskoelastischen Verhalten und den Wirkungsmechanismen auf der molekularen Ebene etabliert werden. Mittels unserer experimentellen Techniken und unserer theoretischen Analyse waren wir in der Lage die mechanischen Eigenschaften der kristallinen Bereiche von den Eigenschaften der amorphen Regionen zu trennen und ihre Wechselwirkung zu zeigen. Unserer Meinung nach verdienen einige unserer neuen Ergebnisse aus dem Bereich der langzeit-viskoelastischen-Relaxation und der molekularen Diffusionsprozesse besondere Aufmerksamkeit. Beide Phänomene zeigen einen Memory-Effekt und sind beschreibbar mit Modellen der differential-fraktionellen Analyse. Trotz der Tatsache, dass beide Phänomene zu verschiedenen zeitlichen und räumlichen Ebenen gehören, zeigen ihre fraktionellen Charakteristika große Ähnlichkeiten.