Seminar Kommunikationskomplexität

Sommersemester 2003

RWTH Aachen



Veranstalter:
 Detlef Sieling


Termin:
 4.8.-7.8.2003

In der Kommunikationskomplexität wird die Aufgabenstellung untersucht eine Funktion auszuwerten, wobei die Eingabe auf mehrere Rechner verteilt ist.  Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versandt werden müssen, damit diese die Aufgabe erfüllen können. Während der Zusammenhang zum Entwurf verteilter Algorithmen eher offensichtlich ist, ist die Kommunikationskomplexität auch ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen. Wenn man beispielsweise die Berechnung einer Funktion mit einem VLSI-Chip betrachtet, kann man die Chipfläche in zwei Bereiche aufteilen, so dass jeder der Bereiche einen Teil der Eingabe erhält. Um die Funktion zu berechnen, müssen die beiden Bereiche des Chips Informationen austauschen. Wenn aufgrund der Eigenschaften der zu berechnenden Funktion viel Information ausgetauscht werden muss, benötigt man entweder viel Rechenzeit oder die Grenzlinie zwischen den beiden Bereichen des Chips und damit der Chip selber müssen groß sein. Mit ähnlichen Argumenten kann man untere Schranken für weitere Berechnungsmodelle, etwa die Größe von Entscheidungsbäumen, oder für die Zugriffszeiten in Datenstrukturen beweisen. In dem Seminar sollen sowohl Methoden zur Untersuchung der Kommunikationskomplexität als auch ihre Anwendungen untersucht werden.




30.7.2003 - Detlef Sieling