Das Graph Isomorphie Problem

 

Vorlesung im Sommersemester 2017

Ansprechpartner

Telefon

work
+49 241 80 21725

E-Mail

E-Mail
 

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

Martin Grohe

 

Ü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.