Proseminar: Perlen der Theoretischen Informatik

Dozent: Prof. Albers

Aktuelles

Es gibt noch freie Plätze im Seminar! Die noch nicht vergebenen Themen können noch gewählt werden. Freie Termine gibt es am 25.05., 08.06., 06.07. und am 13.07. Anmeldungen für diese Termine bitte bis zum 27.04. per E-Mail.

Termine

SE	Dienstag	13:00 - 15:00	(RUD 26 0.313)

Zuordnung

Grundstudium, Proseminar, Theoretische Informatik

Inhalte und Lernziele

In diesem Seminar sollen einige besonders schöne und elegante Resultate der theoretischen Informatik aus den letzten Jahren und Jahrzehnten präsentiert werden. Dabei soll aufgezeigt werden, dass die Beschäftigung mit raffinierten Beweistechniken, eleganten Argumenten und überraschenden Konstruktionen höchst vergnüglich sein kann.

Anforderungen

regelmäßige Anwesenheit und aktive Mitarbeit
Vortrag (45 bis 60 Minuten)
schriftliche Ausarbeitung (acht bis zwölf Seiten). Die Ausarbeitung sollte bis zum Ende der Vorlesungszeit vorliegen.

Vortragsthemen

Das Messbecher-Problem: vergeben!
Im Film „Stirb langsam - Jetzt erst recht“ muss der Hauptdarsteller zur Entschärfung einer Bombe genau vier Liter Wasser abmessen, hat dazu aber nur einen 3l- und einen 5l-Eimer zur Verfügung. Kann er das schaffen? Was wäre im Film passiert, wenn der Bösewicht seine Bombe auf ein anderes Volumen eingestellt und andere Messbecher bereitgestellt hätte? Allgemeiner: Seien n Messbecher gegeben mit Kapazitäten c1,...,cn; kann man damit Flüssigkeit mit Volumen x abmessen? Und falls ja, mit wie vielen (Umfüll-)Operationen? Schließlich haben Filmhelden nicht beliebig viel Zeit...
„Game of LIFE“: vergeben!
LIFE ist ein zellulärer Automat: Auf einem Gitter ist in jedem Schritt der Folgezustand eines Knotens entweder tot oder lebend, abhängig von seinem bisherigen Zustand und dem seiner Nachbarn. LIFE ist ein ganz einfaches System mit einfachen Regeln, aber es entwickelt ein unglaublich komplexes Verhalten. Überraschenderweise kann man mit LIFE sogar einen modernen Computer simulieren!
BUNDESLIGA ist NP-vollständig: vergeben!
Jeder Fußballfan kennt das Problem: Nach Spieltag i blickt man auf die aktuelle Tabelle und fragt sich, ob die eigene Lieblingsmannschaft X noch eine Chance auf die Meisterschaft hat. Obwohl das Problem täglich Stammtischthema ist, stellt sich heraus, dass dieses Problem im Allgemeinen gar nicht so einfach gelöst werden kann!
Magisches Münzenumdrehen:
Der Magier möchte möglichst schnell und mit verbundenen Augen eine Anzahl von Münzen entweder alle auf Kopf oder alle auf Zahl setzen. Die einzige Information die er zur Verfügung hat ist, ob die Münzen nach jeder Aktion alle auf der selben Seite liegen. Wie lautet die minimale Anzahl von Aktionen die der Magier braucht um sein Ziel zu erreichen? Was passiert wenn, die Münzen zwischen zwei Aktionen gemischt werden oder wenn das Ziel dahingehend geändert wird, dass die Anzahl von Münzen mit Kopf und Zahl gleich ist? Was passiert, wenn der Magier Würfel statt Münzen verwendet?
Die Welt ist klein: vergeben!
Im Jahre 1967 hat der Psychologe Stanley Milgram nach einem Experiment herausgefunden, dass jede Person der US-amerikanischen Bevölkerung von jeder anderen Person aus den USA über eine Kette von durchschnittlich sechs Personen erreicht werden kann. Also ist selbst in der großen USA die Welt eigentlich sehr klein. Hier wird dieses Resultat aus einer algorithmischen Perspektive betrachtet.
Polygon Triangulation - Bewachung von Kunstgalerien:
Eine Kunstgalerie soll mit so wenigen Kameras wie möglich überwacht werden. Wie findet man heraus, wieviele Kameras mindestens benötigt werden, um potentiellen Dieben das Leben schwer zu machen?
Spannbaum-Algorithmen: vergeben!
Die Berechnung minimaler Spannbäume findet direkte Anwendung in der Praxis, beispielsweise für die Erstellung von kostengünstigen zusammenhängenden Netzwerken, wie beispielsweise Telefonnetze oder elektrische Netze. Hier geht es um zwei bekannte Algorithmen zur Berechnung minimaler Spannbäume, und um eine Anwendung der Spannbäume.
Arora's PTAS für das Euklidische TSP: vergeben!
Viele Optimierungsprobleme sind NP-vollständig, d.h. auch Supercomputer benötigen sehr viel Zeit, um solche Probleme exakt zu lösen. Für viele Anwendungen reicht es allerdings, wenn ein Optimierungsproblem nur näherungsweise gelöst wird. Interessanterweise ist für viele Optimierungsprobleme eine solche Näherungslösung deutlich schneller berechenbar. Es gibt sogar Optimierungsprobleme, die mit geringer Laufzeit beliebig gut approximiert werden können. Ein solches Problem ist das Euklidische TSP, eine wichtige Variante des Problems des Handelsreisenden.
Superkonzentratoren und der Heiratssatz:
n-Superkonzentratoren sind kreisfreie Graphen mit n Eingangsknoten und n Ausgangsknoten und für beliebig gewähltes k gibt es k <= n disjunkte Pfade durch den Graphen, die Eingangs- und Ausgangsknoten verbinden. Wie viele Kanten müssen n-Superkonzentratoren mindestens haben? Der Heiratssatz aus der Graphentheorie hilft uns hierbei.
P != NP mit Wahrscheinlichkeit 1:
Das P-versus-NP-Problem ist eines der berühmten Millenniumprobleme und neben Ruhm und Ehre erhält man für dessen Lösung auch eine Millonen Dollar. Bis jetzt ist dies allerdings noch niemandem gelungen. Es gibt aber ein erstaunliches Resultat: Man kann „Welten“ definieren, in denen P=NP gilt und andere in denen P != NP gilt. Wählt man nun eine solche „Welt“ zufällig, dann gilt P!=NP sogar mit Wahrscheinlichkeit 1.

Vortragstermine

Termin	Vortragende(r)	Titel	Betreuer
13.04.2010	-	Vorbesprechung und Themenvergabe	-
11.05.2010	Daniel Lunow	Spannbaum-Algorithmen	AA
18.05.2010	Ben Lenser	Das Messbecher-Problem	AA
01.06.2010	Mario Völker	Arora's PTAS für das Euklidische TSP	AA
15.06.2010	Denis Erfurt	„Game of LIFE“	AA
22.06.2010	Anna-Lisa Deussing	Die Welt ist klein	AA
29.06.2010	Alexander Priebe	entfallen

Literatur

Bücher

Uwe Schöning: Perlen der Theoretischen Informatik,Spektrum Akademischer Verlag, 1995.
Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: GEWINNEN Strategien für mathematische Spiele, Vieweg Verlagsgesellschaft; Auflage: 1., 1985.
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry: Algorithms and Applications, Springer Verlag, Auflage: 3., 2008
Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest,: Algorithmen - Eine Einführung, Oldenbourg Wissensch.Vlg; Auflage: 1., 2004.
Vijay V. Vazirani: Approximation Algorithms, Springer Verlag, 2001.

Veröffentlichungen

P. Boldi, M. Santini and S. Vigna: Measuring with Jugs, Theoretical Computer Science, Volume 282, Issue 2, Pages 259-270, 2002.
J. Kleinberg: The Small-World Phenomenon: An Algorithmic Perspective, in Proceedings of the 32nd ACM Symposium on Theory of Computing, Pages 163-170, 2000.
T. Bernholt, A. Gülich, T. Hofmeister and N.Schmitt: Football Elimination is Hard to Decide Under the 3-Point-Rule, in Proceedings of Symposium on Mathematical Foundations of Computer Science, Pages 410-418, 1999.
N. Benbernou, E.Demaine, M. Demaine and B.Rossman: Coin-Flipping Magic,Manuscript, April 2008. Presented at Gathering for Gardner 8, Atlanta, Georgia, March 2008.

Links

Bei Anregungen und Fragen zum Seminar wenden Sie sich bitte an Antonios Antoniadis oder Pascal Lenzner.

last modified 07/09/10 (alkox-www)