05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

2005 - 200912010 - 201520

Settings

Institute: search.filters.UBSInstitut.Institut für Formale Methoden der InformatikPublication Type: search.filters.UBSTyp.Abschlussarbeit (Diplom)

Search Results

Now showing 1 - 10 of 21
  • Thumbnail Image
    ItemOpen Access
    Normalformenberechnung in Graph-Gruppen und Coxeter-Gruppen
    (2011) Kausch, Jonathan
    Im 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.
  • Thumbnail Image
    ItemOpen Access
    Kürzeste Wege im Wikipedia-Linkgraph
    (2013) Kara, Ferdi
    Diese 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.
  • Thumbnail Image
    ItemOpen Access
    Multimodale Bereichsanfragen im Kontext von Routenplanern
    (2012) Bahrdt, Daniel
    Um 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.
  • Thumbnail Image
    ItemOpen Access
    Das Wortproblem für Omega-Terme über Zweivariablenlogik
    (2014) Wächter, Jan Philipp
    Kaum ein Maschinenmodell ist von so großer Bedeutung wie das der endlichen Automaten. Es findet nicht nur Anwendung in der technischen, theoretischen und praktischen Informatik, sondern auch in vielen anderen Wissenschaften und Wissenschaftsbereichen. Von daher mag es kaum verwundern, dass nicht nur die mit den endlichen Automaten untrennbar verbundenen regulären Sprachen, sondern auch viele darin enthaltene Sprachklassen von großem akademischen und praktischen Interesse sind. Neben der automatentheoretischen Untersuchung der regulären Sprachen gibt es daher noch andere Herangehensweisen: beispielsweise durch Logiken oder durch algebraische Strukturen. Dass es sich bei endlichen Automaten um recht einfache Maschinen handelt, überträgt sich auch auf die algebraischen Strukturen. So werden reguläre Sprachen durch endliche Monoide erkannt, einer algebraischen Struktur, die nur wenigen Axiomen gerecht werden muss. Ein Sprachklasse unterhalb der regulären Sprachen erhält man beispielsweise, indem man sich auf Sprachen beschränkt, die durch Sätze der Prädikatenlogik erster Stufe oder "first-order logic" FO definierbar sind. Durch Beschränkung der Anzahl der in einem solchen Satz erlaubten Variablen lässt sich diese Sprachklasse weiter spezialisieren. Es ist bekannt, dass die Verwendung von nur drei Variablen keine Einschränkung darstellt. Die Untersuchung jener Sprachen, die sich mit Prädikatenlogik erster Stufe unter Verwendung von nur zwei Variablen, also durch die Zweivariablenlogik FO2[<] definieren lassen, ergibt sich daher auf natürliche Weise. Auf algebraischer Seite korrespondiert diese Klasse von Sprachen mit der Menge endlicher Monoide, genauer der Varietät endlicher Monoide DA. Jene Varietät DA erhält man auch durch Vereinigung der abzählbar unendlich hohen, sogenannten Trotter-Weil-Hierarchie. Diese besteht aus Ecken, Join-Ebenen und Schnitt-Ebenen und ist zentraler Gegenstand der Betrachtungen dieser Arbeit. Diese Betrachtungen befassen sich mit dem Wortproblem für Omega-Terme von Varietäten in der Trotter-Weil-Hierarchie. Bei Omega-Termen oder, wie sie hier genannt werden, Pi-Termen handelt es sich um Terme von Variablen, die mit einer zusätzlichen Pi-Potenz versehen werden können. Anschließend können für die Variablen Elemente eines Monoids eingesetzt werden, die Pi-Potenzen erhalten dann einen Wert, der als "unendlich oft" interpretiert werden kann. Anschaulich lässt sich ein Pi-Term daher mit dem Verhalten eines endlichen Automaten, dessen Ausführung nicht durch eine bestimmte Anzahl an Schritten beschränkt ist, verknüpfen. Zwei Pi-Terme u und v lassen sich zu einer Gleichung u = v verknüpfen. Es ist dann möglich zu fragen, ob ein Monoid M diese Gleichung erfüllt. Dies ist dann der Fall, wenn sich links und rechts stets das selbe Monoidelement ergibt, sobald man für die Variablen beliebige Elemente einsetzt. Diese Fragestellung lässt sich erweitern: Erfüllt jedes Monoid in einer Varietät die Gleichung? Dabei handelt es sich um die Frage des Wortproblems für Pi-Terme der Varietät. Diese Arbeit wird zeigt, dass sich das Wortproblem für Pi-Terme der Ecken und Join-Ebenen der Trotter-Weil-Hierarchie durch eine logarithmisch platzbeschränkte nichtdeterministische Turingmaschine entscheiden lässt, dass es also zur Komplexitätsklasse NL gehört. Obwohl es sich bei NL um eine nichtdeterministische Platzklasse handelt, ist dieses Ergebnis interessant, da sich die Probleme aus NL effizient parallel entscheiden lassen. Eine Eigenschaft, die nicht zuletzt seit dem Aufkommen von Mehrkernprozessoren, eine immer größere Rolle spielt. Gleichzeitig liefert ein NL-Algorithmus auch einen deterministischen Polynomialzeitalgorithmus. Der NL-Algorithmus für die Entscheidung des Wortproblems für Pi-Terme der Ecken und Join-Ebenen der Trotter-Weil-Hierarchie lässt sich leicht abwandeln, um die Zugehörigkeit des Wortproblems für Pi-Terme von DA zu NL zu zeigen. Im Sinne der Komplexitätsklassen verbessert dies ein Ergebnis von A.~Moura, das einen deterministischen Polynomialzeitalgorithmus zur Entscheidung dieses Problems liefert und damit Erkenntnisse von Almeida und Zeitoun erweitert, die zeigten, dass sich das Wortproblem für Pi-Terme der Varietät der endlichen R-trivialen Halbgruppen in Linearzeit entscheiden lässt. Die Varietät der endlichen R-trivialen Monoide tritt auch als Ecke in der Trotter-Weil-Hierarchie auf. Das Vorgehen in dieser Arbeit unterscheidet sich von dem Vorgehen in den genannten anderen Arbeiten. Das zentrale Konzept ist dabei das Einsetzen linearer Ordnungstypen für die Pi-Potenzen der Pi-Terme, ähnlich wie bei Huschenbett und Kufleitner. Auf die dabei entstehenden, im Allgemeinen unendlichen, verallgemeinerten Wörter werden dann einige Instrumente, die bei der Untersuchung der Trotter-Weil-Hierarchie sonst in einer endlichen Form vorkommen, übertragen. Am wichtigsten dabei sind die sogenannten Ranker, die auf die "trurtle programs" von Schwentick, Thérien und Vollmer zurückgehen und anschließend u.a. durch Weis und Immerman weiter entwickelt wurden. Über die eindeutige Intervall-Temporallogik von Lodaya, Pandya und Shah ergibt sich ihr Bezug zur Logik.
  • Thumbnail Image
    ItemOpen Access
    Separierbarkeit über endlichen Wörtern bei einer Quantorenalternierung
    (2015) Abdelaziz, Amir
    Das Separierbarkeitsproblem entspricht der Fragestellung ob für zwei Mengen X und Y ein sogenannter Separator S existiert mit X ⊆ S und Y ∩ S = ∅. Man sagt dann, dass S die Menge X von Y trennt. Formale Sprachen können durch prädikatenlogische Formeln definiert werden. Ein bekanntes Logikfragment der prädikatenlogischen Formeln ist Σ2 . Diese Diplomarbeit beschäftigt sich mit der Σ2 -Separierbarkeit von regulären Sprachen, d.h. mit der Entscheidbarkeit ob für zwei reguläre Sprachen L1 und L2 eine dritte Sprache S existiert die durch eine Formel in Σ2 definiert werden kann und L1 von L2 trennt. Grundlage dafür ist der Artikel Going Higher in the First-Order Quantifier Alternation Hierarchy on Words von Thomas Place und Marc Zeitoun.
  • Thumbnail Image
    ItemOpen Access
    Varianten des NTRU-Kryptosystems
    (2012) Bächtle, Patrick
    Die vorliegende Arbeit behandelt das NTRU-Kryptosystem, welches zu den Public-Key-Kryptosystemen gehört. Bei den Public-Key-Kryptosystemen gibt es jeweils einen öffentlichen Schlüsselanteil zum verschlüsseln und einen passenden geheimen Schlüsselanteil, der zum Entschlüsseln benötigt wird. Wie die Bezeichnung bereits vermuten lässt, ist verschlüsseln für jeden möglich, da dieser Schlüsselanteil öffentlich zugänglich ist. Einem Angreifer eines Kryptosystems darf es also nicht möglich sein aus der Kenntnis des öffentlichen Schlüssels die ursprüngliche Nachricht zu rekonstruieren. Um dies zu gewährleisten greifen Kryptosysteme auf schwer zu lösende mathematische Probleme zurück. Das RSA-Verfahren aus dem Jahr 1977 benutzt hierzu die Schwierigkeit große Zahlen zu faktorisieren. Wählt man die für das RSA-Verfahren benutzten Zahlen groß genug, so geht man davon aus, dass ein Angreifer das Verfahren nicht in kurzer Zeit brechen kann. Beweisbar ist diese Sicherheit nicht, auf Experimenten basierende Beobachtungen zeigen jedoch, dass bei geeigneter Parameterwahl die Laufzeit solcher Angriffe sehr viel Zeit beansprucht. Ein anderes Public-Key-Kryptosystem, das Diffie-Hellman-System, basiert auf einem anderen schwer zu lösendem mathematischen Problem. Hierbei verlässt man sich auf die Schwierigkeit des diskreten Logarithmus in endlichen Gruppen. Es ist auch hier die Sicherheit des Verfahrens nicht beweisbar. Für genügend große Parameter liegt aber die gleiche Situation wie beim RSA-Verfahren vor. Ein Verfahren mit beweisbarer Sicherheit ist das Vernom-One-Time-Pad. Dieses Verfahren zeichnet sich einerseits dadurch aus, dass die Schlüssel die gleiche Länge wie die zu verschlüsselnden Nachrichten haben müssen. Bei längeren Nachrichten führt dies zu einem großen Aufwand bei der Schlüsselerzeugung. Diese Ineffizienz ist der Grund, warum das Vernom-One-Time-Pad in der Praxis nur selten Anwendung findet. In dieser Diplomarbeit wollen wir das NTRU-Verfahren genauer betrachten. Das NTRU-Kryptosystem wurde 1996 von Hoffstein, Pipher und Silverman im Rahmen der RUMP Session auf der CRYPTO '96 vorgestellt. Erst kürzlich wurde es als Standard in der Finanzbranche zertifiziert. NTRU ist ein Public-Key-Kryptosystem, bei dem Ver- und Entschlüsselung Operationen im Quotienten eines Polynomrings (genauer: R = Z[x]/xN − 1) sind. Die Schlüssel, die für das Verfahren benutzt werden sind demnach Polynome aus diesem Polynomring. Wie auch bei den anderen Public-Key-Systemen kann die Sicherheit bei NTRU nicht bewiesen werden. Die Sicherheit basiert auf der Annahme, dass faktorisieren eines Polynoms in R schwer ist. Wie auch schon bei RSA und Diffie-Hellman stützt sich diese Annahme auf experimentelle Ergebnisse, die auf eine exponentielle Laufzeit der Angriffsversuche hindeuten. Im Rahmen dieser Diplomarbeit werden wir grundlegend das NTRU-Verfahren und einige Angriffe vorstellen. Anschließend wollen wir den algebraischen Grundraum R mit einer leicht modifizierten Version austauschen und so modifizierte Variante von NTRU genauer untersuchen. Im Vordergrund dieser Untersuchung steht die Funktionalität des Verfahrens, da schon beim Standard Verfahren Entschlüsselungsfehlern auftreten können. Des Weiteren wollen die modifizierten Varianten auf ihre theoretische Sicherheit hin überprüfen. Dabei werden wir insbesondere auf die sogenannten Gitterangriffe gegen ein NTRU-System eingehen.
  • Thumbnail Image
    ItemOpen Access
    Abdeckung von Verschnittresten unter Konnektivitätsbedingungen
    (2015) Hildinger, Markus
    In 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.
  • Thumbnail Image
    ItemOpen Access
    Minimierung von Automaten mit einer beschränkten Anzahl von Fehlern
    (2012) Jahn, Franz G.
    Benedikt, Puppis und Riveros haben 2011 gezeigt, dass für zwei reguläre Sprachen L und K entscheidbar ist, ob sich L in die Sprache K so einbetten lässt, dass man in einem Reparaturvorgang auf jedes Wort aus L nur beschränkt viele Zeichenoperationen (Einfügen, Löschen, Substituieren) ausführen muss um ein Wort aus K zu erhalten. Es wird dabei zwischen den Reparaturmodi "Streaming" und "Nonstreaming" unterschieden. Zwei Sprachen sind in diesem Kontext äquivalent, wenn sie sich auf diese Weise gegenseitig ineinander einbetten lassen. In dieser Diplomarbeit werden die Eigenschaften der Äquivalenzklassen mit dem Fokus auf minimale Automaten analysiert. Für den Modus "Nonstreaming" wird gezeigt, dass die Konstruktion eines minimalen Automaten innerhalb einer Äquivalenzklasse PSPACE hart ist. Für den "Streaming" Modus wird ein Polynomialzeitalgorithmus zur Konstruktion eines minimalen Automaten erarbeitet. Als Sprachklassen werden in diesem Zusammenhang Ideale, Filter und Boolesche Kombinationen von Idealen sowie entsprechende Automatenmodelle betrachtet.
  • Thumbnail Image
    ItemOpen Access
    Contraction Hierarchies für komplexe Kostenmaße
    (2012) Ruopp, Manuel
    Die Routenplanung ist ein erheblicher Bestandteil im alltäglichen Leben. Es können Kosten beim gewerblichen Transport von Waren oder Zeit bei privaten Reisen eingespart werden. Über die letzten Jahre sind immer mehr mobile Geräte -- vor allem Smartphones -- in alltäglicher Benutzung. Daher liegt es nahe, die Routenplanungsalgorithmen speziell für mobile Geräte zu optimieren. Dabei spielen die Geschwindigkeit, der Stromverbrauch (Rechenaufwand, Speicherzugriffe) und der beschränkte Speicherplatz eine bedeutende Rolle. In letzter Zeit wurde dafür als Grundlage oft das Contraction Hierarchy Verfahren in der Forschung verwendet. Contraction Hierarchies ermöglichen eine schnelle Routenberechnung in Graphen. Die Graphen werden bei diesem Verfahren in einer Vorbereitungsphase um eine Hierarchie erweitert. Der Graph kann nun aber nachträglich nur noch mit großem Aufwand verändert werden. Es lohnt sich daher nur, wenn viele Routen auf einem gleichbleibenden Graphen berechnet werden sollen. Der Speicherplatzverbrauch ist niedrig, da sich nur die Kantenanzahl des Graphen in der Vorbereitungsphase in etwa verdoppelt. Diese Arbeit erweitert das Contraction Hierarchy Verfahren um komplexe Kostenmaße für die Berechnung von kürzesten Wegen. Dabei haben wir zwei voneinander getrennte Zielsetzungen. Als Erstes wird versucht, verschiedene Metriken für die Kantengewichte des Graphen in einer einzigen Hierarchie zu vereinen. Damit könnten verschiedene Kantengewichte für unterschiedliche Fahrzeugstypen, wie zum Beispiel PKW und Fahrrad in einem Graphen modelliert werden. Und als Zweites werden die Kantengewichte durch Gewichtsfunktionen ersetzt. So lassen sich zeitliche Bedingungen modellieren: zum Beispiel ist zur Mittagszeit auf dieser Straße immer Stau, und deshalb wird für diese Strecke das Vierfache der Zeit benötigt.
  • Thumbnail Image
    ItemOpen Access
    SAT Solving mit GPU Unterstützung
    (2012) Sieweck, Philipp
    Vorgestellt wird eine Implementierung des Survey Propagation Algorithmus (SP) auf einer GPU mit CUDA, sowie ein SAT Solver auf Basis von MiniSAT, der SP als zusätzliche Heuristik verwendet, um zufällige $k$-SAT Probleme schneller lösen zu können.