Das Graph Isomorphie Problem
Vorlesung im Sommersemester 2017
Ansprechpartner
Name
- E-Mail schreiben
Termine
Vorlesung
Mo, 16:15 - 17:45 Uhr (AH I)
Mi, 10:15 - 11:45 Uhr (5055)
Übung
Mo, 12:15 - 13:45 Uhr (5052)
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.
Termine
Montag, 16:15 Uhr - 17:45 Uhr im 2350|009 (AH I)
Mittwoch, 10:15 Uhr - 11:45 Uhr im 2356|055 (5055)
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.
Die Lösungen der Übungsaufgaben werden immer Montags, 12:15-13:45 Uhr im 2356|052 (5052) vorgestellt.
Mündliche Prüfung
Zum erfolgrichen Absolvieren der Vorlesung gehört das bestehen einer mündlichen Prüfung.
Die genauen Details zur Prüfung werden im L2P bekannt gegeben.