Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Communication Complexity

MSc Lecture - Winter 2021/22

Beschreibung

In der theoretischen Informatik gehört die Analyse der Komplexität von Algorithmen und Problemstellungen zu einem der zentralsten Forschungsbereichen. Klassischerweise wird unter "Komplexität" dabei die "Zeitkomplexität" verstanden; man interessiert sich also grob gesagt dafür, wie viele Rechenschritte ein Algorithmus zum Bearbeiten einer Eingabe eines Problems benötigt, und ob es schnellere Algorithmen geben kann. Die zugrundeliegende Annahme ist dabei meist, dass beliebig viel schneller Speicher verfügbar ist, und ein einzelner Prozessor die Rechenschritte abarbeitet.

Betrachtet man heutige Ausführungsumgebungen genauer, so treffen diese Annahmen in der Regel nicht zu: Große Datenmengen liegen verteilt auf verschiedenen Systemen (oder verteilt auf mehrere getrennte Komponenten eines Rechners) und müssen für die Berechnung einer Ausgabe zusammengeführt werden. Im Zentrum der Communication Complexity steht nun die Analyse der Kommunikation, die zwischen den verteilten Systemen erfolgt bzw. erfolgen muss, bis die Ausgabe feststeht. Die Erkenntnisse aus diesen Analysen können insbesondere Anwendung finden beim Entwurf von Schaltkreisen, dem Entwickeln effizienter Datenstrukturen sowie der Gestaltung von Netzwerken und Protokollen für verteilte Systeme.

Fokus der Lehrveranstaltung ist eine Einführung in das mathematische Modell der Communication Complexity, Entwurfstechniken für Kommunikationsprotokolle sowie Analysetechniken für untere und obere Schranken an den Umfang der benötigten Kommunikation zwischen den beteiligten Parteien. Als Anwendungsfelder werden insbesondere einfache Streaming-Algorithmen, Chip-Design sowie Datenstrukturen betrachtet. Zudem wird das Modell auch aus dem Blickwinkel der Data Privacy beleuchtet.

Voraussetzungen

Die Vorlesung richtet sich an Master-Studierende, die Interesse am Entwurf und der Analyse von Algorithmen haben. Es gibt keine formalen Voraussetzungen, um diese Vorlesung zu belegen; es wird jedoch erwartet, dass die Teilnehmenden die Grundlagen der Mathematik und Theoretischen Informatik aus gängigen Bachelorstudiengängen der Informatik beherrschen; dazu gehören insbesondere der souveräne Umgang mit formaler mathematischer Notation und den wichtigsten Begriffen der diskreten Mathematik, das Beherrschen grundlegender Beweistechniken, die Fähigkeit zum Entwurf von Algorithmen sowie der Analyse deren Korrektheit und Komplexität. Empfehlenswert ist Spaß am (algorithmischen) Knobeln. Ausführlichere Erfahrungen und Kompetenzen im Bereich der Algorithmik und Komplexitätstheorie, beispielsweise aus der Lehrveranstaltung Algorithmix, sind vorteilhaft aber nicht notwendig.

Leistungserfassung

Die Leistungserfassung erfolgt als mündliche Prüfung. (Prüfungstermin in individueller Absprache wählbar; Zeitraum 21.02.2022 – 31.03.2022).

Termine

Wöchentlich montags um 09:15 Uhr über Zoom.