05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
208 results
Search Results
Item Open Access Performance measurements for personalizable route planning for uncorrelated edge costs(2021) Bühler, FelixNowadays, ordinary route planners compute paths by choosing the shortest or fastest route. However, there exist additional metrics from which users with varying preferences could benefit. Personalized route planning offers the possibility to combine different metrics with personal preferences. Nevertheless, personalized route planning has mainly been tested with correlated metrics. But when including uncorrelated metrics, the computing time increases significantly. Previous work found that the speedup technique “Customizable Route Planning” can lead to feasible speedups for single metric calculations. Thus, in this work, we investigate how this speedup technique for Dijkstra improves the query performances of “Personalizable Route Planning” compared to “Personalizable Contraction Hierarchies”. Furthermore, we study the performances on uncorrelated metrics. We introduce a graph structure to compare the personalized speedup techniques “Personalizable Contraction Hierarchies”, “Personalizable Customizable Route Planning” and “Personalizable Route Planning”. Three graph partitioning algorithms have been implemented to realize “Customizable Route Planning”: K-means, Gonzales, and Merge. Our experiments show that Merge works well in combination with “Personalizable Contraction Hierarchies” preprocessing. We found that “Personalizable Customizable Route Planning” is a good alternative, as it uses much fewer edges for finding the costs of the shortest path. For uncorrelated metrics, “Personalizable Customizable Route Planning” and “Personalizable Route Planning” achieved speedups higher than “Personalizable Contraction Hierarchies”. Our contribution comprises a novel graph structure for comparing different Dijkstra variants. With our experiments, we provide a deeper understanding of the personalized route planning problem. Additionally, we propose improvements for “Personalizable Contraction Hierarchies” for less contracted graphs with uncorrelated metrics.Item Open Access Das Ordnungsproblem für Automatengruppen und verwandte Fragestellungen(2019) Bühler, AndreasIn dieser Arbeit werden Problemstellungen in der Klasse der Automatenhalbgruppen untersucht. Ein besonderer Augenmerk gilt dabei dem Ordnungsproblem welches im Allgemeinen sowohl für Automatenhalbgruppen als auch für Automatengruppen unentscheidbar ist. Es wird dann für die Klasse der Automatenhalbgruppen mit beschränkter Aktivität ein Algorithmus mit überraschend geringem Platzbedarf vorgestellt. Danach wird ein Entscheidungsalgorithmus für das Mitgliedschaftsproblem in ultimativ periodischen Teilmengen von Automatenhalbgruppen beschränkter Aktivität erarbeitet. Dieses Problem beinhaltet insbesondere das Mitgliedschaftsproblem in monogenen Unterhalbgruppen, welches dadurch ebenfalls in Automatenhalbgruppen beschränkter Aktivität entscheidbar ist.Item Open Access Fully-polynomial-time approximation schemes for the Euclidean shortest path problem(2024) Schneewind, AxelThe shortest path problem is a well-studied problem in computer-science. For transport networks, there exist natural graph representations and highly efficient algorithms that can compute shortest paths on millions of nodes within milliseconds. In contrast, computing shortest paths in space (e.g. in R^2) poses some challenges. Shortest path computations in space have applications in robotics, naval routing or video games. As shortest paths in a continuum are hard to compute (with the Euclidean shortest-path problem in 3D even proven to be NP-hard), approximations can be necessary to obtain acceptable runtimes. In this thesis, an approximation scheme is studied that guarantees solutions with cost at most (1+ε) times the optimum. It uses a triangulation of the domain and, given ε, construct a discretization. By performing a Dijkstra search, one can then approximate shortest paths with the given quality guarantee. This scheme is implemented and its practicality evaluated on larger instances.Item Open Access Normalformenberechnung in Graph-Gruppen und Coxeter-Gruppen(2011) Kausch, JonathanIm Rahmen der Diplomarbeit wurde das Normalformenproblem für partiell kommutative Gruppen in logarithmischem Platz untersucht. Diese Gruppen sind in der Mathematik als Graph-Gruppen oder "rechtwinklige Artingruppen" bekannt und werden u.a. in der kombinatorischen Gruppentheorie untersucht. In der Informatik erscheinen sie als natürliche Erweiterung der Spurmonoide, die von Keller und Mazurkiewicz eingeführt wurden und insbesondere für die Untersuchung von Nebenläufigkeit in der Informatik von Bedeutung sind. Zur Analyse der Normalformenproblemberechnung werden die Graph-Gruppen zunächst in rechtwinklige Coxeter-Gruppen eingebettet. Für beliebige Coxeter-Gruppen kann das Alphabet der längenlexikographischen Normalform in logarithmischem Platz bestimmt werden. Darauf aufbauend kann die längenlexikographische Normalform in rechtwinkligen Coxeter-Gruppen berechnet werden. Für allgemeine Coxeter Gruppen wird in "Combinatorics of Coxeter Groups" (Björner, Brenti) ein Algorithmus vorgestellt, der die Normalform mit linear vielen reellen arithmetischen Operationen und Vergleichen bestimmt. Die Berechnung lässt sich allerdings nicht ausschließlich mit ganzen Zahlen durchführen, sondern es werden komplexe Einheitswurzeln benötigt. In dieser Arbeit wird geklärt, wie viele Bits zur Repräsentation notwendig sind. Außerdem wird ein elementarer Beweis angegeben, der zeigt, dass für Coxeter-Gruppen ein präperfektes Ersetzungssystem existiert. Ein präperfektes Ersetzungssystem ist ein Ersetzungssystem, welches nur längenerhaltende und längenreduzierende Regeln besitzt. Coxeter-Gruppen gehören unter anderem zur Klasse der automatischen Gruppen. Für rechtwinklige Coxeter-Gruppen wird in dieser Arbeit ein Beweis angegeben, der zeigt, dass diese automatisch sind.Item Open Access Experimentelle Bestimmung vergleichsoptimaler Sortieralgorithmen(2019) Obst, JulianDie gängigsten Sortierverfahren sortieren Mengen, indem sie zwei Elemente miteinander vergleichen und damit Schritt für Schritt eine Ordnung aufbauen. Es stellt sich die Frage, was die minimale Anzahl an Vergleichen ist, die benötigt wird, um eine beliebige Permutation einer Menge zu sortieren. Das zentrale Ziel dieser Arbeit ist es, die theoretischen Grundlagen zur Bestimmung vergleichsoptimaler Sortieralgorithmen zu erläutern und die Anzahl der Vergleiche von solchen Algorithmen zu bestimmen. Dabei werden auch die praktischen Ansätze besprochen, die benutzt wurden, um einen Algorithmus zu erstellen, der dieses Problem lösen soll. In diesem Zusammenhang werden die Aspekte der Implementierung dieses Algorithmus beleuchtet. Vor allem werden in diesem Punkt aber auch Optimierungen beschrieben, die helfen sollen, die Laufzeit zu verkürzen. Für n = 12, 13 konnten bekannte Ergebnisse bestätigt werden.Item Open Access Kürzeste Wege im Wikipedia-Linkgraph(2013) Kara, FerdiDiese Arbeit beschäftigt sich mit unterschiedlichen Beschleunigungstechniken zur Suche kürzester Pfade in einem Graph. Im Gegensatz zu klassischen Weganfragen wird jedoch kein geographischer Graph als Datenquelle genutzt, sondern der manuell extrahierte Wikipedia-Linkgraph. Um eine Vergleichsgrundlage für Beschleunigungsalgorithmen zu erhalten, wird eine Auswertung der Breitensuche als Basis geschaffen. Zur optimalen Auswahl eines Beschleunigungsalgorithmus ist es unabdingbar, ein grundlegendes Verständnis über die Struktur des Graphen zu erhalten. In Folge dieser Untersuchung und einer Vorstellung unterschiedlicher Beschleunigungsalgorithmen wird das Transitknotenkonzept, welches in der Arbeit von Bast u.a. [BFM+07] vorgestellt wurde, auf den Wikipedia-Linkgraph angewandt. Um das Konzept auf einen nicht geographischen Graph anwenden zu können, wird nach der Arbeit von Eisner/Funke [EF12] die Suche nach einer passenden Transitknotenmenge als Hitting-Set-Problem formuliert. Die Qualität der ausgewählten Transitknoten wird mit unterschiedlichen Konstruktionen zur Transitknotenbestimmung verglichen und die verschiedenen Lösungen werden anhand der vorhergehenden Untersuchung der Graphstruktur erklärt. Schlussendlich wird gezeigt, warum die verschiedenen Konstruktionen der Transitknotenmenge schlechte Ergebnisse liefern, wodurch das Transitknotenkonzept angewandt auf den Wikipedia-Linkgraph fehlschlägt.Item Open Access Fragments of first-order logic over infinite words(2009) Diekert, Volker; Kufleitner, ManfredWe give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic for omega-languages: Sigma2, FO2, the intersection of FO2 and Sigma2, and Delta2 (and by duality Pi2 and the intersection of FO2 and Pi2). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke and Bojanczyk and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.Item Open Access Reachability analysis of multithreaded software with asynchronous communication(2005) Bouajjani, Ahmed; Esparza, Javier; Schwoon, Stefan; Strejcek, JanWe introduce asynchronous dynamic pushdown networks (ADPN), a new model for multithreaded programs in which pushdown systems communicate via shared memory. ADPN generalizes both CPS (concurrent pushdown systems) and DPN (dynamic pushdown networks). We show that ADPN exhibit several advantages as a program model. Since the reachability problem for ADPN is undecidable even in the case without dynamic creation of processes, we address the bounded reachability problem, which considers only those computation sequences where the (index of the) thread accessing the shared memory is changed at most a fixed given number of times. We provide efficient algorithms for both forward and backward reachability analysis. The algorithms are based on automata techniques for symbolic representation of sets of configurations.Item Open Access Neue Bedienkonzepte für mobile Routenplaner(2014) Bahle, StefanieBei 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.Item Open Access Multimodale Bereichsanfragen im Kontext von Routenplanern(2012) Bahrdt, DanielUm eine Route zu planen, müssen Start, Ziel und eventuelle Zwischenpunkte bekannt sein. Sind deren Koordinaten nicht bekannt, jedoch andere Informationen, so könnten die Routenpunkte mit Hilfe dieser Informationen gefunden werden. OpenStreetMap bietet hierfür eine interessante Datenbasis, da Geo-Objekte oftmals nicht nur durch Text sondern auch durch strukturierte Informationen beschrieben werden. Ein Supermarkt besitzt dabei neben den Koordinaten noch den Namen, den Typ des Supermarktes sowie eventuell Öffnungszeiten, Internetadressen und mehr. Diese Informationen sollen in dieser Arbeit durch eine Suchmaschinen-ähnliche Texteingabe zugänglich gemacht werden. Die Suche nach textuellen Informationen soll hierbei unter anderem eine Suche nach Teilzeichenketten ermöglichen. Die Ergebnisse der Suche können durch einfache Mengenoperationen miteinander in Verbindung gebracht werden, sodass eine einfache relationale Abfragesprache entsteht. Hauptanwendungsgebiet soll hierbei die Suche auf mobilen Geräten sein. Zu Vergleichszwecken wurde auch ein Programm zur Suche auf einem normalen Desktoprechner entwickelt.