Allgemeines

Veranstaltungsnummer  
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Seminar
Semester Wintersemester 2017/18
Ort und Zeit  
Vorbesprechung 12.9.2017, 10:00 Uhr
(eine spätere Themenvergabe ist in Ausnahmefällen nach Absprache möglich)

Inhalt

Das Seminar befasst sich mit fortgeschrittenen Themen in meinen Lehr- und Forschungsgebieten .

Da ich im Masterbereich zwischen WS 16/17 und WS 17/18 drei verschiedene Vorlesungen angeboten habe (bzw. haben werde) und der Teilnehmerkreis für das Seminar sicher nicht riesig sein wird, ist der Plan, dass Themen aus (mindestens) diesen drei Gebieten möglich sind, also:

- Datenbanktheorie
- Komplexitätstheorie
- Logik und Komplexität.

Aufgrund der Heterogenität wird es sinnvoll sein, dass in den Vorträgen eine großzügige Einführung ins Thema stattfindet, und auch einige Haupterkenntnisse vorgestellt und erläutert werden, bevor dann eine speziellere Fragestellung vertieft wird.

Die Vorträge sollen deshalb wie eine 90-minütige Vorlesung konzipiert werden, quasi im KoMTI-Teil. 90 Minuten klingt nach sehr viel, meine Erwartung ist aber, dass versucht wird, möglichst alle Zuhörer "mitzunehmen" und deshalb recht langsam vorzugehen. Dabei kann auch teilweise die Verwendung der Tafel sinnvoll sein und ich würde tendenziell mit etwa 20 Folien rechnen. Es wird zusätzlich weitere Vorträge aus meiner Arbeitsgruppe geben.

Die Seminararbeit sollte dann in etwa wie ein dazugehöriges Skript sein.

Thematisch ist vieles möglich. Sie finden weiter unten fünf beispielhafte Themen. Wenn mehr gebraucht wird, werde ich weitere Themen bereitstellen. Selbstgewählte Themen sind nach Absprache auch möglich.

Sollten Sie auch nur prinzipielles Interesse haben, wäre ich für eine baldige Information per Mail dankbar.

Beispielhafte Themen:

Aus der Datenbanktheorie:

Effiziente parallele Anfrageauswertung.
Mögliche Hauptquelle:

  • Bas Ketsman, Dan Suciu: A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries. PODS 2017: 417-428

 

Effiziente Anfragebeantwortung bei großen Datenmengen durch Konzentration auf wichtige und kleine Teildaten.
Mögliche Hauptquelle:  

  • Wenfei Fan, Floris Geerts, Yang Cao, Ting Deng, Ping Lu: Querying Big Data by Accessing Small Data. PODS 2015: 173-184

Aus der Komplexitätstheorie:

Wie sich algorithmische Probleme "ohne Speicherverbrauch" lösen lassen
Mögliche Hauptquelle:

  • Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman: Computing with a full memory: catalytic space. STOC 2014: 857-866

Aus Logik und Komplexität:

Effiziente Aufzählung von Anfrageergebnissen
Mögliche Hauptquellen:

  • Wojciech Kazana, Luc Segoufin: First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science 7(2) (2011)
  • Wojciech Kazana, Luc Segoufin: Enumeration of monadic second-order queries on trees. ACM Trans. Comput. Log. 14(4): 25:1-25:12 (2013)

 

Lernen von logisch definierbaren Eigenschaften
Mögliche Hauptquelle:

  • Martin Grohe, Martin Ritzert: Learning first-order definable concepts over structures of small degree. LICS 2017