05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

Settings

End date: 2022Subject: search.filters.subject.004Institute: search.filters.UBSInstitut.Institut für Formale Methoden der Informatik

Search Results

Now showing 1 - 10 of 184
  • Thumbnail Image
    ItemOpen Access
    Average case considerations for Mergelnsertion
    (2018) Stober, Florian
    The MergeInsertion Algorithm, also known as Ford-Johnson Algorithm, is a sorting algorithm that was discovered by Ford and Johnson in 1959. It was later described by Knuth as MergeInsertion. The algorithm can be divided into three steps: First pairs of elements are compared. Then the larger half is sorted using MergeInsertion. And last the remaining elements are inserted. The most interesting property of this algorithm is the number of comparisons it requires, which is close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average-case. This thesis takes a closer look at the average case behavior. An upper bound of n log n − 1.4005n + o(n) is established. For small n the exact values are calculated. Furthermore the impact of different approaches to binary insertion on the number of comparisons is explored. To conclude we perform some experiments to evaluate different approaches on improving MergeInsertion.
  • Thumbnail Image
    ItemOpen Access
    Experimental analysis of randomized calculations of average rankings
    (2016) Zeiß, Tim
    Listing a set of points, such that a point gets a higher rank, if none of its coordinates is smaller, creates a partial order. It is possible to get a ranking without randomly favoring certain points, by averaging all valid rankings. However, this brute force algorithm is too slow for more than ten points. To handle more points, we will give a randomized, approximative approach to solve this problem and analyze the convergence rates of different strategies.
  • Thumbnail Image
    ItemOpen Access
    Contraction Hierarchies für kontinuierliche Graphsimplifizierung mit Qualitätsgarantien
    (2016) Rupp, Tobias
    Moderne Navigationsdienste können kürzeste Pfade berechnen und diese dann auf Straßenkarten anzeigen. Als zugrunde liegende Datenstruktur für beide Aufgaben kann eine Contraction Hierarchy verwendet werden. Ursprünglich waren Contraction Hierarchies dazu konzipiert, die Suche nach kürzesten Pfaden zu beschleunigen. In dieser Arbeit wurde untersucht, wie sich Contraction Hierarchies aufbauen lassen, sodass sie sich besser für kontinuierlich vereinfachte Darstellungen eignen. Dazu sollten vor allem die groben Straßenverläufe erhalten bleiben und topologische Inkonsistenzen wie Überschneidungen vermieden werden. Diese Anforderungen wurden formalisiert und in heuristischen Vereinfachungsalgorithmen zum Aufbau von Contraction Hierarchies umgesetzt. Für kleine Eingaben wurden mithilfe ganzzahliger linearer Programme garantiert optimale Lösungen berechnet. Damit konnten in empirischen Vergleichen auf dem Deutschlandgraphen Qualitätsgewinne nahe dem Optimum für vereinfachte Darstellungen von Contraction Hierarchies nachgewiesen werden. Außerdem mussten keine längeren Berechnungszeiten für kürzeste Pfade hingenommen werden.
  • Thumbnail Image
    ItemOpen Access
    Improved approximation schemes for the restricted shortest path problem
    (2016) Holzmüller, David
    In this thesis we present several variants of an approximation scheme for the restricted shortest path problem. This problem concerns finding a shortest path with respect to one criterion while not exceeding a length bound with respect to another criterion. After formally introducing the problem, we describe the approximation scheme by Lorenz and Raz. Our algorithm then introduces additional steps to reduce the runtime complexity from O(|E|n(1/epsilon + log log n)) to O(|E|n(1/epsilon + \log \log \log n)). A variant of this algorithm yields a complexity of O(|E|n(1/epsilon + (n log n) / m)), which is a further improvement for sufficiently dense graphs. Furthermore, a slight modification leads to an O(|E|n(1/epsilon + 1))-algorithm for directed acyclic graphs, providing an arguably easier algorithm than the algorithm proposed by Ergun et al.
  • Thumbnail Image
    ItemOpen Access
    OSM ticket to ride
    (2022) Friedsam, Wenzel
    Board games such as Ticket to Ride by Days of Wonder use game boards which are based on real geographic data. In this particular example the game map is an abstract railway graph consisting of a set of train stations, that are connected by train routes. Generating such maps by hand is a long and time consuming process. Therefore we present an algorithm that can generate playable maps for the game Ticket to Ride for different countries and continents. The result of this work is an application which is able to automatically create a game graph using OpenStreetMap data as input. We try to keep the generated graph as similar as possible to the original game in terms of important metrics that affect the gameplay, while trying to keep the result close to the geographic data during the abstraction process. The result is exported into a format that can be imported by an open source web version of Ticket to Ride, which allows players to play on the generated map.
  • Thumbnail Image
    ItemOpen Access
    Deriving bisimulation congruences in the DPO approach to graph rewriting. Long version
    (2004) Ehrig, Hartmut; König, Barbara
    Motivated by recent work on the derivation of labelled transitions and bisimulation congruences from unlabelled reaction rules, we show how to solve this problem in the DPO (double-pushout) approach to graph rewriting. Unlike in previous approaches, we consider graphs as objects, instead of arrows, of the category under consideration. This allows us to present a very simple way of deriving labelled transitions (called rewriting steps with borrowed context) which smoothly integrates with the DPO approach, has a very constructive natureand requires only a minimum of category theory. The core part of this paper is the proof sketch that the bisimilarity based on rewriting with borrowed contexts is a congruence relation.
  • Thumbnail Image
    ItemOpen Access
    Automatic synthesis of distributed transition systems
    (2006) Stefanescu, Alin; Esparza, Javier (Prof. Dr.)
    This thesis investigates the synthesis problem for two classes of distributed transition systems: synchronous products and asynchronous automata. The underlying structure of these models consist of local automata synchronizing on common actions. The synthesis problem discussed is as follows: Given a global specification as a transition system TS and a distribution pattern D, find a distributed transition system over D whose global state space is equivalent' to TS. As criteria for the correctness of the (distributed) implementation vs. the specification (i.e., their equivalence') we use: transition system isomorphism, language equivalence, and bisimilarity respectively. In particular, the synthesis of asynchronous automata modulo language equivalence is a notoriously hard problem solved by Zielonka at the end of the 80s. One of the motivations behind our work was to bring this theory closer to practical applications. From the theoretical point of view, we conduct a detailed analysis of the synthesis problem for both models of distributed systems, look at effective algorithmic approaches and draw a map of computational complexity results. E.g., we provide several matching lower and upper complexity bounds for the distributed implementability problem. From the practical perspective, we provide prototype implementations for most of the synthesis algorithms discussed in the thesis. Moreover, we offer assistance when a given specification is not distributable by trying to modify this specification such that distributed synthesis can be applied. By using several heuristics to overcome the classical state space explosion, we are able to automatically generate small distributed algorithms for problems such as mutual exclusion.
  • Thumbnail Image
    ItemOpen Access
    Deterministische endliche Automaten und Zwei-Variablen-Logik erster Stufe
    (2013) Müller, Sebastian
    Therien und Wilke zeigten in einer Arbeit von 1998, dass 2-Variablen-Logik erster Stufe (FO^2) einer entscheidbaren Klasse endlicher Monoide entspricht. Damit läßt sich insbesondere für jede reguläre Sprache entscheiden, ob sie in FO^2 definierbar ist. Dieses Entscheidbarkeitsresultat konnte 2012 in einer Arbeit von Weil und Kufleitner auf die Alternierungshierarchie innerhalb von FO^2 ausgedehnt werden. Im Rahmen dieser Arbeit wird untersucht, wie effizient sich diese Entscheidbarkeitsresultate umsetzen lassen, wenn die reguläre Sprache durch deterministische endliche Automaten gegeben ist. Als Vorstufe hierzu werden geeignete algebraische Charakterisierungen der Alternierungshierarchie innerhalb von FO^2 recherchiert. Basierend darauf werden Entscheidungsverfahren auf Basis sogenannter Verbotsmuster entwickelt.
  • Thumbnail Image
    ItemOpen Access
    Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken
    (2022) Berner, Lukas
    Für die Suche nach kürzesten Pfaden in sehr großen Graphen wurden verschiedene Beschleunigungstechniken, wie z.B. Contraction Hierarchies, Hub-Labels oder Transit Node Routing, entwickelt. Um optimale Anfragezeiten und Speicherverbrauch zu erreichen, benötigen viele Beschleunigungstechniken eine Menge wichtiger Knoten. In dieser Arbeit wird eine Methode zur Berechnung wichtiger Knoten eines Graphen vorgestellt. Um diese Knoten zu finden, wird auf einer repräsentativen Pfadmenge ein Hitting Set Problem mit einem Greedy-Algorithmus gelöst. Die repräsentative Pfadmenge, die möglichst unterschiedliche kürzeste Pfade des Graphen enthalten soll, wird mit einer well-separated pair decomposition und einem Quadtree berechnet. Das Verfahren wurde mit dem deutschen Straßennetzwerk (25M Knoten) getestet und liefert hier einige tausend wichtige Knoten, mit denen bereits etwa 99,9 % aller kürzesten Pfade im Graph abgedeckt sind.
  • Thumbnail Image
    ItemOpen Access
    Neue Bedienkonzepte für mobile Routenplaner
    (2014) Bahle, Stefanie
    Bei Routenplanern werden Start und Ziel typischerweise über eine Display-Tastatur eingegeben, was insbesondere bei Smartphones mit kleinem Display mühsam sein kann. Vor allem unter erschwerten Bedingungen, wie während der Fahrt auf dem Fahrrad oder mit Handschuhen, ist eine Eingabe über die Display-Tastatur kaum möglich. Aus diesem Grund wurden in dieser Arbeit Bedienmethoden entwickelt, welche die Bedienung unter erschwerten Bedingungen erleichtern sollen. Die Ansätze sind verschiedene Suchen mit zwei, drei oder vier Buttons zur Auswahl des Zielortes sowie eine Methode die die Lautstärketasten des Smartphones nutzt. Hierbei muss der gesuchte Ort alphabetisch eingeordnet werden und der entsprechende Button ausgewählt. Diese Bedienmethoden wurden in einer Benutzerstudie mit bekannten Eingabemethoden verglichen um festzustellen, ob die neuen Methoden eine bessere Alternative darstellen. Dies konnte zwar nicht bestätigt werden, dennoch sollte ein Weiterverfolgen der zugrunde liegenden Idee nicht ausgeschlossen werden.