Arbeitsgruppe Theoretische Informatik

Abschlussarbeiten

Falls Sie bei uns eine Abschlussarbeit schreiben möchten, bieten wir Ihnen die Möglichkeit ein individuelles Thema zu bearbeiten. Sprechen Sie uns einfach an!

Zudem haben wir einige Themenvorschläge ausgearbeitet, die wir Ihnen hier präsentieren möchten. Wenn Ihnen eines gefällt, melden Sie sich beim angegebenen Ansprechpartner.

Bachelorarbeiten

Hier finden Sie einige Themenvorschläge für Bachelorarbeiten für 1-Fach-Bachelor Informatik.

Algorithmen zur Entscheidung von Informationsflusssicherheit

Ansprechpartner: Oliver Woizekowski

Noninterference beschreibt die Abwesenheit von sicherheitskritischen Informationsflüssen. In dieser Arbeit sollen Sie Algorithmen zum Testen einiger Varianten von Noninterference in der Programmiersprache Haskell implementieren. Testen bedeutet hier, zu überprüfen, ob in einem gegebenen System Noninterference vorliegt.

Analyse eines Kartensystems zur Kundenbindung

Ansprechpartner: Björn Kinscher

In dieser Bachelorarbeit sollen Sie ein Mifare-Classic-gestütztes System zur Kundenbindung analysieren. Dafür müssen Sie zunächst bekannte Angriffe auf Mifare Classic nachvollziehen und auf dieses System anwenden. Darüber hinaus müssen die applikationsspezifischen Daten untersucht werden.

Quellen (als Einstieg)

  1. www.cs.ru.nl/~flaviog/publications/Attack.MIFARE.pdf
  2. www.cs.ru.nl/~flaviog/publications/Dismantling.Mifare.pdf
  3. www.cs.ru.nl/~flaviog/publications/Pickpocketing.Mifare.pdf

Offline Dynamic Graph Drawing of Trees: Stabilität von Layouts

Ansprechpartner: Malte Skambath 

Aufgrund der häufigen Nutzung von Graphen zur Modellierungen, sowie für Datenstrukturen ist das automatisierte Zeichnen von Graphen [3]
in übersichtlicher und "schöner" Form wünschenswert. Neben statischen Graphen bietet es sich bei zeitlich veränderlichen Graphen an eine Folge von Zeichnungen zu erzeugen oder zu animieren. Dabei ergeben sich zusätziche Probleme. 
Beim Offline Ansatz, wenn der vollständigen Zeitverlauf eines Graphens bekannt ist, kann es wünschenswert sein bestimmte Bewegungen von Knoten zu verhindern [1]. 

Im Rahmen dieser Arbeit sollen verschiedene Strategien zum Reduzieren von Bewegungen gefunden, untersucht, sowie deren Nutzen evaluiert werden. Betrachtet werden können dabei sowohl die Machbarkeit (Berechnbarkeit/Komplexität) wie auch berechenbare Metriken (Stabilität) oder durch Umfragen möglicherweise erfassbare Kriterien zur Evaluierung der Ergebnisse.

Quellen

  1. M. Skambath and T. Tantau, 
    Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
    In Proc. of the 24th International Symposium on Graph Drawing & Network Visualization 2016 (GD2016),
    in Lecture Notes in Computer Science Vol. 9801, p. 572-586, Springer-Verlag, 2016. 
    https://arxiv.org/abs/1608.08385
  2. E. M. Reingold, J. S Tilford,
    Tidier Drawings of Trees. 
    IEEE Transactions on Software Engineering. Vol. 7, Issue 2, 1981.
  3. Wikipedia: Graph Drawing

Implementierung und Vergleich exakter paralleler Algorithmen für Vertex Cover

Ansprechpartner: Malte Skambath 

Das Vertex-Cover- oder Knotenüberdeckungsproblem [1] ist ein Standardbeispiel für ein NP vollständiges und insbesondere auch FPT Problem [2]: Gegeben ein Graph und eine Zahl k, gibt es eine Knotenmenge (das Vertex-Cover) aus dem Graphen mit höchstens k Knoten, sodass jede Kante mindestens einen Knoten aus der Menge besitzt, also abgedeckt ist.

Im Rahmen dieser Arbeit sollen parametresierte parallele Algorithmen für Vertex Cover implementiert und verglichen werden.

Quellen

  1. Wikipedia (EN): Vertex Cover
  2. Wikipedia: Parametrisierter Algorithmus

Masterarbeiten

Hier finden Sie einige Themenvorschläge für Masterarbeiten für 1-Fach-Master Informatik.

Offline Dynamic Graph Drawing: Algorithmen für komplexere Graphen

Ansprechpartner: Malte Skambath 

Aufgrund der häufigen Nutzung von Graphen zur Modellierungen oder Datenstrukturen ist das automatisierte Zeichnen von Graphen [3]
in übersichtlicher und "schöner" Form wünschenswert. Neben statischen Graphen bietet es sich bei zeitlich veränderlichen Graphen als eine Folge von Zeichnungen zu erzeugen oder zu animieren. Dabei ergeben sich zusätziche Probleme. 
Es gibt bisher wenige Offline Algorithmen, die für konkrete Graphklassen unnötige Bewegungen von Knoten verhindern [1]. In [1] wurde gezeigt, dass unter gewissen Einschränkungen solche Ansätze möglich und der rekursive Algorithmus von Reingold und Tilford [2] verallgemeinert.

In dieser Arbeit sollen neue Ansätze/Algorithmen beziehungsweise deren Machbarkeit für komplexere Graphklassen wie seriell-parallele Graphen untersucht werden.
Diese können ggf. rekursive Layoutstrategien für statische Graphen basieren und verallgmeinern.

Quellen

  1. M. Skambath and T. Tantau, 
    Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
    In Proc. of the 24th International Symposium on Graph Drawing & Network Visualization 2016 (GD2016),
    in Lecture Notes in Computer Science Vol. 9801, p. 572-586, Springer-Verlag, 2016. 
    https://arxiv.org/abs/1608.08385
  2. E. M. Reingold, J. S Tilford,
    Tidier Drawings of Trees. 
    IEEE Transactions on Software Engineering. Vol. 7, Issue 2, 1981.
  3. Wikipedia: Graph Drawing

 

Verschlüsselung moderner Messenger

Ansprechpartner: Björn Kinscher

In dieser Masterarbeit analysieren und vergleichen Sie die Sicherheit moderner Messenger, z. B. das Signal Protocol (Signal, WhatsApp) und die Protokolle Threema und Telegram.

NP-intermediate

Ansprechpartner: Fabian Müller

Eine der wichtigsten offenen Fragen in der Theoretischen Informatik ist, ob P = NP gilt. Wir betrachten in diesem Kontext eine Menge von Problemen, die man als NP-intermediate bezeichnet. Dabei handelt es sich um Probleme, für die man bisher nur zeigen konnte, dass sie in NP liegen, aber nicht NP-vollständig sind.

Ziel der Arbeitet ist es, eine Übersicht über besagte Probleme zu schaffen.

Quellen

  1. http://dl.acm.org/citation.cfm?doid=321864.321877
  2. http://gustavnordh.com/blowing_holes_revised.pdf