Seminar Theoretische Informatik

Seminar 1: Proofs from THE BOOK. Das Buch der Beweise ist eine Sammlung besonders eleganter mathematischer Beweise aus den Bereichen Zahlentheorie, Geometrie, Analysis, Kombinatorik und Graphentheorie, von denen wir einige im Seminar durchgehen.

Vorläufige Themen:

  1. Eigenschaften von Primzahlen und Binomialkoeffizienten (Kapitel 1-3)
  2. Der Zwei-Quadrate-Satz von Fermat (Kapitel 4)
  3. Mengen, Funktionen und die Kontinuum-Hypothese (Kapitel 15)
  4. Einfache Beweisprinzipien in der abzählenden Kombinatorik (Kapitel 21)
  5. Cayley-Formel f√ľr die Anzahl beschrifteter B√§ume (Kapitel 24)
  6. Lateinische Quadrate und das Problem von Dinitz (Kapitel 25-26)


Seminar 2: Komplexitätstheorie und Kryptographie. In diesem Seminar behandeln wir ausgewählte Themen der Komplexitätstheorie und deren Anwendung in der Kryptographie.

Vorläufige Themen:

  1. Das √Ąquivalenzproblem f√ľr LOOP(1) und LOOP(2) Programme
  2. Kolmogoroff-Komplexität
  3. Reduktionsbeweise und vollständige Probleme in unterschiedlichen Komplexitätsklassen
  4. Informationstheoretische Aspekte der Kryptographie
  5. Komplexitätstheorie und beweisbare Sicherheit
  6. Sicherheitsreduktionsbeweise

Hier finden Sie die im ersten Treffen vorgestellten Seminarthemen und die vereinbarten Termine.