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: bei Masterarbeiten sind 2 Gutachter notwendig, bei Bachelorarbeiten einer.

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)

&nbs

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.

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)

Sequenzanalyse

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

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 Uwe Baier).

Statistische Methoden zur experimentellen Algorithmenanalyse

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

 

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.