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

  • Ein SAT-Algorithmus, der besser ist als man denkt.

    Der Algorithmus von Paturi, Pudlak, Sacks und Zane war für eine lange Zeit der schnellste, bekannte Algorithmus für k-SAT. Aktuelle Untersuchungen zeigen, dass der Algorithmus exponentiell besser ist als bisher bekannt. In dieser Arbeit sollen die neusten Entwicklungen und Erkenntnisse nachvollzogen und zusammengefasst präsentiert werden.

    Quelle: https://eccc.weizmann.ac.il/report/2021/069/

    Leitung und Ansprechpartner der Abschlussarbeit

  • Die Komplexität von Go

    Go ist ein 2-Spieler Strategiespiel, welches auf einem 19x19 Brett gespielt wird. 1983 wurde bewiesen, dass die Komplexität von (verallgemeinertem) Go - also die Frage, ob Schwarz von einer gegebenen Position einen Sieg erzwingen kann - EXPTIME vollständig ist. Der Beweis dafür, welcher sich durch mehrere Papers zieht, soll nachvollzogen und präsentiert werden. Das genannte Resultat gilt nur für eine bestimmte Variante des Spiels. (Ohne die sogenannte "Superko-Regel".) Diese Einschränkung soll erklärt werden und es soll untersucht werden, ob sich diese Lücke schließen lässt. Dieses Thema ist vorrangig für eine Masterarbeit geeignet.

    Ansprechpartner der Abschlussarbeit

    Leitung 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

  • Diagonalisierungsspiele

    Diagonalisierungsargumente sind beispielweise im Rahmen des Halteproblems oder auch bei dem Platzhierarchiesatz das Mittel zum Beweis. In einer aktuellen Arbeit (Alon et al., Diagonalization Games, ECCC, TR23-002; https://eccc.weizmann.ac.il/report/2023/002/) werden eine Reihe von kombinatorischen Spielen untersucht, welche auf Cantors Idee basieren. In der Arbeit sollen die Beweise nachvollzogen, präsentiert und die Resultate (sprich auch die unterschiedlichen Spiele) an eigenen Beispielen illustriert werden.

    Leitung und Ansprechpartner der Abschlussarbeit

  • Boole’sche Erfüllbarkeitsprobleme höherer Ordnung

    Das bekannte aussagenlogische Erfüllbarkeitsproblem wurde kürzlich erweitert, in dem Variablen nicht nur für Boole’sche Werte sondern für Boole’sche Funktionen oder Funktionen höherer Ordnung stehen. Die bekannten Komplexitätsresultate sollen nachvollzogen werden.

    Siehe: Dmitry Chistikov, Christoph Haase, Zahra Hadizadeh and Alessio Mansutti, Higher-Order Boolean Satisfiability, MFCS 2022, https://www.ac.tuwien.ac.at/mfcs2022/

    Leitung und Ansprechpartner der Abschlussarbeit

  • Sehr große Komplexitätsklassen

    Hierarchien von Komplexitätsklassen, deren Ressourcenschranke nicht elementar ist, d.h. schneller wächst als jeder Turm von Exponentialfunktionen fester Höhe, werden in einer Arbeit von S. Schmitz untersucht. Eine neue Komplexitätsklasse TOWER spielt eine wichtige Rolle. Die Ergebnisse sollen zusammengefasst werden.

    Siehe: Sylvain. Schmitz, Complexity Hierarchies beyond Elementary, https://doi.org/10.1145/2858784.

    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

  • Computational Social Choice Theory

    Beziehungen zwischen der Computational Social Choice Theory und der Komplexitätstheorie sollen zusammengefasst 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.

    [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

Aktuell leider keine Themenvorschläge vorhanden.

Logik

  • Strukturierte Neuronale Netze

    Klassen neuronaler Netze, die eine innere Struktur aufweisen, werden derzeit stark untersucht. Die bestehende Literatur soll gesichtet und zusammengefasst werden. 

    Siehe: Gustav Šír, From Graph ML to Deep Relational Learning, https://towardsdatascience.com/from-graph-ml-to-deep-relational-learning-f07a0dddda89

    Leitung und Ansprechpartner der Abschlussarbeit

  • Neuronale Netze und Logik

    Die Berechnungskraft gewisser Klassen neuronaler Netze (sog. Graph Neural Networks) wurde kürzlich mit Hilfe der Modallogik und der Prädikatenlogik mit zwei Variablen charakterisiert. Die Resultate sollen nachvollzogen und möglichst erweitert werden.

     

    Siehe: Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, Juan Pablo Silva,

    The Logical Expressiveness of Graph Neural Networks, https://openreview.net/forum?id=r1lZ7AEKvB.

    Leitung und Ansprechpartner der Abschlussarbeit

  • Bipolare Argumentation Frameworks

    Abstract Argumentation ist ein Framework, in dem Argumente und deren Beziehungen zueinander graphisch modelliert. Die Argumente sind Knoten wohingegen die Kantenrelation darstellt, welche Argumente sich gegenseitig angreifen. Nun wird nach Knotenteilmengen gesucht, welche bestimmte Eigenschaften haben (z.B. dass die Menge sich gegen die Argumente von außerhalb verteidigt). In dieser Arbeit beschäftigt man sich mit einer neuen Erweiterung dieses Frameworks und die Resultate sollen nachvollzogen und präsentiert werden.

    Quelle: https://arxiv.org/abs/1903.01964

    Leitung und Ansprechpartner der Abschlussarbeit

  • Claim-Augmented Argumentation Framewoks

    Abstract Argumentation ist ein Framework, in dem Argumente und deren Beziehungen zueinander graphisch modelliert. Die Argumente sind Knoten wohingegen die Kantenrelation darstellt, welche Argumente sich gegenseitig angreifen. Nun wird nach Knotenteilmengen gesucht, welche bestimmte Eigenschaften haben (z.B. dass die Menge sich gegen die Argumente von außerhalb verteidigt). In dieser Arbeit beschäftigt man sich mit einer neuen Erweiterung dieses Frameworks und die Resultate sollen nachvollzogen und präsentiert werden.

    Quelle: https://ojs.aaai.org/index.php/AAAI/article/view/16782

    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

  • 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.

    In diesem Bereich sind nur noch einzelne Fragestellungen als Thema für eine Abschlussarbeit verfügbar - sprechen Sie uns diesbezüglich bei Interesse einfach an.

    Siehe: Egon Börger et al., The Classical Decision Problem, Springer-Verlag, 1997.

    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.