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

Komplexitätstheorie

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

    • Darstellung der Grundzüge der mathematischen Matroid-Theorie
    • Darstellung der Zusammenhänge zwischen Matroiden und Greedy-Algorithmen
    • 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:
    Mikkel Abraham et al., The Art Gallery Problem is ∃R-complete, https://dl.acm.org/doi/10.1145/3486220, 2021.
    Saugata Basu et al., Existential Theory of the Reals. In: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol 10. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-33099-2_14

    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:
    Peter Bürgisser, Gorav Jindal, On the Hardness of PosSLP, https://arxiv.org/abs/2307.08008, 2023.
    Eric Allender et al., On the Complexity of Numerical Analysis, https://epubs.siam.org/doi/10.1137/070697926, 2009.

    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

    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

  • Logische Beschreibung verborgener Variablen in der Quantenphysik

    In der Quantenmechanik werden nicht erklärbare oder zufällige Phänomene teilweise auf das Vorhandensein sog. verborgener Variablen oder Parameter zurückgeführt. Die sog. Teamlogik erlaubt eine rein logische Beschreibung und Analyse dieser Phänomene. Ein Überblick über das Gebiet soll gegeben werden.

    Literatur:

    Rafael Albert und Erich Grädel, Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of Dependence and Independence, www.sciencedirect.com/science/article/pii/S0168007222000021, 2022.

    Leitung und Ansprechpartner der Abschlussarbeit
  • Teamlogik und Semantik natürlicher Sprachen

    In der Linguistik wird seit einigen Jahren die mathematische Logik verwendet, um die Semantik natürlicher Sprachen zu beschreiben. Insbesondere findet hier die sog. Teamlogik Anwendung. Ergebnisse aus diesem neuen Forschungsbereich sollen vorgestellt und zusammengefasst werden.


    Literatur:
    Maria Aloni, Logic and Conversation: The Case of Free Choice, https://semprag.org/index.php/sp/article/view/sp.15.5, 2022.
    Maria Aloni et al., State-based Modal Logics for Free Choice, https://www.researchgate.net/publication/370937884_State-based_Modal_Logics_for_Free_Choice, 2023.

    Leitung und Ansprechpartner der Abschlussarbeit
  • Logische Beschreibung verborgener Variablen in der Quantenphysik

    In der Quantenmechanik werden nicht erklärbare oder zufällige Phänomene teilweise auf das Vorhandensein sog. verborgener Variablen oder Parameter zurückgeführt. Die sog. Teamlogik erlaubt eine rein logische Beschreibung und Analyse dieser Phänomene. Ein Überblick über das Gebiet soll gegeben werden.

    Literatur:
    Rafael Albert und Erich Grädel, Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of Dependence and Independence, https://www.sciencedirect.com/science/article/pii/S0168007222000021, 2022.

    Leitung und Ansprechpartner der Abschlussarbeit
  • 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

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