Institut für Theoretische Informatik, Algorithmik

Proseminar: Klassiker der Theoretischen Informatik

Betreuung

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