Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Aktuelles

• 13.11.23: krankheitsbedingt muss der Termin am 15.11.23 leider entfallen.
• Die Vorbesprechung, Themenvergabe und Festlegung weiterer Termine findet am Mittwoch, den 01.11.2023, um 13h30 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.

  Wichtig: Die Anzahl der verfügbaren Seminarplätze ist begrenzt, die Anmeldung erfolgte über AGNES. Ich bitte 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 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

Das Seminar findet im Wesentlichen als Blockseminar ganztägig am Samstag und Sonntag, den 27. und 28. Januar 2024 statt. Vorher sind Einführungstermine zu besuchen: am 1.11.23, 15.11.23 und 29.11.23, jeweils 13h30-15h00 in Raum 3.408.

Veranstalterin

Prof. Dr. Nicole Schweikardt

Spielregeln

Zum erfolgreichen Absolvieren des Seminars sind nötig:

1. Der Besuch der drei beiden Einführungsveranstaltungen am 1.11.23, 15.11.23 und 29.11.23 (jeweils 13h30-15h00 in Raum 3.408).
2. Einsenden eines 2-seitigen Exposés zum eigenen Vortragsthema, Layout gemäß der Latex-Vorlage, Deadline: 10.12.23 (23h59), als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt
3. Einsenden der fertigen Vortragsfolien, Deadline: 21.1.24 (23h59), als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt
4. das Halten eines wissenschaftlichen Vortrags im Blockseminar (30 Min. Vortrag + 10 Min. Diskussion)
5. die Anwesenheit an mind. 75% aller Vorträge (d.h. die Einführungsveranstaltungen und die Vorträge im Blockseminar) und
6. das Erstellen einer schriftlichen Ausarbeitung: Länge ca 5 Seiten (mindestens 4, maximal 6), Layout gemäß der Latex-Vorlage, Deadline 4.2.24 (23h59), als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt.

Alle genannten Deadlines sind strikt.

Vortragsthemen

1. Thema 2 in [S] — Das zehnte Hilbertsche Problem
2. Thema 3 in [S] — Das Äquivalenzproblem für LOOP(1) und LOOP(2) Programme
3. Thema 4 in [S] — Das zweite LBA-Problem
4. Thema 5 in [S] — LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen
5. Thema 6 in [S] — Exponentielle untere Schranke für die Länge von Resolutionsbeweisen
6. Thema 8 in [S] — Kolmogoroff-Komplexität, universelle Wahrscheinlichkeitsverteilung, worst-case vs. average-case
7. Thema 10 in [S] — PAC-Lernen und Occam's Razor
8. Thema 13 in [S] — Komplexität von Craig-Interpolanten
9. Thema 14 in [S] — Äquivalenzprobleme und untere Schranken bei Branching Programmen
10. Thema 17 in [S] — Probabilistische Algorithmen, Wahrscheinlichkeitsverstärkung und Recycling von Zufallszahlen
11. Thema 20 in [S] — Interaktive Beweise und Zero Knowledge
12. Thema 22 in [S] — P ≠ NP, mit Wahrscheinlichkeit 1
13. Thema 23 in [S] — Superkonzentratoren und der Heiratssatz
14. Thema 24 in [S] — Pebble Game
15. Thema 1 in [S2] — Dominos und logische Entscheidungsprobleme

Literatur

Hier finden Sie eine Zusammenfassung einiger Grundlagen zur Wahrscheinlichkeitsrechnung. Hier finden Sie weitere Informationen.