Ein Deterministischer endlicher Automat ist ein grundlegendes Konzept in der theoretischen Informatik. Sie besitzt vielseitige Anwendungsgebiete, wie beispielsweise die tatsächliche Abstraktion von Getränke- und Bankautomaten, lexikalische Analyse von Compilern, Behandlung von Zeichenketten beim Entwerfen eines Algorithmus oder auch die Modellierung in der Softwaretechnik. Um den Entwurf eines DEA zu vereinfachen, wurde im Rahmen meiner Bachelorarbeit eine Anforderungsanalyse durchgeführt. Anhand dieser Analyse wurden Funktionalitäten bestimmt und implementiert, um eine digitale Form eines DEA zu visualisieren. Anschließend wurden automatisierte Tests und Befragungen von unterschiedlichen Testpersonen durchgeführt.

This thesis contributes to the study of extremal functions in 0-1 matrices, pivoting from a predominantly theoretical focus to a more application oriented perspective. The cornerstone of this research is the translation of theoretical insights into practical code by treating matrix pattern detection as a Constraint Satisfaction Problem (CSP), coupled with a systematic search for potential reductions. These strategies turn out to be very efficient and enable the examination of a wider range of matrices.

Graphen spielen insbesondere in der Informatik eine wichtige Rolle, um komplexe Zusammenhänge zu verstehen, da sie diese relativ übersichtlich darstellen können. Um einen Graphen übersichtlich und verständlich zu halten, können Heuristiken eingesetzt werden, die die Ausrichtung und Position von Kanten und Knoten festlegen. Eine solche Heuristik ist die Sugiyama-Heuristik. Sie verwendet eine hierarchische Ordnung und verwendet orthogonale Kanten, die horizontal oder vertikal verlaufen. Durch die feste Größe der Knoten sind bei diesem Ansatz Knicke in den Kanten unvermeidlich, die einerseits die Ästhetik des Graphen und andererseits die Übersichtlichkeit beeinträchtigen. Im Rahmen der Bachelorarbeit wurden Algorithmen entwickelt, die durch Anpassung der Kantengröße die Anzahl der Kantenknicke reduzieren sollen. Die verschiedenen Ansätze werden miteinander verglichen und evaluiert.

In light of the established NP-hardness of the Boolean Satisfiability Problem (SAT), contemporary SAT-solvers showcase remarkable prowess in tackling even large instances of the problem. This proficiency has been honed over decades through the refinement of two prominent solving paradigms: the DPLL-algorithm and stochastic local search (SLS). The former stands out as the preferred choice for exact solutions, while the latter sacrifices reliability in favor of speed.

In this work we try to break away from these established paradigms by introducing an alternative approach to solving the SAT-Problem. Similar to DPLL, our method yields exact results. However, instead of systematically searching for a singular solution, we leverage periodic patterns inherent in the structure of truth tables. These patterns allow us to model the entire solution space of a formula in a highly condensed form, reminiscent of a binary decision diagram. Although still inherently exponential, our algorithm exhibits promising performance characteristics and provides all solutions for a given problem. Furthermore, we give a comprehensive overview on our optimization efforts and provide performance metrics based on test results from variously sized uniform random 3-SAT formulas to underscore the algorithm's effectiveness.

Die Kantenfärbung zählt zu den fundamentalsten Problemen innerhalb der Graphentheorie. Im Streaming Modell werden die Kanten des Eingabegraphen dem Algorithmus einzeln präsentiert. Hierbei ist der zur Verfügung stehende Speicher kleiner als die Größe des Eingabegraphen, weshalb nicht alle Kanten des Graphen gespeichert werden können. Da die Ausgabe genauso groß ist wie die Eingabe selbst, müssen auch die Farben der Kanten als Stream ausgegeben werden, das sogenannte W-Streaming. In der Vergangenheit wurden schon einige Lösungen für dieses Problem in verschiedensten Modellen vorgestellt. In dieser Arbeit werden wir uns die Entwicklung und Fortschritte dieser genauer anschau- en. Zuletzt lieferten zwei randomisierte Algorithmen im gegnerischen Kantenan- kunftsmodell, aus ESA 2019, SOSA 2021 und ESA 2022, die besten Ergebnisse. Hierbei färbt der neueste jeden Graphen mit 2∆t Farben in O(n∆/t) Platz für jedes n ≤ ∆, wobei ∆ der maximale Grad des Graphen ist. Diese Lösung bietet den einzigen bekannten Online-Kantenfärbungsalgorithmus mit sublinearem Platzbedarf. Unser Ziel ist es die verschiedenen Ergebnisse mit einander zu vergleichen, um potenzielle Verbesserungen zu identifizieren.

Die vorliegende Arbeit beschäftigt sich mit der Wahrheitstheorie nach Alfred Tarski, welche besagt, dass innerhalb einer formalisierten Sprache, die eine Metasprache besitzt, keine wohlgeformte Definition von Wahrheit - bzw. eines Wahrheitsprädikates - konstruiert werden kann, die nur aus Formeln der zugrundeliegenden Objektsprache besteht.

Zunächst werden in Abschnitt 1 die für dieses Teilgebiet der formalen Logik nötigen Grundbegriffe definiert - formalisierte Sprachen, Syntax und Semantik - und die Konzepte dahinter erklärt. Ebenso werden wir uns mit den Charakteristika von Aussagenlogik und Prädikatenlogik erster und zweiter Ordnung befassen. Im Anschluss wird in Abschnitt 2 detailliert Alfred Tarskis Arbeit und die konkrete Aussage des Undefinierbarkeitssatzes beschrieben. Im Zuge dessen wird der Undefinierbarkeitssatz erläutert, weitere Konzepte - zentral ist hierfür beispielsweise Tarskis Konvention T - für das Verständnis dargestellt und schließlich der Beweis des Satzes skizziert. Zuletzt werden in Abschnitt 4 die Implikationen dieser Wahrheitstheorie für Aussagenlogik, sowie Prädikatenlogik erster und zweiter Ordnung und die Anwendungsbereiche für die moderne Logik diskutiert.

Das Ziel der Arbeit ist, die Relevanz einer Auseinandersetzung mit dem Wahrheitsbegriff in der formalen Logik als Disziplin der Mathematik darzustellen. Weiter soll eine kritische Diskussion dessen erfolgen, wie aktuelle Forschungsergebnisse mit Tarskis Theorie übereinstimmen, welche Differenzen existieren und inwiefern sein Wahrheitstheorie infragezustellen ist. 1

Ephemeral data structures retain only the most recent version of the data structures, while persistent data structures maintain a full history of the data structures. Fortunately, several methods can be employed to make any pointer-based ephemeral data structure persistent. This thesis aims to clarify and analyse classical approaches and apply them to the implementation of persistent binary search trees. Subsequently, we evaluate the efficiency of these approaches by conducting several benchmark tests. Furthermore, a partially persistent binary search tree is employed to address the traditional planar point location problem. This approach offers a solution with O(n) space cost, O(logn) query time, and O(nlogn) preprocessing time.

Hintergrund: Das effiziente Finden eines kürzesten Pfades in einem Straßennetzwerk zwischen zwei Positionen ist eine wichtige Aufgabe für Echtzeitanwendungen wie Navigationssysteme, um flexibel auf dynamische Veränderungen im Straßennetzwerk, wie Änderungen von Start- und Endpositionen, reagieren zu können. In der Literatur gilt der Highway-Hierarchies-Star-Algorithmus als einer der effizientesten Algorithmen zur Ermittlung des kürzesten Pfades zwischen zwei Knoten in einem Straßennetzwerk.

Ziele: In dieser Arbeit soll überprüft werden, ob der Highway-Hierarchies-Star-Algorithmus tatsächlich effizienter ist als verschiedene etablierte Algorithmen zum Finden des kürzesten Pfades, wie in der Literatur beschrieben. Methoden: Dafür werden verschiedene Algorithmen zur Berechnung des kürzesten Pfades implementiert und anhand unterschiedlicher Suchanfragen in deutschen Straßennetzwerken bewertet.

Ergebnisse: Die Experimente zeigen, dass der Highway-Hierarchies-Star-Algorithmus die besten Ergebnisse bei den Suchanfragen erzielt und dabei auch eine annehmbare Vorverarbeitungszeit aufweist.

Schlussfolgerungen: Der Highway-Hierarchies-Star-Algorithmus bietet schnelle Anfragezeiten in statischen Graphen, sodass verschiedene Anfragen mit unterschiedlichen Start- und Endpositionen in Millisekunden berechnet werden können. Dies bestätigt weitgehend die Bewertung in der Literatur. Dennoch sind weitere Tests auf dynamischen Graphen erforderlich, um eine komplette Beurteilung vornehmen zu können.

This thesis aims to comprehensively examine and compare two implementations of Concurrent Robin Hood Hashing: Bolt [8] and K-CAS Robin Hood [11]. The primary objective is to gain a deep understanding of their performance characteristics, identify key differences, and explore the optimizations applied in these advanced techniques.

By conducting this examination, we aim to provide concrete insights into the strengths, weaknesses, and unique features of each implementation. This analysis will contribute to advancing the understanding of Concurrent Robin Hood Hashing and inform the design of high-performance concurrent data structures.

Longest planar spanning trees are thought to be an NP-hard task. One approach to such problems is to relax the solution’s criteria. This can be achieved by identifying solutions that are not necessarily the longest spanning tree but are planar. This paper investigates the lower bound of the approximation factor of algorithms producing planar spanning trees. We analyze the algorithm proposed in Cabello et al. (2021). The algorithm finds AB trees that improve star graphs. The star is a simple graph proposed by Alon et al. (1993), where one point is connected to every other point. The AB tree algorithm attempts to improve the star by adding zig-zag edges, which increases the total length. To analyze the approximation factors, we implement four algorithms: the aforementioned AB tree algorithm, a brute force algorithm for the longest planar spanning tree, a longest spanning tree algorithm, and a specialized algorithm for convex point sets. A genetic algorithm was used to find point sets with low approximation factors programmatically. The brute force algorithm implementation performed poorly and was only utilized for point sets of no more than 10 points. We analyzed point sets with approximation factors of less than 0.9. The genetic algorithm’s output has an approximation factor of 0.9 as well. The sets with low approximation factors are very elongated point sets, particularly ellipsoid forms. In this work, the lowest approximation factor determined is 0.877. Our analysis finds a more overly stretched graph results in an even lower approximation factor.

Der implementierte Routingalgorithmus ist dezentral und verteilt, ein sogenanntes Routing Scheme. Jeder Knoten des Netzwerks entscheidet selbstständig, wohin ein Paket als nächstes weitergeleitet wird. Die Entscheidung wird mit Hilfe einer Routing Table getroffen. In jedem Knoten wird eine Routing Tabelle lokal gespeichert. Das Paketziel wird einem Knoten über den Header des Pakets mitgeteilt. Das Routing-Scheme lässt sich, nur auf eine bestimmte Graphklasse, anwenden. Das sind ungewichtete r-Sichtbarkeitsgraphen von Histogrammen. Wenn eine Kante zwischen zwei Knoten existiert, sind bestimmte geometrische Bedingungen erfüllt. Durch die Bedingungen können kürzeste Wege bestimmt werden, ohne den gesamten Graph zu betrachten. Die Verteidigung beinhaltet eine kleine Demonstation des Programms. Das Programm ist in C++ geschrieben. Es gibt eine GUI, die grafische Darstellungen des Algorithmus produziert. Der letzte Punkt sind Experimente, bei denen das Routingscheme auf zufällig erzeugte Graphen angewendet wurde.

In dieser Arbeit geht es um Suchalgorithmen in spalten- und zeilenweisen sortierten Matrizen. Neben der herkömmlichen Zeitkomplexität soll ein besonderes Augenmerk auf dem asymptotischen Verhalten der Anzahl der Vergleiche eines Elements (der Matrix) mit dem gesuchten Objekt liegen. Es wird ein Suchalgorithmus für endliche n×m-Matrizen vorgestellt und eine detaillierte Komplexitätsanalyse vorgenommen. Zudem werden alternative Algorithmen präsentiert und miteinander verglichen.

Finding optimal binary search trees in terms of minimal search cost for a sequence of key queries is a well studied problem in computer science. An important theorem over the combinatorial structure of the problem found by Knuth in 1971 can be used to speed up a dynamic program for the problem to O(n^2) time, where n is the number of keys. Recently, Berendsohn and Kozma gave a 2-approximation algorithm for a generalization of optimal binary search trees to search trees on trees, which runs in O(n^3) time. We show, that Knuth theorem also holds in this setting and use it to improve the running time of the algorithm to O(min(D^2*L^2, n^3)), where D denotes the diameter and L the number of leaves of the search space tree. We give a full implementation of both algorithms and verify the correctness and running time on randomly generated trees of different types. Further, we show that a bound given by Mehlhorn for binary search trees can be generalized to search trees on trees.

We present and analyze a new algorithm idea to hierarchically cluster data, and show that it performs well compared to other established hierarchical clustering methods when evaluated based on Dasgupta’s cost function. We prove that in one iteration, our algorithm finds the optimal hierarchical clustering tree for the given order of the points, when limited to hierarchical clustering trees the leaves of which have the same ordering as said points.

Additionally, we show that the cost of the found tree can only improve or remain the same with each iteration. Thus, the presented algorithm can be used for hierarchical clustering tasks, or on the results of other hierarchical clustering algorithms to improve those, and leaves room for theoretical improvements and experimentation.

Sortierverfahren sind ein großes Thema in der Informatik und über die Jahre werden immer wieder neue Sortieralgorithmen entwickelt. Sortieralgorithmen sind außerdem oft Themen von wissenschaflichen Arbeiten und es wird heute noch erforscht, wie man sie verbessern kann. Es stellt sich die Frage, warum es so viele verschiedene Algorithmen gibt, was deren Vor-­ und Nachteile sind und in welchen Situationen man welchen Algorithmus verwenden sollte. Gibt es einen ”besten” Sortieralgorithmus den man immer verwenden soll oder ist es eher sinnvoll, basierend auf den gegebenen Daten einen bestimmten Algorithmus auszuwählen? Das Ziel dieser Arbeit ist die Implementierung von ausgewählten Sortieralgorithmen und die Erstellung verschiedener Testfälle, mit denen die Algorithmen in unterschiedlichen Situationen getestet und verglichen werden können. Damit soll experimentell die Frage beantwortet werden, wie sehr es sich lohnt, je nach Situation verschiedene Sortieralgorithmen zu verwenden.

Das Cup-Game ist ein klassisches Problem in der Informatik, das das Prozessor-Scheduling modelliert. Beim Cup-Game mit n Bechern gibt es einen Befüller und einen Entleerer, die abwechselnd Wasser in den Bechern füllen und daraus entnehmen. Bei dem Prozessor-Scheduling heißt es, dass es neue Aufgaben hereinkommen und der Scheduler Prozessoren zuweisen muss, um die eingehende Arbeit zu erledigen.

Diese Arbeit beschäftigt sich mit verschiedenen (sowohl determistischen als auch randomisierten) Algorithmen für die Befüller und Entleerer. Zunächst wurde theoretische Recherche durchgeführt. Des Weiteren wurden Algorithmen für das Single-Processor Cup-Game implementiert. Anschließend wurden die Ergebnisse aus der Implementierung visualisiert, um einen Überblick über den Vergleich zwischen der Theorie und Praxis zu schaffen.

Bottleneck problems are optimization problems on directed or undirected graphs with edge weights. They are related to problems that deal with finding structures that minimize the sum of edge weights, such as the well studied Shortest Path and Minimum Spanning Tree problems. Bottleneck problems deal with finding structures that maximize the minimum edge weight.

Bottleneck problems have important applications in fields that deal with network routing such as logistics and computer networking, and others like digital compositing. The Bottleneck Path problem appears as a subproblem in the algorithm by Edmonds and Karp [1] for solving the Maximum Flow problem and in the k-splittable flow algorithm [2].

In the thesis we look at three Bottleneck problems, namely the Bottleneck Path problem, the Bottleneck Spanning Tree problem and the Single Source Bottleneck Path problem. We explore various algorithms and techniques that are used in solving these problems and examine their runtime characteristics. We focus especially on the algorithms by Chechik, Kaplan, Thorup, Zamir, and Zwick 2016 [3] and Duan, Lyu, and Xie 2018 [4], that have been discovered within the last couple of years and give the best running time for their problem currently known.

• [1] Jack Edmonds and Richard M. Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”. In: J. ACM 19.2 (Apr. 1972), pp. 248–264.
• [2] Georg Baier, Ekkehard Köhler, and Martin Skutella. “On the k-Splittable Flow Problem”. In: Algorithms — ESA 2002. Ed. by Rolf Möhring and Rajeev Raman. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 101–113.
• [3] Shiri Chechik et al. “Bottleneck Paths and Trees and Deterministic Graphical Games”. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Ed. by Nicolas Ollinger and Heribert Vollmer. Vol. 47. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016, 27:1–27:13.
• [4] Ran Duan, Kaifeng Lyu, and Yuanhang Xie. “Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs”. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Ed. by Ioannis Chatzigiannakis et al. Vol. 107. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, 43:1–43:14.

The Subset Sum Problem is a well-known NP-complete problem. It is both theoretically interesting and practically important to look into it. A very intuitive algorithm is exhaustive search, with time complexity O*(2ⁿ) and space complexity O*(n), where O*(^.) notation suppresses all polynomially bounded factors. In 1974 Horowitz and Sahni discovered algorithm with time and space complexity O*(2^n/2). Then the space complexity was further improved in a classic paper by Schroeppel and Shamir in 1981, and their algorithm is a general-purpose algorithm that can solve a number of NP-complete problems in time T = O*(2^n/2) and space S = O*(2^n/4), including Knapsack problem. And the Schroeppel-Shamir time-space tradeoff T·S ∈ O*(2ⁿ) has long been the most efficient way to trade space against time for the Subset Sum problem. Based on Dinur et al.’s dissection algorithm(2012), in 2013, Per Austrin et al. presented a significantly improved time-space tradeoff curve which matches the Schroeppel–Shamir tradeoff at the extreme points S = O*(1) and S = O*(2^n/4) but is strictly better in between and removed strong randomness assumptions.

Non-negative matrix factorization (NMF) refers to a group of algorithms that seek to factorize an input matrix X into a matrix product WH with the additional constraint that all three matrices may only contain non-negative entries. Because of its non-negativity constraint, it is a widely used tool in multivariate data-analysis as it allows for meaningful interpretations of extracted features. In this thesis we first motivate non-negative matrix factorization on two examples. Lee and Seung's multiplicative update rules to compute NMF provide us with an easy-to-implement, iterative algorithm, for which we provide its derivation and proof of convergence. We then address properties of NMF with a main focus on initialization, where we propose a novel initialization technique based on k-means++ clustering. Lastly, we include preliminary experimental results regarding the effects of different initialization techniques on the convergence of NMF.

The point-set registration problem seeks the transformation that optimally aligns a point set A to a reference point set B, and has numerous applications in computer graphics, computer vision, and robotics. Proposed by Besl and McKay, the iterative closest point (ICP) algorithm has seen wide adoption as a heuristic solution to this problem, with good performance in practice. In this bachelor's thesis we review and illustrate results from the literature about the convergence characteristics of ICP, focusing primarily on complexity bounds. We first explain in detail some of the results by Ezra, Sharir, and Efrat that bound the number of iterations performed by the algorithm, and then explore work by Arthur and Vassilvitskii that improve on the earlier results. In the process we build an intuition for geometric properties of the algorithm on which the presented ICP point configurations used to prove the complexity bounds rely. Finally, we propose a tool for exploratory analysis by creating convergence diagrams that visualise the final cost value the ICP algorithm converges on when run on (A + t₀, B), for initial offsets t₀ on a grid of arbitrary resolution.

We will describe fixed parameter tractable algorithms for finding simple paths and cycles in a graph. Therefore we will look at algorithms using random orientations, but the main focus lies on the algorithms using the method color-coding. We also discuss the derandomization of the algorithmsseveral random graphs.

We will see that the color-coding methods are generally more suitable for finding paths or cycles than the easier methods using random orientations, except for finding k-paths in dense graphs G with |E(G)| < k|V(G)|. 

Im Fokus meiner Bachelorarbeit steht die Methode der Individualisierung mit Verfeinerung, welche von den meisten praktischen Algorithmen verwendet wird, um zwei Graphen auf Isomorphie zu testen. Die Grundbegriffe zum Verständnis des Graphisomorphieproblems werden erläutert. Ein Ziel der Arbeit ist die algorithmische Darstellung der Methode und ihrer Bestandteile mit mathematischen Grundlagen. Anschließend wird ein Algorithmus vorgestellt, der sich dem Graphisomorphieproblem widmet, in dem - in einem mit einfachen Mitteln erklärten Black-Box-Modell und anhand von Suchbäumen mit gefärbten Blättern - dieses in reduzierter und damit vereinfachter Form angegangen und gelöst wird.

The Burrows-Wheeler Transformation (BWT) is an algorithm, used in some compression algorithms. It rearranges the symbols of a too compressed string after its context. That will lead to a better cluster of symbols, which results in a better compression ratio. The BWT itself does not change the size of the string, and since it only requires memory for a single pointer and some computation time, it is almost for "free". Bzip2 is nowadays one of the standard compression algorithms which use the BWT as a core algorithm. The thesis will explain how the BWT works and explain why the other algorithms in the bzip2 perform well with the rearranged data and try to reduce the compression rate further.

In der Praxis stellt sich oft die Frage nach der effektiven Speicherung von Informationen und dem Umgang mit unsicherem Wissen. Das Ziel der vorliegenden Arbeit ist eine methodische Einführung in das Gebiet der Datenverarbeitung, vor allem für Zuhörer:innen, der Lehrveranstaltung “Logik und diskrete Mathematik” zu geben. Es werden Aufbau, Eigenschaften, Umsetzung, theoretische Zusammenhänge und Hintergründe von Bayes-Netzen beschrieben. Es geht um die bedingte Unabhängigkeit von Zufallsvariablen und ihre Verbindung mit den Graphen, daher werden alle grundlegenden und notwendigen Konzepte aus der Wahrscheinlichkeits- und Graphentheorie berücksichtigt und wiederholt, so dass die Arbeit als eigenständiges Unterrichtsmaterial im Selbststudium verwendet werden kann. Generell basiert diese Ausarbeitung auf den Kurs “Logik und diskrete Mathematik” aus dem Wintersemester 2019/1020 und gibt einen Überblick über eine mögliche Einführung der probabilistischen Modelle an.

Differentielle Privatsphäre ist ein Konzept aus der Kryptographie und Datenanalyse. Sie liefert eine rigorose Definition zur Klassifikation von Analysemethoden hinsichtlich des Trade-off Aussagekraft/Privatsphäre. Haben wir eine Menge an Daten von Personen erhoben, wollen wir den Datensatz analysieren und daraus aussagekräftige Schlüsse ziehen. Gleichzeitig muss aber die Privatsphäre der Personen geschützt werden, das heißt es sollte nicht möglich sein, mit (veröffentlichten) Analyseergebnissen die (geheimen) Daten von Einzelpersonen zu rekonstruieren.

Die konvexe Hülle ist eine grundlegende Struktur der algorithmischen Geometrie, die eine Menge von Datenpunkten im d-dimensionalen Raum auf eine bestimmte Art von allen Seiten umschließt. Ein (möglichst zentraler) Punkt in der konvexen Hülle eines Datensatzes kann ein guter Repräsentant des Datensatzes sein. In der Arbeit "How to Find a Point in the Convex Hull Privately" von Kaplan, Sharir und Stemmer wird ein Algorithmus beschrieben, der unter bestimmten Annahmen differentiell privat einen Punkt in der konvexen Hülle eines Datensatzes aus n Datenpunkten findet, in Laufzeit O(n^d). Dies stellt sich als relativ komplexes Problem heraus, das weitere Konzepte der algorithmischen Geometrie benötigt, unter anderem die sog. Tukeytiefe, ein Maß der Zentralität in der konvexen Hülle, und die Punkt-Geraden Dualität. Wir ziehen eine weitere Arbeit zur Hilfe und untersuchen und implementieren den Algorithmus im zweidimensionalen Fall. Mit der Implementierung stellen wir Messungen zur Privatsphäre, Laufzeit und Nutzen an.

Every engineer wants to obtain as much control over the system as possible. One of the instruments to increase control rate is a possibility to reset the system, i.e. to return it to a known state at any moment. Most of the systems can be described in state-transition form, i.e. as deterministic finite automata (DFA). The concept of resetting a DFA was introduced by Cerný (1964) and now is called a DFA synchronization. This thesis focuses on synchronization problems, such as: how to determine whether a given DFA is synchronizing and what is a length of a reset word. This problems are believed to be one of the hardest and oldest prob- lems in the theoretical computer science. After a short theory introduction, some of the discovered algorithms with their improvements are discussed. The last sec- tion contains tests implemented in Python3. In those tests a big number of DFA is generated and synchronization property is checked under different conditions. The practical part aims to give a sense of the behaviour of the synchronization property. With help of the performed tests it is shown that the most automata tend to be synchronizing, which is quite impressive and counterlogical.

Finger sind externe Pointer, durch welche man eine "Abkürzung" bei der Suche nehmen kann. Im Vergleich zur Suche von der Wurzel aus, fängt man bei der Fingersuche zuerst vom Finger aus an zu suchen. Finger sollten daher in hoch frequentierte Bereiche in abstrakten Datenstrukturen gestellt werden, sodass diese "Abkürzung" besonders oft genutzt werden kann.

In meiner Bachelorarbeit wird sich mit drei Konzepten der Fingersuche beschäftigt: dem Lazy-Finger, Min-Max-Finger und dem Splay-Tree. Die Konzepte werden im Vortrag kurz vorgestellt.

Es wird eine einfache Antwort auf die Anzahl der Finger geboten und eine Simulation der Fingersuchalgorithmen präsentiert.

Today, cellular networks are a vital component of our day-to-day life, due to the inevitable requirements to technology to have wireless capabilities. An oversimplified theoretical model for cellular networks are unit disk graphs. One of the most uncomplicated, yet most popular problems, concerning graphs, is the triangle detection problem. In this thesis, a robust algorithms model is used, combined with the kissing property of unit disk graphs, in order to construct robust algorithms for finding a triangle in unit disk graphs, given in abstract graph form, which run in polynomial time. The correctness of the approach is proven theoretically and the running time is evaluated with the help of O-Notation for two possible graph representations - adjacency list and adjacency matrix. Furthermore, for each graph representation a Python implementation is introduced. With the help of the implementation, the execution time of the algorithms is evaluated empirically. Different data sets from several graph classes are created, in order to gain a better understanding of the running time dependency on the input. The data sets are parameterized with values, which could affect the running time, like number of vertices, sample size, axis bounds and edge inclusion probabilities. Eventually, linear plots are visualized, comparing the sample mean and the sample standard deviation of the running time of the algorithm for data sets, consisting of different graph classes and represented in different abstract forms.

The goals of this thesis are to determine the process of the creation of custom- tailored catering menus and to construct and to validate an algorithm, which can create a custom-tailored catering menu automatically. In the first part, there is an introduction to the problem and its domain. The second part is devoted to the discussion about two approaches: one is data driven and the other interview driven. These two approaches are used in order to find patterns, causalities and investigate the manual process of creating custom-tailored catering menus. In the third part, the manual process is translated into an algorithm step by step. The last part gives an outlook on further improvements and on continuous learning.

Selection problem has been studied intensively over the last decades, and many diffe- rent algorithms are known. These algorithms have different performance in the ave- rage case, worst case,and best case. In my thesis, I mainly introduce some famous algorithms, compare their performance through experiment.

At the beginning of the thesis, I first introduce the mathematical premises of based on the comparative selection model, followed by the well-known selection problem, for which I focus on these algorithms Quickselect, BFPRT , Selecting using a random sample, and Heapsort, present the procedure, the pseudo-code, and the proof of the time complexity of these algorithms, and give an example of every algorithm. Then I put up python code of every algorithm, and in the final experiment I randomly ge- nerated 10,000 numbers and executed it 1,000 times to compare the time required by each algorithm to find the k-th samllest number in a unsorted array, and make final conclusions.

Grötzsch's theorem affirms that every planar graph G in which there is no triangle is 3-colorable. Dvorak, Kawarabayashi, and Thomas have designed a linear-time algorithm relying on the Grötzsch's theorem to find a proper 3-coloring of the given graph. Compared to Kowalik who used a data structure called "Short Path Data Structure (SPDS)", it avoids complex data structures, which makes it easier to implement. However, because of the difficulty of their paper and complicated proofs, it's really hard to understand it. So we will explain their main idea and proofs with more illustrations and in detail.

Let us consider eps in (0,1)  and an undirected, weighted graph G with n nodes and low doubling dimension d. Konjevod, Richa and Xia introduced a (1 + eps)-stretch labeled routing scheme with (log n)-bit routing labels, O(log^2 n / log log n)-bit packet headers and ((1/eps)^O(d) log^3 n)-bit routing tables at every node for such graphs G. Now, we want to analyze the preprocessing step of this method. We show that the running time for this is O(n^3 + eps^{-1} n^2 log^2 n).

Also, we adapt the method for Unit Disk Graphs and improve the running time to be O(eps^{-1} n^2 log^2 n). We show that the doubling dimension for Unit Disk Graphs is O(max(1, D^2), with D being the diameter of the graph. Additionally, we simplfy Konjevod et al.'s routing algorithm and transform it into a recursive form.

The diameter of a graph equals the longest distance between any pair of vertices. A graph can be oriented by assigning a direction to each edge. A strongly connected orientation includes a directed path from each vertex u ∈ V (G) to each other vertex v ∈ V (G). The oriented diameter of a graph G is the minimum diameter of all strongly connected orientations of G. Let f (d) be the maximum oriented diameter of all graphs of diameter d. In other words, every 2-edge- connected graph of diameter d admits an orientation of diameter f (d) or less. Chvátal and Thomassen [2] showed the following bounds: 0.5d² + d ≤ f (d) ≤ 2d² + 2d. A recent paper by Babu, Benson, Rajendraprasad and Vaka improves the upper bound for all d ≥ 8 and d = 4 [1]. By using a similar approach, I improve the upper bounds for all d ≥ 5. None of these upper bounds could be shown to be tight, so there is room for further improvement. Additionally this thesis gives an overview of the current best results and techniques used to prove the current best results.

Die vier Berechnungsmodelle Zellulärer Automat, Markow-Algorithmus, Post’sches Tag-System und Zählermaschine besitzen die gleiche Berechnungsstärke wie Turingmaschine, Lambda-Kalkül, Random Access Machine und WHILE-Schleife. Ihre Funktionsweise unterscheidet sich größtenteils stark von den aus dem Informatik-Bachelor bekannten Berechnungsmodellen. Der Zelluläre Automat berechnet den folgenden Zellenzustand anhand des vorliegenden Zustands der Zelle und der Zustände der Nachbarzellen, wodurch er auf allen Zellen gleichzeitig (parallel) arbeitet. Der Markow-Algorithmus arbeitet auf Wörtern, wobei er das Eingabewort durch Suchen und Ersetzen jeweils eines Teilwortes umwandelt. Das Tag-System arbeitet auch auf Wörtern, schneidet aber ein Teilwort fester Länge am Anfang des Wortes ab und hängt ein Teilwort am Ende an. Die Zählermaschine ähnelt der Random Access Machine, besitzt aber – je nach Autor – nur drei bis vier Operationen und kann Register nicht indirekt adressieren.

Meine Arbeit vertieft die Funktionsweise der vier Modelle anhand der Erarbeitung des Primzahltests. Das gemeinsame Beispiel erleichtert wiederum den Vergleich zwischen den vier Modellen. Außerdem skizziert sie die Beweise, dass die Modelle turingvollständig sind. Bei meiner Verteidigung werde ich unter anderem auf die vier Modelle und den Primzahltest für den Markow-Algorithmus eingehen.

Übertragungsgraphen sind eine Art von gerichteten Graphen, bei denen die Knoten einen zugehörigen Radius haben, der die Erreichbarkeitsbeziehungen bestimmt.

Um zu bestimmen, ob Knoten miteinander verbunden sind, werden drei Methoden vorgestellt, von denen zwei weit verbreitet, aber vermutlich inef- fizient sind. Die dritte ist eine von Kaplan, Mulzer et al. vorgestellte Daten- struktur namens Erreichbarkeitsorakel, die experimentell evaluiert und mit den anderen Methoden verglichen werden soll.

Die vorgestellte Datenstruktur erweist sich als platzsparend und performant bei Abfragen. Allerdings ist die Vorverarbeitungszeit der Implementierung länger als erwartet.

Dennoch ist die Gesamtleistung sehr gut und erreicht eine hohe Wahrschein- lichkeit für die Beantwortung von Erreichbarkeitsfragen, ohne sich einige der gravierenden Nachteile der trivialen Methoden zu teilen.

Der Suffix-Baum ist eine wichtige Datenstruktur für Probleme im Bereich der Verarbeitung von Zeichenfolgen. Die Datenstruktur bietet lineare Zeit- und Speicherplatzlösungen für viele String-Matching-Probleme. Der Ukkonen-Algorithmus ist ein linearer Online-Algorithmus zur Konstruktion von Suffix-Bäumen. Der Algorithmus scannt den Text Zeichen für Zeichen von links nach rechts und erstellt schrittweise Suffix-Bäume für das Präfix der bisher gescannten Textzeichenfolge. Die Laufzeit zeigt sich in Theorie und Praxis als linear. Eine Implementierung kann zügig und nah am Pseudocode erfolgen. Der Algorithmus von Ukkonen wird in der Praxis von geläufigen und modernen Algorithmen in der Ausführungszeit geschlagen. Die Funktionsweise erweist sich bei der Nutzung eines Prozessors mit Cache als unvorteilhaft.

The separating words problem poses the question of how many states a deterministic finite automaton needs to have in order to distinguish two given strings, with respect to their length n. We aim to provide an easily accessible version of the algorithms and proofs given in J. M. Robson's 1989 Paper "Separating Strings with Small Automata", which established an upper bound on the state count of O(n^{2/5} log^{3/5}{n}), which had not seen any improvements until earlier this year.

Bei dieser Arbeit wird ein Algorithmus, basierend auf dem k-Nearest-Neighbor-Algorithmus und der Kernregression, entwickelt und in der Software elect implementiert. Der Algorithmus wird verwendet, um Stimmenprognose zu erzeugen. Zusätzlich wird die Authentizität der Stimmenzahlen mittels Benfordschen Gesetzes geprüft. Anhand dessen werden Bemerkungen zu den Auffälligkeiten verschiedener Gebiete für den Anwender ermittelt, die durch graphische Abbildungen nachvollziehbar gemacht werden. Hauptsächlich wird die Bundestagswahl 2017 in Berlin sowie die Landtagswahl 2018 in München zum Testen benutzt. Der Algorithmus für die Stimmenprognose erzeugt Stimmenanteile, die durchschnittlich um weniger als 13% der tatsächlichen Stimmenanteile bei der Bundestagswahl 2017 in Berlin abweichen. Eine Übernahme der Vorperiodenwerte ergibt gegenüber den prognostizierten Stimmen eine durchschnittliche Abweichung von etwa 39%. Obwohl die von den auffälligsten Gebieten gemeldeten Zahlen manchmal der Benfordverteilung nicht genügen, konnte keine signifikante Korrelation zwischen der Größe der Abweichung bzgl. der prognostizierten Stimmen und bzgl. der Benfordverteilung festgestellt werden. Das kann daran liegen, dass die oft umstrittene Verwendung von auf dem Benford-Gesetz basierten Tests bei Wahlen ungeeignet ist.

The Arrival game is a zero-player game on switch graphs. Switch graphs are graphs in which the vertices have at most two outgoing edges to their successors and the successors are switched successively when traversed. In the case of Arrival a switch graph is given, an origin and a destination in that graph and the problem Arrival is to decide whether a run through the switch graph starting at the origin will at some point arrive at the destination.

Arrival’s complexity is of interest because Arrival has been proven to lie in the intersection of UP and co-UP but there has yet not been found a polynomial-time algorithm to solve it.

We present previous research on Arrival’s complexity as well as introduce an experimental examination of the solutions of Arrival for small switch graphs. The following work is to be seen as an introduction to Arrival. The experimental part shall give a hint on the runtime of YES-instances of Arrival.

Einen Weg für ein Datenpaket von einem Start- zu einem Zielknoten durch ein Netzwerk zu finden wird als Routing bezeichnet und stellt ein wichtiges Problem in Netzwerken dar. Damit das Paket schnell an sein Ziel gelangt werden effiziente Algorithmen benötigt, um dieses Problem zu lösen.

Diese Arbeit behandelt einen Routing Algorithmus für eine spezielle Art von Graphen, die beispielsweise in der Robotik dazu verwendet werden können, um ein Gebiet mit Hindernissen in Form von Polygonen darzustellen. Der Algorithmus verspricht in der Theorie gute Ergebnisse. Nach einer Vorverarbeitung findet dieser einen Weg durch das Gebiet, der beliebig nah am bestmöglichen Weg liegt und dabei nur wenig zusätzlichen Speicher benötigt. In dieser Bachelorarbeit wird der Algorithmus vorgestellt, erklärt und visualisiert. Zudem wurde dieser implementiert und anschließend auf eine mögliche Anwendung untersucht. Dabei konnte festgestellt werden, dass der Algorithmus und seine Implementierung für eine mögliche Anwendung wohl gut geeignet wäre.

Die Anzahl an gesammelten und zu verarbeiten steigt jedes Jahr weiter an. Es wird umso wichtiger diese Daten effizient auswerten zu können. Teil dieser Auswertung ist die Identifizierung von Extremwerten, zum einen um Datenfehler zu entfernen und zum anderen um seltene und interessante Ereignisse zu finden. Über die Jahre wurden viele verschiedene Techniken entwickelt. Einige davon werden in dieser Arbeit näher erläutert, selber in Python implementiert und anschließend auf einigen ausgesuchten Testdatensätzen angewendet. Anhand der Ergebnisse werden die Techniken schließlich bezüglich verschiedener Eigenschaften bewertet.

Ein Graph ist genau dann planar, wenn er nach dem Satz von Kuratowski keinen Unterteilungsgraphen eines Kuratowski-Graphen enthält. Dieses Kriterium ist bereits seit 1930 bekannt, trotzdem wurde der erste Algorithmus, der einen Graphen auf Planarität in linearer Zeit prüft, erst in den siebziger Jahren des letzten Jahrhunderts formuliert. Moderne Algorithmen dieser Art, genannt Planaritätstests, prüfen nicht nur Graphen auf Planarität, sondern liefern auch eine Einbettung in linearer Zeit, wenn der Graph planar ist und extrahieren darüber hinaus einen Unterteilungsgraphen eines Kuratowski-Graphen, sollte dieser nicht planar sein.

Einer dieser Algorithmen ist der Boyer-Myrvold-Algorithmus, der in der Praxis einer der schnellsten Planaritätstests und im Vergleich zu anderen linearen Planaritätstests einfacher zu implementieren ist. Diese Arbeit ist eine theoretische Untersuchung des Boyer-Myrvold-Algorithmus, einschließlich eines ausführlichen Beweises der linearen Laufzeit sowie dass der Algorithmus einen Graphen korrekt auf Planarität prüft.

The Count-min sketch is a data structure, which uses the probabilistic nature of a hash table to approximate the frequencies of elements in a data stream.

Compared to an exact counter that does not use hash functions, the Count-min sketch has advantages in its update time and space needed. The disadvantage of the Count-min sketch is that the count is not exact and has an error rate that depends on two parameters: the number of hash functions used and the size of their codomains. The theoretical analysis of Cormode and Muthukrishnan is restated in this thesis. It provides a mathematically proven method on how to pick these parameters for a wanted error range. This thesis also explains how the Count-min sketch and its conservative update variant work in theory.

The aim of the conducted experiments is to determine how the parameters should be picked. For this, the results of the theoretical analysis are used in a python3 implementation of both variants.

We show that the Count-min sketch works well at approximating the most frequent elements in language data, by conducting experiments on the complete works of Shakespeare. Then we show that on the contrary this is not the case with data, where the distribution of elements is uniform. It is also shown that the conservative update is more accurate in both data sets. For this reason, it is advised to use this variant in practice if possible.

Die Streckenoptimierung stellt für elektronisch betriebene Fahrzeuge aufgrund der unterschiedlichen Verfügbarkeit und Beschaffenheit von Ladesäulen ein komplexes Problem dar. In dieser Arbeit soll eine kürzeste Strecke inklusive Ladestrategie gefunden werden, welche die Summe aus Lade- und Fahrzeit, also die Reisezeit insgesamt, optimiert. Dies stellt im Allgemeinen ein NP-schweres Problem dar. In dieser Arbeit wurde untersucht, unter welchen Einschränkungen der polynomielle Ansatz zur Lösung des bekannten "Gasstation Problem" erweitert und auf das Routingproblem angewandt werden kann. Zusätzlich wurde ein bekannter, exponentieller Ansatz implementiert. Bei der Analyse der Laufzeiten zeigt der polynomielle Ansatz eine deutliche Abhängigkeit vom Ladesäulennetz, während der exponentielle Ansatz vor allem von dem Abstand der gewählten Start- und Zielknoten abhängt. Zusätzlich erwiesen sich die nötigen Einschränkungen, um den polynomiellen Ansatz zu verwenden, als zu gravierend, um realistische Problemstellungen abzubilden.

This thesis considers assymmetric convex intersection testing (ACIT). We are given two convex polytopes, one as the convex hull of a set of points and the other one as the intersection of a set of halfspaces. The question of interest is then whether they have a common point or not. This problem is a special case of polytope intersection detection and has applications in various fields including data analysis.

The algorithm presented here solves the ACIT problem in O(d^^O(d)(n+m)) expected time. It does so by using the LP-type framework, in particular, it uses a method introduced by Chan for implicitly defined LP-type problems.

Since the introduction of map-reduce in 2004, this programming model has been adopted by many leading technology companies. The easy-to-use implementations of map-reduce enable extensive data processing and generation "without" a deep understanding of parallel and distributed programming. Nevertheless, reducing the runtime on map-reduce computations can be crucial when processing terabytes of data on clusters with over a thousand machines. In this work, we will identify cost drivers in map-reduce and discuss an approach to designing efficient map-reduce algorithms. In particular, we will focus on the tradeoff between a high degree of parallelism and low communication cost. Furthermore, we will examine different algorithms that solve the Hamming distance problem using map-reduce and analyze them theoretically and experimentally.

Die wiederkehrend hohe Durchfallquote in der Veranstaltung „Grundlagen der theoretischen Informatik“ an der Freien Universität Berlin ist der Anlass, ebenjene Veranstaltung mit dem Ziel der Steigerung des Studienerfolges zu überarbeiten. Grundlage der Überarbeitung ist die Theorie des Constructive Alignments. In dieser Theorie steht die Ausrichtung der Lehr- und Lernaktivitäten und der Prüfung an den intendierten Lernergebnissen im Mittelpunkt. Das Constructive Alignment beruht auf der konstruktivistischen Lerntheorie und fordert dementsprechend eine Studierendenzentrierung. Dies zeigt sich an den vorgeschlagenen Änderungen an Vorlesung, Tutorien und Übungszetteln, die bei den Studierenden die Verwendung eines tiefgehenden Lernansatzes fördern. Das zweite zentrale Konzept des Constructive Alignments ist die Kompetenzorientierung. Um diese umzusetzen, wurden konkrete, überprüfbare Kompetenzen für die Veranstaltung formuliert und durch Beispielaufgaben erläutert, die ebenfalls zeigen, welche kognitiven Stufen (im Sinne der SOLO-Taxonomie) zur Bearbeitung der Aufgaben von den Studierenden eingesetzt werden müssen.

Tabulation Hashing has been regarded as a simple and an effective method to construct universal families of hash functions, which, though three-independent, provides plenty of the algorithmically important probabilistic guarantees that usually higher-independent does.

According to Zobrist, the scheme for simple tabulation hashing is that, we split a key x into c characters: x_1,...,x_c and initialize c totally random tables T_1,...T_c. The hash value comes out by performing exclusive OR operations on the c random codes generated from tables.

This thesis demonstrates why the simple tabulation hashing for chaining has the desired mathematics guarantees, which is the property from truly random hash functions. The proof has been done by Mikkel and Mihai, where the Chernoff bounds and Peeling technique were used.

Die Arbeit behandelt Zip-Trees, eine neue Art binärer Suchbäume, die von Tarjan, Levy und Timmel 2019 eingeführt wurde. In einem Zip-Tree bekommt jeder Knoten einen sogenannten "Rang" zugewiesen, der einer aus einer geometrischen Verteilung gezogenen natürlichen Zahl entspricht. Betrachtet man einen perfekt balancierten binären Baum fällt auf, dass die Verteilung der Knoten auf die verschiedenen Ebenen des Baumes exakt einer geometrischen Verteilung mit Mittelwert eins entspricht. Daher besteht die Kernidee hinter Zip-Trees darin, die Knoten zusätzlich zur binären Suchbaumeigenschaft anhand des zugewiesenen Ranges nach der max-heap-Eigenschaft anzuordnen, um den Baum damit in eine einigermaßen balancierte Form zu bringen. Der zweite Grundgedanke der Zip-Trees besteht darin, anstatt Rotationen sogenannte "zip" und "unzip" Operationen zu verwenden, um die Struktur des Baumes beim Einfügen und Löschen zu erhalten.

Neben einer theoretischen Analyse der Eigenschaften der Zip-Trees befasst sich die Bachelorarbeit mit einem Vergleich dieser neuen Bäume gegen bereits etablierte verwandte Datenstrukturen. Ausgewählt wurden hierbei Treaps, Skip-Listen, AVL-Bäume sowie Rot-Schwarz-Bäume. All diese Datenstrukturen werden in der Arbeit kurz besprochen und sowohl in ihren theoretischen Eigenschaften als auch mit Hilfe konkreter Implementierungen mit Zip-Trees verglichen. Damit konnte gezeigt werden, dass Zip-Trees, insbesondere in einer neueren, optimierten Variante, durchaus performant sind und sie aufgrund ihrer vergleichsweise einfachen Implementierung durchaus als Alternative zu "klassischeren" Datenstrukturen in Erwägung gezogen werden sollten.

In dieser Arbeit werden der Bloom-Filter und einige Erweiterungen vorgestellt. Der Bloom-Filter bietet eine Lösung für das statische Wörterbuchproblem. Da der Bloom-Filter eine probabilistische Datenstruktur ist, besitzt der Bloom-Filter eine False Positive Rate. Diese ist eine der großen Schwächen des Bloom-Filters.Die hier vorgestellten Erweiterungen implementieren das dynamische Wörterbuch oder verbessern die False Positive Rate gegenüber dem Bloom-Filter. Die Erweiterungen wurden aus verschiedenen anderen Arbeiten übernommen und werden ausführlich betrachtet und zu jedem der Filter der Pseudocode angegeben um dem Leser die Implementation in einer belieben Programmiersprache zu erleichtern. Es wird auf ihre False Positive Rate eingegangen und sie werden einander gegenübergestellt, um für mögliche Szenarien eine geeignete Erweiterung zu finden. Zum Ende der Arbeit wird die Analyse der False Positive Rate nach Bloom untersucht und festgestellt, dass die Analyse nach Bloom zwar nicht korrekt ist, da sie eine falsche Annahme trifft, aber eine gute Näherung für die False Positive Rate ergibt.

Besonders interessant ist die Arbeit für Leser, die einen Bloom-Filter implementieren oder aus der theoretischen Analyse erfahren wollen, ob ein Bloom-Filter als Lösung ihres Problems in Frage kommt. Auch Leser die den Bloom-Filter schon kennen, aber die in vielen Fällen angegebene False Positive Rate in Frage stellen, werden in dieser Arbeit eine Erklärung zu dieser Problematik finden.

Let S be a set of points located in the unit square [0, 1]^2, which contains (0, 0). An open conjecture states that for any S it is possible to cover half of the area by rectangles inside the unit square, with the conditions that the lower-left corner of each rectangle is a point in S and that the rectangles are non-overlapping and axes-parallel.

The focus of this thesis is to suggest an algorithm, which for any S determines what the maximum area is that can be covered by rectangles. This algorithm improves the running time of the currently best-known algorithm with running time poly(n)*n! to poly(n)*2^n by the use of dynamic programming. To analyze how this algorithm performs, lower bounds for different types of instances are proven, e.g. that the conjecture can be confirmed for n

For a given set of points in the plane V we call a graph G = (V ∪ S, E) with Steiner points S a Manhattan network if it only includes axis-parallel edges and connects each pair of vertices via a path of minimal distance. Finding minimum L1-norm Manhattan networks for given input points V is a problem introduced and first studied by Gudmundsson, Levcopoulos and Narasimhan. Finding minimum L1 Manhattan networks is known to be an NP-hard problem. We present an algorithm constructing a 4-approximation for the length minimization problem in O(n³). We also consider the problem of minimizing the amount of introduced Steiner points |S| and present an algorithm giving us a 2-approximation in O(n³).

In 2015 wurde die Splitdicke als Graphparameter eingeführt. Die Splitdicke hat Ähnlichkeiten zu der Dicke von Graphen. In dieser Arbeit stellen wir die beiden Parameter in Beziehung, erläutern die Ahnlichkeiten und nennen ein paar bekannte Fakten. Darauf aufbauend analysieren wir die Dicke und Splitdicke der Graphenklasse der (multidimensionalen) Gittergraphen, wozu auch die Würfelgraphen gehören. Abschließend gehen wir noch auf die Komplexit ät ein und zeigen, dass es NP-schwer ist für einen gegebenen Graphen die Gleichheit von Dicke und Splitdicke zu prüfen.

Einer der wichtigsten Anwendungsgebiete in der Graphentheorie ist die Untersuchung der optimalen Wege zwischen den Knoten. Dabei wird ein Weg als optimal bezeichnet, wenn er am kürzesten, am schnellsten oder am günstigsten ist. Je
nach Anwendung soll die Summe der Kanten die sich auf diesen Weg befinden optimal sein. Es gibt allgemein drei Verfahren für das Finden des optimalsten Weges: zwischen zwei beliebig gewählten Knoten, zwischen einem Startknoten und allen anderen Knoten und zwischen allen Paaren von Knoten. Diese Arbeit wird sich mit dem dritten Verfahren beschäftigen, auch bekannt unter dem Namen APSP-Problem. Bis einschließlich 2007 lag die optimalste Lösung in einer Laufzeit vonO(n^3/(log n)^c), 0 < c ≤ 2. 2014 gelang Ryan Williams [Wil13] ein besserer Ansatz.

Mit Tricks wie verbesserter Schaltungskomplexität, Zerlegung von Matrizen in kleinere Teilmatrizen und Methoden zur schnellen Polynom-Auswertung durch Matrix-multiplikation gelang es ihm ein deterministisches Verfahren abzuleiten mit einer Laufzeit von: n^3 ⋅ log M ⋅ poly(log log M)/2^((0.1 log n)^c).

Darüber hinaus entwickelte er auch ein randomisiertes Verfahren was dem deterministischen sehr ähnelt. Durch Manipulation der gegebenen Matrizen und randomisierten Techniken entwickelte Williams ein noch schnelleres Verfahren zur Lösung des APSP-Problems. Es liefert mit einer sehr hohen Wahrscheinlichkeit das richtige Ergebnis in einer Laufzeit von n^3/2^Ω(√ log n).

Die vorliegende Arbeit beschäftigt sich hauptsächlich mit der einfachen Beschreibung dieses komplexen randomisierten Verfahrens. Um das zu realisieren ergänzt diese Arbeit Williams Paper um eigene weiterführende Beispiele und Erklärungen. Dazu wird zunächst das APSP-Problem vorgestellt sowie nötige Erklärungen und Definitionen vorgenommen. Anschließend wird im Kapitel 2 das deterministische Verfahren und in Kapitel 3 das randomisierte Verfahren erläutert.

Zum Schluss wird ein Fazit gezogen, in dem die Auswirkungen der Arbeit von Williams auf andere Fragen und Probleme dargestellt werden. Zudem evaluiert der Autor seine Probleme und Schwierigkeiten mit dem Bearbeiteten des Papers.

Building systems capable of replicating global illumination models within limited time-frames has long been one of the toughest conundrums plaguing computer graphics researchers.

A new and innovative method proposed by Cyril Crassin et al. in 2011 appears to provide a well-disposed balance between performance and physical fidelity.

Termed voxel cone tracing, the method utilizes seemingly uncorrelated techniques well established in the realm of computer graphics to achieve hardware accelerated indirect illumination.

This thesis explores the differences between the underlying mathematical model and an actual software-based implementation of this algorithm.

Given a set S of n discs, where the center coordinates of each disc D ⊂ R^2 and each disc has an associated radius RD > 0. The disc graph is the graph with the set S and an edge between two discs A and B if and only if the euclidean distance between A and B |AB| is smaller or equal to the sum of the radii RA and RB, i.e., if the two discs directly intersect.

The problem of finding triangles in disc graphs has been studied by Kaplan et al. in the research paper "Finding Triangles and Computing the Girth in Disk Graphs". This problem is particularly difficult for general graphs, but specific graph classes, such as planar graphs do already have a solution.

Kaplan et al. observe that a triangle within a disc graph can be found in 𝒪(n log n) worst- case time. In this thesis, an attempt has been made to implement their theoretical approach in a real- world setting.

In dieser Arbeit wird die Effizienz von Constant-Workspace-Algorithmen für Delaunay-Triangulationen und Voronoi-Diagramme getestet. Dazu werden die Algorithmen implementiert und bezüglich Laufzeit und Speicherverbrauch mit einem Algorithmus verglichen, für den bereits gezeigt wurde, dass er im Vergleich zu anderen Algorithmen der Art effizient ist. Es wird gezeigt, dass die Constant-Workspace-Algorithmen nicht annähernd so schnell sind, wie der Vergleichsalgorithmus, aber dennoch in einigen Situationen nützlich sein können.

Bitcoin wurde 2009 von Satoshi Nakamoto veröffentlicht und ist die bekannteste Kryptowährung. In der Vergangenheit sorgte Bitcoin für Schlagzeilen, nicht zuletzt, weil man nach wie vor keine Kenntnis darüber hat, wer oder was Satoshi Nakamoto tatsächlich ist. Obwohl Bitcoin nach wie vor auf dem ersten Platz der Kryptowährungen ist, gibt es inzwischen viele neue Kryptowährungen, die mehr als Bitcoin können. Ein Kandidat hierfür ist Ethereum.

Ethereum wurde 2015 veröffentlicht und ist nicht nur eine reine Kryptowährung, sondern auch eine Plattform für dezentrale Applikationen. Beide basieren auf der Blockchain, welche als eine Art Buchführungssystem fungiert. In der Blockchain sind alle Transaktionen gespeichert. Diese Transaktionen werden durch digitale Signaturen und kryptographische Hashfunktionen geschützt, so dass sie nicht manipuliert werden können.

Die Arbeit basiert auf dem von Satoshi Nakamoto veröffentlichten Whitepaper, auf dem Ethereum Whitepaper, sowie auf dem Ethereum Yellowpaper, eine mathematische Definition von Ethereum. Im Rahmen dieser Arbeit werden beide Kryptowährungen einzeln betrachtet und bezüglich ihrer technischen Funktionsweise erläutert.

In den letzten Jahren ist die Monte-Carlo-Baumsuche als Algorithmus um Spielbäume zu analysieren immer populärer und erfolgreicher geworden. In dieser Arbeit wird die Möglichkeit analysiert diese Inhalte auch in eine Vorlesung zu integrieren. Dazu wurden eine Herangehensweise an das Themengebiet mit aussagekräftigen Beispielen und auch Übungsaufgaben Entwickelt. Ziel ist es, dass die Studenten dadurch einen Vergleich zwischen dem Monte-Carlo-Algorithmus und dem herkömmlichen Minimax Algorithmus ziehen können.

The classical Fréchet distance is the minimal connecting distance needed to monotonically traverse two paths completely. Lexicographic Fréchet matchings utilize the steepest descent and apply the Fréchet distance recursively (i.e. divide and conquer) to minimize the time spent at a distance greater than a threshold. We take a deep dive into degenerate inputs where different matchings appear equal when viewed at a distance. The problem of choosing one of the multiple paths through critical events at the same distance is investigated. Multiple critical events are compared using derivatives and second derivatives.

Let S be a set of points in the plane. In a square graph QG(S), each point is the centre of a square of bounded size. The points represent the vertices of QG(S) and two vertices share an edge, iff their squares intersect. There is a similar definition for region graphs: each point is the centre of the minimum enclosing circle of a region. Two points share an edge in the region graph RG(S), iff their respective regions intersect. We define the edge weight in both graphs to be the Euclidean distance between the endpoints of an edge.

This thesis describes routing schemes for a special case of region graphs and for the general case of square graphs that allow a packet to be routed along those graphs with a routing distance that is arbitrarily close to the optimal distance (i.e. the length of the shortest path).

Fusionierbare Heaps wie die Fibonacci-Heaps sind abstrakte Datenstrukturen zur Implementierung einer Prioritätswarteschlange. Mit den Rank-Pairing Heaps und den Hollow Heaps werden zwei Heap-Varianten vorgestellt und bewertet, die mit dem Ansatz entwickelt wurden, die gleichen amortisierten Laufzeiten wie Fibonacci-Heaps bei einfacherer Struktur zu erhalten.

Rank-Pairing Heaps sind klassische, aus Mengen von Bäumen bestehende binäre Heaps, die sich zu beliebiger Form entwickeln können. Sie benötigen nur eine einzige Strukturveränderung während des Verringerns eines Schlüssels und nutzen kaskadierende Rangveränderungen der einzelnen Knoten als Balancebedingung, um die Laufzeiten zu garantieren. Hollow Heaps bestehen aus einem gerichteten azyklischen Graphen. Verzögertes Löschen und Wiedereinfügen von Knoten sorgt in Kombination mit Knotenrängen dafür, dass bei simpler Struktur die amortisierte Laufzeit der Fibonacci-Heaps erreicht wird.

Die Conway-Folge ist eine ungewöhnliche mathematische Folge, bei der jedes Folgenglied eine Ziffernsequenz darstellt. Hierbei sei eine beliebige endliche Ziffernsequenz als Startsequenz gewählt und jedes weitere Folgenglied "beschreibt" den Aufbau des vorigen Folgengliedes. Als Beispiel sei gegeben: 1, 11, 21, 1211,111221, 312211, 13112221, ...

Die Arbeit beschäftigt sich nun mit der Aufarbeitung eines bereits existierenden Beweises von R. A. Litherland, welcher zeigt, dass (unabhängig von der Wahl der Startsequenz) nach spätestens 24 Schritten jede mögliche Ziffernsequenz aus einem Pool von 94 festen Elementen zusammengesetzt ist.

Let a convex set in the plane be given by either a set of points or half-spaces. The maintenance of it under insertion and deletion of elements is a fundamental problem in computational geometry. This thesis considers a data-structure which solves this problem. It was drafted by the researchers Kaplan, Tarjan and Tsioutsiouliklis in a paper about kinetic heaps (priority queues with linear functions as keys rather than fixed values). However it was never written down in detail. We state their construction explicitly. Its foundation is built by a deletion-only structure which uses finger trees (height balanced trees with preferred access points) to represent convex sets. With the semi-dynamic structure at hand, a fully dynamic one may be constructed using given dynamization transformations. The binary counting scheme transformation of Bentley and Saxe yields an insertion-and-deletion structure with O(log² n) worst-case vertical ray query time, O(log n) amortized insertion time and O(log n log log n) amortized deletion time. A transformation of Brodal and Jacob results in a structure with O(log n) worst-case vertical ray query time, O(log n log log log n) amortized insertion and O(log n log log n) amortized deletion time.

Owing to its speed and simplicity, the peak signal to noise ratio (PSNR) is still one of the most widely used image quality metrics today. In runtime critical applications, such as live-video encoding, using a more sophisticated image quality metric can be prohibitive for encoder mode decisions. Bosse et al. 2017 improved on the PSNR’s mediocre performance by perceptually adapting the PSNR, thereby introducing the notion of distortion sensitivity.

In this work we will expand on the concept of distortion sensitivity and explore the possibilities of estimating distortion sensitivity with a data-driven approach.

Dijkstra's Shunting Yard Algorithmus (dt. Rangierbahnhof Algorithmus) überführt mathematische Terme von der Infixnotation in die umgekehrte polnische Notation. Der ursprüngliche Shunting Yard Algorithmus ist jedoch nur eine effiziente Methode, um einfache mathematische Terme mit binären Operationen zu konvertieren. Für komplexere Terme, wie z.B. Funktionen mit mehreren Parametern, muss der Algorithmus erweitert werden.

Im Rahmen der Bachelorarbeit soll die Erweiterung zweistufig erfolgen. Die erste Stufe vervollständigt und erweitert die Grundidee des Algorithmus dahingehend, dass weitere mathematische Ausdrücke in umgekehrte polnische Notation überführt werden.

In der zweiten Stufe soll der Algorithmus CASE-WHEN Ausdrücke, die in einer SQL Abfrage auftreten, in abstrakte Syntaxbäume umwandeln. Aus einem abstrakten Syntaxbaum wiederum lässt sich ein Programmcode für semantisch äquivalente Ausdrücke in verschiedenen Programmiersprachen erzeugen.

Das Triangle Scheduling Problem, von Dürr u.a. in [1] vorgestellt, ist ein Spezialfall von Mixed-criticility Scheduling mit Jobs in Form gleichschenkliger Dreiecke. Da es NP-schwer ist, kann der optimale Zeitplan im Allgemeinen nur mittels Brute-Force-Algorithmus gefunden werden, unter der Annahme P≠NP.

Der effiziente gierige Ansatz, jeweils das größte Dreieck in die größte Lücke im Zeitplan zu setzen, kann in vielen Fällen die optimale Lösung ermitteln, wie quantitative Tests mit gleich verteilt zufälligen Jobgrößen zeigen. An den wenigen Beispielen mit nicht optimalem Ergebnis kann man untersuchen, wann der gierige Algorithmus die falsche Entscheidung trifft.

Darüber hinaus kann mit Hilfe dynamischer Programmierung eine (1+ε)-Approximation des optimalen Zeitplans gefunden werden. Indem die Jobgrößen und Startzeiten vorher aufgerundet werden, reduziert sich die Lösung dabei auf die Lösung von O(n^log(n)) vielen Teilproblemen.

In dieser Arbeit entwerfe ich die drei Algorithmen in Pseudocode und implementiere sie in der Programmiersprache Java.

Außerdem ist das Triangle Scheduling Problem geometrisch betrachtet ein Spezialfall des Packungsproblems in einem Rechteck und ich verallgemeinere den Brute-Force-Algorithmus auf andere Figuren wie gleichseitige Dreiecke, Kreise etc.

Beim 3D-Druck dient die Stützstruktur der Stabilisierung des Modells während des Druckprozesses. Da die Stützstruktur das Modell von unten abstützt, wirkt sich dessen Orientierung im Raum stark auf das Volumen der notwendigen Stützstruktur aus. Es lässt sich zeigen, dass das Problem der optimalen Orientierung eines 3D-Modells unter diesem Gesichtspunkt in polynomieller Zeit lösbar ist. Desweiteren wird ein approximativer Algoritumus vorgestellt, welcher das Problem für konvexe Modelle in linearer Zeit löst. In modifizierter Form lässt sich der Algorithmus auch auf nicht-konvexe Modelle anwenden, was allerdings in einer quadratischen Laufzeit resultiert. In der Auswertung zeigt sich, dass durch Anwendung des Algorithmus auf bestimmte Modelle signifikante Einsparungen in den Materialkosten erzielt werden können.

2012 stellte Xin-She Yang in einem Paper den Flower Pollination Algorithm for Global Optimization vor. Mit diesem konnte Yang in seinem Paper bereits einige mathematische Funktionen approximieren und auch Optimierungsprobleme lösen. In dieser Arbeit soll nun eine weitere Anwendungsmöglichkeit für diesen Algorithmus untersucht werden. Ziel ist es auf Grundlage von Yangs Arbeit einen Algorithmus zu entwickeln und zu implementieren, mit dem eine einfache Variante des Shape-Matching Problems approximiert werden kann. Dabei soll der Fréchet Abstand zwischen zwei Kurven minimiert werden.

Jump Point Search (kurz JPS) ist ein neuer Algorithmus in der Wegfindung. Durch seine herausragenden Performance findet er, vor allem in der Spiele-Entwicklung, viel Anwendung.Leider beschränkt sich die Definition dieses Algorithmus' auf quadratische Gitter.

Meine Arbeit beschäftigte sich mit der Idee, den Anwendungsbereich des JPS zu erweitern.Hierfür abstrahierte und mathematisierte ich sowohl seine Entwicklung, als auch seine Handlungsweise,adaptierte dieses Konzept auf regelmäßige Dreiecks-tesselierte Flächen und arbeitete die Kriterien für eine Verallgemeinerung heraus. Den entstandenen Algorithmus analysierte ich stochastisch und testete ihn gegen den "Jack of all trades"-Pathfinder A*.

Das Mitte der 1970er Jahre veröffentlichte Betriebssystem CP/M stellte zum Zeitpunkt seiner Veröffentlichung das erste hardwareunabhängige Mikrocomputer-Betriebssystem dar und trug maßgeblich zum Entstehen eines von Hardware-Herstellern unabhängigen Software-Marktes bei.

Diese Arbeit untersucht den Aufbau und die Struktur der ersten öffentlich verfügbaren CP/M-Version 1.3, um Einblicke in die interne Funktionsweise von CP/M zu erlangen. Dazu wird zunächst auf die von CP/M genutzte Hardware-Umgebung eingegangen, um anschließend einen detaillierten Einblick in die einzelnen CP/M-Komponenten zu geben. Insbesondere wird auf die Hardwareabstraktionsschicht und das Dateisystem von CP/M eingegangen. Im weiteren Verlauf der Arbeit wird die Architektur von CP/M mit modernen Prinzipien der Betriebssystementwicklung verglichen.

Die Veröffentlichung des IBM-PCs und des MS-DOS-Betriebssystems Anfang der 1980er Jahre führte zum graduellen Niedergang von CP/M. MS-DOS war zu CP/M kompatibel, so dass im Rahmen dieser Arbeit Version 1.x von MS-DOS mit CP/M 1.3 verglichen wird, um etwaige Ähnlichkeiten oder Unterschiede zwischen beiden Systemen festzustellen. Dieser Vergleich ergibt, dass MS-DOS durchaus einige CP/M-Konzepte übernimmt, die Systemarchitektur allerdings in vielen Bereichen verbessert.

Insgesamt zeigt sich im Verlauf dieser Arbeit, dass CP/M 1.3 zwar dank der Hardwareabstraktionsschicht ein portables Betriebssystem darstellt, jedoch auf Grund von Hardware-Limitierungen und teilweise daraus resultierenden Architektur-Schwächen unter Leistungsproblemen zu leiden hat.

Die Englische Sprache hat ein starke SPO Struktur. (Subjekt, Prädikat, Object)

Diese Struktur/Redundanz des Satzbaues könnte potenziell zusätzlich genutzt werden um höhere Kompressionsraten zu erhalten. Hierfür wurde ein Kompressionsverfahren entwickelt/erweitert und ausgewertet. Ein Vergleich mit einer PPMC (mit exclusion) Referenz-Implementierung zeigt, dass die Ergebnisse durch das in der Bachelorarbeit vorgestellte Verfahren sich leicht verschlechtert haben. (Vergleich der besten Ergebnisse bei ca. 2000 Datensätzen) Potenzielle Gründe dafür wurden genannt, sodass die Ergebnisse aus dieser Arbeit noch weiter verbessert werden können.

Similarity measures are useful for many applications, such as recommender systems and search engines. Graph-theoretic similarity measures try to determine similarities by analyzing the relations between objects. SimRank is a popular such similarity measure with an intuitively sensible notion of similarity that is strongly inspired by PageRank. However, SimRank suffers from the fact that the algorithm originally suggested for its computation has an efficiency of Θ(n⁴). It is not computationally feasible to apply such an algorithm to a large dataset, and hence this thesis explores various alternative algorithms. It is derived how memorizing subresults can improve the efficiency to O(n³). Furthermore, an alternative graph-theoretic similarity measure, called CoSimRank, is discussed. CoSimRank has the advantage that individual similarity scores can be computed in quadratic time. Finally, the performance of the various algorithms introduced is evaluated using data from MovieLens, a collection of large real-world datasets for recommender systems.

In der Bachelorarbeit diskutieren wir die Attraktor-Überdeckung und das Attraktor-Routing in einfachen orthogonalen Polygonen. Diese beiden Probleme sind Varianten des klassischen Art Gallery Theorems. Bei der Attraktor-Überdeckung ist es das Ziel, das Innere eines solchen Polygons mit Attraktoren zu überdecken. Attraktoren ("beacons") sind dabei Punkte innerhalb des Polygons, die, wenn aktiviert, alle anderen Punkte innerhalb des Polygons auf direktem Wege anziehen. Das Attraktor-Routing-Problem beschäftigt sich mit der Frage, wie viele Attraktoren nötig sind, um zwischen zwei beliebigen Punkten innerhalb des Polygons zu routen. Einen Punkt zu einem Zielpunkt zu routen beschreibt dabei den Prozess, diesen Punkt durch sequentielle Aktivierung einer Menge von Attraktoren zu seinem Ziel zu leiten. Zu beiden Fragen werden in der Arbeit die kürzlich von Bae et al. bzw. von Shermer bewiesenen optimalen worst-case-Schranken vorgestellt. Zudem führen wir ein neues, stärkeres Modell des Attraktor-Routings ein und beweisen eine untere Schranke für den worst case.  

Die Arbeit beschäftigt sich mit der Erstellung eines Parsergenerators für allgemeine kontextfreie Grammatiken unter Verwendung des GLL-Algorithmus, welcher mit ambigen Grammatiken in O(n^3) umzugehen weiß. Sein Einsatz bietet sich unter anderem in der Computerlinguistik, dem Software Reengineering und in Compilern an. Die Laufzeit wird durch die Verwendung von als Graphen strukturierten Stacks (GSS) sowie einem Shared Packed Parse Forest (SPPF) erreicht, der mehrerer valide Ableitungen zusammenfasst. Zunächst wird auf den Algorithmus, danach auf den Generator und die Parser eingegangen. Der Generator abstrahiert die Grammatiken in einem Modell, analysiert dieses und erzeugt daraus einen Parser, der sich an die asymptotische Laufzeit des Algorithmus hält. Damit die Parser ambige Grammatiken schneller ableiten können, wird der Algorithmus um eine Parallelisierung erweitert. Abschließend wird beleuchtet, wie der Parsergenerator in Zukunft ausgebaut werden kann. Bedeutend ist sowohl der weitere Umgang mit den SPPFs als auch die Verbesserung des GSS.

In der Arbeit haben wir zwei Varianten zur Verallgemeinerung der aus der Kombinatorik bekannten Catalan-Zahlen diskutiert. Zum einen ging es um die von Manuel Wettstein in seinem Artikel „Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers“ vorgeschlagene Variante, die Catalan-Zahlen als Anzahl balancierter Klammerausdrücke (BKA) zu definieren. Diese hat sich mathematisch als besonders fruchtbar herausgestellt. Das liegt vor allem daran, dass es möglich ist, für die d-dimensionalen Catalan-Zahlen eine geschlossene Formel anzugeben. Für einige Objektklassen haben wir gezeigt, dass sie sich in das Konzept der d-dimensionalen Catalan-Zahlen im Sinne von Wettstein einbetten lassen: bei den Standard-Young-Tableaus benötigten wir dazu noch die schwer zu beweisende Hook-Length-Formel als zusätzliches Hilfsmittel, bei den Gitterwegen und Dyck-Pfaden ergaben sich im d-dimensionalen natürliche Bijektionen.

Andere schon lange bekannte Interpretationen der Catalan-Zahlen passen jedoch nicht dazu. Die Catalan-Zahlen zählen die binären Bäume, jedoch weiß man, dass die Anzahl echter d-närer Bäume nicht den d-dimensionalen Catalan-Zahlen entspricht. Auch die Triangulation von konvexen Polygonen lässt sich nicht so auf höhere Dimensionen verallgemeinern, dass wir wieder die Catalan-Zahlen erhalten.

Wir haben trotzdem eine überraschende Erkenntnis über den Zusammenhang zwischen d-nären Bäumen und den primen BKA, die Wettstein eingeführt hat, gefunden. Nachdem wir nämlich eine Primzerlegung von BKA eingeführt haben und einfache BKA definiert haben, ergab sich die zentrale Erkenntnis, dass es eine Bijektion zwischen der Menge der echten d-nären Bäume und der Menge der einfachen BKA gibt. Außerdem haben wir Bijektionen zwischen zwei Mengen von geschlossenen Dyck-Pfaden und der Menge der primen BKA gefunden.

Wir beschäftigen uns mit geraden Triangulierungen von 3-zusammenhängenden planaren Graphen. Dabei heißt eine Triangulierung gerade, falls sie ausschließlich gerade Knotengrade hat. Wir untersuchen zunächst 3-zusammenhängende bipartite planare Graphen und übertragen dann die gewonnenen Erkenntnisse auf sogenannte Mosaike, also 3-zusammenhängende planare Graphen, deren Facetten Dreiecke oder Vierecke sind und auch auf verallgemeinerte Mosaike. Wir geben für jede betrachtete Klasse von Graphen Kriterien an, in wie fern für diese Klasse eine gerade Triangulierung existiert und wie diese gegebenenfalls konstruiert werden kann.

Sortieren ist ein fundamentales algorithmisches Problem mit vielfältigen Anwendungsmöglichkeiten. Für die Laufzeit von vergleichsbasiertem Sortieren ist eine untere Schranke von Omega(n log n) bekannt, für das Sortieren von ganzen Zahlen (integer sorting) gilt diese Schranke allerdings nicht. Für die Word-RAM, eine Variante der RAM, die zwar Operationen im Einheitskostenmaß misst, aber eine abhängig von der Anzahl und Größe der Eingabezahlen beschränkte Registergröße hat, existieren Algorithmen, die Zahlen beliebiger Größe in o(n log n) Zeit sortieren können. In dieser Arbeit soll der Algorithmus von Han und Thorup mit einer Laufzeit von O(n sqrt(log log n)) vorgestellt werden. Dabei wird sich auf das folgende Hauptergebnis beschränkt: ein Algorithmus zum Partitionieren von n Zahlen in eine Folge von Teilmengen, sodass alle Elemente einer Teilmenge kleiner als die der folgenden Teilmenge sind und jede Teilmenge höchstens sqrt(n) Zahlen oder nur gleiche Zahlen enthält.

The complexity classes P and NP are well known. However we are often interested in the actual globally optimal solutions of some NP decision problems. Local search is an attempt to approximate a hard to find global optimum with a local optimum. The complexity class Polynomial Local Search (PLS) was introduced to analyze the complexity of local search algorithms, where it is verifiable in polynomial time, whether a solution is a local optimum or not. One can PLS-reduce local search problems to one another and establish PLS-completeness. This work presents the basic definitions of the class PLS, its relation to other complexity classes, PLS-reductions, PLS-completeness, as well as a list of PLS-complete problems. The aim is to give a general overview of this topic and make further proofs for PLS-completeness and further investigations of the characteristics of the class PLS easier.

During this thesis a new routing scheme for Unit Disk Graphs described first in Kaplan et al. (2016) was implemented in Python and tested for performance. In addition, dynamic visualisation of the routing process was implemented through Mathplotlib allowing visual inspection of the routing process.
Although experiments show the routing scheme working as intended,  its routing tables scale unfavourably for most graphs that can be feasibly computed in 2016. It is also shown that for the class of random graphs presented in this thesis, routing results are much better than to be expected from the theoretical worst case considerations in the original paper. Finally, this thesis shows that the results given in the original paper can be improved considerably for smaller graphs if 'one-sided' well separated pair decompositions are used as the basis of the global routing tables.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs.
In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico,
April 11-15, 2016, Proceedings, pages 536–548, 2016.

Regular expressions, or regexes for short, are a pattern matching standard for string parsing and replacement. They are widely used computational primitive employed in many programming languages and text processing utilities such as JavaScript, Perl, Python, Ruby, Google RE2. They are also used in computer networks, databases and data mining, computational biology etc. A regular expression consists of symbols from some alphabet ∑ and a set of operators O. We will start by introducing various operators and explain their usage, giving us the basics with the help of which we will be able to construct different types of regular expressions. Then we will show the Thompson transformation, which converts an arbitrary regular expression into an equivalent nondeterministic finite automata, thus providing us with algorithm that solves the regular expression matching problem for the general case in the “rectangular” O(mn) time. Later there were improvements to this method that led to an algorithm that is the fastest for this problem known to date. However there are some specific types of regular expressions, for which faster matching algorithms exist. We will introduce some examples, which are reason to be considered that faster algorithm for the general case might exist. Finally we will classify the regular expressions based on their depth and the used set of operators and present the respective results.

The compressed data container format ZPAQ embeds decompression algorithms as ZPAQL bytecode in the archive. This work contributes a Python-subset compiler written in Rust for the assembly language ZPAQL, discusses design decisions and improvements. On the way it explains ZPAQ and some theoretical and practical properties of context mixing compression by the example of compressing digits of π. As use cases for the compiler it shows a lossless compression algorithm for PNM image data, a LZ77 variant ported to Python from ZPAQL to measure compiler overhead and as most complex case a implementation of the Brotli algorithm. It aims to make the development of algorithms for ZPAQ more accessible and leverage the discussion whether the current specification limits the suitability of ZPAQ as an universal standard for compressed archives.

Diese Bachelorarbeit nimmt sich der Problematik an die geometrischen Eigenschaften von Gebäuden zu vereinfachen. Die Ergebnisse der Vereinfachungen werden durch eine Simulation der auftretenden Sonnenenergie evaluiert. Dazu wurde ein Tool geschrieben mit welchem sich die Vereinfachungen und Simulationen durchführen lassen und welches erlaubt eine Visualisierung der Simulation und Gebäude-Vereinfachungen in OpenGL durchzuführen.

Leiterplatten sind heutzutage essenzieller Bestandteil vieler Wirschafts- und Konsumgüter. Ist eine Leiterplatte defekt, beeinträchtigt dies meist das ganze Produkt oder macht es komplett unbrauchbar.

Für die Reparatur und Nachfertigung solcher defekten Leiterplatten werden Schalt- und Layoutpläne benötigt. Sind diese Pläne nicht verfügbar, müssen sie nachträglich abgeleitet werden.

Am Fraunhofer-Institut für Produktionsanlagen und Konstruktionstechnik wurden in dem Forschungsprojekt INPIKO mehrere automatisierte Verfahren vorgestellt und prototypisch implementiert, um besagte Pläne zu rekonstruieren.

Im Rahmen dieser Arbeit wurde eine neue Softwarelösung konzipiert und implementiert, die die Rekonstruktion solcher Plänen anhand eines Computertomographiescans einer Leiterplatte ermöglicht. Die in dem Forschungsprojekt entstandenen Verfahren wurden in die neue Softwarelösung integriert und erweitert. Durch die Kombination von manuellen und automatisierten Rekonsturktionsverfahren entsteht schließlich ein teilautomatisierter Rekonstruktionsprozess zur Ableitung der Pläne.

Graphen werden häufig genutzt, um Beziehungen zwischen Objekten zu modellieren. Ein bekanntes Beispiel ist das von Milgram beschriebene Kleine-Welt-Phänomen. Dabei geht es unter anderem um die Frage, ob sich zwei zufällig ausgewählte Personen (über weitere Personen) kennen. Im Modell werden Personen als Knoten und Bekanntschaften als Kanten des Graphen dargestellt. Eine Bekanntschaft zwischen zwei Personen besteht, wenn sich die entsprechenden Knoten in der gleichen Zusammenhangskomponente befinden.

Mit wachsender Komplexität der Modelle und häufigeren Änderungen am Graphen rückten dynamische Datenstrukturen vermehrt in den Fokus. Wenn diese Datenstrukturen zusätzlich Zusammenhangsanfragen schnell beantworten können, unterstützen sie den so genannten dynamischen Zusammenhang (dynamic connectivity).

In dieser Arbeit werden zwei Datenstrukturen für den dynamischen Zusammenhang vorgestellt und implementiert. Eine unterstützt allgemeine Graphen, die andere Unit Disk Graphen. Die Laufzeiten beider Datenstrukturen betragen für eine Graphveränderung amortisiert O(log 2 n) und für eine Zusammenhangsanfrage amortisiert O(log n). Für die Auswertung werden beide Datenstrukturen mit simulierten Daten getestet und mit naiven Ansätzen verglichen. Zur Anschauung und zum besseren Verständnis wurden Visualisierungen für Unit Disk Graphen und für die untere Kontur (lower envelope) entwickelt und implementiert.

Ich habe mich mit der Approximation einer minimalen rechteckigen Packung für Kreise beliebiger Größe beschäftigt. 

Die Approximation basiert auf einen Algorithmus von Prof. Helmut Alt, Prof. Mark de Berg und Prof. Christian Knauer, welcher für die Approximation von rechteckigen minimalen Packungen konvexer Polygone entwickelt wurde. Das Ergebnis der Anwendung auf Kreise ist ein Approximationsfaktor von 9,049 in linearer Laufzeit. Der besagte Algorithmus kann auch für die Approximation einer konvexen Packung verwendet werden. Diese Möglichkeit wird für die Anwendung auf Kreisen untersucht.

IBM/MS/PC-DOS war weltweit auf Millionen von Computern für mehrere Jahrzehnte in Betrieb. Während dieser Zeit hat es die Benutzung von Computern durch Menschen stark beeinflusst, z.B. durch die 8+3 Namenskonvention für Dateinamen.
Mittlerweile wurde DOS größtenteils durch andere Betriebssysteme ersetzt. Sein Nachlass jedoch, darunter das Dateisystem FAT, ist noch sehr verbreitet. Es kann unter anderem in den Standards bekannter Hardware oder Software die viele Menschen täglich benutzen gefunden werden, z.B. SD-Karten, Smartphones oder Digitalkameras.
2014 hat das Computer History Museum (CHM) ein Archiv mit dem Quellcode der ersten beiden Versionen von DOS veröffentlicht.
Dies erlaubt es erstmals genau zu studieren, wie dieses einflussreiche Stück Software bestimmte Funktionalität umsetzt und warum es bestimmte Limitationen aufweist.

Diese Arbeit untersucht den Quellcode aus dem veröffentlichten Archiv, um zu diesem Ziel beizutragen. Es werden wenig bekannte Details zum Bootprozess des IBM PC und seiner Nachfolger, die bis zum heutigen Tag verkauft werden, präsentiert. Des weiteren werden beachtenswerte Merkmale der ersten FAT-Implementierung in DOS genauer untersucht. Die daraus gewonnenen Erkenntnisse werden hinsichtlich ihres Einflusses auf aktuelle Systeme evaluiert.

Um dies zu erreichen werden die Inhalte des vom CHM veröffentlichten Archivs zunächst in ihren Zusammenhang gesetzt was das Hardware- und das historische Umfeld angeht. Anschließend werden Auszüge des Quellcodes präsentiert und detailliert diskutiert, um dem Leser ein detaillierteres Verständnis der prägenden Konzepte von DOS zu ermöglichen.

Die Geschichte von DOS und die weite Verbreitung und Annahme seiner Konzepte dienen als erstklassiges Beispiel dafür, wie ein Prototyp, seine erwartete Lebensdauer um Jahrzehnte überschritten hat und dadurch die Nutzung von Computern durch Endanwender und Systemprogrammierer für Jahrzehnte geprägt hat.
Auch wenn DOS 1.x und 2.x tatsächlich eine sehr begrenzte Lebensdauer hatten, wurden die dort enthaltenen Konzepte und Design-Entscheidungen in ihren Nachfolgern übernommen ohne diese für das neue Einsatzgebiet erneut zu evaluieren.
Dadurch kam es zu einem de-facto Standard, der bestimmte Gebiete bis heute beeinflusst. 

Ein topologischer Graph ist die Projektion eines Graphen auf eine Oberfläche, so dass jeder Knoten auf einen eindeutigen Punkt und jede Kante auf eine einfache Kurve auf der Oberfläche abgebildet wird. Es wird ein Algorithmus gegeben, um für eine Menge von bis auf Homeomorphie der Kurven äquivalenten topologischen Graphen auf dem Zylinder die minimale Menge an erforderlichenSchnittpunkten zwischen den jeweiligen Kurven zu bestimmen.

„Divide-and-conquer“ erweist sich als effektive Methode algorithmische und
kombinatorische Probleme in der Informatik zu lösen. Die Idee hinter diesem
Ansatz ist es, das ursprüngliche Problem in einfachere Teilprobleme zu
zergliedern, welche, nachdem sie gelöst wurden, wieder zum Ausgangsproblem
zusammengesetzt werden. Um diesen Ansatz auf planare Graphen anwenden zu können,
werden planare Separatoren benötigt, die die Graphen in mehrere Komponenten
zerlegen. Ziel der vorliegenden Arbeit ist es, verschiedene Beweise für planare
Separatoren eingehender zu untersuchen und einen Überblick über die
verschiedenen Beweise zu geben. Zu diesem Zweck werden zunächst die wichtigsten
theoretischen Begriffe vorgestellt. Aufbauend auf den theoretischen Grundlagen
werden vier ausgewählte Beweise für planare Separatoren vorgestellt. Dabei
handelt es sich um die Beweise von Lipton und Tarjan, Goodrich, Gazit und Miller
sowie Spielman und Teng. Sie werden im Detail untersucht, um sie anhand der
hieraus gewonnenen Erkenntnisse zu vergleichen und in einer Rangliste zu
bewerten. Der Beweis von Spielman und Teng überzeugt durch die kurze Darstellung
und die Verknüpfung von Graphentheorie und Geometrie. Der grundlegende Beweis
von Lipton und Tarjan belegt den zweiten Platz, weil er am einfachsten
nachzuvollziehen ist. Der Ansatz von Goodrich folgt auf Platz drei, da die
zusätzlich benötigten Datenstrukturen den Beweis komplizierter gestalten. Die
Herangehensweise von Gazit und Miller belegt den letzten Platz durch ihre
hohe Komplexität. 

Die Klasse der Packungs- und Zuschnittsprobleme umfasst eine Vielzahl diverser
praktischer und theoretischer Problemstellungen, aus der in dieser Arbeit das
zweidimensionale nesting problem betrachtet wird. Das nesting problem ist ein
Optimierungsproblem, bei dem die Problemstellung darin besteht, die Anordnung
mehrerer geometrischer Objekte so zu optimieren, dass der Platz optimal ausgenutzt
wird.

Bei den zu packenden Objekten handelt es sich in dieser Arbeit um einfache und
lochfreie Polygone, d.h. Polygone, deren Kanten sich jeweils untereinander nicht
schneiden dürfen. Die Anordnung der Polygone wird dahingehend optimiert, dass die
Ausnutzung der Fläche der achsenparallelen Bounding Box maximiert bzw. der Verschnitt
in Bezug auf ebendiese minimiert wird.

Da es sich bei dem nesting problem um ein NP-schweres Optimierungsproblem handelt,
ist bis dato kein effizienter Algorithmus bekannt, der in der Lage ist, eine optimale
Lösung für das Problem zu erzeugen. Daher wird eine Lösung mittels Metaheuristiken
approximiert, bei denen es sich um problemunabhängige abstrakte Verfahren zur Erzeugung
von heuristischen Optimierungsalgorithmen handelt.

In der Arbeit werden die Metaheuristiken Simulated Annealing und genetische Algorithmen
verwendet. Es werden verschiedene Ansätze zur Anwendung der beiden Metaheuristiken auf das
nesting problem vorgestellt und implementiert. Anhand eines Schnittmusters für T-Shirts aus
der Praxis und weiteren Probleminstanzen, wie Legepuzzles, werden die Ansätze getestet und
die Ergebnisse ausgewertet.

Die erzielten Ergebnisse der verschiedenen Ansätze unterscheiden sich teilweise deutlich in
ihrer Qualität. Insgesamt werden mit den Ansätzen gute, allerdings entsprechend der
heuristischen Natur der Verfahren, nicht optimale Ergebnisse erzielt. 

In industriellen Betrieben muss die Verfügbarkeit von kostenintensiven Maschinen und Anlagen über 30 bis 50 Jahre sichergestellt werden. Viele Unternehmen setzen daher zunehmend 3D-Scanning-Verfahren zur Inspektion und Instandhaltungsplanung (Reverse Engineering, RE)  ein. Problematisch hierbei ist der hohe manuelle Aufwand. Am Fraunhofer IPK im Bereich virtuelle Produktentstehung wird intensiv an einem automatisierten Prozessablauf geforscht. Dabei ist eine komplette Demontage der Baugruppe nicht mehr vorgesehen, wodurch Kosten und Zeit eingespart werden können. Diese Arbeit stellt ein grundlegendes Verfahren vor, dass eine automatisierte Rekonstruktion des Baugruppenmodells mit eingebauter Nutzerassistenz vorsieht. Dazu wurde ein Algorithmus für das Fitting von Einzelteilen in ein Gesamtobjekt unter der Verwendung der Open-Source-Bibliothek Point Cloud Library in C++ entwickelt. Ein weiterer Schwerpunkt bestand in der Programmierung der graphischen Benutzeroberfläche. Hierbei musste der Einbau einer manuellen Rotationsbedienung berücksichtigt werden, da eine automatisierte Rotation mittels algorithmischer Verfahren derzeit nicht möglich ist.  

Die Fréchet-Metrik ist ein weit verbreitetes und gut untersuchtes Maß zur Bestimmung der Ähnlichkeit zwischen Kurven. Es gibt mehrere Varianten dieser Metrik; der Schwerpunkt der Bachelorarbeit liegt auf der diskreten Fréchet-Metrik, welche die Eckpunkte von Polygonzügen betrachtet. Der initiale Algorithmus von Eiter und Mannila [1] hat eine Laufzeit von O(n^{^2}). Erst kürzlich konnten leicht subquadratische Algorithmen dafür gefunden werden. Jedoch hat Bringmann [2] gezeigt, dass es unmöglich ist, für das Problem eine Lösung mit stark subquadratischer Laufzeit O(n^(2-e)), für ein konstantes e > 0, zu finden. Daraufhin sind Bringmann und Mulzer [3] der Frage nachgegangen, wie gut sich die Fréchet-Metrik approximieren lässt und haben zwei Approximationsalgorithmen dazu vorgestellt: Einen gierigen Algorithmus mit linearer Laufzeit, der eine Approximationsschranke von 2^O(n) hat und einen allgemeinen alpha-approximativen Algorithmus, der O(n \log n + (n^{^2}) / alpha) Zeit benötigt, für jedes 1 <= alpha <= n. Im Rahmen der Bachelorarbeit wurden diese beiden Algorithmen und zwei Referenzalgorithmen implementiert und experimentell untersucht. Die Ergebnisse des gierigen Algorithmus sind weitaus besser, als es die Schranke von 2^O(n) vermuten lässt. Die Implementierung des alpha-Approximationsalgorithmus konnte in den Experimenten die gute theoretische Laufzeit jedoch nicht bestätigen. 

Ein planares Morphing ist eine stetige Transformation zwischen topologisch äquivalenten straight-line-Zeichnungen Z_s und Z_t desselben planaren Graphen G. Ein solches Morphing kann z.B durch eine Sequenz von linearen Morphingschritten angegeben werden, dabei bewegt sich jeder Knoten in jedem Schritt mit konstanter Geschwindigkeit auf einer Geraden und zu jedem Zeitpunkt liegt eine topologisch äquivalente Zeichnung vor. Die Komplexität des Morphings ist dabei die Länge dieser Sequenz, also die Anzahl der linearen Morphingschritte. In einer Arbeit aus dem Jahre 2014 haben Angelini et al. gezeigt, dass für einen gegebenen planaren Graphen G und topologisch äquivalenten straight-line-Zeichnungen Z_s und Z_t eine Morphingsequenz existiert, deren Länge in O(n) liegt, wobei n die Anzahl der Knoten des Graphen ist. Auf der anderen Seite existieren Zeichnungen ein und desselben planaren Graphen auf n Knoten, sodass jede lineare Morphingsequenz Ω(n) Schritte benötigt. Die Bachelorarbeit entwickelt zunächst die Grundlagen und präsentiert dann die wesentlichen Ideen der Arbeit.

Der eindimensionale Median ist einer der grundlegenden Bestandteile der Informatik und Mathematik. Die Idee des Medians kann auf höhere Dimensionen als Centerpoint verallgemeinert werden. Hierbei zerlegen alle Hyperebenen durch einen Centerpoint die Eingabe in zwei etwa gleich große Teile.

Der bisher schnellste Algorithmus um einen Centerpoint für n Punkte in d Dimensionen zu finden hat eine erwartete Laufzeit von O(n^(d - 1)). Durch die in d exponentielle Laufzeit ist dieser Algorithmus nur für kleinere Dimensionen sinnvoll anwendbar. Es ist kein Algorithmus bekannt um einen Centerpoint in polynomieller Laufzeit bezüglich sowohl n als auch beliebiger Dimension d zu finden. Aus diesem Grund sind vor allem approximative Algorithmen für dieses Themengebiet von großem Interesse.

In dieser Arbeit werden mehrere approximative Algorithmen für eine beliebige Anzahl an Dimensionen vorgestellt. Diese Algorithmen haben ein bezüglich Anzahl der Punkte n und der Dimension d polynomielles Laufzeitverhalten. Weiterhin wurden diese Algorithmen implementiert und deren durchschnittliche Güte bei zufälliger Eingabe ermittelt, da die Algorithmen nur eine untere Schranke der Güte des Ergebnisses garantieren.

Das 3SUM-Problem beschreibt das Ermitteln dreier Zahlen aus einer gegebenen Menge von n reellen Zahlen, die aufaddiert null ergeben. Bisher hat man noch keinen vergleichsbasierten Algorithmus für das 3SUM-Problem gefunden, der eine schnellere Laufzeit als n² hat. Diese Arbeit beschäftigt sich mit der genaueren Analyse des Artikels ”Threesomes, Degenerates and Love-Triangles” und vor allem mit dem Algorithmus zur Erstellung eines Entscheidungsbaums mit der subquadratischen Tiefe von O(n^(3/2)*(log n)^(3/2)). Dieser wird Schritt für Schritt in seinem Aufbau und Vorgehen erläutert. Es wird der wichtige Unterschied zwischen Entscheidungsbäumen und der Laufzeit von Algorithmen betrachtet.

Im zweiten Teil wird das 3SUM-schwere Problem "Ein Punkt auf drei Geraden" betrachtet. Es wird seine Komplexität untersucht und gezeigt, dass das 3SUM-Problem transformierbar zum "Ein Punkt auf drei Geraden"-Problem ist.

Sortieren ist eines der grundlegenden Probleme in der Informatik. Die Zeitkomplexität für vergleichsbasiertes Sortieren ist bekanntermaßen Theta(n log n). Wenn nun die Eingaben auf Integer beschränkt werden und eine RAM mit einer beschränkten und von der Eingabegröße abhängigen Wortlänge als Modell für die Komplexitätsanalyse gewählt wird, kann diese Schranke unterschritten werden. Die Beschränkung der Wortlänge ist notwendig um reale Einschränkungen abbilden zu können. Die Frage ob mit diesen Vorraussetzungen in linearer Zeit sortiert werden kann ist noch offen.
Der in der Arbeit vorgestellte Algorithmus von Han und Thorup kombiniert bekannte Algorithmen für die Sortierung von Integern mit einem neuen Algorithmus der eine Eingabemenge in kleinere Mengen auf denen eine gewisse Ordnung definiert ist aufteilt. Somit wird eine Komplexität von O(n sqrt(log log n)) für das randomisierte Sortieren beliebig langer Integer erreicht. 

In der Arbeit wird das Problem betrachtet, wie man ein einfaches orthogonales Polygon P mit einer endlichen Wächtermenge abdecken kann, bei der jeder Wächter eine von k Farben zugeordnet bekommt. Diese zugehörige Färbung der Wächter heißt konfliktfrei, falls jeder Punkt p in P wenigstens einen Wächter sieht, der einzigartig gefärbt ist unter allen Wächtern, die von p aus sichtbar sind. Für die Anzahl der benötigten Farben konnte eine O(loglog n)-Schranke, sowie eine Omega(loglog n/logloglog n)-Schranke nachgewiesen werden (wobei n die Anzahl der Eckpunkte von P ist). Dabei gingen wir von der r-Sichtbarkeit aus, d.h. dass sich zwei Punkte genau dann sehen, wenn ihr aufgespanntes achsenparalleles Rechteck innerhalb des Polygons liegt. Bei der starken Version unseres Färbungsproblems - das heißt alle Wächter, die von einem Punkt aus gesehen werden, müssen unterschiedliche Farben haben - konnte sogar eine Theta(log n)-Schranke nachgewiesen werden.

Die Schnittgraphen geometrischer Objekte sind ein interessanter Bestandteil der Graphentheorie, da sie eine Verbindung zur Geometrie schlagen und außerdem ein weitreichendes Feld an Anwendung, zum Beispiel in Genetik und Elektrotechnik, bieten.

Ein Schnittgraph (engl. intersection graph) ist ein Graph, der die Gestalt von Schnittpunkten einer Familie von Mengen darstellt. Wir betrachten Familien geometrischer Objekte in der Ebene und ordnen jeder Menge, das heißt jedem Objekt, einen Knoten zu und beschreiben eine Kante genau dann, wenn sich die betreffenden geometrischen Objekte berühren oder überlagern. Daher kann man Schnitt- graphen in das Feld der geometrischen Graphentheorie einordnen.

Wenn man beliebige Mengen zulässt, kann jeder Graph als Schnittgraph dargestellt werden. Betrachtet man jedoch Mengen bestimmter Kategorien, gibt es zu einigen Graphen keine Mengenfamilie in dieser Kategorie, welche den Graphen als Schnittgraphen hervorbringen. Diese Graphen müssen somit bezüglich dieser Kategorie bestimmte Eigenschaften erfüllen. Wir betrachten in dieser Arbeit Mengen von Intervallen, Kurven, Strecken und Kreisscheiben als geometrische Objekte.

Wir befassen uns in dieser Arbeit besonders mit den folgenden Fragestellungen bezüglich unseren geometrischen Objekten:

Wann ist ein gegebener Graph ein Schnittgraph beziehungsweise wie ist er charakterisiert?

Ist ein Graph ein Schnittgraph einer Art von geometrischen Objekten? Können wir einen Algorithmus angeben, um die Realisierung zu einem Schnittgraphen zu geben? Welche Laufzeit hat dieser?

Welche besonderen Eigenschaften haben die Schnittgraphen zu den gegebenen Objekten?

In dieser Arbeit wird das Problem untersucht, ob ein Polygon in ein anderes hineinpasst, bzw. ein Polyeder in einen anderen Polyeder. Das Ziel ist dieses “Containment Problem” mit linearer Programmierung zu lösen. Dabei werden verschiedene Varianten des Problems betrachtet und Lösungen vorgestellt. Zu Beginn ist nur eine Translation erlaubt, um das eine Objekt in das andere hinein zu verschieben. Später kann dafür zusätzlich zur Translation auch eine Rotation verwendet werden. Um den Drehwinkel der Rotation mit linearer Programmierung zu betrachten werden zwei Lösungsansätze untersucht. Als erster Ansatz wird eine bestimmte Anzahl von Winkeln diskretisiert. Für zwei Dimensionen wird zusätzlich der zweite Lösungsansatz verwendet, bei dem eine Bedingung für den Drehwinkel linearisiert wird.

Ein weiterer wesentlicher Bestandteil dieser Arbeit war die Implementierung der herausgearbeiteten Algorithmen. Bedienung und Funktionsweise des geschaffenen Programmes werden als Teil der Arbeit erläutert.

Most interesting discrete optimization problems are NP-hard and thus the
existence of algorithms that find optimal solutions efficiently is very
unlikely for these problems. One approach to encounter this is to design
efficient algorithms that find approximate solutions. In this thesis two NP-
hard interval scheduling problems are studied. In both the goal is to schedule
a set of intervals on given machines such that intervals scheduled on the same
machine do not overlap. Additionally, the machines have a capacity constraint
in one of the variants, while in the other one an interval can be restricted
to a subset of the machines. They fall into a class of problems called
separable assignment problems, for which a framework to obtain approximation
algorithms, whose guarantees depend on the problem for a single machine,
exists.
On the basis of this framework I will describe a local search approximation
algorithm and one using linear programming with randomized rounding for both
problems.      

Given k planar graphs on a shared vertex set V , simultaneous geometric embedding (SGE) is the problem of finding an embedding of V into the plane such that none of the k graphs intersects itself when edges are drawn as straight line segments. Several positive results, i.e., graphs that always admit an SGE, as well as negative results are known today.

In this thesis, we analyse the size of drawings obtained by two algorithms from Cabello et al. [1]. The first creates an SGE for a wheel and a cycle. We show that an O(n^2) x O(n^2) integer grid suffices to support the resulting drawing. The second creates an SGE for a tree and a matching.

Here, we show that there exist graphs such that a grid with more than singly exponential size is needed if one uses the original algorithm. Afterwards an improvement is suggested so that singly exponential size suffices. Furthermore, we prove that a wheel and the union of two matchings always admit an SGE. In contrast to that, we give two wheels on the same six vertices such that each planar embedding of one forces the other into intersecting itself.

Graphen, die sich in die Ebene zeichnen lassen, ohne dass sich ihre Kanten schneiden, heißen planare Graphen. Sie spielen in der Informatik eine wichtige Rolle: einige algorithmische Probleme lassen sich auf planaren Graphen effizienter als auf allgemeinen lösen, wie zum Beispiel dem Finden von kürzesten Wegen oder dem Bestimmen von maximalen Flüssen. Es gibt eine Vielzahl von Algorithmen, die in linearer Zeit entscheiden, ob ein Graph planar ist und gegebenenfalls eine Einbettung in die Ebene finden. Ein grundlegender Meilenstein hierfür war der Algorithmus von Booth und Lueker, der auf einer neuen Datenstruktur namens PQ-Bäumen basiert. Es wurden immer einfachere Algorithmen vorgestellt, die einen anderen Ansatz verfolgten oder die Datenstruktur modifizierten. Diese Arbeit stellt neben den PQ-Bäumen zwei dieser Algorithmen vor: den Algorithmus von Booth und Lueker (1976), sowie einen neuen, einfacheren Algorithmus von Häupler und Tarjan (2008), der PQ-Bäume auf eine andere Weise benutzt.

In den vergangenen Jahren wurden zahlreiche Heapalgorithm vorgestellt, welche unterschiedliche Eigenschaften in Sachen Struktur und Performance für ein breites Spektrum von Anwendungen besitzen. Sie werden vor allem für die Realisierung von Priority-Queues, Clustering- oder Graphalgorithmen eingesetzt. Ersteres werden häufig von Schedulern in Servern oder Betriebssystemen verwendet. 2009 stellte [5] die Theorie zu Quake-Heap, einer effizienten Alternative zum vielfach implementierten und untersuchten Fibonacci-Heap, vor. Dieser Algorithmus, so die Behauptung des Autors, soll vor allem durch seine Einfachheit einen pädagogischen mehrwert liefern.

In dieser Arbeit wurde der Quake Heap erstmals implementiert und in zweierlei Hinsicht untersucht. Laufzeitmessungen des Dijkstra Algorithmus auf randomisierten Graphen haben ergeben, dass der Quake-Heap auf der Grundlage mehrerer Messreihen durchschnittlich bessere Werte liefert als der Fibonacci-Heap, was eine praktische Rechtfertigung dieser Datenstruktur liefert. Ebenfalls ließ sich die Datenstruktur
des Quake-Heaps auf Grund der Vermeidung von doppelt verketteten, zyklischen Listen wie sie im Fibonacci-Heap verwendet werden, einfacher implementieren, was für einen höheren pädagogischen Mehrwert spricht.

Im Rahmen der Bachelorarbeit wurde die statistische Verteilung der Knotengrade bei zufälligen Triangulierungen untersucht. Als Triangulationsverfahren werden neben einem universellen Greedy-Verfahren auch die Delaunay-Triangulierung und das zufällige Kantenkippen auf einer beliebigen Triangulierung einer gegebenen Knotenmenge V verwendet. Das hierzu entwickelte Java-Werkzeug wird ebenfalls vorgestellt. 

In der von mir vorgestellten Arbeit werden B- -Bäume theoretisch untersucht. B- -Bäume sind B+ -Bäume mit dahingehend vereinfachter Löschoperation, dass unterbesetzte Knoten zugelassen sind. Dadurch können die Bäume aber entarten, das heißt sie sind nicht mehr balanciert und ihre Höhe ist nicht mehr logarithmisch in der Anzahl der gespeicherten Elemente.

Um trotzdem die von B+ -Bäumen gewohnten Schranken in Bezug auf Platzverbrauch und Höhe zu garantieren, müssen die Bäume regelmäßig neu gebaut werden. Im wesentlichen basiert diese Arbeit auf den Ergebnissen von Sen und Tarjan in "Deletion Without Rebalancing in Multiway Search Trees".

Kuckucks-Hashing ist ein Hashverfahren, das einen amortisiert konstanten erwarteten Zeitaufwand für Einfügeoperationen und einen garantiert konstanten Zeitaufwand für Such- und Löschoperationen anbietet. Der Speicherplatzbedarf für eine Schlüsselmenge der Größe n ist dabei 2(1+ε)n für ein ε > 0. Die wesentliche Schwäche des Verfahrens ist, dass das Einfügen der Schlüsselmenge mit Wahrscheinlichkeit O(1/n) scheitert; es müssen neue Hashfunktionen gewählt und alle Schlüssel neu eingefügt werden.

Im ersten Teil unserer Arbeit stellen wir einen Kodierungsbeweis zur Laufzeit der Einfügeoperation und zur Wahrscheinlichkeit des Scheiterns vor, der zuerst von Mihai Pătraşcu skizziert wurde. Wir verallgemeinern den Beweis, so dass er für beliebige ε > 0, statt nur für ε = 1, funktioniert. 

Im zweiten Teil führen wir Experimente durch, die einerseits die theoretischen Ergebnisse aus dem ersten Teil bestätigen und andererseits zeigen, dass es effiziente Hashfunktionen gibt, die beim Kuckucks-Hashing vergleichbare Eigenschaften aufweisen wie zufällige Funktionen; die Anzahl der Schritte beim Einfügen und die Wahrscheinlichkeit des Scheiterns steigen nur geringfügig.

In der vorliegenden Arbeit werden Algorithmen zum effizienten Packen und Stapeln von geometrischen Objekten untersucht und entwickelt. Beim Packen von Objekten soll eine möglichst kompakte Anordnung gefunden werden, sodass alle Objekte disjunkt sind. Im Gegensatz dazu dürfen die Objekte beim Stapeln auch ineinander platziert werden.

Der Schwerpunkt der Arbeit basiert auf den aktuellen Ergebnissen von Arkin et al. für das Stapeln einer Menge von konvexen Polygonen. Sie haben gezeigt, wie die Polygone in polynomieller Zeit so angeordnet werden können, dass der Umfang der konvexen Hülle eine (1+ epsilon)–Approximation bezüglich der konvexen Hülle einer optimalen Anordnung ist.

Darauf aufbauend konnte ein Verfahren für das effiziente Stapeln von dreidimensionalen Polytopen zur Optimierung des Durchmessers der konvexen Hülle entwickelt werden.

Der Schönhage-Strassen-Algorithmus ist ein 1971 vorgestellter schneller Algorithmus zur Multiplikation von großen natürlichen Zahlen. Es wird zunächst die Funktionsweise des Algorithmus und anschließend eine Implementierung des Algorithmus in C vorgestellt. Weiterhin wird die Möglichkeit aufgezeigt, den Algorithmus durch massiv parallele Ausführung einiger Teilabschnitte zu beschleunigen. Die parallelen Berechnungen werden auf die Grafikkarte ausgelagert und erfolgen mit Hilfe der NVIDIA-Architektur CUDA. Durch Einsatz von Laufzeittests und Profiling-Tools werden abschließend die Ergebnisse evaluiert.