Instituts-Logo Logik in der Informatik
Prof. Dr. Nicole Schweikardt
Humboldt-Logo

Seminar Aktuelle Themen der Theoretischen Informatik

Sommersemester 2018

Aktuelles   Einführung    Ort und Zeit    Vorträge    Vortragsthemen   Spielregeln


Aktuelles


Einführung

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Theoretischen Informatik erarbeitet.

Ziele sind das Kennenlernen neuer Forschungsergebnisse, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Beweistechniken, sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.

Das Seminar richtet sich an fortgeschrittene Studierende in einem Diplom- oder Masterstudiengang, die sich im Bereich Theoretische Informatik spezialisieren wollen. Die Teilnahme am Seminar setzt Kenntnisse, die in den Vorlesungen "Ausgewählte Kapitel der Logik", "Logik und Komplexität" oder "Einführung in die Datenbanktheorie" vermittelt werden, voraus.


Ort und Zeit

Zeit und Raum
Mittwochs, 15:30-17:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408
 
Veranstalter/in
Prof. Dr. Nicole Schweikardt

Vorträge

Nach und nach wird hier eine Liste der Vortragstermine angegeben.

Datum Vortragende/r Thema
25.04.18 Nicole Schweikardt
Fabian Gerhardt
Vorbesprechung und Themenvergabe und erster Vortrag:
Aufzählung der Ergebnistupel von azyklischen konjunktiven Anfragen mit konstanter Verzögerung
Donnerstag, 03.05.18, 13h00 (s.t.) Benjamin Hauskeller Dynamic Query Evaluation of Conjunctive Queries under Bag Semantics
09.05.18 heute findet kein Seminar statt
16.05.18 heute findet kein Seminar statt
23.05.18 Fabian Gerhardt Vortrag zu Thema 2: Das Faktorisierungs-Wald Theorem von Simon
30.05.18 Dr. Hubie Chen (University of London) The Logic of Counting Query Answers: A Study via Existential Positive Queries
06.06.18 heute findet kein Seminar statt
13.06.18 Tobias Löffler Thema 4: Lernen von MSO-definierbaren Hypothesen auf Strings
20.06.18 heute findet kein Seminar statt
27.06.18 tba tba
04.07.18 Dr. Sebastian Siebertz (Univ. of Warsaw) tba
11.07.18, 15h15 bis 17h00 Sarah Kleest-Meißner und David Luis Wiegandt Thema 7: Das Zählen von Dreiecken in einem Graphen unter Updates (Teile 1 und 2)
18.07.18 Dennis Radtke Thema 5: Überdeckungen von Anfrageergebnissen


Mögliche Vortragsthemen

  1. 2 Vorträge zum Thema Faktorisierte Datenbanken: Kompakte Repräsentation von Anfrageergebnissen durch f-Repräsentationen und d-Repräsentationen.
    Literatur:
    Dan Olteanu und Jakub Závodný. "Size Bounds for Factorised Representations of Query Results". ACM Trans. Database Syst. 40, Nr. 1 (März 2015): 2:1-2:44. LINK.
  2. 2 Vorträge zum Thema Das Faktorisierungs-Wald Theorem von Simon: Kompakte Repräsentationen von regulären Sprachen und deren Anwendungen.
    Literatur:
    Mikolaj Bojanczyk: "Factorization Forests". In Proc. DLT 2009, pp. 1-17. LINK.
    und
    Mikolaj Bojanczyk: "Algorithms for regular languages that use algebra". SIGMOD Record 41(2): 5-14 (2012). LINK.
  3. 2 Vorträge zum Thema Der Beweis von Courcelles Vermutung: Graphklassen beschränkter Baumweite sind genau dann in modulo-Zähl-MSO-Logik CMSO definierbar, wenn die Klasse ihrer Baumzerlegungen von einem Baumautomaten erkennbar ist.
    Während die Hin-Richtung dieser Aussage seit langem als "Courcelles Theorem" bekannt (und nicht Teil dieses Seminarvortrags) ist, löst die Rück-Richtung ein Problem, das mehr als 25 Jahre lang offen war. Zum Beweis werden u.a. eine neue und sehr nützliche Sichtweise auf MSO-Interpretationen sowie das Faktorisierungs-Wald Theorem von Simon genutzt.
    Literatur:
    Mikolaj Bojanczyk und Michal Pilipczuk: "Definability equals recognizability for graphs of bounded treewidth". In Proc. LICS 2016, pp. 407-416. LINK.
  4. 1 Vortrag zum Thema Lernen von MSO-definierbaren Hypothesen auf Strings: Unter Verwendung des Faktorisierungs-Wald Theorems von Simon wird ein Lernverfahren entwickelt, das in einer Linearzeit-Vorverarbeitungsphase eine Indexstruktur aufbauen kann, mit deren Hilfe MSO-Hypothesen auf Strings in Zeit polynomiell in der Größe der Trainingsdaten gelernt werden können.
    Literatur:
    Martin Grohe, Christof Löding, Martin Ritzert: "Learning MSO-definable hypotheses on strings". In Proc. ALT 2017, pp. 434-451. LINK. Eine etwas ausführlichere Vorabversion findet sich hier: LINK.
  5. 1 Vortrag zum Thema Überdeckungen von Anfrageergebnissen: Kompakte Repräsentationen von Anfrageergebnissen für Join-Anfragen.
    Literatur:
    Ahmet Kara, Dan Olteanu: "Covers of Query Results". In Proc. ICDT 2018, 16:1-16:22. LINK.
  6. 1 Vortrag zum Thema Verfahren und untere Schranken zum Aufzählen aller unabhängigen Mengen eines Graphen: Diese Arbeit ist ein "Klassiker" und eine der ersten Arbeiten, die sich mit der Komplexität von Aufzählungsproblemen beschäftigte.
    Literatur:
    David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: "On Generating All Maximal Independent Sets". Inf. Process. Lett. 27(3): 119-123 (1988)
  7. 2 Vorträge zum Thema Das Zählen von Dreiecken in einem Graphen unter Updates: Diese Arbeit liefert eine neue, worst-case optimale Datenstruktur zum Zählen der in einem Graphen vorkommenden Dreiecke, die die Modifikation des Graphen durch Einfügen oder Löschen von Kanten unterstützt.
    Literatur:
    Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu und Haozhe Zhang: "Counting Triangles under Updates in Worst-Case Optimal Time". Vorabversion erschienen als arXiv:1804.02780v1 [cs.DB] 9. Apr 2018. 21 Seiten. LINK.

Spielregeln

Zum Bestehen des Moduls sind nötig:
  1. Rechtzeitige Vereinbarung und Wahrnehmung eines Sprechstundentermins, der mindestens 1 Woche vor dem eigenen Seminarvortrag stattfindet und während dem ein detailliertes Vortragskonzept inkl. Vortragsfolien/Tafellayout vorgelegt wird,
  2. einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
  3. Anwesenheit an mind. 75% aller Vorträge und
  4. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas: Länge ca 5 Seiten (mindestens 4, maximal 7), Layout wie in der Layout-Vorlage angegeben, Deadline: Ende der Vorlesungszeit des Sommersemesters 2018 als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt.

Last modified: 19.06.2018
Nicole Schweikardt