05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
9 results
Search Results
Item Open Access Übersicht und Evalution am Markt erhältlicher Systeme zur graphischen Darstellung von Kartenmaterial(2013) Scheurich, Jonas; Scholz, Martin; Steinhart, DavidDiese Arbeit bietet einen Überblick über bis Anfang Juli 2013 erhältliche Karten-Renderer. Grundsätzlich wird hierbei unterschieden zwischen kommerziellen und gemeinnützigen Projekten. Ein Projekt wird dann als kommerziell bezeichnet, wenn Karten gegen Geld bereitgestellt werden oder eine größere Organisation die Entwicklung der Karten in Auftrag gegeben hat. Gemeinnützige Projekte sind solche, die ihre Karten kostenlos zur Verfügung stellen, ohne finanzielle Absichten zu verfolgen. Es stellt sich heraus, dass viele der nicht-kommerziellen Projekte versuchen neue Techniken einzusetzen, wie zum Beispiel das On-The-Fly-Rendern oder 3D-Darstellung von Kartenmaterial. Im Gegensatz dazu setzen kommerzielle Hersteller weitestgehend auf statische Techniken, zum Beispiel das Rendern von Karten im Vorhinein, welche anschließend nur geladen und angezeigt werden müssen. Des Weiteren setzen die kommerziellen Hersteller auf breite Marktabdeckung. Diese bieten ihre Karten meistens in allen gängigen Formaten an (als Webanwendung, als JavaScript- Plugin, als Plugin bzw. App für iOS und Android), wohingegen die nicht-kommerziellen Projekte meistens nur ein einziges Medium bedienen. Die Nutzung von vorgerenderten Karten hat den großen Vorteil, dass hochwertigere Karten ohne Verzögerung angezeigt werden können. Zudem muss der Karten-Renderer, der den größten Aufwand erzeugt, nicht auf verschiedene Systeme portiert werden. Vor allem On- The-Fly-Renderer sind oft langsam und haben dennoch qualitativ schlechte Karten, weil auf langsame Optimierungsalgorithmen verzichtet werden muss. Der Vorteil von On-The-Fly- Renderern ist, dass man eine Karte nach eigenen Wünschen verändern kann (z.B. Radwege hervorheben), allerdings gibt es wenige Anwendungen, wo dies von Nutzen wäre. Diese Arbeit versucht für verschiedene Anwendungsfälle Empfehlungen auszusprechen. Wenn man z.B. eine Anwendung entwickelt, die Karten in veränderter Form benutzen möchte (z.B. andere Optik, personalisierte Karten), so empfiehlt sich die Nutzung eines Freeware-Produkts. Diese sind oft quelloffen und haben geringe Auflagen, allerdings ist die Dokumentation meist mangelhaft und viele der Produkte sind unausgereift. Für die meisten Anwender reicht eines der kostenlosen Pakete eines kommerziellen Anbieters, da diese (in einem festgelegten Rahmen) ohne großen Aufwand genutzt werden können.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 Übersicht und Evaluation am Markt erhältlicher Routenplaner auf Web- bzw. Android-Plattform(2013) Heidenwag, Jarkko; Niethammer, Philipp; Sanwald, TimDiese Arbeit dient dazu, eine Übersicht der Web- und Android-basierten Routenplaner, welche 2013 auf dem Markt frei erhältlich waren, zu bieten. Bei einer einfachen Suche stellt sich schnell heraus, dass vor allem im Internet dutzende Anbieter eines solchen Services versuchen, neue Benutzer zu werben. Wer den für seine An- wendung besten Routenplaner sucht, wird sich auf Vergleichstests verschiedener Webseiten verlassen müssen. Während Web-Routenplaner ihren Android-Pendants insgesamt in den meisten Punkten überlegen sind, ist offensichtlich, dass diese den großen Vorteil haben, auf mobile Geräte optimiert zu sein und somit oft ein Navigationsgerät ersetzen zu können. Aufgrund der großen Unterschiede der Eigenschaften sowie auch der Anwendungsbereiche der beiden Kategorien, werden sie in dieser Arbeit weitestgehend getrennt untersucht. Dabei werden Kriterien betrachtet, welche aus der Sicht des Benutzers von Bedeutung sein können. Da viele dieser Daten subjektiver Natur sind und andere nicht anders in Erfahrung zu bringen waren, wurden sie für diese Studie gesammelt und für die einzelnen Produkte möglichst übersichtlich zusammengetragen. Anschließend wurde für beide Kategorien jeweils eine Übersichtstabelle mit den Wertungen für Kartendaten, User-Experience und Funktionalität sowie einer Gesamtwertung erstellt. Nach dem Vergleich werden für verschiedene Anwendungsfälle von Web- und Android- Routenplanern Empfehlungen ausgesprochen, da für unterschiedliche Zwecke manche Kriterien wichtiger oder vernachlässigbar sind.Item Open Access Hierarchisierung und Darstellung von Geodaten(2014) Krumpe, FilipDie vorliegende Arbeit beschäftigt sich mit der Darstellung von geographischen Basisdaten im Gebiet der Bundesrepublik Deutschland. Die Arbeit basiert auf zwei Datensätzen des Bundesamtes für Karthographie und Geodäsie und visualisiert sowohl Namen verschiedener geographischer Objekte (u.a. Ortsnamen, Namen von Verwaltungsgebieten) als auch den Verlauf der Grenzen von Verwaltungsgebieten (u.a. Staatsgrenzen, Bundeslandgrenzen, Gemeindegrenzen). Die Darstellung ermöglicht eine Navigation innerhalb der Daten durch Zoom und Verschieben des dargestellten Datenausschnitts und das Hinzufügen und Entfernen von Details. Um die Übersichtlichkeit der Darstellung zu gewährleisten, wurde eine Hierarchisierung der zugrundeliegenden Datensätze entwickelt und eine Filterung der anzuzeigenden Details implementiert. Zudem wurde, zur Beschleunigung der interaktiven Operationen, eine Approximation der Verwaltungsgebietsgrenzen implementiert. In der vorliegenden Arbeit werden die zugrundeliegenden Datensätze GN250 und VG250 und das UTM-Koordinatensystem, in welchem die geographischen Daten referenziert sind, beschrieben. Der Algorithmus für die Approximation der Grenzverläufe sowie die Hierarchisierung der Daten wird erläutert. Zudem wird der grundsätzliche Ablauf des Programms skizziert und zentrale Aspekte des Programms, wie der Aufbau der SHAPE-Datei, welche die Grenzverläufe enthält, und die interne Verwaltungsstruktur der geographischen Daten, beschrieben. Des Weiteren wird die Datenbank beschrieben, welche die initialen Daten bereitstellt, die beim Programmstart geladen werden. Eine Zusammenfassung und ein Ausblick auf weitere Forschungsfragen schließen die Arbeit ab.Item Open Access Kaskadenzerlegung spezieller Automatenklassen(2013) Wächter, Jan PhilippDer Begriff des endlichen Automaten spielt für die Informatik eine große Rolle. Vom Chip-Design über die Progammimplementierung bis hin zur Sprach- und Automatentheorie findet er Anwendung. Dies ist Grund genug sich mit endlichen Automaten genauer zu beschäftigen. Auf algebraischer Seite ist der endliche Automat eng verwandt mit der Halbgruppe oder dem Monoid. Zwar sind diese Konzepte weniger anschaulich als ein endlicher Automat, sie erlauben jedoch einen anderen Blickwinkel und machen die mathematische Betrachtung an einigen Stellen einfacher. Durch das Krohn-Rhodes-Theorem ist bekannt, dass sich eine beliebige endliche Halbgruppe in einfache Gruppen und FlipFlops zerlegen lasst. Die Rückkopplungsfreiheit dieser Zerlegung motiviert den Begriff der "Kaskadenzerlegung". Während die einfachen Gruppen, die dabei auftreten, in der ursprünglichen Halbgruppe selbst enthalten sind, ist dies beim FlipFlop nicht notwendigerweise der Fall. Es stellt sich daher die Frage: Gibt es eine Menge von strukturell möglichst einfachen Halbgruppen, die als Bausteine eine Zerlegung jeder – auch komplexeren – Halbgruppe so ermöglichen, dass jeder verwendete Baustein in der Halbgruppe selbst enthalten ist? Ist die Menge endlich und wie funktioniert die Zerlegung? Angetrieben durch diese Fragestellung werden in dieser Arbeit Zerlegungen von Halbgruppen und Monoiden aus speziellen Klassen genauer untersucht, für die die Frage nach den Bausteinen beantwortet werden kann.Item Open Access Untersuchung der Struktur großer Straßennetzwerke(2012) Hartmann, FrederikIn den letzten Jahren hat die Bedeutung von Geoinformationen durch das Aufkommen von navigationsfähigen Smartphones und personalisierter Werbung stark zugenommen. Diese Anwendungsbereiche, aber auch intelligentes Routing oder Verbesserungen im Straßenbau, benötigen exakte, detaillierte Karten, die Straßendaten mit Points of Interests oder Stauinformationen vernetzen. Im Jahr 2004 wurde durch die Gründung von OpenStreetMap eine Plattform für eine Open Source Straßenkarte geschaffen, an der sich jeder mit einem GPS Empfänger oder GPS fähigem Smartphone beteiligen kann. Der Open Source Ansatz kann jedoch auf Grund fehlender Organisationsstrukturen auch ein Problem sein. Dies lässt sich alleine an 199 unterschiedlichen Straßentypen erkennen, von denen jedoch nur 20-30 Typen weitere Verbreitung erfahren. Auch werden viele Straßen uneinheitlich eingepflegt. Dennoch ist die Qualität der OSM bereits heute in manchen Bereichen gleichwertig oder besser als kommerzielle Alternativen. Um die OpenStreetMap algorithmisch verwenden zu können, muss zunächst eine Transformation und eine Bereinigung der Karte durchgeführt werden, da das Ursprungsformat nicht für die algorithmische Bearbeitung geeignet ist und viele nicht benötigte Informationen enthält. Die vorliegende Studienarbeit beschäftigt sich im Kapitel 2 mit der Umwandlung in ein algorithmisch gut verwendbares Datenformat und der Bereinigung des Graphen. In den Kapiteln 3 und 4 geht es um die Ermittlung von grundlegenden Eigenschaften des Graphen, die zur Optimierung und Laufzeitabschätzung von Algorithmen benötigt werden. Durch die Analyse der Verzerrung der Weglängen und Distanzen werden Hinweise auf problematische Gebiete im Graphen gegeben.Item Open Access Effiziente Textsuche in OpenStreetMap-Daten auf mobilen Geräten(2011) Bahrdt, DanielIn dieser Arbeit sollen mehrere Möglichkeiten zur effizienten Textsuche in OpenStreetMap- Daten vorgestellt werden. Das Ziel ist ein Androidprogramm, mit welchem nach Zeichenketten in OpenStreetMap-Daten gesucht werden kann. Zur effizienten Suche bieten sich hier Hash-Verfahren und vor allem Baumstrukturen, wie Patrica- oder HAT-Tries, an. Für die Suche auf Mobilgeräten kann eine Datenstruktur verwendet werden, die nur Lesezugriffe, jedoch keine Veränderungen ermöglicht. Neben einem auf minimalen Hash-Funktionen basierenden Verfahren wurde ein Patricia-Trie in serialisierter Form in einem Byte-Feld abgelegt. Die Datenstruktur ermöglicht so eine Suche nach Präfixen in O (k ), mit k der Länge des gesuchten Präfixes, bei guter Cache-Nutzung. Die Baumstruktur erwies sich dabei dem Hash-Verfahren überlegen. Eine potentielle Erweiterung, die Schnittoperationen und die Suche nach mehreren Zeichenketten ermöglicht, soll im Abschnitt Ausblick kurz umrissen werden.Item Open Access Gewisse Eigenschaften deterministischer Automaten und ihre Komplexität(2014) Rathgeber, MoritzIn dieser Arbeit wird untersucht, wie sich die Ergebnisse von Cho und Huynh [CH91] zur Komplexität der Probleme gegeben ein deterministischer endlicher Automat: ist die von diesem Automat akzeptierte Sprache sternfrei bzw. piecewise testable bzw. dot-depth-one'' auf andere Klassen von Sprachen übertragen lassen. Es kann gezeigt werden, dass alle Klassen, die durch Omega-Gleichungen charakterisierbar sind, in PSPACE entscheidbar und NL-schwer sind. Wir geben Verfahren an, dass zu jeder Gleichung, die eine gewisse Bedingung erfüllt, ein Verbotsmuster erzeugt, das in NL entscheidbar ist, und zeigen, dass das Schnittproblem bereits für die Klasse der deterministische endliche Automaten, die locally testable Sprachen akzeptieren, PSPACE-vollständig ist, wodurch der PSPACE-Vollständigkeitsbeweis für die Klasse der sternfreien Spachen vereinfacht werden kann.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.