Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Die Vorbesprechung und Themenvergabe finden in der zweiten Vorlesungswoche, am Mittwoch, den 23.10.2019, um 13:30-15:00 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.

Einführung

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Theoretischen Informatik, insbesondere der Logik, Datenbanktheorie und Komplexitätstheorie erarbeitet. Ziele sind das Kennenlernen neuer Forschungsergebnisse der Theoretischen Informatik, 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 Masterstudiengang, die sich im Bereich Theoretische Informatik spezialisieren wollen. Die Teilnahme am Seminar setzt sehr gute und zumindest in einem der o.g. Bereiche auch tiefergehende Kenntnisse der Theoretischen Informatik voraus.

Ort und Zeit

Zeit und Raum

mittwochs, 13:30-15:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408

 

Veranstalter/in

Prof. Dr. Christoph Berkholz

Vorträge

Nach und nach wird hier eine Liste der Vortragstermine angegeben.

Datum	Vortragende/r	Thema
23.10.19	Christoph Berkholz	Vorbesprechung und Themenvergabe
30.10.19	Christoph Berkholz	Compiling Existential-Positive Queries to Bounded-Variable Fragments (talk based on PODS'19 paper of C. Berkholz and H. Chen)
06.11.19	Markus Schmid	On the Complexity of the Smallest Grammar Problem over Fixed Alphabets
08.01.20	Narek Bojikian	Knowledge Compilation und #SAT
15.01.20	Benjamin Scheidt	Knowledge compilation und Weiteparameter
29.01.20	Christoph Berkholz	Untere Schranken für knowledge compilation Schaltkreise

Mögliche Vortragsthemen

• Adnan Darwiche, Pierre Marquis. "A Knowledge Compilation Map". Journal Of Artificial Intelligence Research, Volume 17, pages 229-264, 2002. LINK

1. Ein Vortrag zum Thema Knowledge Compilation und Kommunikationskomplexität.
   Literatur: Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky: Knowledge Compilation Meets Communication Complexity. IJCAI 2016: 1008-1014 LINK.
   
2. Ein Vortrag zum Thema Knowledge Compilation und #SAT
   Literatur: Florent Capelli: Understanding the complexity of #SAT using knowledge compilation. LICS 2017: 1-10 LINK.
3. Ein Vortrag zum Thema Knowledge compilation und QBF
   Literatur: Florent Capelli, Stefan Mengel: Tractable QBF by Knowledge Compilation. STACS 2019: 18:1-18:16 LINK.
4. Ein Vortrag zum Thema Knowledge compilation und Enumeration
   Literatur: Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel: A Circuit-Based Approach to Efficient Enumeration. ICALP 2017: 111:1-111:15 LINK.
5. Zwei Vorträge zum Thema Knowledge compilation und Weiteparameter
   Literatur: Antoine Amarilli, Mikaël Monet, Pierre Senellart: Connecting Width and Structure in Knowledge Compilation. ICDT 2018: 6:1-6:17 LINK.
6. Zwei Vorträge zum Thema Knowledge compilation und probabilistische Datenbanken
   Literatur: Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu: Exact Model Counting of Query Expressions: Limitations of Propositional Methods. ACM Trans. Database Syst. 42(1): 1:1-1:46 (2017) LINK . (Vom HU-Netz aus erreichbar.)

Spielregeln

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: max. 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 Wintersemesters 2019/20 als pdf-Datei per Email zu senden an Dr. Christoph Berkholz.