THEMEN
Wenn Sie eigene Vorschläge haben, wenden Sie sich gerne an einen unserer Mitarbeiter. Prinzipiell kann jedes Thema im Umfang angepasst werden, sodass es für eine Bachelor-, Master- oder Diplomarbeit passend ist.
Algorithmen
-
Randomwalk-Algorithmen
Sogenannte Randomwalk-Algorithmen werden in vielfältigen Bereichen eingesetzt. Eine Anwendung findet im Bereich von Erfüllbarkeitsalgorithmen statt und führt zu einem kompetetiven Algorithmen, der deutlich besser als deterministische erschöpfende Suche ist. In dieser Arbeit soll ein Überblick geschaffen werden, der einige Resultate solcher Algorithmen zusammenfasst und ansprechend präsentiert.
Schöning: A probabilistic algorithm for k-SAT and constraint satisfaction problems
Leitung und Ansprechpartner der Abschlussarbeit
-
Pseudodeterministische Datenstrom-Algorithmen
Klassische Datenstrom-Algorithmen sind deterministische Approximationsalgorithmen, die bei mehrfacher Ausführung mit einer hohen Wahrscheinlichkeit zum selben Ergebnis kommen. Generell arbeiten solche Algorithmen auf einem Datenstrom und nähern eine Funktion auf den Werten im Datenstrom an. In dieser Arbeit sollen neue Entwicklungen im Bereich pseudoterministischer Datenstrom-Algorithmen zusammengefasst und dargestellt werden.
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff: Pseudo-deterministic Streaming
Leitung und Ansprechpartner der Abschlussarbeit
-
Starke Hintertüren in Default-Logik
Gegeben eine aussangelogische Formel und eine Teilmenge X ihrer Variablen, sagt man, dass X eine starke HORN-Hintertür für die Formel ist, wenn für alle Belegungen über den Variablen aus X die resultierende Formel eine HORN-Formel ist.
Default-Logik ist eine Erweiterung einer Logik um sogenannte Default-Regeln. Diese Regeln sind Formel-Tripel bestehend aus einer Vorbedingung, einer Rechtfertigung und einer Schlussfolgerung. Gegeben eine Wissensbasis (Menge von Formeln) sowie eine Menge von Default-Regeln, fragt man in einem wichtigen Entscheidungsproblem nach der Existenz einer stabilen Erweiterung. Diese Erweiterungen spiegeln im Prinzip das folgerbare Wissen aus der Wissensbasis unter Anwendung der Default-Regeln wider.
Kürzlich haben Fichte und andere [1] das Konzept von Hintertüren in Default-Logik eingeführt und hinsichtlich seiner parametrisierten Komplexität analysiert.
In einer weiteren Veröffentlichung von Egly und anderen [2] wurde ein Framework entwickelt, mit dem Probleme aus der Polynomialzeithierarchie über QBF-Formeln gelöst werden können.
In der Arbeit soll das Framework von [2] auf die Resultate in [1] angewendet werden.
[1] Strong Backdoors for Default Logic. Johannes K. Fichte, Arne Meier, Irina Schindler (2016)
Leitung und Ansprechpartner der Abschlussarbeit
Komplexitätstheorie
-
Selbstreduzierbarkeit
Selbstreduzierbarkeit ist eine wichtige algoritmische Technik, die dabei hilft, ein Problem in einer strukturierten Weise zu lösen, indem Instanzen systematisch nach Lösungen durchsucht werden. In dieser Arbeit soll ein Überblick über die Technik gegeben sowie mit Beispielen und Erklärungen versehen werden.
Hemaspaandra: The Power of Self-Reducibility: Selectivity, Information, and Approximation
Leitung und Ansprechpartner der Abschlussarbeit
-
Enumeration in modaler Logik
Enumerationskomplexität befasst sich mit der Ausgabe aller Lösung ohne Duplikate einer Eingabe. Hierbei handelt es sich häufig um Algorithmen mit exponentieller Laufzeit. Aus diesem Grund klassifiziert man diese deterministischen Algorithmen an Hand ihres Delays. Der Delay eines Algorithmus beschreibt die Zeit, die zwischen der Ausgabe von zwei Lösungen verstreicht. Hierbei gibt es zum Beispiel die Klassen DelayP und IncP. Problem in der Klasse DelayP besitzen solche Enumerationsalgorithmen, welche einen polynomiellen Delay in der Eingabelänge besitzen, bei IncP ist der Delay der i-ten Lösung ein Polynom in der Eingabelänge und des Lösungsindex.
In der Arbeit soll die Enumerationskomplexität von Problemen in der Modallogik betrachtet werden. Gegeben eine modallogische Formel sowie ein Model, ist die Menge der Teilbäume gesucht, die die Formel erfüllen.
Leitung und Ansprechpartner der Abschlussarbeit
-
Separation von Formeln und nicht-uniformen Schaltkreisen für AC0[xor]
In dieser Arbeit soll ein aktuelles Resultat nachvollzogen und im Gesamtkontext dargestellt werden. Es geht um den Vergleich der Mächtigkeit von Formeln und Schaltkreisen. AC0[xor]-Schaltkreise verwenden Gatter der Form AND, OR, NOT und MOD 2 von unbeschränktem Eingangsgrad. Bei der Fragestellung handelt es sich um eine Einschränkung der generellen Frage, ob NC1 (Sprachen, für die es polynomiell große Boole'sche Formeln gibt) eine echte Teilklasse von P/poly (Sprachen, für die es einen polynomiell großen Boole'schen Schaltkreis gibt) ist.
Leitung und Ansprechpartner der Abschlussarbeit
-
Maschinengrößen
In einem Blog-Eintrag von Gasarch wird über sogenannte Bounding Functions referiert. Eine Funktion f nennt man eine Bounding Function für zwei Maschinentypen (D, E), wenn eine Sprache L durch eine D- und E-Maschine akzeptiert werden kann und L von einer E-Maschine der Größe höchstens f(n) akzeptiert wird, sobald L von der D-Maschine der Größe n akzeptiert wird.
In der Arbeit sollen die Resultate bzgl. DEA, NEA, DKA, NKA und LBA erläutert und in Bezug zueinander gesetzt werden. Hierzu gibt es in dem Blog-Eintrag Verweise auf Original-Literatur.
Leitung und Ansprechpartner der Abschlussarbeit
-
New circuit lower bound
Kürzlich wurde in einer Arbeit von R. Williams die Komplexitätsklasse ACC von NEXPTIME getrennt. Der Beweis soll nachvollzogen werden.
Siehe auch: Gödels Lost Letter
Leitung und Ansprechpartner der Abschlussarbeit
-
New circuit lower bound II
Die Permanente ist eine Eigenschaft von Matrizen und ist ganz ähnlich zur Determinante definiert, weist aber interessanterweise sehr unterschiedliche Komplexitätseigenschaften auf. Die bestehenden Resultate über die Komplexität der Permanente sollen zusammengefasst werden.
Siehe auch: Gödels Lost Letter
Leitung und Ansprechpartner der Abschlussarbeit
-
Computational Social Choice Theory
Beziehungen zwischen der Computational Social Choice Theory und der Komplexitätstheorie sollen zusammengefasst werden.
Leitung und Ansprechpartner der Abschlussarbeit
-
Das Matching-Problem
Ein Matching ist eine Teilmenge der Kanten eines Graphen, sodass nie zwei Kanten gewählt wurden, die einen Endpunkt teilen. Ein Matching ist perfekt, wenn jeder Knoten im Graph zu einer Matchingkante gehört.
Das Matching-Problem behandelt die Frage nach der Berechnung eines perfekten Matchings eines Graphen.
Es ist seit dem Algorithmus von Edmonds bekannt, dass das Problem in Polynomialzeit gelöst werden kann.
In dieser Arbeit soll einerseits die Historie der Resultate aufgezeigt und diskutiert werden sowie ein Einblick in die neusten Resultate gegeben werden.
Leitung und Ansprechpartner der Abschlussarbeit
-
Clique und CFG-Parsing
In einer kürzlich veröffentlichen Arbeit von A. Abboud et al. [1] wurde ein überraschender Zusammenhang zwischen dem graphentheoretischen Cliquenproblem und dem Parsen von kontextfreien Sprachen angegeben. Diese Resultate sollen nachvollzogen werden.
Leitung und Ansprechpartner der Abschlussarbeit
-
Fine-grained complexity
In den vergangenen etwa 10 Jahren wurden zahlreiche Beziehungen zwischen Laufzeiten optimaler Algorithmen für kombinatorische Probleme gefunden, z. B. zwischen der Laufzeit des All-pairs-Shortest-Path-Problem und der des Triangle-Problems. Zu dem Themengebiet liegen verschiedene Überblickartikel und Skripten vor (siehe etwa [1]). Ein Überblick über das Gebiet soll verfasst werden.
Leitung und Ansprechpartner der Abschlussarbeit
-
Algebraische Charakterisierungen von Komplexitätsklassen
Von vielen wichtigen Komplexitätsklassen ist bekannt, dass sie aus sehr einfachen Funktionen (Nachfolger, Identität, etc.) mit Hilfe verschiedener Rekursionsschema generiert werden können. Einzelresultate dieses Gebietes sollen dargestellt werden.
Leitung und Ansprechpartner der Abschlussarbeit
Kryptographie
-
Byzantinische Widersacher und perfekte Sicherheit
1988 wurde von Ben-Or, Goldwasser und Wigderson ein wichtiger Meilenstein auf den Gebieten der Kryptographie und des verteilten Rechnens gelegt, indem sie zeigten, dass jede Funktionalität mit perfekter (informationstheoretischer und fehlerfreier) Sicherheit in Gegenwart eines aktiven (byzantinischen) Gegners, der bis zu 1/3 der Parteien kontrolliert, berechnet werden kann. In dieser Arbeit sollen die nötigen Grundlagen sowie dieses Resultat dargestellt und mit Beispielen veranschaulicht werden.
Leitung und Ansprechpartner der Abschlussarbeit
Logik
-
Räuber und Gendarm
Sogannte Räuber und Gendarm Spiele erlaube es die Baumweite eines Graphen spielerisch zu beschreiben. Die Baumweite eines Graphen ist ein Maß dafür, wie nah ein gegebener Graph an der Struktur eines Baumes liegt. Ein Baum hat eine Baumweite von 1. Ein Kreis hat eine Baumweite von 2. Cliquen und Grids erhöhen die Baumweite eines Graphen signifikant. In dieser Arbeit sollen Zusammenhänge von diesen Spielen zu Tseitin Formeln aufgezeigt werden.
Galsi, Talebanfard, Toran: Cops-Robber games and the resolution of Tseitin formulas
Leitung und Ansprechpartner der Abschlussarbeit
-
Unabhängigkeitsresultate
Viele Beziehungen zwischen Komplexitätsklassen sind trotz jahrzehntelanger Forschungen noch ungeklärt; am bekanntesten ist das P-NP-Problem, also die Frage, ob die Klassen P und NP zusammenfallen. In der Logik wurde die Frage untersucht, ob das P-NP-Problem und weitere offene Fragen vielleicht gar nicht mit mathematisch-logischen Mitteln gelöst werden können. Aussagen, die in einer bestimmten logischen Theorie weder bewiesen noch widerlegt werden können, nennt man unabhängig von der Theorie. Erstaunlich einfache Unabhängigkeitsresultate sind bekannt. In dieser Arbeit soll ein Überblick über diese Untersuchungen gegeben werden.
Link: A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory https://arxiv.org/abs/1605.04343
Leitung und Ansprechpartner der Abschlussarbeit
-
Implementierung eines Theorembeweisers für Dependence-Logik
Kürzlich wurde von J. Väänänen eine Erweiterung der Prädikatenlogik, die sog. Dependence-Logik, eingeführt [1]. Das Implikationsproblem ist in Spezialfällen entscheidbar. Der zugehörige Algorithmus soll implementiert werden.
Literatur:
[1] Jouko Väänänen, Dependence Logic - A New Approach to Independence Friendly Logic. London Mathematical Society student texts 70, Cambridge University Press 2007, ISBN 978-0-521-70015-3.
Leitung und Ansprechpartner der Abschlussarbeit
-
Komplexität logischer Theorien
Prädikatenlogische Theorien sind im Allgemeinen unentscheidbar. Für viele bedeutende eingeschränkte Theorien sind jedoch Entscheidungsalgorithmen bekannt. Einzelresultate aus diesem Gebiet sollen nachvollzogen werden. Rein theoretische Abschlussarbeiten, aber auch solche mit Implementationsaspekt sind möglich.
Siehe: Egon Börger et al., The Classical Decision Problem, Springer-Verlag, 1997.
Leitung und Ansprechpartner der Abschlussarbeit
