Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

SE Kommunikationskomplexität

 

Dozent: Prof. Dr. Christoph Berkholz

 

Das Bachelorseminar "Kommunikationskomplexität" findet digital statt. Informationen und aktuelle Mitteilungen werden im Moodle-Kurs der Lehrveranstaltung unter

https://moodle.hu-berlin.de/course/view.php?id=97939

bereitgestellt. Alle Teilnehmer*innen müssen sich dort anmelden, der Einschreibeschlüssel für den Moodle-Kurs wird an die in Agnes zugelassenen Studierenden verschickt. Alternativ kann der Einschreibeschlüssel auch per E-Mail an den Dozenten erfragt werden.

 

Inhalt

Wie viel Kommunikation ist nötig, um eine Funktion zu berechnen, wenn die Eingabebits auf zwei oder mehrere Parteien aufgeteilt sind? Diese Frage steht im Zentrum der Kommunikationskomplexität, einem Teilgebiet der theoretischen Informatik. Mit der Beantwortung dieser Frage für konkrete Funktionen liefert die Kommunikationskomplexität ein elegantes und mächtiges mathematisches Werkzeug zum Beweisen von unteren Schranken in verschiedenen Berechnungsmodellen. In diesem Seminar sollen Methoden und Ergebnisse der Kommunikationskomplexität erarbeitet und präsentiert werden.

 

Die Vortragsthemen orientieren sich an den folgenden beiden Büchern (PDF-Versionen sind aus dem HU-Netz verfügbar):

 

Zeitplan

  • Mittwoch, 28. Oktober 2020. Ende der zentralen Einschreibefrist in Agnes, anschließend Anmeldung im Moodle-Kurs.
  • Freitag, 6. November, 11:15 - 12:45. Gemeinsame Vorbesprechung via ZOOM (verpflichtend für alle Teilnehmer*innen, die ZOOM-Zugangsdaten werden über Moodle bekannt gegeben).
  • Dezember 2020. Individuelle Vorbesprechungstermine.
  • An einem oder mehreren Freitagen im Januar 2021. Durchführung des Blockseminars via ZOOM.
  • Bis 31. März 2021. Abgabe der Seminarausarbeitungen.