Bachelor- und Masterarbeit

  • Eine Abschlussarbeit steht in Verbindung mit Forschungs- (oder Interessen-) Gebieten des Instituts.
  • Eine gute Vorbereitung für eine Abschlussarbeit ist die vorherige Teilnahme an entsprechenden Vorlesungen/Hauptseminaren.
  • Themen werden auf dieser Seite angekündigt. Eigene Themenvorschläge sind auch willkommen. Setzen Sie sich mit einem möglichen Betreuer in Verbindung.
  • Formalien: 2 Gutachter notwendig, einer davon Professor oder Privatdozent.

Wie sieht eine Abschlussarbeit in der Theoretischen Informatik aus?

  • Literaturarbeit: Ausgangspunkt ist oft eine Arbeit von einer Konferenz (FOCS, STOC, ...), in der ein neues/interessantes Themenfeld besprochen wird. Man kann (leider) nicht davon ausgehen, dass in diesen Konferenzartikeln "schon alles drinsteht". Deswegen: Literaturrecherche, Beweislücken ausfüllen, eigene Konzepte/Beweisvereinfachungen einbringen, ... womöglich sogar eigene Resultate. Möglicherweise ist das darzustellende Ergebnis "verteilt" über mehrere Literaturstellen, unterschiedliche Terminologien ...

oder:

  • Implementierung von theoretischen Resultaten, Optimierung, Auswertung, ... auch kombiniert mit entsprechender Literaturarbeit.

 

Mögliche Themen und Themengebiete für eine Abschlussarbeit (z.T. Beispiele für bereits vergebene Themen)

Automatische Programmanalyse

Die Idee ist, dass man die noch fehlenden Befehle in die Maske eines kleinen Schleifen-Programm eingibt:
       Angabe, was die Eingabe- und was die Hilfsvariablen sind.
       Wie werden die Hilfsvariablen initialisiert.
       Dann Durchlauf einer Schleife:
        while (...)
       {  Wertzuweisung_1 ;   ...  ; Wertzuweisung_k ;  }
Diese Wertzuweisungen dürfen aus plus, minus, und konstanten Faktoren bei den Variablen bestehen und  weisen den Eingabe- bzw. Hilfsvariablen neue Werte zu.  Herauskommen soll (symbolisch!), was das Rechenergebnis ist.
Zum Beispiel dieses Programm (vgl. S. 119 in Mathe-Toolbox von Schöning/Kestler):
       a=0 ;
       b=1 ;
       while (a<=n)
       { a=a+b; b=a-b; }

Das zu konzipierende Programm nimmt dieses Programm als Eingabe und liefert die explizite Formel  für die Fibonacci-Folge als Endwert von a (vgl. S. 118, Mathe-Toolbox).  Wie man das leicht "von Hand" mittels erzeugender Funktionern (bzw. Z-Transformation)  und Partialbruchzerlegung  machen kann, wird im Buch beschrieben. Was man "von Hand" machen kann,  müsste auch ein Computer erledigen können.

Einwegfunktionen

Intuitiv ist eine Funktion eine Einwegfunktion, wenn sie effizient berechenbar ist, jedoch die Umkehrfunktion nicht effizient berechnet werden kann. Es gibt viele formale Definitionen, die diese Intuition präzisieren, insbesondere muss festgelegt werden, ob die betreffende Funktion injektiv ist, ob die Funktionswerte in etwa dieselbe Länge wie die Eingangswerte haben, ob die Einwegfunktion eine "Falltürfunktion" ist, so dass mit einem geeigneten Schlüssel doch effizient invertiert werden kann,  und in welchem Sinne die nicht-effiziente Berechenbarkeit gemeint ist. Es sollen in dieser Arbeit die verschiedenen Definitionen dargestellt und untersucht werden. Manche Annahmen über die (Nicht-)Existenz von bestimmten Einwegfunkionen haben Konsequenzen für die Relation bestimmter Komplexitätsklassen bzw. für die Existenz von Pseudozufallszahlengeneratoren. (Betreuer: Prof. Dr. Uwe Schöning)

Pollards Rho-Algorithmus

Dieser (Typ von) Algorithmus verwendet Pseudozufallszahlen, um effizient "cycle detection" durchführen zu können. Andererseits wird das Phänomen des Geburtstagsparadoxons ausgenutzt, welches (im Prinzip) ideale Zufallszahlen voraussetzt. In diesem Projekt sollen die Einflüsse verschiedener Pseudozufallszahlengeneratoren, sowie verschiedener Formen des cycle detection auf die Effizienz des Verfahrens untersucht werden.

Kryptografische Hypothesen

Nahezu alle kryptografischen Verfahren beruhen auf nach wie vor unbewiesenen Hypothesen, dass nämlich bestimmte algorithmische Probleme nicht effizient lösbar sind. Manche dieser Hypothesen sind in gewissem Sinne äquivalent, andere dagegen nicht, oder vermutlich nicht. Derartige algorithmische Probleme sind: Faktorisieren, modulares Quadratwurzelziehen, diskreter Logarithmus, Diffie-Hellman-Problem, RSA-Problem, quadratische Reste-Problem, u.a.m.. In dieser Arbeit sollen diese Probleme dargestellt, miteinander verglichen werden (zum Beispiel bzgl. deterministischer oder probabilistischer Orakel-Reduzierbarkeit). (Betreuer: Prof. Dr. Uwe Schöning)

Schema-Theorem

Es gibt im Kontext von evolutionären/genetischen Algorithmen kaum theoretische Ergebnisse über die Komplexität bzw. Konvergenz derartiger Algorithmen. Eine Ausnahme ist das Schema-Theorem von John Holland, obwohl auch dieses in verschiedener Weise hinterfragt und interpretiert werden kann. Diese Arbeit soll das Schema-Theorem beweisen, kritisch hinterfragen und evtl. nach alternativen Formulierungen suchen. (Betreuer: Prof. Dr.  Uwe Schöning)

Expandergraphen

Expandergraphen sind Graphen mit extremen Verbindungseigenschaften: Für jede Teilmenge von Knoten (bis zur einer bestimmten Mächtigkeit, oder entnommen aus einer bestimmten Teilmenge aller Knoten) gibt es mindestens eine bestimmte Anzahl von Nachbarn im Rest des Graphen. Gleichzeitig haben diese Graphen aber nur vergleichsweise wenige Kanten (linear in der Anzahl der Knoten). Solche Expandergraphen sind die Grundbausteine für komplexere Graphenfamilien wie z.B. Superkonzentratoren. Die Existenz solcher Expandergraphen - oder daraus abgeleiteten Graphen - bildet oftmals den Kern von untere-Schranken-Beweisen (für die Länge von Resolutionsbeweisen, Pebble-Strategien oder für Schaltkreise) oder Algorithmen-Derandomisierungen.
Die Existenz von Expandern kann man entweder mit einer probabilistischen Konstruktion (oder ähnlich: mittels Kolmogorov-Komplexität) nachweisen. In manchen Fällen ist aber eine "explizite effiziente Konstruktion" unumgänglich, auch hier sind einige Konstruktionsprinzipien bekannt. Darüber hinaus gibt es einen algebraischen Zugang zu Expandergraphen, indem man die Eigenwerte der Adjazenzmatrix inspiziert. Das Thema liefert insgesamt Material für mehrere Abschlussarbeiten, man könnte sich z.B. konzentrieren auf:

  • probabilistische Konstruktionsmethoden für Expandergraphen
  • deren Einsatz bei unteren Schranken
  • explizite Konstruktionen
  • den algebraischen Zugang über den zweit-größten Eigenwert der Adjazenzmatrix

(Betreuer: Prof. Dr. Uwe Schöning)

Universal Hashing

Universal Hashing ist eine Methode, um aus einer geeignet gewählten (möglichst kleinen) Klasse von Hashfunktionen eine davon zufällig auszuwählen mit dem Zweck, die Verteilung der Hashwerte einer Gleichverteilung anzunähern - unabhängig von der Verteilung der Schlüsselwerte. Es gibt verschiedenartige
Konstruktionen von universalen Hashfunktionklassen, sowie verschiedene Varianten der Definition von "universale Hashklasse". Diese Abschlussarbeit soll diese Begriffe, Definitionen und Eigenschaften von Universal Hashing systematisch durchforsten, auflisten und Beweise nachvollziehen. (Betreuer: Prof. Dr. Uwe Schöning)

Paarweise Unabhängigkeit

Bei der Analyse von probabilistischen Algorithmen geht man normalerweise von zugrunde liegenden Zufallszahlen aus, die vollständig unabhängig sind und aus der jeweiligen Grundmenge gleichverteilt gezogen werden. Tatsächlich verwendet man in der Praxis aber Pseudozufallszahlengeneratoren, die diese Eigenschaften nicht oder nur in beschränktem Umfang haben. Eine schwächere Form der Zufälligkeit liegt vor, wenn man nur paarweise Unabhängigkeit der verwendeten Zufallszahlen zur Verfügung hat. In vielen Fällen zeigt sich jedoch, dass paarweise Unabhängigkeit für die Algorithmenanalyse bereits ausreichend ist - oder zu ähnlichen Ergebnissen führt wie vollständige Unabhängigkeit. Darüber hinaus können n paarweise unabhängige Zufallszahlen aus ca. log n "echten" Zufallszahlen erzeugt werden. Diese Abschlussarbeit soll dieses Konzept der paarweisen Unabhängigkeit näher beleuchten und feststellen, in welchen Fälen paarweise Unabhängigkeit (fast) genausogut ist wie vollständige Unabhängigkeit. (Betreuer: Prof. Dr. Uwe Schöning)

SAT-Solver

SAT-Solver sind Algorithmen, die zu einer gegebenen Boole'schen Formel in KNF, eine erfüllende Belegung suchen. Effiziente Verfahren hierfür sind aus mehreren (theoretischen und praktischen) Gründen von großem Interesse. Auf der einen Seite gibt es die Suche nach einem theoretisch optimalen Verfahren, d.h. einem Algorithmus, dessen Laufzeit im worst-case nachweislich möglichst gut ist. Auf der anderen Seite werden diese Verfahren aber auch implementiert und es zeigt sich, dass "in der Praxis" nicht nur die Konzepte gut sind, bei denen sich das auch beweisen lässt. Sondern es werden Heuristiken für die Suche nach einer Lösung verwendet, die sich einfach bei Experimenten als gut bewiesen haben. Als Abschlussarbeit können diese Heuristiken genauer untersucht werden und dann auch verbessert werden, indem Parameter experimentell optimiert werden. (Betreuer: Prof. Dr. Uwe Schöning)

Implementierung eines deterministischen 3-Färbbarkeitsalgorithmus

Innerhalb dieser Abschlussarbeit soll der Algorithmus von Beigel und Eppstein für das 3-Färbbarkeitsproblem implementiert werden (bis dato sind keine Implementierungen bekannt). Es handelt sich dabei um einen deterministischen Backtracking-Algorithmus mit einer sehr komplexen Fallunterscheidung, dessen Worst-Case-Laufzeit O(1.328n) beträgt. Die Vermutung liegt nahe, dass er in der Praxis weitaus bessere Ergebnisse erzielt, da die Worst-Case-Fall-Instanzen sehr unwahrscheinlich sind. (Betreuer: Prof. Dr. Uwe Schöning, Adrian Balint)

Lovasz Local Lemma (LLL)

Wenn man auf probabilistischen Weg die Existenz eines gewissen kombinatorischen Objekts zeigen will, so muss man oft nachweisen, dass das erwünschte Objekt die (schlechten) Eigenschaften E_1, E_2,...,E_n alle nicht hat.
Sofern diese Eigenschaften stochastisch vollständig unabhängig sind und für alle E_i gilt Pr(E_i)<1, so folgt die Existenz des gesuchten Objekts durch einfache Wahrscheinlichkeitsrechnung.
Trivial folgt die Existenz auch, wenn n und p sehr klein sind, np<1. Das LLL führt den Existenznachweis auch dann, wenn die gegebenen Voraussetzungen zwischen diesen beiden Extremen liegen. Darüber hinaus gibt es eine konstruktive, also effiziente Version des LLL, bei der - allerdings unter stärkeren Voraussetzungen -
das gesuchte Objekt effizient konstruiert werden kann. Eine Anwendung findet diese Methode bei einem SAT-Algorithmus (das gesuchte Objekt ist hier eine erfüllende Belegung; die negativen Eigenschaften ergeben sich aus den Klauseln).
Einstieg in das Thema ist ein entsprechender Abschnitt in dem Buch Mitzenmacher/Upfal: "Probability and Computing". Inzwischen wurden einige sehr überraschende neue Ergebnisse zu LLL von Robin Moser (ETH) erzielt. (Betreuer: Prof. Dr. Uwe Schöning)

Die Methode Branch-and-Bound

Branch and bound ist eine flexible Technik, um Lösungsverfahren zu entwickeln, insbesondere für schwierige (NP-vollständige)  Optimierungsprobleme. Es müssen verschiedene Entwurfsentscheidungen getroffen werden: die Darstellung der Baumstruktur (die Art der  Verzweigung), die Berechnung der Bounds  (z.B. mittels Relaxation). Darüber hinaus kann die Basisversion von Branch-and-Bound  mit weiteren Strategien oder Heuristiken angereichert werden. Eng verwandt ist B+B auch mit dem heuristischen A*-Algorithmus aus  der KI.  Das relative Verhalten verschiedener B+B Implementierungen kann mittels Dominanzrelationen verglichen werden.  Diese Abschlussarbeit soll die Methode B+B mit ihren Varianten möglichst allgemein, aber auch illustriert an Beispielen, beschreiben  und existierende theoretische oder experimentelle Ergebnisse hierzu darstellen.  (Betreuer: Prof. Dr. Uwe Schöning)

Sequenzanalyse

Wir haben laufend aktuelle Themen auf dem Gebiet Sequenzanalyse, bei Interesse geben wir gerne nähere Informationen. (Betreuer: Prof. Dr. Enno Ohlebusch mit Timo Beller).

SAT Preprozessor SATELITE

Ein SAT-Solver ist ein Algorithmus, der zu einer gegebenen aussagenlogischen Formel eine erfüllende Belegung sucht. Es hat sich im Zusammenhang mit der praktischen Entwicklung von SAT-Solvern gezeigt, dass Vorverarbeitungsschritte, die die gegebene Formel vereinfachen, durchaus die Laufzeit eines SAT-Solvers verbessern können.

SATELITE ist der bisher beste Preprozessoralgorithmus und hat seine Effizienz bereits in vielen Benchmarks unter Beweis gestellt. Bisher sind jedoch nur C++ Implementierungen von SATELITE verfügbar, die die Integration in bereits bestehende C-Projekte nicht reibungslos gestatten. Eines dieser Projekte ist ein am Institut für Theoretische Informatik entwickelter hybrider SAT-Solver.

Um diesen zu verbessern, wird eine effiziente Implementierung von SATELITE in C benötigt. Ziel dieser Arbeit ist eine solche Implementierung zu erstellen, sowie die theoretischen Grundlagen für diese Implementierung genau zu diskutieren. Bei Interesse melden sie sich bitte bei Oliver Gableske.

Algorithmische Bioinformatik

Wir haben laufend aktuelle Themen auf dem Gebiet Algorithmische Bioinformatik, bei Interesse geben wir gerne nähere Informationen. (Betreuer: Prof. Dr. Enno Ohlebusch mit Timo Beller).

Selbstverständlich sind weitere Themen denkbar, sprechen Sie dazu einfach mit einem Mitarbeiter des Instituts über mögliche Themen und/oder machen Sie eigene Vorschläge.