Proseminar: Klassiker der Theoretischen Informatik
Betreuung
Dr. Lukas Barth, Guido Brückner, M.Sc., Dr. Valentin Buchhold, Sascha Gritzbach, M.Sc., Dr. Michael Hamann, Dr. Roman Prutkin, Dr. Marcel Radermacher, Dr. Franziska Wegner, Dr. Matthias Wolf, Dr. Tobias Zündorf
Anmeldung
Die maximale Teilnehmerzahl ist hiermit erreicht.
Die Nachrückerliste ist ebenfalls voll.
Die Teilnehmerzahl ist beschränkt, die Plätze werden nach Anmeldereihenfolge vergeben. Anmeldung bitte per Mail bei Dr. Roman Prutkin.
Regelmäßiger Termin
Montags um 11:30 im SR 301 (Informatikgebäude)
Vorbesprechung am 24. April, Folien
Themen
Der Inhalt orientiert sich am Buch „Perlen der Theoretischen Informatik“ von Uwe Schöning.
| # | Termin | Betreuung | Thema | Studenten |
|---|---|---|---|---|
| 1 | 22.05. | Roman | Das zehnte Hilbertsche Problem. Gibt es einen Algorithmus zum Prüfen, ob eine gegebene diophantische Gleichung (Polynomgleichung mit mehreren Variablen und mit ganzzahligen Koeffizienten) ganzzahlige Lösungen besitzt? | Michael |
| 2 | 22.05. | Michael | Probabilistische Algorithmen, Wahrscheinlichkeitsverstärkung und Recycling von Zufallszahlen. Wie man die Anzahl in einem probabilistischen Algorithmus verwendeter Zufallszahlen einschränken, und wie wirkt sich das auf die Fehlerwahrscheinlichkeit aus? | Simon |
| 3 | 29.05. | Guido | Kolmogoroff-Komplexität, universelle Wahrscheinlichkeitsverteilung, worst-case vs. average-case. Kolmogoroff-Komplexität einführen. Man kann eine Wahrscheinlichkeitsverteilung definieren, unter der der mittlere und der schlechteste Fall bis auf einen konstanten Faktor zusammenfallen, und zwar für alle Algorithmen. | Sebastian |
| 4 | 29.05. | Lukas | Untere Schranken durch Kolmogoroff-Komplexität. Mit Hilfe des Konzepts der Kolmogoroff-Komplexität lassen sich manche Beweise von unteren (Komplexitäts-)Schranken durchführen. Beispiele: Anzahl Primzahlen $\leq n$, Komplexität Boolescher Schaltkreise, und Andere. | Henning |
| 5 | 12.06. | Matthias | LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen. Entscheidungsprobleme, die mit logarithmischem Speicher gelöst werden können. Klassen L $\subseteq$ RL $\subseteq$ NL. Pfadsuche in Graphen mit logarithmischem Speicher. | Emil |
| 6 | 12.06. | Marcel | Superkonzentratoren und der Heiratssatz. $n$-Superkonzentratoren: gerichtete azyklische Graphen mit $n$ Eingangs- und $n$ Ausgangsknoten, so dass für beliebig gewählte $k \leq n$ Eingangs- und Ausgangsknoten es knotendisjunkte Pfade gibt, die diese Eingangs- und Ausgangsknoten verbinden. Es genügen $O(n)$ Kanten. | Sarah |
| 7 | 26.06. | Sascha | Pebble Game. Das Pebble Game ist ein Modell für das sukzessive Durchführen einer Rechnung, unter Verwendung von Hilfsspeichern. Das Spiel kann daher verwendet werden, um Trade-Off Effekte zwischen notwendigem Speicherplatz und Rechenzeit für die Durchführung einer Rechnung zu studieren. Zu zeigen ist, dass gewisse auf Superkonzentratoren basierende Graphen sehr viele Pebbles benötigen. | Jan |
| 8 | 26.06. | Franziska | Die Prioritätsmethode. Turing-reduzierbare und Turing-äquivalente Mengen werden eingeführt. Es wird die Existenz unentscheidbarer, rekursiv aufzählbarer Mengen gezeigt, die nicht Turing-äquivalent zum Halteproblem sind. | Xiahong |
| 9 | 03.07. | Guido | Exponentielle untere Schranke für die Länge von Resolutionsbeweisen. Es gibt Formeln in KNF, so dass jeder Beweis ihrer Unerfüllbarkeit mit Hilfe des Resolutionskalküls eine exponentielle Länge hat. | Joshua |
| 10 | 03.07. | Tobias | Der BP-Operator und Graphenisomorphie. Basierend auf probabilistischen Algorithmen wird der BP-Operator definiert. Mit dessen Hilfe wird die Komplexität des Problmes untersucht, ob zwei gegebene Graphen zueinander isomorph sind. | Laura |
| 11 | 10.07. | Valentin | Kollabierende Hierarchien. Die Polynomialzeithierarchie kann in völliger Analogie zu der arithmetischen Hierarchie der Rekursionstheorie definiert werden. Es ist allerdings unbekannt, ob die Polynomialzeithierarchie auch eine echte Hierarchie von Sprachklassen bildet. Unter verschiedenen Annahmen über die Klasse NP „kollabiert“ diese allerdings. | Oliver |
| 12 | 10.07. | Valentin | P $\neq$ NP, mit Wahrscheinlichkeit 1. Es gibt „Welten“, in denen P = NP gilt und andere, in denen P $\neq$ NP gilt. Mit Wahrscheinlichkeit 1 gilt ferner in einer zufällig ausgewählten „Welten“, dass dort P $\neq$ NP gilt. | Samuel |