oder:
Einwegfunktionen
Intuitiv ist eine Funktion eine Einwegfunktion, wenn sie effizient berechenbar ist, jedoch die Unkehrfunktion 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. Schöning)
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-Reduzierbartkeit). (Betreuer: Prof. Schöning, T. Eibach)
Entwicklung eines AllSAT-Solvers
In der Diplomarbeit soll ein SAT-Solver entwickelt werden. Hierzu besteht eine Zusammenarbeit mit der Uni Kaiserslautern. Von dort stammt der Vorschlag einen "AllSAT" Solver zu entwickeln, der zu einer gegebenen Booleschen Formel alle (!) Lösungen findet. (Betreuer: Prof. Schöning, T. Eibach)
Diplomarbeitsthemen im Bereich Kommunikationskomplexität
Sowohl in der Theoretischen Informatik als auch z.B. im Bereich Verteilte Systeme spielt neben den Resourcen Zeit und Platz insb. die Resource Kommunikation eine herausragende Rolle. Ist in einem verteilten System von mehreren Parteien ein nichttriviales Problem P zu lösen, so wird Kommunikation zwischen den Parteien stattfinden müssen. Die minimale Anzahl von Bits, die kommuniziert werden müssen, um P zu lösen, wäre dann die
Kommunikationskomplexität C(P). Da i.a. C(P) schwer auszurechnen ist, sind für eine Reihe von Modellen Methoden entwickelt worden, um diese zu approximieren. Eine Fragestellung in diesem etablierten Gebiet der Komplexitätstheorie ist, inwieweit diese (untere-Schranke-)Methoden Kommunikationskomplexität gut approximieren. Eine weitere grundlegende Fragestellung ist die folgende: Sind nicht ein, sondern mehrere Probleme P_1,...,P_k zu lösen, was ist die Kommunikationskomplexität des Problems (P_1,...,P_k), d.h. wenn man diese Probleme gemeinsam lösen möchte. Ist es möglich, Kommunikation einzusparen, oder gilt ein "direktes-Summen-Theorem": C(P_1,...,P_k) \geq \Omega(\sum_{1}^{k}C(P_i)) Ein konkretes (und gelöstes) Beispiel wären Dateivergleiche in einer verteilten Datenbank. Im allgemeinen Fall sind die meisten "direkte-Summen-Fragestellungen" noch offen.
Eine Diplomarbeit in diesem Gebiet könnte darin bestehen, ein bis zwei Originalarbeiten im Detail vorzustellen, oder auch zu versuchen, für bestimmte interessante Klassen von Funktionen die in diesem Gebiet entwickelten Methoden zur Bestimmung der Kommunikationskomplexität anzuwenden. (Betreuer: H. Wunderlich)
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. 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 Diplomarbeiten, man könnte sich z.B. konzentrieren auf:
(Betreuer: Prof. 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 Diplomarbeit soll diese Begriffe, Definitionen und Eigenschaften von
Universal Hashing systematisch durchforsten, auflisten und Beweise nachvollziehen. (Betreuer: Prof. 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 Diplomarbeit 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. Schöning)
Bloom Filter
Bloom Filter sind probabilistische Datenstrukturen, mit deren Hilfe sehr schnell (on-line) festgestellt werden kann, welche Daten in einem kontinuierlich fließenden Datenstrom schon einmal "gesehen" wurden und welche "neu" sind. Hierzu wird mit einer geeigneten Zahl von Hashfunktionen ein "Fingerabdruck" des gesehenen Datums in einer Hashtabelle hinterlassen. In dieser Arbeit sollen die bisher bekannten Ergebnisse zu Bloom Filtern erfasst und dargestellt werden. (Betreuer: Prof. Schöning)
SAT-Solver
SAT-Solver sind Algorithmen, die zu einer gegebenen Boolschen Formel in KNF, eine erfüllende Belegung suchen. Effiziente Verfahren hierfür sind aus mehreren (theoretischen und parktischen) 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 WC 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 Diplomarbeit können diese Heuristiken genauer untersucht werden und dann auch verbessert werden, indem Parameter experimentell optimiert werden. (Betreuer: Prof. Schöning, M. Maucher)
Implementierung eines deterministischen 3-Färbbarkeitsalgorithmus
Innerhalb dieser Diplomarbeit 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.328^n) 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. Schöning, A. Balint)
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.
Anstelle eines Praktikums im Hauptstudium können Informatikstudenten auch eine Studienarbeit anfertigen (und erhalten dafür einen Praktikumsschein). Eine Studienarbeit ist eine "kleine Diplomarbeit" mit ca. 3 Monaten Umfang. Es gelten ähnliche Bestimmungen wie bei Diplomarbeiten, d.h. die Arbeit wird bei einem Betreuer des Instituts geschrieben zu einem Forschungsthema des Instituts. Es ist sowohl eine Literaturarbeit als auch eine Implementierung möglich. Eine Studienarbeit eignet sich i.d.R. gut um später zu einem ähnlichen Thema eine Diplomarbeit zu schreiben und um einen Eindruck von der Arbeit in der TI zu bekommen.
(Stand: 14.02.2007)