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

Aktuelles

• 29.1.24: Detail-Informationen zum Ablauf des Blockseminars:
  • Die Vorträge im Blockseminar finden am Samstag, den 3.2.24 (ab 9h15) und am Sonntag, den 4.2.24 (ab 10h00) 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 3.2. 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. Analog wird am 4.2. der Haupteingang von 9:45-10:00 geöffnet, und der erste Seminarvortrag beginnt pünklich 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-41100 (Heike Neugebauer, Sekretariat) oder per Email an heike.neugebauer-at-hu-berlin.de melden, um sich die Tür öffnen zu lassen.
  • Alle Vortragenden werden gebeten, ihre Vortragsfolien als pdf-Datei auf einem USB-Stick mitzubringen.
  • Den Zeitplan für die Vorträge am 3.+4.2. finden Sie hier: Link
  • Zeit pro Vortrag: 30 Min. Vortrag + 10 Min. für 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 Dozentin, sondern an alle Teilnehmer:innen des Seminars!
    Fragen der Teilnehmer:innen (auch kritische!) an die Vortragenden sind erwünscht; Ziel ist, dass wir während des Blockseminars eine fundierte wissenschaftliche Diskussion pflegen. Sie müssen keine Bedenken haben, dadurch evtl. Schwachstellen der Vortragenden aufzudecken; relevante Schwächen und Stärken werden von der Dozentin unabhängig vom Feedback der anderen Teilnehmer:innen wahrgenommen und bewertet.
    Ergänzend zu Ihren Vortragsfolien können gerne auch die Tafel verwenden.
• 24.1.24: krankheitsbedingt muss der Termin des Blockseminars leider um 1 Woche verschoben werden, auf den 3.+4.2.24. Die Deadline zur Abgabe der schriftlichen Ausarbeitung wird entsprechend auch um 1 Woche verschoben, auf den 11.2.24.
• 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 3. und 4. Februar 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 11.2.24 (23h59), als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt.

Alle genannten Deadlines sind strikt.

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 5 in [S] — LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen
• Thema 6 in [S] — Exponentielle untere Schranke für die Länge von Resolutionsbeweisen
• 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 13 in [S] — Komplexität von Craig-Interpolanten
• Thema 14 in [S] — Äquivalenzprobleme und untere Schranken bei Branching Programmen
• 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
• Thema 1 in [S2] — Dominos und logische Entscheidungsprobleme

Zeitplan der Vorträge

Samstag, 3.2.24

• 09h15-09h55: Thema 2 "Das zehnte Hilbertsche Problem"
• 09h55-10h00: 5 Minuten Pause
• 10h00-10h40: Thema 3 "Das Äquivalenzproblem für LOOP(1) und LOOP(2) Programme"
• 10h40-11h00: 20 Minuten Pause
• 11h00-11h40: Thema 5: "LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen"
• 11h40-11h45: 5 Minuten Pause
• 11h45-12h25: Thema 6: "Exponentielle untere Schranke für die Länge von Resolutionsbeweisen"
• 12h25-14h00: Mittagspause
• 14h00-14h40: Thema 8: "Kolmogoroff-Komplexität, universelle Wahrscheinlichkeitsverteilung, worst-case vs. average-case"
• 14h40-14h45: 5 Minuten Pause
• 14h45-15h25: Thema 1 in [S2]: "Dominos und logische Entscheidungsprobleme"
• 15h25-15h55: Diskussion

Sonntag, 4.2.24

• 10h00-10h40: Thema 14 "Äquivalenzprobleme und untere Schranken bei Branching Programmen"
• 10h40-10h45: 5 Minuten Pause
• 10h45-11h25: Thema 22: "P ≠ NP, mit Wahrscheinlichkeit 1"
• 11h25-11h45: 20 Minuten Pause
• 11h45-12h25: Thema 24: "Pebble Game"
• 12h25-14h00: Mittagspause
• 14h00-14h40: Thema 20: "Interaktive Beweise und Zero Knowledge"
• 14h40-14h45: 5 Minuten Pause
• 14h45-15h25: nochmals Thema 20: "Interaktive Beweise und Zero Knowledge"
• 15h25-15h55: Diskussion

Literatur

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