### Refine

#### Document Type

- Bachelor Thesis (4) (remove)

#### Language

- English (4) (remove)

#### Keywords

#### Faculty / Organisational entity

For some optimization problems on a graph \(G=(V,E)\), one can give a general formulation: Let \(c\colon E \to \mathbb{R}_{\geq 0}\) be a cost function on the edges and \(X \subseteq 2^E\) be a set of (so-called feasible) subsets of \(E\), one aims to minimize \(\sum_{e\in S} c(e)\) among all feasible \(S\in X\). This formulation covers, for instance, the shortest path problem by choosing \(X\) as the set of all paths between two vertices, or the minimum spanning tree problem by choosing \(X\) to be the set of all spanning trees. This bachelor thesis deals with a parametric version of this formulation, where the edge costs \(c_\lambda\colon E \to \mathbb{R}_{\geq 0}\) depend on a parameter \(\lambda\in\mathbb{R}_{\geq 0}\) in a concave and piecewise linear manner. The goal is to investigate the worst case minimum size of a so-called representation system \(R\subseteq X\), which contains for each scenario \(\lambda\in\mathbb{R}_{\geq 0}\) an optimal solution \(S(\lambda)\in R\). It turns out that only a pseudo-polynomial size can be ensured in general, but smaller systems have to exist in special cases. Moreover, methods are presented to find such small systems algorithmically. Finally, the notion of a representation system is relaxed in order to get smaller (i.e. polynomial) systems ensuring a certain approximation ratio.

It has been observed that for understanding the biological function of certain RNA molecules, one has to study joint secondary structures of interacting pairs of RNA. In this thesis, a new approach for predicting the joint structure is proposed and implemented. For this, we introduce the class of m-dimensional context-free grammars --- an extension of stochastic context-free grammars to multiple dimensions --- and present an Earley-style semiring parser for this class. Additionally, we develop and thoroughly discuss an implementation variant of Earley parsers tailored to efficiently handle dense grammars, which embraces the grammars used for structure prediction. A currently proposed partitioning scheme for joint secondary structures is transferred into a two-dimensional context-free grammar, which in turn is used as a stochastic model for RNA-RNA interaction. This model is trained on actual data and then used for predicting most likely joint structures for given RNA molecules. While this technique has been widely used for secondary structure prediction of single molecules, RNA-RNA interaction was hardly approached this way in the past. Although our parser has O(n^3 m^3) time complexity and O(n^2 m^2) space complexity for two RNA molecules of sizes n and m, it remains practically applicable for typical sizes if enough memory is available. Experiments show that our parser is much more efficient for this application than classical Earley parsers. Moreover the predictions of joint structures are comparable in quality to current energy minimization approaches.

This bachelor thesis is concerned with arrangements of hyperplanes, that
is, finite collections of hyperplanes in a finite-dimensional vector
space. Such arrangements can be studied using methods from
combinatorics, topology or algebraic geometry. Our focus lies on an
algebraic object associated to an arrangement \(\mathcal{A}\), the module \(\mathcal{D(A)}\) of
logarithmic derivations along \(\mathcal{A}\). It was introduced by K. Saito in the
context of singularity theory, and intensively studied by Terao and
others. If \(\mathcal{D(A)}\) admits a basis, the arrangement \(\mathcal{A}\) is called free.
Ziegler generalized the concept of freeness to so-called
multiarrangements, where each hyperplane carries a multiplicity. Terao
conjectured that freeness of arrangements can be decided based on the
combinatorics. We pursue the analogous question for multiarrangements in
special cases. Firstly, we give a new proof of a result of Ziegler
stating that generic multiarrangements are totally non-free, that is,
non-free for any multiplicity. Our proof relies on the new concept of
unbalanced multiplicities. Secondly, we consider freeness asymptotically
for increasing multiplicity of a fixed hyperplane. We give an explicit
bound for the multiplicity where the freeness property has stabilized.

In 2003, a dictionary data structure called jumplist has been introduced by Brönnimann, Cazals and Durand. It is based on a circularly closed (singly) linked list, but additional jump-pointers are added to provide shortcuts to parts further ahead in the list.
The original jump-and-walk data structure by Brönnimann, Cazals and Durand only introduces one jump-pointer per node. In this thesis, I add one more-jump pointer to each node and present algorithms for generation, insertion and search for the resulting data structure.
Furthermore, I try to evaluate the effects on the expected search costs and the complexity of the generation and insertion.
It turns out that the two-jump-pointer variant of the jumplist has a slightly better prefactor (1.2 vs. 2) in the leading term of the expected internal path length than the original version and despite the more complex structure of the two-jump-pointer variant compared to the regular jumplist, the complexity of generation and insertion remains linearithmic.