Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼
 

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Seminar: Komplexität und Kryptologie


Termin: SE Mi 11-13 (RUD 26, 1'306) Prof. J. Köbler, S. Kuhnert
Zuordnung:

Bachelor-Monostudiengang (B.Sc.): Seminar

Bachelor-Kombinationsstudiengang (B.A.): Seminar

Diplom-Hauptstudium: Seminar


Inhalte und Lernziele

In diesem Seminar werden aktuelle Themen der Theoretischen Informatik, insbe-
sondere der Komplexitätstheorie und der Kryptologie behandelt. Hierbei gehen wir
auch gern auf Teilnehmerwünsche ein.
In diesem Semester liegt der Schwerpunkt auf dem Graphisomorphieproblem, also
der Frage, ob es für zwei gegebene Graphen G und H eine Bijektion zwischen deren
Knotenmengen gibt, die Kanten auf Kanten und Nicht-Kanten auf Nicht-Kanten
abbildet. Für dieses Problem ist kein Polynomialzeitalgorithmus bekannt, gleichzeitig
gilt es als unwahrscheinlich, dass es NP-hart ist. Wegen der hohen praktischen Rele-
vanz wurden zahlreiche Algorithmen entwickelt, die das Problem für eingeschränkte
Graphklassen effizient lösen.
Vorkenntnisse über das Isomorphieproblem sind zum Besuch dieses Seminars nütz-
lich, jedoch nicht notwendig.
 

Seminarankündigung (PDF)

 

Vorträge

  • Sebastian Kuhnert: Isomorphie von k-Bäumen in Logspace
    31.10.2012
  • Florian Häber: Isomorphie von partiellen k-Bäumen
    07.11.2012 und 14.11.2012
  • Michael Jung: Graphisomorphie in SPP
    21.11.2012 und 28.11.2012
  • Sebastian Kuhnert: Isomorphie von Intervallgraphen in Logspace
    09.01.2013 und 16.01.2013
  • Zeno Sebastian Endemann: „Graphenisomorphie auf Schnittgraphen
    23.01.2013
  • Immanuel Sims: Graphen mit beschränkter Baumweite
    30.01.2013 und 6.02.2013