Das Graphisomorphie-Problem
Inhalt
Die Fragestellung ob es einen Polynomialzeit Algorithmus gibt, welcher für zwei gegebene Graphen entscheidet, ob diese isomorph sind, ist as das "Graph Isomorphie Problem" bekannt und war für über 40 Jahre eins der bekanntesten offenen Probleme in der theoretischen Informatik. Tatsächlich ist das Graph Isomorphie problem eines der wenigen natürlichen Probleme in NP, für das weder die Zugehörigkeit zu P noch die NP-Härte bekannt ist. Interessanterweise wurde dieses Fragestellung ursprünglich in den 1950er Jahren von Chemikern untersucht. Obwohl das Problem immer noch offen ist, wurden viele wichtige Teilresultate herausgefunden. Diese Ergebnisse basieren auf verschiedenen Techniken aus unterschiedlichen Bereichen der Theoretischen informatik und Diskreten mathematik. In dieser Vorlesung behandeln wir die Highlights aus der Forschung der letzten vierzig Jahre, von frühen Ergebnissen aus den 1970ern bis zu aktuellen Ergebnissen aus den letzten Jahren.
Von daher gibt diese Vorlesung zum einen tiefgehende Einblicke in aktuelle Forschung in der Theoretischen Informatik. Zum anderen, behandelt sie viele verschiedene Themen in den Bereichen Algorithmen, Komplexitätstheorie, Logik, Graphtheorie und Gruppentheorie.
Voraussetzungen
Für diese Vorlesung werden gute Grundkenntnisse in der Theoretischen Informatik, sowie das Erfolgreiche bestehen der Bachelor-Kurse "Datenstrukturen und Algorithmen" und "Berechenbarkeit und Komplexität" vorausgesetzt.
Organisatorisches
Die Vorlesung wird in englischer Sprache gelesen.
Dozent