Seminar und Proseminar: Perlen der Theoretischen Informatik

Seminar	Proseminar	Thema	Name	Seminar	Proseminar	Thema	Name
v		1	Daniel Warner		v	6	Markus Theelen
	v	1	Yascha Cebeci		v	6	Milita Fischer
v		3	Siyuan Wei	v		8	Stephan Mueller
	v	3	Berthold Krevert	v		8	Yuanda Li
	v	3	Sven Kindermann	v		11	Matthias Keller
v		4	Gilles Bertrand Gnokam Defo		v	11	Christoph Konersmann
	v	4	Anatol Derksen		v	12	Dominic Eschweiler

Gruppenfoto

Für eine größere Version des Bildes bitte auf das Bild klicken.

1.)

Lineare Programmierung

Die Lineare Programmierung beschäftigt sich mit dem Optimieren linearer Zielfunktionen, die durch lineare Gleichungen oder Ungleichungen beschränkt sind. Hauptanwendungsgebiet der Linearen Programmierung ist das Operations Research. In praktischen Anwendungen wird oft der Simplexalgorithmus eingesetzt, der jedoch im ungünstigsten Fall exponentielle Laufzeit haben kann. Ein polynomieller Algorithmus ist die Elipsoid-Methode, die sich jedoch in der Praxis nicht einsetzen lässt.

Das Proseminar beschäftigt sich mit dem Simplexalgorithmus. Das Seminar wird die Elipsoid-Methode behandeln.

Literatur für beide Methoden ist bspw. das Buch:
Combinatorial Optimization - Algorithms and Complexity
Christos H. Papadimitriou, Kenneth Steiglitz
Dover Publications, 1998 oder Prentice Hall, 1982

2.)

Reelle Semi-Entscheidbarkeit

Wann eine Turingmaschine eine Sprache -- d.h. eine Menge L endlicher Zeichenketten -- akzeptiert, wurde im Grundstudium definiert und an Beispielen (Halteproblem, Diagonalsprache) untersucht. Wie verhaelt es sich aber mit Mengen reeller Zahlen wie beispielsweise der Einheitskreisscheibe oder dem Graph der Exponentialfunktion? Hier gibt es im Wesentlichen zwei Arten erweiterter Turingmaschinen, die auf verschiedene, sinnvolle Definitionen von "reeller Semi-
Entscheidbarkeit" fuehren: das BSS-Modell und die Typ-2 Maschine.

Proseminar 1: Reelle Semi-Entscheidbarkeit im BSS-Modell
Im ersten Proseminarthema soll Semi-Entscheidbarkeit im BSS-Modell vermittelt werden anhand (Kapitel 2, nur bis einschliesslich Subkapitel 2.4) dem Buch "Complexity and Real Computation" von Blum, Cucker, Shub und Smale (Springer 1998).

Proseminar 2: Reelle Semi-Entscheidbarkeit in der Rekursiven Analysis
Im zweiten Proseminarthema geht es um das Analogon im Typ-2 Modell anhand von (im wesentlichen) Kapitel 5.1 in "Computable Analysis: An Introduction" von Weihrauch (Springer 2000).

Seminar: Reelle Semi-Entscheidbarkeit im Vergleich beider Modelle
Im dritten Thema wird die Arbeit "Equality is a Jump" von Boldi und Vigna, S.49-64 Band 219 in "Theoretical Computer Science" (1999) praesentiert, die beide Modelle vergleicht.

Voraussetzungen:

3.)

Proseminar: Hashverfahren

Um eine Menge von Datensätzen mit je eindeutigen Schlüsseln aus einer Menge K möglicher Schlüssel so zu speichern, dass die Operationen Einfügen, Löschen und Suchen effizient durchführbar sind, wird bei Hashverfahren versucht, durch Berechnung den Speicherort des Datensatzes mit z.B. Schlüssel k zu ermitteln. Die Datensätze werden in einem linearen Feld der Größe m mit den Indizes 0,..., m -1 gespeichert, der Hashtabelle. Eine Abbildung, die Hashfunktion h : K -> {0,..,m-1} ordnet jedem Schlüssel k einen Index h(k) mit 0 <= h(k)<= m -1 zu, die Hashadresse.
In der Regel ist die Menge der zu speichernden Schlüssel K sehr viel kleiner als K , so dass die Hashfunktion i.A. nicht injektiv sein kann, sondern muss evtl. verschiedene Schlüssel auf die gleiche Adresse abbilden. Somit ergeben sich Adresskollisionen, die anschliessend aufgelöst werden müssen.

Eine Hashfunktion muss also zwei Forderungen genügen:
a) Es sollen möglichst wenig Kollisionen auftreten
b) Adresskollisionen sollen möglichst effizient aufgelöst werden

In diesem Vortrag soll die Wahl einer guten Hashfunktion erörtert werden. Als zweiter Punkt werden bekannte Verfahren zur effizienten Adressauflösung diskutiert !

Seminar 1: Consistent Hashing

Describes a family of caching protocols for distributed networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for use with very large networks such as the Internet, where delays caused by hot spots can be severe, and where it is not feasible for every server to have complete information about the current state of the entire network. The protocols are easy to implement using existing network protocols such as TCP/IP, and require very little overhead. The protocols work with local control, make efficient use of existing resources, and scale gracefully as the network grows. Our caching protocols are based on a special kind of hashing that we call consistent hashing. Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes.

Seminar 2: cuckoo hashing - explanation of a new hashing data structure

Definition: A dictionary implemented with two hash tables, T1 and T2, and two different hash functions, h1 and h2. Each key, k, is either in T1[h1(k)] or T2[h2(k)]. A new key, k, is stored in T1[h1(k)]. If that location is already occupied by another key, l, the other key is moved to T2[h2(l)]. Key are moved back and forth until a key moves to an empty location or a limit is reached. If the limit is reached, new hash functions are chosen, and the tables are rehashed. For tables that are a bit less than half full and universal hashing functions, performance is good. A key is deleted by removing it from a table.

Betreuer: Gunnar Schomaker

4.)

Paging

Das Paging Problem ist vielleicht das bekannteste Online Problem. Um den Zugriff auf die Festplatte (langsamer Speicher) zu beschleunigen, wird ein Teil der angefragten Speicherseiten in einem schnellen Speicher (Cache) zwischengespeichert. Wiederholte Anfragen können so sehr schnell bearbeitet werden. Da der Cache jedoch nur wenige Seiten speichern kann, muss Online, d.h. ohne Wissen über die zukünftigen Seitenanfragen, entschieden werden, welche Seite aus dem Cache entfernt wird um Platz für eine neu angefragte Seite zu schaffen.

Im Rahmen des Proseminars soll das Themengebiet sowie die Competitive Analyse, insbesondere der Algorithmen "Least Recently Used" (LRU) und "Flush When Full" (FWF) vorgestellt werden. Darauf aufbauend soll im Rahmen des Seminars eine Anayse vorgestellt werden, die verdeutlicht, warum in der Praxis die Performance von LRU wesentlich besser ist, als die von FWF.

Proseminar:
In: Online Computation and Competitive Analysis, A. Borodin, R. El-Yaniv. Cambridge University Press, Seite 32-52, 1998.

Seminar:
A Probabilistic Analysis of LRU and FWF, L. Becchetti. Proc. 12th Annual European Symposium on Algorithms (ESA), 2004.

Betreuer: Jens Krokowski

5.)

Markovsche Prozesse im Casino

Dieser Vortrag soll sich mit der Theorie und Praxis der Markovschen Prozesse befassen. Es wird besonders viel Wert auf die Frage über die Konvergenzgeschwindigkeit der Prozesse gelegt. Somit können wir beispielsweise präzise berechnen wie lange man ein Deck von Spielkarten mischen muss, um eine wirklich faire Verteilung der Karten zu erreichen. Das Problem ist prominent und deren Lösung hat es sogar einmal in die New York Times geschafft (was für mathematische Probleme an sich nicht üblich ist).

Im Rahmen des Proseminars werden die grundlegenden Eigenschaften markovscher Prozesse besprochen (hauptsächlich anhand [1]). Weiterhin werden übliche Verfahren zum Mischen von Spielkarten besprochen und die dafür entwickelten mathematischen Modelle dargestellt (siehe [2]).

Der Vortrag im Rahmen des Seminars gliedert sich in zwei Teile. Im ersten Teil muss die Theorie der Strong Uniform Times ([3,4]) behandelt werden. Anhand dieser Theorie kann im zweiten Teil eins der Verfahren zum Mischen von Spielkarten genauer untersucht werden (anhand von [4]).

Anforderungen: Grundlagen in der Wahrscheinlichkeitstheorie

[1] Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press 1995
[2] Card-Shuffling Analysis with Markov Chains, Harald Hammarström, unpublished
[3] Strong Uniform Times and Finite Random Walks, D. Aldous and P. Diaconis, Advances in Applied Mathematics 1987
[4] Shuffling Cards and Stopping Times, D. Aldous and P. Diaconis, The American Mathematical Monthly, 1986

Betreuer: Jaroslaw Kutylowski

6.)

Vervollständigung Lateinischer Quadrate:

Lateinische Quadrate wurden bereits im Altertum betrachtet. Man erhält ein Lateinisches Quadrat der Ordnung n, indem man die Felder eines (n x n)-Quadrates so mit den Zahlen 1, 2, ..., n füllt, dass jede Zahl genau einmal in jeder Zeile und genau einmal in jeder Spalte steht. Wir betrachten das Problem, wann ein Quadrat, das schon einige Einträge vorgegeben hat, zu einem Lateinischen Quadrat gleicher Ordnung vervollständigt werden kann.

Proseminar:
Heiratssatz und Anwendung des Heiratssatzes beim Beweis, dass jedes Lateinische Rechteck zu einem Lateinischen Quadrat vervollständigt werden kann.

Seminar:
Satz von Smetaniuk: Jedes (n x n)-Quadrat mit bis zu n-1 vorgebenen Einträgen, wobei in jeder Zeile und in jeder Spalte kein Wert doppelt vorkommt, kann zu einem Lateinischen Quadrat der Ordnung n vervollständigt werden.

Literatur: Proofs from THE BOOK; Martin Aigner, Günter M. Ziegler; Springer-Verlag Berlin Heidelberg, 2003.

7.)

The robot worth loglog(n) pebbles

One robot may try to explore unlabelled directed graph, but since it cannot distinguish nodes of the graph it will ceirtenly fail. First we will observe that two robots can explore graphs with high conductance. We will also find a new application for a simple tool, namely a pebble. One robot using loglog(n) pebbles can efficiently explore the given graph too!
REMARK: additional robot is worth of loglog(n) pebles

Proseminar:
Markov chains (basic definitions), Conductance, Approximate mixing time

Seminar:
1. M. A. Bender, D. K. Slonim (FOCS '94)
"The Power of Team Exploration: Two Robots Can Learn Unlabelled Directed Graphs"
2. M. A. Bender, A. Fernandez, D. Ron, A. Sahai, S. Vadhan (STOC '98)
"The Power of Pebble: Exploring and Mappi ng Directed Graphs"

Betreuer: Miroslaw Dynia

8.)

Rudolf Ahlswede erhielt kürzlich den Shannon-Preis. Sicherlich auch für seine Arbeit im Bereich des Network Codings, welches nicht nur effiziente robuste Nachrichtenübertragung in drahtlosen Netzwerken ermöglicht, sonder auch Microsofts Antwort auf Bittorrent darstellen soll. Letztere ist ein Peer-to-Peer-Netzwerk welches im Moment 50% des Internetverkehrs einnimmt (hoffentlich alles legal).

Proseminar:
Network Coding for Large Scale Content Distribution
IEEE Infocom 2005
Christos Gkantsidis, College of Computing Georgia Institute of Technology
Pablo Rodriguez Rodriguez, Microsoft Research, Cambridge, CB3 0FD, UK

Seminar:
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 46, NO. 4, JULY 2000
Network Information Flow
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Senior Member, IEEE, and
Raymond W. Yeung, Senior Member, IEEE

Betreuer: Christian Schindelhauer

9.)

Wegberechnung mit bewegten Hindernissen

Seminar:
Thema ist die Komplexität der Berechnung einer Flugbahn durch bewegte Hindernisse. Dabei steht das Entscheidungsproblem "Gibt es eine Flugbahn von Position A nach Position B für ein bestimmtes Objekt?" im Mittelpunkt. Im 3-dimensionalen Raum mit beschränkter Geschwindigkeit ist dieses Problem PSPACE-schwer, wie durch eine Simulation einer Turingmaschine gezeigt wird.

Literatur:
Motion Planning in the Presence of Moving Obstacles
John Reif and Micha Sharir, Journal of the ACM, 41:764-790
DOI Bookmark (Zugriff auf die elektronische Version von Rechnern der Uni aus möglich)

Proseminar:
Im Proseminar sollen grundlegende Begriffe aus der Komplexitätstheorie eingeführt werden: Sprachklassen (P, NP, PSPACE, ...), Reduktionen, usw.

10.)

Proseminar: Konstruktion von Hashfunktionen mit beschränkter Unabhängigkeit

Hashfunktionen sind Funktionen, bei denen die Funktionswerte in abhängigkeit vom Eingabewert zufällig gewürfelt werden. Man benutzt sie beispielsweise, um zu speichernde Daten auf Speicherbereiche zu verteilen. Wenn man eine vollständig zufällige Verteilung der Daten erreichen wollte, bräuchte die Hashfunktion in etwa so viel Platz wie die Daten selbst, da alle Funktionswerte der Hashfunktion gespeichert werden müßten. Dies soll vermieden werden durch die Konstruktion von Hashfunktionen mit beschränkter Abhängigkeit, die nur noch konstanten Platz im Speicher belegen.
Im Proseminar werden algebraische Grundlagen zur Konstruktion paarweise unabhängiger Hashfunktionen vorgestellt, insbesondere Körper endlicher Kardinalität und Polynome (bzw. lineare Funktionen) auf diesen Körpern.

Seminar: The space complexity of approximating the frequency moments

Im Seminarthema wird eine Veröffentlichung von Alon, Matias und Szegedy vorgestellt, die 2004 mit dem Gödelpreis ausgezeichnet wurde. In ihr werden die Grundlagen für den immer weiter wachsenden Bereich der Datenstromalgorithmen gelegt. Hierbei geht man davon aus, daß die Eingangsdaten für ein Problem in Form eines Datenstroms vorliegen, den man jedoch nur ein einziges mal sequenziell lesen kann und danach nicht weiter speichern kann.
In der Veröffentlichung wird die Berechnung der sogenannten Frequency Moments behandelt. Darunter fällt z.B. das Zählen der verschiedenen Objekte in einem Datenstrom (schwierig, wenn Objekte mehrfach auftreten). Außerdem werden untere Schranken bewiesen an den Platz, den man braucht, um Frequency Moments in einem Datenstrom zu berechnen.

11.)

Sortieren auf der Grafikkarte

Für eine Reihe von Problemen in der Computergraphik ist die Sortierung von Objekten nach Sichtbarkeit von Bedeutung. Eine Anwendung ist beispielsweise die Darstellung von transparenten Objekten. Wird ein Polygon von einem anderen verdeckt, so muss das hinten liegende Polygon zuerst gezeichnet werden. Grafikkarten verfügen mittlerweile über Operationen, durch die sich Überschneidungen im Bildraum feststellen lassen. Diese Operationen können in einem Sortieralgorithmus verwendet werden, um eine korrekte Tiefensortierung zu erzeugen.

Seminar:
In der Arbeit wird ein Ansatz vorgestellt, der die Grafikkarte nutzt, um Verdeckungen zu erkennen und damit das Problem der der Tiefensortierung zu lösen.
Literatur:
Interactive Visibility Ordering and Transparency Computations among Geometric Primitives in Complex Environments
Naga K. Govindaraju, Michael Henson, Ming C. Lin, Dinesh Manocha
Proceedings of the 2005 symposium on Interactive 3D graphics and games
DOI Bookmark (Zugriff auf die elektronische Version von Rechnern der Uni aus möglich)

Proseminar:
Im Proseminar soll eine Übersicht über einige Sortierverfahren gegeben werden, die im Buch "The Art of Computer Programming, Volume 3: Sorting and Searching (Addison Wesley, 1998)" von Donald E. Knuth behandelt werden.

Betreuer: Michael Kortenjan

12.)

Online-Navigation

Bei Online-Navigationsproblemen geht es darum, dass ein Roboter in einer unbekannten Umgebung den Weg zu einem Zielpunkt finden muss und weder Lage noch Position von Hindernissen kennt. Dabei bewertet man die Güte eines Algorithmus, indem man die gefundene Lösung mit der optimalen Lösung vergleicht (die offline bzw. mit globalem Wissen ermittelt wird) und daraus das so genannte kompetitive Verhältnis bestimmt. Für die folgenden beiden Probleme existieren deterministische und randomisierte Online-Algorithmen, wobei die randomisierten Algorithmen bessere Schranken liefern.

Proseminar: The Cow-Path Problem

Das Cow-Path-Problem besteht darin, dass eine kurzsichtige Kuh ein Loch in einem Weidezaun sucht. Sie darf an dem Weidezaun entlanglaufen, aber weiß nicht, in welcher Richtung sich das Loch befindet. Für das Cow-Path-Problem gibt es einen optimalen Online-Algorithmus mit einem kompetitiven Verhältnis von 9. Eine randomisierte Strategie liefert in diesem Fall eine bessere Schranke.

Baeza-Yates, Culberson, Rawlins: Searching in The Plane, Information and Computation, 106(2):234–252, 1993

Kao, Reif, Tate: Searching in an Unknown Environment. An Optimal Randomized Algorithm for the Cow-Path Problem, Symposium on Discrete Algorithms, pp. 441--447, 1993

Seminar: The Wall-Problem

Beim Wall-Problem muss ein Roboter eine Wand erreichen, wobei ihm der Weg durch rechteckige Hindernisse versperrt wird. Ein optimaler deterministischer Algorithmus liefert ein kompetitives Verhältnis von O(sqrt(n)), wobei n die euklidische Distanz zwischen Start und Ziel ist. Auch in diesem Fall kann durch einen randomisierten Algorithmus die Schranke verbessert werden.

Blum, Raghavan, Schieber: Navigatin in Unfamiliar Geometric Terrain, SIAM J. Comput. 26(1):110-137, 1997

Berman, Blum, Fiat, Karloff, Rosen, Saks: Randomized Robot Navigation Algorithms, Symposium on Discrete Algorithms, pp. 75-84, 1996

13.)

3D Visibility Complex

Sichtbarkeit ist eines der grundlegenden Probleme in der Computergrafik. In vielen Anwendungen möchte man zu einem gegebenen Standpunkt wissen welche der vor einem stehenden Objekte oder welche Teile davon sichtbar sind. Bei einer leichten Bewegung des Beobachters kann sich die Sichtbarkeit von Objekten sehr stark ändern; beispielsweise wenn man um die Ecke eines Hauses schaut und dahinter ganze Zeilen von Häusern auftauchen. Ebenso ist es jedoch möglich, dass dahinter nichts erscheint und sich die Menge der sichtbaren Objekte oder Objektteile nicht geändert hat. Interessant ist daher die Frage wieviele Standpunkte es gibt, bei denen sich die Sichtbarkeit ändert oder gleich bleibt.

Seminar:
Das Seminar behandelt eine Antwort auf dieses Problem, die in dem folgenden Artikel gegeben wurde:

The 3D visibility complex
Fredo Durand, George Drettakis, Claude Puech
ACM Transactions on Graphics (TOG), Vol. 21, Issue 2, 2002.
DOI Bookmark (Zugriff auf die elektronische Version von Rechnern der Uni aus möglich)

Proseminar:
Das Proseminar behandelt Grundlagen zu Fragen der Sichtbarkeit. Dazu wird der Visibilitygraph betrachtet, der im Zusammenhang mit Motion Planning Anwendung findet. Der Basisartikel ist im folgenden Buch zu finden (Kapitel 15, S. 305):

Computational Geometry - Algorithms and Applications
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf
Springer Verlag, 1997.

Seminar und Proseminar »Perlen der Theoretischen Informatik«

Wintersemester 2005/2006

Inhalt

Aufbau des Seminars/Proseminars

Hinweise

Perlenseminare vergangener Jahre

Scheinerwerb

Bereich

Veranstalter

Termine

Schloß Gehrden

Anmeldung

Themen