Lehre
Studien- & Abschlussarbeiten

Studien- und Abschlussarbeiten

Sind Sie auf der Suche nach einem Thema für eine Abschlussarbeit? Wir bieten verschiedene Themen aus vielen Bereichen der Theoretischen Informatik an, darunter Komplexitätstheorie, Kryptographie, Berechenbarkeit und Logik.

THEMEN

Hinweis

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

  • Synthese von Maschinenprogrammen aus Ausführungsspuren

    Eine Ausführungsspur (execution trace) beschreibt die Werte der Variablen des Programms nach jedem Ausführungsschritt für eine bestimmte Eingabe. Durch das Hinzufügen gewisser Informationen zu den Ausführungsspuren kann ein Programm (re)konstruiert werden. Dies ermöglicht eine Alternative Art der Programmierung bei der zuerst Ausführungsspuren generiert werden und dann nach dem Hinzufügen weiterer Informationen ein Programm automatisch abgeleitet wird, welches konsistent mit diesen Spuren ist. In [1] wird diese Vorgehensweise näher beschrieben. In dieser Arbeit soll ein Programm entwickelt werden, welche diese Art der Programmierung unterstützt, indem es aus Ausführungsspuren Programme ableitet.

    [1] Separating Algorithmic Thinking and Programming. Maurice Chandoo (2020) (PDF)

    Leitung und Ansprechpartner der Abschlussarbeit

  • Weisfeiler-Lehman Algorithmus

    Beim Graphenisomorphieproblem (GI) muss entschieden werden, ob zwei gegebene Graphen G=(V,E) und G'=(V',E') isomorph sind. G und G' sind isomorph, falls es eine Abbildung f : V -> V' gibt, sodass für alle Knoten u, v in V gilt: (u,v) in E gdw. (f(u),f(v)) in E'. Trotz großer Forschungsanstrengungen ist nicht bekannt, ob GI in Polynomialzeit lösbar ist. Ein simpler und effizienter Ansatz, um zu testen, ob zwei Graphen nicht isomorph sind, besteht darin, in beiden Graphen jedem Knoten eine Farbe zuzuweisen, wobei zwei Knoten die gleiche Farbe haben, wenn sie die gleiche Anzahl an Nachbarn haben. Falls eine Farbe unterschiedlich oft in beiden Graphen vorkommt, bedeutet dies, dass die Graphen nicht isomorph sein können. Diese sogenannte Graphinvariante kann weiter verfeinert werden, indem man in einer weiteren Iteration den Knoten neue Farben zuweist, welche auf den alten Farben ihrer Nachbarknoten basieren. Nach einer gewissen Anzahl an Iterationen ändern sich die Farben der Knoten nicht mehr. Dieses Verfahren wird Color-Refinement genannt und ist so effektiv, dass es auch in state-of-the-art Programmen (wie z.B. nauty) zum Lösen von GI zum Einsatz kommt. Jedoch gibt es auch Paare von nicht-isomorphen Graphen, welche sich durch diese Methode nicht unterscheiden lassen. In solchen Fällen würde der Color-Refinement Algorithmus fälschlicherweise ausgeben, dass die beiden Graphen isomorph seien. Der k-dimensionale Weisfeiler-Lehman Algorithmus ist eine Verallgemeinerung dieses Verfahrens, bei dem k-Tupel von Knoten betrachtet werden. Für k=1 entspricht dies dem Color-Refinement Algorithmus. In dieser Arbeit soll der k-dimensionale Weisfeiler-Lehman Algorithmus erläutert werden und es soll gezeigt werden, für welche Paare von Graphen der Algorithmus kein korrektes Ergebnis liefert.

    [1] On the Combinatorial Power of the Weisfeiler-Lehman Algorithm. Martin Fürer (2017) (PDF)

    Leitung und Ansprechpartner der Abschlussarbeit

  • Visualisierung von Lindells Isomorphiealgorithmus für Bäume

    Lindells Algorithmus erlaubt es zu überprüfen, ob zwei Bäume isomorph sind und benötigt dafür nur logarithmisch viel Speicherplatz. Um dies zu realisieren, wird auf geschickte Art und Weise eine Rekursion linearer Tiefe durchgeführt, welche stellenweise sogar die Umgebung vorheriger rekursiver Aufrufe ohne Zusatzinformationen vom Call Stack wiederherstellen kann. In dieser Arbeit soll Lindells Algorithmus implementiert und die Ausführung visuell dargestellt werden.

    [1] A logspace algorithm for tree canonization. Steven Lindell (1991) (PDF)

    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)

    [2] Solving Advanced Reasoning Tasks using Quantified Boolean Formulas. Uwe Egly, Thomas Eiter, Hans Tompits, Stefan Woltran (2000)

    Leitung und Ansprechpartner der Abschlussarbeit

Komplexitätstheorie

  • Existenzielle Theorie der reellen Zahlen

    Die ex. Theorie der reellen Zahlen ist die Menge aller wahren prädikatenlogischen Sätze erster Stufe der Gestalt "E x_1 ... E x_n : F(x_1, ... ,x_n)", wobei E für den Existenzquantor steht, F eine quantorenfreie Formel über der Signatur (0,1,+,*,<) ist und der Satz über dem Universum der reellen Zahlen interpretiert wird. Das dazugehörige Entscheidungsproblem besteht darin zu entscheiden, ob ein gegebener Satz dieser Form wahr ist. Die entsprechende Komplexitätsklasse ist definiert als die Menge der Entscheidungsprobleme, welche sich in Polynomialzeit auf dieses Problem reduzieren lassen. Von dieser Komplexitätsklasse ist bekannt, dass sie NP-hart ist und in PSPACE liegt [1]. In dieser Arbeit sollen grundlegende Resultate zu dieser Komplexitätsklasse erläutert werden.

    [1] Some algebraic and geometric computations in PSPACE. John Canny (1988) (Link)

    [2] Complexity of Some Geometric and Topological Problems. Marcus Schaefer (2010) (PDF)

    Leitung und Ansprechpartner der Abschlussarbeit

  • Beweis der Sensitivity Conjecture

    Die Sensitivity s(f) und Block Sensitivity bs(f) messen grob gesagt wie empfindlich eine boolsche Funktion f bezüglich Änderungen der Eingabe ist. Die Sensitivity Conjecture sagt, dass es eine Konstante c > 0 gibt, sodass für jede boolsche Funktion f gilt: bs(f) <= s(f)^C. Diese Vermutung wurde 1989 von Nisan und Szegedy aufgestellt und wurde seitdem intensiv von Forschern untersucht. Kürzlich konnte Hao Huang diese Vemutung beweisen [2]. In dieser Arbeit soll der Beweis nachvollzogen werden und die Implikationen des Resultats für die Komplexitätstheorie erläutert werden.

    [1] Sensitivity Conjecture resolved. Scott Aarson (2019) (Link)

    [2] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Hao Huang (2019) (PDF)

    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

  • Incremental Computation

    Sogenannte inkrementelle Probleme sind parametrisierte Probleme, für die zwei zusätzliche Eingaben Δ und S (neben der üblichen Instanz x und dem Parameter k) definiert werden. Hierbei ist Δ eine Menge an Änderungen an x und der andere ein Zeuge für die Mitgliedschaft von (x,k) zur parametrisierten Sprache.

    In der Abschlussarbeit soll ein Überblick über die betrachteten Probleme mit deren komplexitätstheoretischen Resultaten geliefert werden. Mögliche Literatur:

    • Ramalingam, G., Reps, T.: A categorized bibliography on incremental computation. In: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages POPL’93, pp. 502–510. ACM (1993)
    • Desikan, P., Pathak, N., Srivastava, J., Kumar, V.: Incremental page rank computation on evolving graphs. In: Special interest tracks and posters of the 14th international conference on World Wide Web, WWW’05, pp. 1094–1095. ACM (2005)
    • Held, M., Huber, S.: Topology-oriented incremental computation of voronoi diagrams of circular arcs and straight-line segments. Comput. Aided Des. 41(5), 327–338 (2009)
    • Jakub Ł., Sankowski, P.: Optimal decremental connectivity in planar graphs. Theory of Computing Systems 59(1), 1–17 (2016)
    • sowie https://link.springer.com/article/10.1007/s00224-016-9729-6?no-access=true

    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.

    Link: https://eccc.weizmann.ac.il/report/2017/059/

    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.

    [1] https://epubs.siam.org/doi/pdf/10.1137/16M1061771

    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.

    [1] https://eta.impa.br/dl/194.pdf

    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

  • Parallel permutation-based cryptography

    Einwegpermutationen sind Permutationen, die Einwegfunktionen sind. Solche Funktionen liegen in FP, d.h. sie können effizient berechnet werden. Für die Umkehrung solcher Funktionen ist es allerdings nicht bekannt, ob dies effizient geht. Die Existenz von solchen Funktionen hat auch bedeutende komplexitätstheoretische Konsequenzen.

    In dieser Arbeit sollen die Grundlagen zu diesem Thema dargestellt sowie eine Arbeit von Bertoni und Weiteren untersucht werden. Hier wird eine Pseudozufallszahlenfunktion eingeführt, welche interessante Eigenschaften besitzt.

    Siehe auch https://tosc.iacr.org/index.php/ToSC/article/view/855.

    Leitung und Ansprechpartner der Abschlussarbeit

Logik

  • 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

  • Konstruktive Mengen

    In der mathematischen Logik wurden konstruktive Mengen von Kurt Gödel eingeführt. Grob gesprochen lassen sie sich induktiv durch einfache Operationen definieren. In dieser Arbeit sollen mögliche Anwendungen konstruktiver Mengen in der Komplexitätstheorie untersucht werden.

    Siehe auch: Gödel's Lost Letter

    Leitung und Ansprechpartner der Abschlussarbeit

  • Endliche Modelleigenschaft in modaler Logik

    Endliche Modelleigenschaften spielen in modalen Logiken eine entschiedene Rolle in Fragestellungen bezüglich Komplexität und Entscheidbarkeit. Endliche Modelleigenschaften können durch verschiedene Techniken bewiesen werden. In dieser Arbeit sollen die Filtrations-, sowie die Selektionstechnik untersucht und dargestellt werden.

    Siehe auch Shethmann, Filtration via bisimulation, 2004.

    Leitung und Ansprechpartner der Abschlussarbeit

  • Quantifizierte Boole’sche Formeln

    Quantifizierte Boole‘sche Logik ist zwischen Aussagenlogik und Prädikatenlogik angesiedelt. Wesentliche Aussagen über Erfüllbarkeit, Deduktion und Ausdrucksstärke sollen zusammengefasst werden.

    Literatur:
    H. Kleine-Büning u. Th. Letmann, Propositional Logic: Deduction and Algorithms, Cambridge Tracts in Theoretical Computer Science, Band 48, 1999.

    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

Formale Sprachen und Automaten

  • Äquivalenz von DPDAs

    Die Äquivalenz von deterministischen Kellerautomaten ist entscheidbar. Der Beweis soll nachvollzogen werden.

    Leitung und Ansprechpartner der Abschlussarbeit

  • Maschinelle Analyse eines umfangreichen natürlichsprachlichen Textcorpus

    Mit der Sammlung Tusculum liegt eine umfangreiche Textsammlung lateinischer Texte elektronisch vor. In diesem Themengebiet sollen Werke der Sammlung maschinell analysiert werden, z. B. hinsichtlich

    • Statistische Analyse des Wortschatzes
    • Erstellung von Konkordanzen
    • Formalsprachliche Analyse grammatikalischer Phänomene usw.

    Lateinische Sprachkenntnisse bilden keine notwendige Voraussetzung, wohl aber Programmierkenntnisse und Beherrschen formalsprachlicher Konzepte und Resultate (z. B. aus GThI).

    In diesem Themengebiet sind mehrere Bachelor- und Master-Arbeiten mit unterschiedlichen Gewichtungen von Theorie- und Implementationsaspekten zu vergeben.

    Leitung und Ansprechpartner der Abschlussarbeit


HINWEISE FÜR HAUS-, STUDIEN- UND ABSCHLUSSARBEITEN

Hier finden Sie eine beispielhafte Selbstständigkeitserklärung sowie eine TeX-Vorlage für diese.