05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
42 results
Search Results
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 Berechnung kürzester Wege mit negativen Kantenkosten(2024) Holtz, PatrickDas Kürzeste-Wege-Problem ist ein elementares Problem der Graphentheorie. Während sich für Graphen mit positiven Kantenkosten schon lange nahe-lineare Algorithmen wie der Dijkstra-Algorithmus etabliert haben, sind im Allgemeinen für Graphen mit beliebigen, also auch negativen Kantenkosten, nur Algorithmen mit schlechterer Komplexität bekannt. Bekannte Beispiele hierfür sind der Bellman-Ford Algorithmus oder der Goldberg-Algorithmus, die in O(nm) bzw. O(m√n log W ) laufen. Der 2022 vorgestellte Algorithmus von Bernstein et al. verspricht mit O(m log⁸(n) log W) erstmals eine nahe-lineare Komplexität, die die bestehenden Algorithmen in der Theorie verbessert. In dieser Arbeit wird Bernsteins Algorithmus vereinfacht und von Grund auf erklärt und eine praktische Implementierung vorgestellt. Außerdem wird durch Laufzeittests untersucht, wie Bernsteins Algorithmus im Vergleich mit ausgewählten bestehenden Algorithmen abschneidet. Die Tests erfolgen auf drei verschiedenen Graphklassen. Es konnte festgestellt werden, dass Bernsteins Algorithmus auf zufällig generierten Graphen mit etwa 106 Knoten um ein Vielfaches langsamer ist als eine effiziente Implementierung von Bellman-Ford (SPFA). Trotzdem konnte gezeigt werden, dass die nahe-lineare Komplexität erreicht wird. Somit ergibt sich bei der Anwendung auf praktische Probleme für Bernsteins Algorithmus kein Laufzeitvorteil, weshalb er die anderen Algorithmen erst bei weitaus größeren Eingabegraphen zeitlich überbieten kann.Item Open Access OSM ticket to ride(2022) Friedsam, WenzelBoard 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.Item Open Access Generierung von Minecraft Welten aus OpenStreetMap-Daten(2024) Dürr, FriedrichDiese Arbeit erforscht die Konvertierung von OpenStreetMap-Daten in spielbare Minecraft Welten. Durch die Nutzung von Höhendaten und Daten aus OpenStreetMap (OSM) wird eine nahtlose Integration von realen Straßen, Gebäuden und Geländemerkmalen in Minecraft ermöglicht. Der Fokus liegt auf der Automatisierung des Prozesses, um vom Nutzer ausgewählte OSM-Datensätze effizient in Minecraft zu übertragen. Verschiedene Herausforderungen wie Datenaufbereitung, Effizienz und Detailgenauigkeit werden untersucht, um realistische Minecraft-Welten zu schaffen. Die resultierenden Welten dienen nicht nur als unterhaltsame virtuelle Umgebungen, sondern auch als nützliche Schablone, um die echte Welt in Minecraft nachzubauen und als Werkzeug für städtische Planung und Geoinformatik-Anwendung.Item Open Access On hierarchical search and preference-based routing in transportation networks(2023) Proissl, Claudius; Funke, Stefan (Prof. Dr.)In dieser Arbeit werden verschiedene Problemstellungen der Routenplanung in Transportnetzwerken behandelt.Item Open Access Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken(2022) Berner, LukasFü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.Item Open Access Asynchronous programs on IoT devices(2022) Pflugfelder, ChristianThe ESP32 is a system-on-chip series developed by Espressif Systems. The chips are low-cost, have low power consumption, many connectivity options, and integrated Wi-Fi. Therefore, they are often used for IoT applications. The development framework distributed by Espressif Systems is largely based on C, so many applications are developed using C and C++. However, other programming languages can also be used on the ESP32. The ESP32 is often used in environments where it must respond to network or environmental events. Asynchronous programming is well suited for such an event-driven context. This thesis investigates how asynchronous programming can be implemented on the ESP32 with different programming languages (C, C++, Rust, Lua, and Python) and the possible limitations. For this purpose, an asynchronous web server is developed with each language. The performance characteristics such as memory consumption, response time, and the maximum number of parallel connections are compared. It is also examined how easy it is to implement asynchronous programs using the concepts supported by the different languages. The performance comparison shows that using operating system threads consumes significantly more memory than asynchronous programming with a runtime. Thus, runtimes are the better option in a context where many network connections are used in parallel. It also shows that the async/await pattern allows easy programming and much more compact code than callbacks.Item Open Access Quadratic equations in free groups and free monoids(2024) Natterer, SilasWe consider word equations over a free monoid or group where every variable occurs at most twice, also called quadratic equations. First, we recount some previously established facts about quadratic equations. We then present the classic solution algorithm for quadratic equations over free monoids based on Nielsen transformations. Next, we prove a theorem that is in some ways analogous to the Pumping Lemma for regular languages: If a quadratic equation permits infinitely many solutions, this already implies the existence of solutions with arbitrarily high exponent of periodicity; this statement is proven both for free monoids and free groups. Finally, we present an algorithm which computes the exponent of periodicity for general equations over free monoids.Item Open Access Consistent pruning and simplification of administrative subdivisions in OpenStreetMap(2022) Bauer, FlorianAppealing and efficient map representations rely on simplifying their map elements in order to reduce the amount of data and rendered objects. However, simplifications inside the well-known OpenStreetMap database are not trivial due to nesting and the associated complex dependencies among elements. A good and consistent simplification of elements in a big way is, therefore, not feasible when working on this data. This thesis aims to develop a consistent simplification strategy for administrative boundaries inside the OpenStreetMap database. In order to achieve this goal, the relevant map data inside the database gets filtered and transformed into an independent graph representation. Based on this representation, we develop different approaches to simplify, store and unpack the administrative boundaries based on their administrative levels and structure. Therefore, we introduce multiple consistent simplification approaches based on approximation and pruning, a geographical data structure for efficiently storing and accessing geographical data, and different approaches for unpacking simplified data. Furthermore, we implement a progressive web application that uses the previously defined algorithms and an evaluation proxy for analysing the interaction between components. Finally, all components are benchmarked with static and dynamic analysis regarding the different approaches.Item Open Access Verbotsmuster für Logik mit zwei Variablen über endlichen und unendlichen Wörtern(2023) Heindl, AmelieDie Varietät DA, die mit der Logik erster Stufe über zwei Variablen übereinstimmt, bildet das höchste Level der Trotter-Weil-Hierarchie. Varietäten in dieser Hierachie können algebraisch über l-Gleichungen charakterisiert werden und haben teilweise äquivalente Klassen in der Quanto- renalternierungshierarchie innerhalb FO2. Um Sprachen mit diesen Klassen in Verbindung zu bringen, ist es möglich, das syntaktische Monoid auszurechnen und für alle möglichen Belegungen die l-Gleichung zu überprüfen. Aus komplexitätstheoretischer Sicht ist dieser Ansatz aufwändig und diese Arbeit befasst sich mit Kriterien, mit denen man die gesuchte Verbindung direkt auf den Automaten der Sprachen prüfen kann. Das zentrale Konzept stellen dabei Verbotsmuster dar. In dieser Arbeit wird eine Definition für Verbotsmuster bei nicht notwendigerweise minimalen DEAs und CMAs gegeben. Damit werden explizite Verbotsmuster für Sprachen über endlichen Wörtern für die Varietäten an den Enden der Hierarchie konstruiert und ein allgemeines Schema für die inneren Level angepasst. Aus diesen Mustern werden Verbotsmuster für fin-syntaktische Monoide von Sprachen über unendlichen Wörtern abgeleitet. Zusammen mit einem Verbotsmus- ter, das die Zugehörigkeit zu DA für inf-syntaktische Monoide entscheidet, lässt sich damit die Trotter-Weil-Hierarchie vollständig für DEAs und CMAs charakterisieren. Für alle konstruierten Verbotsmuster werden NL- und P-Algorithmen erstellt, die Automaten auf das Enthalten dieser Verbotsmuster prüfen. Dies beinhaltet sowohl Algorithmen, bei denen ein festes Verbotsmuster gegeben ist, als auch Algorithmen, bei denen es Teil der Eingabe ist. Für die Varietäten der Trotter-Weil-Hierarchie existieren auch Verbotsmuster mit Teilwortbeziehungen, die von Henriksson und Kufleitner definiert wurden. Die beiden Verbotsmusterarten werden in dieser Arbeit verglichen. Dabei werden insbesondere die Größen der Muster, die Komplexitätsschranken der Algorithmen und die gefundenen Zeugen berechnet. Es ergibt sich ein Größenvorteil der Teilwortmuster gegenüber den Faktormustern bei vergleichbaren Komplexitäten der Algorithmen.