Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Die Vorträge im Blockseminar finden am Samstag, den 25.01.2020 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*innen werden wir am 25.01.20 den Haupteingang des Johann von Neumann-Hauses in der Zeit von 9:45 bis 10:00 Uhr öffnen; der erste Seminarvortrag beginnt pünktlich um 10:00 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-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.
  
  Unseren Zeitplan finden sie hier.
  
  Zeit pro Vortrag: 30 Min. Vortrag + 10 Min. Fragen + 5 Min. Pause
  
  Sonstige Hinweise:
  Versuchen Sie, die vorgesehene 30 Min. Vortragszeit einzuhalten (optimalerweise +/- max. 3 Min. Abweichung).
  Ihr Vortrag richtet sich nicht nur an die Dozent*innen, sondern an alle Teilnehmer*innen des Seminars!
  Fragen der Teilnehmer*innen (auch kritische!) an die Vortragenden sind erwünscht. Sie müssen keine Bedenken haben, dadurch Schwachstellen der Vortragenden aufzudecken; für uns relevante Schwächen (und Stärken) sehen und berwerten wir unabhängig des feedbacks der anderen Teilnehmer*innen.
  Sie können gerne die Tafel verwenden. Das Schreiben auf einer Tafel dauert in der Regel etwas länger und sollte daher bei der Zeitplanung des eigenen Vortrags insbesondere berücksichtigt werden.
  
• Als Vortragstag wurde der 25.01.2020 vereinbart.
• Die Vorbesprechung, Themenvergabe und Festlegung weiterer Termine fand am Mittwoch, den 23.10.2019, um 17:15-18:45 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.

  Wichtig: Die Teilnehmerzahl ist begrenzt, die Anmeldung erfolgte über AGNES. Wir bitten alle, die an der Teilnahme am Seminar interessiert sind, zu diesem Termin zu kommen. Wer per AGNES die Zulassung zum Seminar bekommen hat und an diesem Termin erscheint, wird ein Vortragsthema bekommen. Wer per AGNES die Zulassung zum Seminar bekommen hat und nicht an diesem Termin erscheint (und sich nicht mit triftigen Gründen vorab per Email bei Prof. Dr. Nicole Schweikardt oder Dr. Markus Schmid meldet), verliert die Zulassung — dadurch freiwerdende Plätze werden unter den restlichen am Termin Erscheinenden (die keine Zulassung per AGNES bekommen haben) per Losverfahren vergeben.

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.

 

Veranstalter/in

Prof. Dr. Nicole Schweikardt

Dr. Markus Schmid

Termine und Deadlines

1. Mittwoch, den 23.10.2019, 17:15-18:45 Uhr, Raum 3.408:
   Vorbesprechung, Themenvergabe und Festlegung weiterer Termine
2. Mittwoch, den 30.10.2019, 17:15-18:45 Uhr, Raum 3.408:
   Einführungsveranstaltung (Teil I) zum Thema "Grundlegende Definitionen und Resultate" (Vortrag: Dr. Markus Schmid)
3. Mittwoch, den 06.11.2019, 17:15-18:45 Uhr, Raum 3.408:
   Einführungsveranstaltung (Teil II) zum Thema "Grundlegende Definitionen und Resultate" (Vortrag: Dr. Markus Schmid)
4. Bis spätestens Freitag, 13.12.2019: Treffen mit der Betreuerin bzw. dem Betreuer zur Besprechung des Vortrags und Vorlage der Vortragsfolien.
   Zu beachten: dazu muss rechtzeitig vorher ein Sprechstundentermin vereinbart werden.
   Termine mit Prof. Dr. Nicole Schweikardt bitte bei Frau Pergl anfragen (per Email an perggesi@informatik.hu-berlin.de).
   Termine mit Dr. Markus Schmid bitte direkt per Email an markus.schmid@informatik.hu-berlin.de anfragen.
5. Die Seminarvorträge finden am Samstag, den 25. Januar 2020 statt.

Vortragsthemen

• Thema 8 in [S] — Kolmogoroff-Komplexität, universelle Wahrscheinlichkeitsverteilung, worst-case vs. average-case
• Thema 10 in [S] — PAC-Lernen und Occam's Razor
• Thema 20 in [S] — Interaktive Beweise und Zero Knowledge
• Thema 23 in [S] — Superkonzentratoren und der Heiratssatz
• Thema 24 in [S] — Pebble Game

Zeitplan

• Themen 8, 10, 20 : 10h00 - 12h15
• Mittagspause : ca. 12h15 - 13h15
• Themen 23, 24 : 13h15 - 14h45
• Diskussion : 14h45 - 15h15

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 (30 Min. Vortrag + 10 Min. Diskussion)
4. die Anwesenheit an mind. 75% aller Vorträge (d.h. die Einführungsveranstaltungen und der Vorträge im Blockseminar) und
5. 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 2019/20 als pdf-Datei per Email zu senden an den jeweiligen Betreuer (Prof. Dr. Nicole Schweikardt, Dr. Markus Schmid).

Literatur

[S]	Uwe Schöning: Perlen der Theoretischen Informatik, BI, 1995.
[S2]	Uwe Schöning: Perlen der Theoretischen Informatik - 11 weitere Themen -, Technischer Bericht, Universität Ulm, 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.