Das Graph Isomorphie Problem
Vorlesung im Sommersemester 2020
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 Englisch gehalten.
Dozent
Übungsaufgaben
Wir werden wöchentliche Übungsaufgaben veröffentlichen. Das erfolgreiche Bearbeiten dieser Aufgaben, damit mindestens 50% der erreichbaren Punkte, ist erforderlich für die Prüfungszulassung.
Prüfung
Zum erfolgreichen Absolvieren der Vorlesung gehört das Bestehen einer Prüfung.
Die genauen Details zur Prüfung (insbesondere ob eine mündliche Prüfung angeboten werden kann) werden in RWTHmoodle bekannt gegeben.