Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting
method for Oracle's Java 7 runtime library. The decision for the change was based on
empirical studies showing that on average, the new algorithm is faster than the formerly
used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot
approach — an idea that was considered not promising by several theoretical studies in the
past. In this thesis, I try to find the reason for this unexpected success.
My focus is on the precise and detailed average case analysis, aiming at the flavor of
Knuth's series “The Art of Computer Programming”. In particular, I go beyond abstract
measures like counting key comparisons, and try to understand the efficiency of the
algorithms at different levels of abstraction. Whenever possible, precise expected values are
preferred to asymptotic approximations. This rigor ensures that (a) the sorting methods
discussed here are actually usable in practice and (b) that the analysis results contribute to
a sound comparison of the Quicksort variants.
Data usage control is a concept that extends access control to also protect data after it
has been released. Usage control enforcement relies on available information about the
distribution of data in the monitored system. In this thesis we introduce an information
engine V8 of the Chromium browser to evaluate the feasibility of the chosen approach.
This research for this thesis was conducted to develop a framework which supports the automatic configuration of project-specific software development processes by selecting and combining different technologies: the Process Configuration Framework. The research draws attention to the problem that while the research community develops new technologies, the industrial companies continue only using their well-known ones. Because of this, technology transfer takes decades. In addition, there is the fact that there is no solution which solves all problems in a software development project. This leads to a number of technologies which need to be combined for one project.
The framework developed and explained in this research mainly addresses those problems by building a bridge between research and industry as well as by supporting software companies during the selection of the most appropriate technologies combined in a software process. The technology transformation gap is filled by a repository of (new) technologies which are used as a foundation of the Process Configuration Framework. The process is configured by providing SPEM process pattern for each technology, so that the companies can build their process by plugging into each other.
The technologies of the repository were specified in a schema including a technology model, context model, and an impact model. With context and impact it is possible to provide information about a technology, for example, its benefits to quality, cost or schedule. The offering of the process pattern as output of the Process Configuration Framework is performed in several stages:
I Technology Ranking:
1 Ranking based on Application Domain, Project & Impact
2 Ranking based on Environment
3 Ranking based on Static Context
II Technology Combination:
4 Creation of all possible Technology Chains
5 Restriction of the Technology Chains
6 Ranking based on Static and Dynamic Context
7 Extension of the Chains by Quality Assurance
III Process Configuration:
8 Process Component Diagram
9 Extension of the Process Component Diagram
10 Instantiation of the Components by Technologies of the Technology Chain
11 Providing process patterns
12 Creation of the process based on Patterns
The effectiveness and quality of the Process Configuration Framework have additionally been evaluated in a case study. Here, the Technology Chains manually created by experts were compared to the chains automatically created by the framework after it was configured by those experts. This comparison depicted that the framework results are similar and therefore can be used as a recommendation.
We conclude from our research that support during the configuration of a process for software projects is important especially for non-experts. This support is provided by the Process Configuration Framework developed in this research. In addition our research has shown that this framework offers a possibility to speed up the technology transformation gap between the research community and industrial companies.
Tropical geometry is a very new mathematical domain. The appearance of
tropical geometry was motivated by its deep relations to other mathematical
branches. These include algebraic geometry, symplectic geometry, complex
analysis, combinatorics and mathematical biology.
In this work we see some more relations between algebraic geometry and
tropical geometry. Our aim is to prove a one-to-one correspondence between
the divisor classes on the moduli space of n-pointed rational stable curves
and the divisors of the moduli space of n-pointed abstract tropical curves.
Thus we state some results of the algebraic case first. In algebraic geometry
these moduli spaces are well understood. In particular, the group of divisor
classes is calculated by S. Keel. We recall the needed results in chapter one.
For the proof of the correspondence we use some results of toric geometry.
Further we want to show an equality of the Chow groups of a special toric
variety and the algebraic moduli space. Thus we state some results of the
toric geometry as well.
This thesis tries to discover some connection between algebraic and tropical
geometry. Thus we also need the corresponding tropical objects to the
algebraic objects. Therefore we give some necessary definitions such as fan,
tropical fan, morphisms between tropical fans, divisors or the topical moduli
space of all n-marked tropical curves. Since we need it, we show that the
tropical moduli space can be embedded as a tropical fan.
After this preparatory work we prove that the group of divisor classes in
classical algebraic geometry has it equivalence in tropical geometry. For this
it is useful to give a map from the group of divisor classes of the algebraic
moduli space to the group of divisors of the tropical moduli space. Our aim is
to prove the bijectivity of this map in chapter three. On the way we discover
a deep connection between the algebraic moduli space and the toric variety
given by the tropical fan of the tropical moduli space.
In this work a 3-dimensional contact elasticity problem for a thin fiber and a rigid foundation is studied. We describe the contact condition by a linear Robin-condition (by meaning of the penalized and linearized non-penetration and friction conditions).
The dimension of the problem is reduced by an asymptotic approach. Scaling the Robin parameters appropriately we obtain a recurrent chain of Neumann type boundary value problems which are considered only in the microscopic scale. The problem for the leading term is a homogeneous Neumann problem, hence the leading term depends only on the slow variable. This motivates the choice of a multiplicative ansatz in the asymptotic expansion.
The theoretical results are illustrated with numerical examples performed with a commercial finite-element software-tool.
In this thesis we present the implementation of libraries center.lib and perron.lib for the non-commutative extension Plural of the Computer Algebra System Singular. The library center.lib was designed for the computation of elements of the centralizer of a set of elements and the center of a non-commutative polynomial algebra. It also provides solutions to related problems. The library perron.lib contains a procedure for the computation of relations between a set of pairwise commuting polynomials. The thesis comprises the theory behind the libraries, aspects of the implementation and some applications of the developed algorithms. Moreover, we provide extensive benchmarks for the computation of elements of the center. Some of our examples were never computed before.
Ever since Mark Weiser’s vision of Ubiquitous Computing the importance of context has increased in the computer science domain. Future Ambient Intelligent Environments will assist humans in their everyday activities, even without them being constantly aware of it. Objects in such environments will have small computers embedded into them which have the ability to predict human needs from the current context and adapt their behavior accordingly. This vision equally applies to future production environments. In modern factories workers and technical staff members are confronted with a multitude of devices from various manufacturers, all with different user interfaces, interaction concepts and degrees of complexity. Production processes are highly dynamic, whole modules can be exchanged or restructured. Both factors force users to continuously change their mental model of the environment. This complicates their workflows and leads to avoidable user errors or slips in judgement. In an Ambient Intelligent Production Environment these challenges have to be approached. The SmartMote is a universal control device for ambient intelligent production environments like the SmartFactoryKL. It copes with the problems mentioned above by integrating all the user interfaces into a single, holistic and mobile device. Following an automated Model-Based User Interface Development (MBUID) process it generates a fully functional graphical user interface from an abstract task-based description of the environment during run-time. This work introduces an approach to integrating context, namely the user’s location, as an adaptation basis into the MBUID process. A Context Model is specified, which stores location information in a formal and precise way. Connected sensors continuously update the model with new values. The model is complemented by a reasoning component which uses an extensible set of rules. These rules are used to derive more abstract context information from basic sensor data and for providing this information to the MBUID process. The feasibility of the approach is shown by using the example of Interaction Zones, which let developers describe different task models depending on the user’s location. Using the context model to determine when a user enters or leaves a zone, the generator can adapt the graphical user interface accordingly. Context-awareness and the potential to adapt to the current context of use are key requirements of applications in ambient intelligent environments. The approach presented here provides a clear procedure and extension scheme for the consideration of additional context types. As context has significant influence on the overall User Experience, this results not only in a better usefulness, but also in an improved usability of the SmartMote.
The scope of this diploma thesis is to examine the four generations of asset pricing models and the corresponding volatility dynamics which have been devepoled so far. We proceed as follows: In chapter 1 we give a short repetition of the Black-Scholes first generation model which assumes a constant volatility and we show that volatility should not be modeled as constant by examining statistical data and introducing the notion of implied volatility. In chapter 2, we examine the simplest models that are able to produce smiles or skews - local volatility models. These are called second generation models. Local volatility models model the volatility as a function of the stock price and time. We start with the work of Dupire, show how local volatility models can be calibrated and end with a detailed discussion of the constant elasticity of volatility model. Chapter 3 focuses on the Heston model which represents the class of the stochastic volatility models, which assume that the volatility itself is driven by a stochastic process. These are called third generation models. We introduce the model structure, derive a partial differential pricing equation, give a closed-form solution for European calls by solving this equation and explain how the model is calibrated. The last part of chapter 3 then deals with the limits and the mis-specifications of the Heston model, in particular for recent exotic options like reverse cliquets, Accumulators or Napoleons. In chapter 4 we then introduce the Bergomi forward variance model which is called fourth generation model as a consequence of the limits of the Heston model explained in chapter 3. The Bergomi model is a stochastic local volatility model - the spot price is modeled as a constant elasticity of volatility diffusion and its volatility parameters are functions of the so called forward variances which are specified as stochastic processes. We start with the model specification, derive a partial differential pricing equation, show how the model has to be calibrated and end with pricing examples and a concluding discussion.
Nowadays, vehicle control systems such as anti-lock braking systems, electronic stability control, and cruise control systems yield many advantages. The electronic control units that are deployed in this specific application domain are embedded systems that are integrated in larger systems to achieve predefined applications. Embedded systems consist of embedded hardware and a large software part. Model-based development for embedded systems offers significant software-development benefits that are pointed out in this thesis. The vehicle control system Adaptive Cruise Control is developed in this thesis using a model-based software development process for embedded systems. As a modern industrial design tool that is prevalent in this domain, simulink,is used for modeling the environment, the system behavior, for determining controller parameters, and for simulation purposes. Using an appropriate toolchain, the embedded code is automatically generated. The adaptive cruise control system could be successfully implemented and tested within this short timespan using a waterfall model without increments. The vehicle plant and important filters are fully deduced in detail. Therefore, the design of further vehicle control systems needs less effort for development and precise simulation.