05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
Item Open Access 7-bit meta-transliterations for 8-bit romanizations(1997) Lagally, KlausWe propose a general strategy for deriving 7-bit encodings for texts in languages which use an alphabetic non-Roman script, like Arabic, Persian, Sanskrit and many other Indic scripts, and for which there is some transliteration convention using Roman letters with additional diacritical marks. These schemes, which we will call 'meta-transliterations', are based on using single ASCII letters for representing Roman letters, and digraphs consisting of a suitable punctuation character and an ASCII letter for representing letters with diacritics. A meta-transliteration is required to be uniquely reversible, human readable, and close to the intended transliteration. We present an example of a scheme that has been in use for several years to transliterate texts in Arabic, Persian, Urdu, Sindhi, and Biblical Hebrew.Item Open Access Abdeckung von Verschnittresten unter Konnektivitätsbedingungen(2015) Hildinger, MarkusIn vielen industriellen Anwendungsgebieten sind geometrische Packungsprobleme zu lösen, so möchte man zum Beispiel bei der Verarbeitung von Blech den Verschnitt minimieren: Gegeben ist eine Menge von Blechteilen, von denen möglichst viele auf einem größeren Blech verteilt werden. Die verbleibenden Blechreste sollen dann noch von der Arbeitsfläche entfernt werden. Typischerweise geschieht dies durch "Wegstanzen" der Blechreste. Es stehen hierfür verschieden Stanzköpfe zur Verfügung. Ziel ist es, mit möglichst wenig Stanzvorgängen und möglichst wenig Wechseln des Stanzkopfes alle Blechreste zu entfernen. Hierbei gilt es zwei Dinge zu beachten: - die verbleibende Restfläche sollte aus Stabilitätsgründen zusammenhängend bleiben - beim Stanzvorgang muss mindestens die Hälfte der Stanzkopffläche auch wirklich mit Material unterlegt sein (d.h. ausschließliche Benutzung des größten Stanzkopfes ist nicht immer möglich). Im Rahmen dieser Diplomarbeit wurde von Grund auf ein Verfahren entwickelt, welches dieses Problem zu lösen versucht. Um die Komplexität des Problems zu reduzieren wurden einige Einschränkungen bezügliche der Probleminstanzen vorgenommen. So wurde festgelegt, dass nur polygonale Wertstücke vom Blech entfernt werden dürfen und die Form der zur Auswahl stehenden Stanzköpfe muss rund sein. Der Hauptaugenmerk der Arbeit liegt auf der Beachtung der Nebenbedingungen. Vor allem für die Sicherstellung des Zusammenhangs der Fläche wurden Ideen entwickelt um umgesetzt. Hierbei spielt die mediale Achse eine besondere Rolle, indem sie als Grundlage für einen Großteil der vorgestellten Verfahren eingesetzt wird. Neben dem Einsatz für die Konnektivitätstest dient sie zusätzlich als Struktur für eine vereinfachte Darstellung einer Fläche. Besondere Merkmale des zu überdeckenden Gebiets können so besser erkannt und genutzt werden.Item Open Access Abschlußbericht der Projektgruppe Evolutionäre Algorithmen(1997) Großmann, Matthias; Leonhardi, Alexander; Schmidt, ThomasViele in der Praxis interessante Optimierungsrobleme sind NP-hart. Da kein Algorithmus bekannt ist, der ein Optimum für solche Probleme mit geringerem als exponentiellem Aufwand findet, sucht man, ein Optimum mit Heuristiken möglicht gut anzunähern. Zu diesen gehören auch die Evolutionären Algorithmen. Ziel der Projektgruppe EVA war die Entwicklung einer Experimentierplattform für Evolutionäre Algorithmen, die die Implementierung und empirische Untersuchung dieser Algorithmen erleichtert. Besonderer Wert wurde daher auf möglichst große Unabhängigkeit der Algorithmen vom Problem gelegt. Der Endbericht der Projektgruppe enthält nach einer Einführung den Entwurf von GENOM, die Beschreibung der Implementierung sowie Hinweise zur Bedienung und zu Erweiterungsmöglichkeiten.Item Open Access Abstraction refinement with craig interpolation and symbolic pushdown systems(2006) Esparza, Javier; Kiefer, Stefan; Schwoon, StefanCounterexample-guided abstraction refinement (CEGAR) has proven to be a powerful method for software model-checking. In this paper, we investigate this concept in the context of sequential (possibly recursive) programs whose statements are given as BDDs. We examine how Craig interpolants can be computed efficiently in this case and propose a new, special type of interpolants. Moreover, we show how to treat multiple counterexamples in one refinement cycle. We have implemented this approach within the model-checker Moped and report on experiments.Item Open Access Algebraische Charakterisierungen von positiver Quantorenalternierung bei Zwei-Variablen-Logik(2013) Fleischer, LukasThérien und Wilke zeigten in einer Arbeit von 1998, dass Zwei-Variablen-Logik erster Stufe (FO2) einer entscheidbaren Klasse endlicher Monoide entspricht. Insbesondere lässt sich damit für jede reguläre Sprache entscheiden, ob sie in FO2 definierbar ist. Dieses Entscheidbarkeitsresultat konnte im vergangenen Jahr von Weil und Kufleitner auf die Alternierungshierarchie innerhalb von FO2 ausgedehnt werden. In einer aktuellen Arbeit von Lauser und Kufleitner wurde dieses Ergebnis noch weiter verfeinert. Sie konnten zeigen, dass die positive Alternierungshierarchie innerhalb von FO2 entscheidbar ist. Krebs und Straubing konnten mit einem anderen Zugang ebenfalls das Entscheidbarkeitsresultat von Weil und Kufleitner beweisen. Anstelle von sogenannten Rankern basiert ihre Charakterisierung auf Blockprodukten. In dieser Arbeit wird diese Technik auf die positive Alternierungshierarchie übertragen. Es werden verschiedene, auf Blockprodukten basierende, algebraische Charakterisierungen der Level der positiven Alternierungshierarchie vorgestellt und deren Entscheidbarkeit bewiesen.Item Open Access Eine algebraische Konstruktion für den Kleene-Stern regulärer Sprachen(2013) Bühler, AndreasIn dieser Bachelorarbeit werden zwei Monoidkonstruktionen vorgestellt, die, auf Basis eines erkennenden Monoids einer Sprache, den Kleene-Stern dieser Sprache erkennen. Die erste Konstruktion basiert nur auf dem erkennenden Monoid der Sprache, während die zweite Konstruktion zusätzlich dazu auch auf der erkennenden Menge in dem Monoid basiert.Item Open Access Algorithm engineering in geometric network planning and data mining(2018) Seybold, Martin P.; Funke, Stefan (Prof. Dr.-Ing.)The geometric nature of computational problems provides a rich source of solution strategies as well as complicating obstacles. This thesis considers three problems in the context of geometric network planning, data mining and spherical geometry. Geometric Network Planning: In the d-dimensional Generalized Minimum Manhattan Network problem (d-GMMN) one is interested in finding a minimum cost rectilinear network N connecting a given set of n pairs of points in ℝ^d such that each pair is connected in N via a shortest Manhattan path. The decision version of this optimization problem is known to be NP-hard. The best known upper bound is an O(log^{d+1} n) approximation for d>2 and an O(log n) approximation for 2-GMMN. In this work we provide some more insight in, whether the problem admits constant factor approximations in polynomial time. We develop two new algorithms, a `scale-diversity aware' algorithm with an O(D) approximation guarantee for 2-GMMN. Here D is a measure for the different `scales' that appear in the input, D ∈ O(log n) but potentially much smaller, depending on the problem instance. The other algorithm is based on a primal-dual scheme solving a more general, combinatorial problem - which we call Path Cover. On 2-GMMN it performs well in practice with good a posteriori, instance-based approximation guarantees. Furthermore, it can be extended to deal with obstacle avoiding requirements. We show that the Path Cover problem is at least as hard to approximate as the Hitting Set problem. Moreover, we show that solutions of the primal-dual algorithm are 4ω^2 approximations, where ω ≤ n denotes the maximum overlap of a problem instance. This implies that a potential proof of O(1)-inapproximability for 2-GMMN requires gadgets of many different scales and non-constant overlap in the construction. Geometric Map Matching for Heterogeneous Data: For a given sequence of location measurements, the goal of the geometric map matching is to compute a sequence of movements along edges of a spatially embedded graph which provides a `good explanation' for the measurements. The problem gets challenging as real world data, like traces or graphs from the OpenStreetMap project, does not exhibit homogeneous data quality. Graph details and errors vary in areas and each trace has changing noise and precision. Hence, formalizing what a `good explanation' is becomes quite difficult. We propose a novel map matching approach, which locally adapts to the data quality by constructing what we call dominance decompositions. While our approach is computationally more expensive than previous approaches, our experiments show that it allows for high quality map matching, even in presence of highly variable data quality without parameter tuning. Rational Points on the Unit Spheres: Each non-zero point in ℝ^d identifies a closest point x on the unit sphere S^{d-1}. We are interested in computing an ε-approximation y ∈ ℚ^d for x, that is exactly on S^{d-1} and has low bit-size. We revise lower bounds on rational approximations and provide explicit spherical instances. We prove that floating-point numbers can only provide trivial solutions to the sphere equation in ℝ^2 and ℝ^3. However, we show how to construct a rational point with denominators of at most 10(d-1)/ε^2 for any given ε ∈ (0, 1/8], improving on a previous result. The method further benefits from algorithms for simultaneous Diophantine approximation. Our open-source implementation and experiments demonstrate the practicality of our approach in the context of massive data sets, geo-referenced by latitude and longitude values.Item Open Access Algorithmen zur Optimierung von geometrischen Packungsproblemen(2014) Geringer, SergejGeometrische Packungs-Probleme sind in vielen industriellen Prozessen anzutreffen. Dadurch motiviert wird in dieser Arbeit untersucht, wie geometrische Formen möglichst oft in einem rechteckigen Gebiet platziert werden können. Um zu garantieren, dass Platzierungen von Formen ohne Überschneidungen sind, wird ein rasterbasierter Schnitttest realisiert, der unter Verwendung der OpenGL-API die Erkennung von Schnitten komplett auf der Grafikkarte durchführt. Die Problemstellung wird anhand von einfachen Polygonen modelliert und mithilfe der geometrischen Eigenschaften der Polygone untersucht. Dafür werden mögliche Platzierungen von Polygonen eingeschränkt und mit Hilfe des Schnitttests auf Überschneidungen geprüft. Eine Datenstruktur zur Verwaltung schnittfreier Polygon-Stellungen wird entwickelt; damit zusammenhängend werden Heuristiken vorgestellt, anhand derer solche Polygon-Stellungen bewertet werden können. Weiterhin werden Strategien diskutiert, die die Anzahl betrachteter Polygon-Stellungen, und somit nötiger Schnitttests, erheblich reduzieren. Diese Strategien orientieren sich an den geometrischen Eigenschaften der Polygone, sowie an strukturellen Eigenschaften der verwendeten Datenstruktur. Durch das iterative Aufbauen lokal enger und schnittfreier Polygon-Platzierungen werden globale Lösungen für das rechteckige Gebiet konstruiert. Anhand einer Software-Implementierung werden die dargelegten Strategien evaluiert und als effizient erachtet.Item Open Access Algorithmen zur Optimierung von Packungsproblemen(2014) Hildinger, MarkusIn vielen industriellen Anwendungsgebieten sind geometrische Packungsprobleme zu lösen, so möchte man zum Beispiel bei der Verarbeitung von Blech oder Stoffen oft den Verschnitt minimieren. Dass heißt, es wird eine Form vorgegeben, die möglichst oft auf einer größeren Fläche platziert werden soll. Die platzierten Formen müssen komplett sein, dass heißt, sie dürfen sich nicht überschneiden und nicht über den Rand hinausragen. Packungsprobleme gehören zur Klasse der NP-vollständigen Probleme. Dies bedeutet, es gibt keinen effizienten Algorithmus (Polynomialzeit-Algorithmus), der in jedem Fall eine optimale Lösung liefern kann, es sei denn, es kann bewiesen werden, dass die Komplexitätsklasse NP gleich der Komplexitätsklasse P ist. Da also keine optimale Lösung in vertretbarer Zeit gefunden werden kann, gilt es, Algorithmen zu entwickeln, welche Ergebnisse liefern, die einer optimalen Lösung so nahe wie möglich kommen. Ziel dieser Studienarbeit ist es, solche Algorithmen zu entwickeln. Um die Komplexität des Problems im Rahmen zu halten, wurden einige Vereinfachungen vorgenommen. So wird das Feld, auf dem die Figuren platziert werden sollen, stets ein Rechteck sein. Des weiteren wird es auch nur eine Figur geben, die auf der Fläche verteilt werden kann und, damit keine gekrümmten Begrenzungen beachtet werden müssen, muss die Figur ein Polygon sein.Item Open Access Algorithms and complexity results for finite semigroups(2019) Fleischer, Lukas; Diekert, Volker (Prof. Dr.)We consider the complexity of decision problems for regular languages given as recognizing morphisms to finite semigroups. We describe efficient algorithms for testing language emptiness, universality, inclusion, equivalence and finiteness, as well as intersection non-emptiness. Some of these algorithms have sublinear running time and are therefore implemented on random-access Turing machines or Boolean circuits. These algorithms are complemented by lower bounds. We give completeness results for the general case and also investigate restrictions to certain varieties of finite semigroups. Except for intersection non-emptiness, the problems mentioned above are shown to be closely connected to the Cayley semigroup membership problem, i.e., membership of an element to a subsemigroup given by a multiplication table and a set of generators. Therefore, the complexity of this problem is one of the main topics of this thesis. In many (but not all) cases, efficient algorithms for Cayley semigroup membership are based on the existence of succinct representations of semigroup elements over a given set of generators. These representations are algebraic circuits, also referred to as straight-line programs. As a compressibility measure for such representations within specific classes of finite semigroups, we introduce a framework called circuits properties. We give algebraic characterizations of certain classes of circuits properties and derive complexity results. As a byproduct, a generalization of a long-standing open problem in complexity theory is resolved. For intersection non-emptiness, a similar tool called product circuits properties is used. We provide completeness results for the problem of deciding membership to varieties of finite semigroups and to varieties of languages. We show that many varieties, which were previously known to be decidable in polynomial time, are actually in DLOGTIME-uniform AC^0. The key ingredient is definability of varieties by first-order formulas. Combining our results with known lower bounds for deciding Parity, we also present a novel technique to prove that a specific variety cannot be defined by first-order formulas with multiplication. Since such formulas are more expressive than finite sets of ω-identities, this implies non-definability by finite sets of ω-identities.Item Open Access Algorithms for vehicle navigation(2012) Storandt, Sabine; Funke, Stefan (Prof. Dr.)Nowadays, navigation systems are integral parts of most cars. They allow the user to drive to a preselected destination on the shortest or quickest path by giving turn-by-turn directions. To fulfil this task the navigation system must be aware of the current position of the vehicle at any time, and has to compute the optimal route to the destination on that basis. Both of these subproblems have to be solved frequently, because the navigation system must react immediately if the vehicle leaves the precomputed route or the optimal path changes e.g. due to traffic jams. Therefore solving these tasks efficiently is crucial for safe and precise navigation. In this thesis we first described a fully autonomous localization scheme based on the shape of the driven trajectory, which provides very accurately the position of the vehicle in the street network. In the second part we investigated route planning for electric vehicle, describing efficient algorithms which allow for retrieving paths with low energy consumption in a fraction of a second on large street networks.Item Open Access Der Algorithmus von Howgrave-Graham und Joux zur Lösung von Rucksackproblemen(2012) Ludwig, MichaelIn dieser Diplomarbeit werden Algorithmen für schwere Rucksackinstanzen (in diesem Fall Subset Sum) behandelt. Eine Instanz heißt schwer, wenn sie eine Dichtekennzahl nahe 1 hat. Die behandelten Algorithmen bauen aufeinander auf. Beginnend beim Horowitz-Sahni-Algorithmus wurde zunächst der Schroeppel-Shamir-Algorithmus und danach der Algorithmus von Howgrave-Graham und Joux hergeleitet. Letzterer hat einen Speicher-Zeit-Tradeoff, welcher in dieser Arbeit ausgebaut werden konnte. Die neuen Algorithmen verwenden außerdem eine Heuristik, deren Korrektheit ebenso bewiesen wurde.Item Open Access Ambiguity functions of context-free grammars and languages(2005) Wich, Klaus; Diekert, Volker (Prof. Dr.)This thesis investigates the relationship between the ambiguity functions for context-free grammars and for context-free languages. It also examines which functions are ambiguity functions and how different ambiguity classes relate to each other. The results can be applied to generalise known results on sequential and parallel parsing of context-free grammars. To understand the main results we define some notions briefly: The ambiguity of a word with respect to a context-free grammar is the number of its derivation trees. The ambiguity function of a context-free grammar maps an integer n to the maximal ambiguity of a word whose length is bounded by n. A context-free language L is f-ambiguous if f is the ambiguity function of some context-free grammar generating L and, roughly speaking, no context-free grammar generating L has a substantially lower ambiguity. A function is an inherent ambiguity function if there is an f-ambiguous context-free language. A homomorphism which maps a symbol either to itself or to the empty word is called a projection. A symbol a is called bounded in a language L if there is a constant c such that no word in L has more than c occurrences of the symbol a. A projection is a bounded contraction for a language L if it erases only symbols which are bounded in L. The main results are: 1. The set of ambiguity functions for cycle-free context-free grammars and the set of inherent ambiguity functions coincide. 2. A technical statement which implies the following two facts: 2.1. The class of context-free languages with polynomially bounded ambiguity is the closure of the class of unambiguous context-free languages under bounded contractions. 2.2. Each reduced cycle-free context-free grammar G is either exponentially ambiguous or its ambiguity is bounded by a polynomial which can be computed from G. (2.2. was already part of the authors Diploma thesis, but the new proof yields in many cases a better polynomial (a polynomial with a lower degree), but never a worse polynomial.) 3. For each computable divergent total non-decreasing function f there is a divergent ambiguity function g such that g(n) is lower than or equal to f(n) for each positive integer n. In fact, the same ambiguity functions occur for the generation of rational trace languages over special independence alphabets. (A rational trace language T is generated by a regular (word) language R if T is the set of traces which are represented by the words in R. The ambiguity of a trace t is the number of representatives in R. It is now straightforward to define the ambiguity function for the generation of T by R.) In addition the thesis contains generalisations for known results on sequential and parallel parsing of context-free grammars. In particular, the thesis considers the (sequential) Earley parsing time of context-free grammars with sublinear ambiguity functions (known to exist due to result 3). Moreover it is shown that each reduced context-free grammars with a polynomially bounded ambiguity can be parsed in logarithmic time on a CREW-PRAM. This is an immediate consequence of 2.1. and a known result for the parallel parsing time of unambiguous context-free grammars.Item Open Access Analyse von Algorithmen zur Bahnverbindungssuche(2014) Wang, MingyuanDiese Arbeit liefert einen Einblick in die Thematiken der elektronischen Fahrplanauskunft und beschreibt den Aufbau eines einfachen Reiseplanungs-systems. Vorteile des time-expanded- und time-dependent-Modells werden dabei kombiniert und ein dafür geeignet angepasster Dijkstra-Algorithmus vorgestellt. Des Weiteren beschäftigt sich die Arbeit mit der Analyse und dem Vergleich von HAFAS, einem gängigen Reiseplanungssystem, und dem Verbindungssuchalgorithmus von PRIMA, einem Nachfrageprognosemodell der Deutschen Bahn AG. Optimierungsvorschläge zum verbesserten Prognosepotenzial von PRIMA werden unterbreitet.Item Open Access Analyse von Pivotwahlstrategien bei Quicksort(2022) Frech, MaximilianSortieren ist ein grundlegendes Problem der Informatik und es existieren viele bekannte Sortieralgorithmen. Der wohl meistgenutzte Algorithmus ist Quicksort, ein rekursiver in-place Algorithmus, welcher nach dem Divide and Conquer Prinzip arbeitet. Die Eingabe des Algorithmus wird durch die Wahl eines Pivotelements aufgeteilt. Hierbei werden alle Elemente, die kleiner als das Pivotelement sind, links platziert und alle Elemente die größeren sind rechts. Nun wird der Algorithmus erneut aufgerufen, einmal mit dem linken Teil der Eingabe und einmal mit dem rechten Teil. Dies geschieht rekursiv, bis die Eingabe vollständig sortiert ist. In dieser Arbeit werden verschiedene Methoden zu Partitionierung und Pivotwahl in einem C++ Framework implementiert und getestet. Es wird außerdem untersucht, ob es von Vorteil ist, das Verfahren abhängig von der Eingabegröße zu wechseln. Zusätzlich werden die Auswirkungen von Randomisierung und der Inklusion des Pivotelements getestet. Für manche Pivotwahlen werden verschiedene Worst Case Eingaben getestet und untersucht. Alle Ergebnisse werden statistisch ausgewertet. Es hat sich herausgestellt, dass die Hoare Partitionierung generell deutlich besser performt als die Lomuto Partitionierung. Bei kleinen Eingabegrößen sollte Median aus 3 benutzt werden, da dies realtiv sicher gegen schlechte Eingaben ist und trotzdem gut performt. Für große Eingaben schneidet Tukeys Ninther hinsichtlich der Laufzeit und Anzahl an Vergleichen am besten ab. Zusätzlich sollte ab einer Größe von 100-200 auf Median aus 3 zurückfallen und ab Eingabegrößen kleiner 10 auf Insertion Sort. Die Inklusion des Pivotelements sowie die Randomisierung konnten hier keinen Vorteil zeigen.Item Open Access Analysing timing behavior of component-based software systems(2023) Hilbig, AaronComponent-based Software Engineering (CBSE) is an established approach for dealing with the complexity of large-scale software systems. In such systems, the impact of small software changes on the overall system can be hard to assess. Because the behavior of the fully integrated system can be diffcult to reason about for developers who know only small parts in-depth, the system can break in unexpected ways. This can also make developers increasingly reluctant to make any changes to the codebase for fear of regressions, leading to a degradation of code quality and maintainability. CBSE is applied in a wide range of application domains in the industry. At ASML, it is used in the controller software of lithography machines. These complex cyber-physical systems consisting of hundreds of components are at the core of modern semiconductor manufacturing. If such a machine is defective in production, it can cost the operator “thousands of euros per minute” until the issue is resolved. The motivation to avoid software bugs, regressions in performance and throughput losses is thus high. To this end, researchers at ASML and TNO have developed the analysis tool Mids. Mids infers a sound approximation of the behavior of the overall system from the output traces of a machines’ components. Using Mids, models learned from the output traces of different software versions can be compared and the changes visualized. This provides a concise overview of the system and of detected behavioral changes between versions to the developers, enabling them to find unexpected changes and regressions. The methodology is not limited to ASML software, but is in principle generally applicable to component-based software. However, Mids only supports the analysis of functional software changes, i.e., added, removed or moved behavior. Finding and analysing the root cause of performance issues in the systems is still an arduous manual process. In this work, we aim to help engineers in finding performance issues or timing behavior changes in component-based software systems by leveraging the automata-based system models inferred by Mids and adding timing information to them. We explore how this data can be extracted from the output traces, added to the system models, and visualized. We further investigate whether signifcant timing behavior changes can be automatically detected, to help engineers focus only on the parts of the system which are impacted by a timing change. We implement our approach as an extension to Mids and evaluate it with artifcially modifed traces as well as with real-world traces. In our case studies, our prototype was not only able to detect the expected timing changes, but also detected additional timing changes that were unknown to the engineers. We received very positive feedback from the ASML engineers, who approached us independently for additional analyses and showed great interest in integrating our prototype into the main-line version of Mids. In a proof-of-concept with the open-source software cURL, we show that our methodology may even be applicable to non-component-based software and for analysing timing changes not caused by software changes.Item Open Access Analysis and verification of systems with dynamically evolving structure(2004) König, Barbara; Esparza, Javier (Prof. Dr.)This thesis is concerned with verification and analysis techniques for software systems characterized by dynamically evolving structure, such as dynamic creation and deletion of objects, mobility and variable topology. Examples for such systems are pointer structures, object-based systems and communication protocols in which the number of participants is not constant. The approach taken here is based on graph transformation systems, an intuitive and---at the same time---powerful formalism for the modelling of distributed and mobile systems. So far there exists comparatively little research concerning the verification of graph rewriting. We will---in the first part of this thesis---introduce graph transformations and give an overview of existing analysis and verification methods, with a focus on the verification of systems with dynamically evolving structure. Then we will describe three original lines of research: behavioural equivalences, type systems and approximation by Petri nets, all of them concerned with the analysis of graph transformation systems. The second part consists of eight refereed research papers treating the previously introduced analysis and verification techniques in depth.Item Open Access Android-Offline-Routenplaner mit Contraction Hierarchies(2022) Hübl, TobiasContraction Hierarchies sind ein Ansatz zur Optimierung von Pfadsuch-Algorithmen, bei welcher eine Graphstruktur um zusätzliche Elemente erweitert wird. Inhalt dieser Arbeit ist die Implementierung einer Android-App zur Berechnung kürzester Pfade auf Teilgraphen unter Verwendung ebensolcher Contraction Hierarchies. Dabei wird unter anderem der Prozess der Extraktion eines Teilgraphen von einem um Contraction Hierarchies erweiterten Graphen auf potentielle Probleme untersucht. Die dabei entdeckten Probleme der Pfadkorrektheit und der Gewährleistung der Absenz ungültiger Kanten werden auf ihre Ursache analysiert und mögliche Lösungsansätze formuliert. Dem folgt eine Dokumentation der Umsetzung der Lösungsansätze in der implementieren Software. Ebenfalls Teil der Arbeit ist eine Untersuchung der Effizienz von einem für Contraction Hierarchies modifizierten Dijkstra-Algorithmus gegenüber einem unmodifizierten Dijkstra. Anhand der Messungen ergab sich eine signifikante Optimierung der Laufzeit des Algorithmus, wenn Contraction Hierarchies zum Einsatz kommen.Item Open Access Anwendung der Well-Separated Pair Decomposition auf Sichtbarkeitsgraphen(2020) Owens, NiklasBisherige Ansätze zur Berechnung von Pfaden zwischen zwei Punkten mit mini- maler euklidischer Länge in einer Umgebung mit unpassierbaren Hindernissen basieren oft auf der Konstruktion des vollständigen Sichtbarkeitsgraphen um auf diesem Routing-Algorithmen auszuführen. Problematisch an diesen Verfahren ist zum einen die hohe Berechnungszeit des vollständigen Sichtbarkeitsgraphen, zum anderen, dass die Komplexität des Sichtbarkeitsgraphen in O(n2) liegt. Um dies zu vermeiden, befasst sich diese Arbeit mit der Entwicklung eines Verfahrens zur Konstruktion von Spannern für Sichtbarkeitsgraphen, auf denen kürzeste Pfade approximiert werden können. Anhand experimenteller Vergleiche mit einem naiven Algorithmus hat sich gezeigt, dass die Spannerkonstruktion deutlich schneller ist als die des vollständigen Sichtbarkeitsgraphen, wobei die Läge der approximierten Pfade im Durchschnitt nur geringfügig von der Länge der tatsächlich kürzesten Pfade abweicht.Item Open Access Anwendung von Contraction Hierarchies und Hierarchical Hub-Labeling auf Geometrischen Graphen(2024) Staib, ChristianWährend Contraction Hierarchies (CH) auf Straßengraphen erfolgreich eingesetzt werden und hohe Speedups bei der Berechnung von kürzesten Pfaden ermöglichen, ist ihre Anwendung auf große Sichtbarkeitsgraphen in angemessener Zeit nicht möglich. Da bisher keine Contraction Hierarchies für die bearbeiteten Sichtbarkeitsgraphen erstellt werden konnten, war auch die Erzeugung von Hierarchical Hub Labelings (HHL) nicht realisierbar. Diese Arbeit untersucht die Hindernisse bei der Anwendung von Contraction Hierarchies auf Sichtbarkeitsgraphen und prüft, ob sich die Kontraktion durch den Einsatz von Heuristiken anstelle der Witness-Suche beschleunigen lässt. Trotz der Anwendung dieser Heuristiken konnten die Sichtbarkeitsgraphen nicht kontrahiert werden. Basierend auf bestehenden Charakterisierungen werden mit PEOPLE und CH-PEOPLE (PrEdetermined Order, Pruned Label) zwei Algorithmen vorgestellt, die es ermöglichen, ohne Kontraktion sowohl Hierarchical Hub Labelings als auch die für CH-Anfragen benötigte Datenstruktur zu erstellen. Beide Algorithmen sind trivial parallelisierbar und wurden erfolgreich auf die bearbeiteten Sichtbarkeitsgraphen angewendet. Während CH-Anfragen nur einen geringen Speedup erzielten, zeigte sich bei HHL-Anfragen ein deutlicher Performance-Gewinn. Zudem war die durchschnittliche Labelgröße der Sichtbarkeitsgraphen vergleichbar mit ihrem durchschnittlichen Knotengrad.