05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
166 results
Search Results
Item Open Access Average case considerations for Mergelnsertion(2018) Stober, FlorianThe 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.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.Item Open Access Experimental analysis of randomized calculations of average rankings(2016) Zeiß, TimListing 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.Item Open Access Das Geographiespiel in der Theorie und seine Realisierung als App(2013) Steinhart, DavidDas sogenannte "Geographiespiel" ist ein simples Spiel, welches dem Leser eventuell in einer Variante bekannt ist. Dabei nennen zwei Spieler abwechselnd Städtenamen, wobei diese jeweils mit dem Endbuchstaben der vorherigen Stadt beginnen müssen. Nennt Spieler A beispielsweise "Stuttgart", so kann Spieler B "Tübingen" als Antwort geben. Daraufhin wären "Nürnberg" oder "New York" mögliche Antworten. Das Ende des Spieles ist erreicht, wenn einem der beiden Spieler keine weitere Stadt einfällt und er somit das Spiel verliert. Bereits genannte Städte dürfen nicht erneut verwendet werden. Denkbar wäre auch eine Variante, in der Personen oder Automarken genannt werden. Beim Geographiespiel wird untersucht, welcher Spieler bei einer festgelegten Städteliste und optimaler Spielweise gewinnen wird. Das Spiel wird dahingehend erweitert, dass die Anzahl der Anfangs- und Endbuchstaben nun nicht mehr auf 26 festgelegt ist. Das Auswerten einer erweiterten Version des Spieles, die eine unbegrenzte Anzahl an Buchstaben zulässt, liegt in P-SPACE. Gibt es dagegen nur endlich vielen Buchstaben, liegt das Problem in P. Zudem ist es für sehr kleine Instanzen (nur 1 bzw. 2 Buchstaben) möglich, diese in logarithmischem Platz zu lösen. Ziel dieser Arbeit ist es, Instanzen mit endlich vielen Buchstaben genauer zu untersuchen. Einerseits wird der Fall mit 3 bzw. 4 Buchstaben betrachtet. Andererseits wird die Möglichkeit untersucht, das Auswertungsproblem für Schaltkreise auf das Geographiespiel mit endlich vielen Buchstaben zu reduzieren und so die P-Vollständig zu zeigen. Als praktischer Teil der Arbeit wurde das Geographiespiel als App implementiert. Dies dient der Untersuchung, mit welchem Aufwand und bis zu welchen Grad die Umsetzung realisierbar ist.Item Open Access Contraction Hierarchies für kontinuierliche Graphsimplifizierung mit Qualitätsgarantien(2016) Rupp, TobiasModerne 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.Item Open 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.Item Open Access Deterministische endliche Automaten und Zwei-Variablen-Logik erster Stufe(2013) Müller, SebastianTherien 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.Item Open Access Turn by Turn Navigation für Android Mobilgeräte(2012) Haag, ChristophDie bei einem Studienprojekt entstandene Routenplanungs-Software "ToureNPlaner" wird mit dieser Bachelorarbeit für den praktischen mobilen Einsatz angepasst. Zu diesem Zweck wird das ToureNPlaner System um Funktionen für die Turn-by-Turn Navigation erweitert. Darunter wird ein System verstanden, das anhand der per GPS ermittelten Position mittels einer Sprachausgabe Navigationsanweisungen gibt. Die Implementierung erfolgt in Form eines Client-Server Systems auf Basis einer PostGIS Datenbank.Item Open Access Formal language theory of logic fragments(2014) Lauser, Alexander; Diekert, Volker (Prof. Dr.)The present thesis consists of two parts. Based on syntactic closure axioms of formula sets, the first part gives a formal definition of logic fragments. It also shows the versatileness of this notion of logic fragments, inter alia, giving, C-variety descriptions of logic fragments and abstractly investigating the influence of certain predicates on the expressiveness of logic fragments. The second part considers two-variable first-order logic FO2. A combinatorial description in terms of so-called rankers is given for all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over the order predicate, both with and without the successor predicate. Also in the second part, effective algebraic criteria describing all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over several signatures are given, yielding in particular decidability of the definability problem.Item Open Access Grafisches Clustering von OSCAR-Suchresultaten(2018) Makolli, SokolDie Suchergebnisse der Suchmaschine OSCAR sind häufig für den Benutzer wegen ihrer großen Menge unübersichtlich. Eine Strukturierung auf Clientseite liefert zwar für den Nutzer relevante Ergebnisse, jedoch ist der dabei entstehende Kommunikationsoverhead zu groß und die Strukturierung somit zu langsam. In dieser Arbeit wird eine Strukturierung auf Serverseite vorgestellt, die Ergebnisse mit zehn- bis zwanzigfacher und bei einer regionalen Strukturierung mit bis zu hundertfacher Geschwindigkeit liefert.