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

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