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

  • 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

Komplexitätstheorie

  • Kommunikationskomplexität

    In der Kommunikationskomplexität untersucht man den Kommunikationsaufwand, der erforderlich ist, um ein Problem zu lösen, wenn die Eingabe für das Problem auf zwei oder mehr Parteien verteilt ist. Ein Überblick über das Gebiet soll erarbeitet werden.

    Literatur:

    • Anup Rao, Amir Yehudayoff, Communication complexity and applications, Cambridge, 2020.  
    • Eyal Kushilevitz, Noam Nisan, Noam, Communication complexity. Cambridge, 2006.
    Leitung und Ansprechpartner der Abschlussarbeit
  • Die Klasse TFNP

    Die Klasse TFNP besteht aus den totalen Funktionen, die in nichtdeterministischer Polynomialzeit berechnet werden können. Das heißt, es handelt sich um die Klasse der Funktionsprobleme, für die garantiert eine Antwort vorliegt, und diese Antwort kann in Polynomialzeit überprüft werden. Die Abkürzung TFNP steht für „Total Function Nondeterministic Polynomial“. Die wesentlichen komplexitätstheoretischen Resultate über diese Klasse sollen zusammengetragen werden.

    Literatur:

    Leitung und Ansprechpartner der Abschlussarbeit
  • Lifting in der Komplexitätstheorie

    Ein Lifting-Theorem ist ein Satz, der eine untere Schranke in einem schwachen Berechnungsmodell in eine untere Schranke in einem starken Modell übersetzt. Ein Überblick über verschiedene derartige Resultate soll erarbeitet werden.

    Literatur:

    Leitung und Ansprechpartner der Abschlussarbeit
  • Problemkerne

    Das Konzept der Problemkerne (engl. problem kernels) in der Komplexitätstheorie bezieht sich auf die Reduktion eines Problems auf eine kleinere, äquivalente Instanz, deren Größe nur von einem Parameter abhängt und nicht von der gesamten Eingabegröße. Diese Reduktion erfolgt durch Datenreduktionsregeln, die in polynomieller Zeit anwendbar sind und die ursprüngliche Instanz auf eine kleinere Instanz reduzieren, die denselben Parameterwert beibehält. Ein Problemkern ist somit der "schwierige" Teil einer Instanz eines NP-schweren Problems, der nach Anwendung der Reduktionsregeln übrig bleibt. Probleme, die in der Klasse FPT (Fixed-Parameter Tractable) liegen, besitzen Problemkerne, deren Größe durch eine Funktion des Parameters beschränkt ist. Die Methode der Problemkern-Reduktion ist besonders nützlich, um die Laufzeit von Algorithmen für schwierige Probleme zu verbessern, indem die Größe der zu bearbeitenden Instanz reduziert wird. In der Arbeit sollen die Grundlagen und Konzepte zu Problemkernen dargestellt werden.

    Literatur:

    • Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013, ISBN 978-1-4471-5558-4, pp. I-SSS, 3-707
    Leitung und Ansprechpartner der Abschlussarbeit
  • Enumeration

    In der Informatik lassen sich viele Probleme so modellieren, dass aus gewissen Basiselementen durch festgelegte Operationen (Abschlussoperationen) neue Elemente generiert werden. Für verschiedene Spezialfälle ist die genaue Komplexität der Aufzählung aller generierten Elemente bekannt. Die Resultate sollen wiedergegeben werden.

    Literatur:

    • Arnaud Mary ORCID und Yann Strozecki, Efficient enumeration of solutions produced by closure operations, dmtcs.episciences.org/5549, 2019
    Leitung und Ansprechpartner der Abschlussarbeit
  • Matroide und Greedy-Algorithmen

    Matroide sind mathematische Strukturen, in denen Abhängigkeiten zwischen Elementen herrschen. Sie finden Anwendung in vielen Bereichen der Informatik, insbesondere der kombinatorischen Optimierung und Graphentheorie. Die Existenz von Greedy-Algorithmen für algorithmische Probleme kann oft auf eine zugrundeliegende Matroid-Struktur zurückgeführt werden.  
    In diesem Bereich sind einige Abschlussarbeiten zu vergeben. Mögliche Themen sind:

    1. Darstellung der Grundzüge der mathematischen Matroid-Theorie
    2. Darstellung der Zusammenhänge zwischen Matroiden und Greedy-Algorithmen
    3. Darstellung und Analyse beispielhafter Algorithmen, bspw. das Berechnen von Spannbäumen oder das Finden aller Kreise eines Graphen.

     

    Literatur:

    • D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London, New York, San Francisco 1976.  
    • Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, Englewood Cliffs (NJ) 1982.  
    • L. Khachiyan, On the Complexity of Some Enumeration Problems for Matroids, https://doi.org/10.1137/S0895480103428338, 2006.
    Leitung und Ansprechpartner der Abschlussarbeit
  • Die Komplexität der Theorie der reellen Zahlen

    Die Klasse ETR (oder auch ∃R) besteht aus allen Sprachen, die sich auf die Frage der Gültigkeit von Formeln über den reellen Zahlen mit Existenzquantor reduzieren lassen. Die Klasse ist zwischen NP und PSPACE angesiedelt. Sie enthält viele kontinuierliche geometrische Probleme, die sich als Verallgemeinerungen von NP-vollständigen Sprachen auf den reellen Grundbereich ergeben. Strukturelle Beziehungen und Vollständigkeitsresultate sollen zusammengefasst und dargestellt werden.


    Literatur:

    Leitung und Ansprechpartner der Abschlussarbeit
  • Die Komplexität der Numerik

    Bei dem Problem PosSLP geht es darum festzustellen, ob eine ganze Zahl, die durch ein gegebenes nicht-verzweigendes Programm (engl. straight line program) berechnet wird, positiv ist. Dieses Problem charakterisiert die Komplexität vieler mit numerischen Berechnungen definierten Problemen. Allerdings ist die genaue Komplexität von PosSLP unbekannt, lediglich verschiedene untere und obere Schranken sind bekannt, die in dieser Arbeit wiedergegeben werden sollen.

    Literatur:

    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.

    Literatur:

    Leitung und Ansprechpartner der Abschlussarbeit
  • Eine faszinierende Methode für untere Schranken für Schaltkreise

    Das von Ryan Williams 2010 erzielte vielleicht bahnbrechendste Resultat der Komplexitätstheorie der letzten vier Jahrzehnte betrifft Schranken der Berechnungskraft von sog. ACC-Schaltkreisfamilien, Schaltkreisfamilien konstanter Tiefe, die neben den üblichen Gattern für Konjunktion, Disjunktion und Negation auch Gatter für Modulo-Tests verwenden dürfen. Das Resultat soll nachvollzogen werden. Der Beweis beruht auf einem sehr überraschenden Zusammenhang, in dem eine obere Schranke zu einer unteren Schranke führt: Williams zeigt, dass für viele Schaltkreisklassen schnellere Satisfiability-Algorithmen zu unteren Schranken führen.

    Literatur:

    Leitung und Ansprechpartner der Abschlussarbeit
  • Computational Social Choice Theory

    Beziehungen zwischen der Computational Social Choice Theory und der Komplexitätstheorie sollen zusammengefasst werden.

    Literatur:

    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


Hinweise für Haus-, Studien- und Abschlussarbeiten

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