TY - THES A1 - Jeschke, Björn-Marcel T1 - Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung N2 - In dieser Arbeit betrachten wir das Problem, für den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnhöfen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen“ Graphen modelliert werden. Es gibt zwei unterschiedliche Ansätze für dieses zeitabhängige Problem: Erstens können die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien“ dargestellt werden, das ist das zeit-expandierte Modell. Zweitens können die Gewichte der Kanten zeitabhängig sein, das ist das zeitabhängige Modell. Wir untersuchen in dieser Arbeit, wie der „klassische“ Dijkstra-Algorithmus und der A* Algorithmus mit einer geeigneten Heuristik im Vergleich abschneiden. Die gewählte Heuristik ist der Abstand zum Zielknoten, wenn die Abfahrtszeiten ignoriert werden. Nach unseren Untersuchungen zeigt sich, dass der A* Algorithmus dem Dijkstra-Algorithmus weit überlegen ist für genügend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gewählte Heuristik besonders gut ist für Start- und Zielknoten, welche unabhängig von ihrer Distanz nur 1–2 verschiedene mögliche kürzeste Pfade für alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht häufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus. Y1 - 2017 ER - TY - THES A1 - Schubert, Christoph T1 - Multi-Level Lookahead Branching Y1 - 2017 ER - TY - THES A1 - Wulkow, Niklas T1 - Modelling the Spread of Innovations by a Markov Process in a Bayesian Framework Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66869 ER - TY - THES A1 - Sikorski, Alexander T1 - An Information-Theoretic Empirical Bayes Method and its Application to a Systems Biology Model N2 - This thesis covers the development and application of an empirical Bayes method to the problem of parameter estimation in systems biology. The goal was to provide a general and practical solution to the Bayesian inverse problem in the case of high dimensional parameter spaces making use of present cohort-data. We show that the maximum penalized likelihood estimator (MPLE) with information penalty is based on natural, information-theoretic considerations and admits the desirable property of transformation invariance. Due to its concavity, the objective function is computationally feasible and its mesh-free Monte-Carlo approximation enables its application to high-dimensional problems eluding the curse of dimensionality. We furthermore show how to apply the developed methods to a real world problem by the means of Markov chain Monte-Carlo sampling (MCMC), affirming its proficiency in a practical scenario. Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65098 ER - TY - THES A1 - Eifler, Leon T1 - Mixed-Integer Programming for Clustering in Non-reversible Markov Processes N2 - The topic of this thesis is the examination of an optimization model which stems from the clustering process of non-reversible markov processes. We introduce the cycle clustering problem und formulate it as a mixed integer program (MIP). We prove that this problem is N P-hard and discuss polytopal aspects such as facets and dimension. The focus of this thesis is the development of solving methods for this clustering problem. We develop problem specific primal heuristics, as well as separation methods and an approximation algorithm. These techniques are implemented in practice as an application for the MIP solver SCIP. Our computational experiments show that these solving methods result in an average speedup of ×4 compared to generic solvers and that our application is able to solve more instances to optimality within the given time limit of one hour. KW - Markov State Models KW - NESS KW - Non-reversible Markov Processes KW - Mixed-Integer Programming Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66486 ER - TY - THES A1 - Zänker, Martin T1 - Estimating Human Face Reflectance from Single-Shot Multiview Data Y1 - 2017 ER - TY - THES A1 - le Roux, Gabriel T1 - Development and Evaluation of Algorithms for 3D Facial Motion Estimation from Stereo Videos Y1 - 2017 ER - TY - THES A1 - Reddy, Gutha Vaishnavi T1 - Automatic Classification of 3D MRI data using Deep Convolutional Neural Networks N2 - The chronic disease of Osteoarthritis of the knee that causes pain and discomfort in the knee is associated with the degradation of the joint between the tibia and the femur. The degeneration of this joint is attributed partially to the damage of the meniscus of the knee which forms an important part of the knee joint. Magnetic Resonance Imaging (MRI) is used to diagnose such a kind of osteoarthritis by identifying the degeneration of the knee meniscus. A computer aided diagnostic system that aims to assist a doctor in decision making regarding such a diagnosis can expedite the very diagnosis. Diagnostic decision making for medical imaging falls into the category of classification for a computer vision task. Very Deep Convolutional Networks have been central to the largest advances in computer vision, in recent years. This work entails application of such convolutional networks for the purpose of recognizing a meniscus tear in MRI images as attempting a step towards developing a computer aided diagnosis system for osteoarthritis. Consequently, state-of-the-art pre-trained image recognition networks namely Alexnet, Inceptionv3, VGG and Resnet and Xception were trained on MRI data of the knee meniscus to see if they work for the task of recognizing a tear. A comparison of their classification performance on MRI data was done. The best performing model was the fine-tuned InceptionV3 network which achieved an accuracy close to 60% for classifying 600 patients based on presence of a tear or not. Y1 - 2017 ER - TY - THES A1 - Skrzypczak, Jan T1 - Weakening Paxos Consensus Sequences for Commutative Commands N2 - Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them. This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances. PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation. KW - Paxos KW - Consensus Y1 - 2017 ER - TY - THES A1 - Makarenko, Oleksandra T1 - Square Root Approximation und statistische Umgewichtungstechnik für das Faltungsverhalten von Polymerbürsten Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65283 ER - TY - THES A1 - Röhm, Jonas T1 - Non-Negative Matrix Factorization for Raman Data Spectral Analysis Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65217 ER - TY - THES A1 - Röhl, Susanne T1 - Computing the minimal rebinding effect for nonreversible processes Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65203 ER - TY - THES A1 - Brust, Lisa T1 - Moleküldynamik-Simulation via eines Faltungsansatzes im Potential Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65198 ER - TY - THES A1 - Binkowski, Felix T1 - On the convergence behavior of spectral deferred correction methods for convection-diffusion equations N2 - Spectral deferred correction (SDC) Methoden, vorgestellt von Dutt, Greengard und Rokhlin in [1], sind iterative Verfahren zur numerischen Lösung von Anfangswertproblemen für gewöhnliche Differentialgleichungen. Wenn diese Methoden konvergieren, dann wird unter Verwendung von Zeitschrittverfahren niedriger Ordnung eine Kollokationslösung berechnet. Die Lösung von steifen Anfangswertproblemen ist eine relevante Problemstellung in der numerischen Mathematik. SDC-Methoden, speziell für steife Probleme, werden von Martin Weiser in [2] konstruiert. Die Theorie und die Experimente beziehen sich dabei auf Probleme, die aus räumlich semidiskretisierten Reaktions-Diffusions-Gleichungen entstehen. In dieser Arbeit werden die Ansätze aus [2] auf Konvektions-Diffusions-Gleichungen angewendet und das resultierende Konvergenzverhalten von SDC-Methoden untersucht. Basierend auf einem einfachen Konvektions-Diffusions-Operator, dessen spektrale Eigenschaften umfassend studiert werden, wird ein Schema zur Verbesserung dieses Verhaltens entwickelt. Numerische Experimente zeigen, dass eine Verbesserung der in [1] eingeführten SDC-Methoden möglich ist. Die Untersuchungen ergeben weiterhin, dass das auch für komplexere Konvektions-Diffusions-Probleme gilt. [1] Alok Dutt, Leslie Greengard, und Vladimir Rokhlin. “Spectral deferred correction methods for ordinary differential equations.” In: BIT 40.2 (2000), pp. 241–266. [2] Martin Weiser. “Faster SDC convergence on non-equidistant grids by DIRK sweeps.” In: BIT 55.4 (2015), pp. 1219–1241. Y1 - 2017 ER - TY - THES A1 - Fischer, Lisa T1 - On the convergence of inexact time parallel time integration Y1 - 2017 ER - TY - THES A1 - Freytag, Yvonne T1 - Optimal Experimental Design to Estimate the Time of Death in a Bayesian Context N2 - This thesis is devoted to the interdisciplinary work between mathematicians and forensic experts: the modeling of the human body cooling process after death laying the foundation for the estimation of the time of death. An inverse problem needs to be solved. In this thesis the inverse problem computes the time of death given the measured body temperature and the Forward Model that simulates the body cooling process. The Forward Model is based on the heat equation established by Fourier. This differential equation is numerically solved by the discretization over space by the Finite Element Method and the discretization over time by the Implicit Euler Method. The applications in this thesis demand a fast computation time. A model reduction is achieved by the Proper Orthogonal Decomposition in combination with the Galerkin Method. For reasons of simplification the computations and the measurements are restricted to a cylindrical phantom that is made out of homogeneous polyethylene. The estimate of the time of death is accompanied by an uncertainty. The inverse problem is incorporated by Bayesian inference to interpret the quality of the estimate and the effciency of the experiment. The uncertainty of the estimate of the time of death is minimized by approaching the Optimal Design of the Experiment. An objective function measures the certainty of the data and lays the foundation of the optimization problem. Solving the optimization problem is successfully done by relaxing the complex discrete NP-hard problem and applying a gradient-based method. The results of this thesis clearly show that the design of an experiment has a great in- uence on the outcome of the quality of the estimate. The comparison of the estimate and its properties based on different designs and conditions reveals the effciency of the Design of Experiment in the context of the estimation of the time of death. Y1 - 2017 ER - TY - THES A1 - Teuchert, Andreas T1 - Degeneriertheit im Simplexverfahren Y1 - 2017 ER - TY - THES A1 - Dillmann, Johannes T1 - Implementierung und Evaluation von Erasure Coding im verteilten Dateisystem XtreemFS Y1 - 2017 ER -