Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Die Vorträge im Blockseminar fanden am Samstag, den 02.02.2019 und am Sonntag, den 03.02.2019 in Raum 3.408 (Johann von Neumann-Haus) statt.
• Bitte beachten Sie, dass das Gebäude am Wochenende i.d.R. nicht frei zugänglich ist. Für die Seminarteilnehmer werden wir am 2. und 3.2.19 den Haupteingang des Johann von Neumann-Hauses in der Zeit von 9:00 bis 9:15 Uhr öffnen; der erste Seminarvortrag beginnt pünklich um 9:15 Uhr.
  Wer auf Grund von S-Bahn-Verspätungen o.ä. zu spät kommt und vor verschlossener Haupteingangstür des Johann von-Neumann Hauses steht, kann sich per Telefon unter 030-2093-3085 (Frau Kämpfer) oder unter 030-2093-3823 (Telefon direkt im Seminarraum) melden, um sich die Tür öffnen zu lassen.
• Alle Vortragenden werden gebeten, ihre Vortragsfolien als pdf-Datei auf einem USB-Stick mitzubringen.
• Der Zeitplan wurde leicht modifiziert; die aktuelle Version finden Sie hier.

Einführung

In diesem Seminar werden "Perlen der Theoretischen Informatik", wie im gleichnamigen Buch von Uwe Schöning dargestellt, behandelt.

Ort und Zeit

Zeit und Raum

Das Seminar findet im Wesentlichen als Blockseminar am Ende des Semesters statt. Vorher sind aber Einführungstermine und individuelle Themenbesprechungen zu besuchen.

 

Veranstalterin

Prof. Dr. Nicole Schweikardt

Termine und Deadlines

1. Mittwoch, den 14.11.2018, 15:30-17:00 Uhr, Raum 3.408:
   Vorbesprechung, Themenvergabe und Festlegung weiterer Termine
2. Bis zum 29.11.2018: bei Frau Kämpfer (Raum 3.411) Einsicht in das Buch [S] nehmen (vorher bitte per Email an kaempfer@informatik.hu-berlin.de anmelden)
3. Mittwoch, den 05.12.2018, 15:30-17:00 Uhr, Raum 3.408:
   Einführungsveranstaltung zum Thema "Grundlegende Definitionen und Resultate" (Vortrag: Prof. Dr. Nicole Schweikardt)
4. Bis spätestens Freitag, 25.01.2019: Treffen mit Prof. Dr. Schweikardt zur Besprechung des Vortrags und Vorlage der Vortragsfolien. Zu beachten: dazu muss rechtzeitig vorher ein Sprechstundentermin mit mir vereinbart werden — bitte Termin bei Frau Kämpfer bzw. Frau Sandig anfragen (per Email an kaempfer@informatik.hu-berlin.de und sandig@informatik.hu-berlin.de)
5. Die Seminarvorträge finden am Samstag und Sonntag, den 2. und 3. Februar 2019 statt.
6. Bis spätestens So, 31.03.2019, 23h59 MEZ: Abgabe der schriftlichen Ausarbeitung (Details dazu siehe Spielregeln).

Mögliche Vortragsthemen

• Thema 2 in [S] — Das zehnte Hilbertsche Problem
• Thema 3 in [S] — Das Äquivalenzproblem für LOOP(1) und LOOP(2) Programme
• Thema 4 in [S] — Das zweite LBA-Problem
• Thema 6 in [S] — Exponentielle untere Schranke für die Länge von Resolutionsbeweisen
• Thema 7 in [S] — Spektralproblem und deskriptive Komplexitätstheorie
• Thema 8 in [S] — Kolmogoroff-Komplexität, universelle Wahrscheinlichkeitsverteilung, worst-case vs. average-case
• Thema 9 in [S] — Untere Schranken durch Kolmogoroff-Komplexität
• Thema 10 in [S] — PAC-Lernen und Occam's Razor
• Thema 13 in [S] — Komplexität von Craig-Interpolanten
• Thema 14 in [S] — Äquivalenzprobleme und untere Schranken bei Branching Programmen
• Thema 15 in [S] — Die Berman-Hartmanis Vermutung und spärliche Mengen
• Thema 17 in [S] — Probabilistische Algorithmen, Wahrscheinlichkeitsverstärkung und Recycling von Zufallszahlen
• Thema 20 in [S] — Interaktive Beweise und Zero Knowledge
• Thema 22 in [S] — P ≠ NP, mit Wahrscheinlichkeit 1
• Thema 23 in [S] — Superkonzentratoren und der Heiratssatz
• Thema 24 in [S] — Pebble Game

Zeitplan

Samstag, 2.2.19

• 09h15 - 09h55 : Thema 2
• 09h55 - 10h00 : 5 Minuten Pause
• 10h00 - 10h40 : Thema 3
• 10h40 - 11h00 : 20 Minuten Pause
• 11h00 - 11h40 : Thema 4
• 11h40 - 11h45 : 5 Minuten Pause
• 11h45 - 12h25 : Thema 7
• 12h25 - 13h45 : 80 Minuten Mittagspause
• 13h45 - 14h25 : Thema 8
• 14h25 - 14h30 : 5 Minuten Pause
• 14h30 - 15h10 : Thema 9
• 15h10 - 15h30 : Diskussion

Sonntag, 3.2.19

• 09h15 - 09h55 : Thema 13
• 09h55 - 10h00 : 5 Minuten Pause
• 10h00 - 10h40 : Thema 14
• 10h40 - 11h00 : 20 Minuten Pause
• 11h00 - 11h40 : Thema 17
• 11h40 - 11h45 : 5 Minuten Pause
• 11h45 - 12h25 : Thema 20
• 12h25 - 13h45 : 80 Minuten Mittagspause
• 13h45 - 14h25 : Thema 22
• 14h25 - 14h30 : 5 Minuten Pause
• 14h30 - 15h10 : Thema 23
• 15h10 - 15h30 : Diskussion

Spielregeln

Zum Bestehen des Moduls sind nötig:

1. Der Besuch der Einführungsveranstaltungen,
2. die regelmäßige Kommunikation mit dem jeweiligen Betreuer,
3. das Halten eines wissenschaftlichen Vortrags im Blockseminar am Ende des Semesters und
4. das Erstellen einer schriftlichen Ausarbeitung: Länge ca 5 Seiten (mindestens 4, maximal 7), Layout wie in der Layout-Vorlage angegeben, Deadline: Ende des Wintersemesters 2018/19 als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt.

Literatur

[S]	Uwe Schöning: Perlen der Theoretischen Informatik, BI, 1995.
[SP]	Uwe Schöning und Randall Pruim: Gems of Theoretical Computer Sciene, Springer-Verlag, 1998

Eine Zusammenfassung einiger Grundlagen zur Wahrscheinlichkeitsrechnung findet sich hier.