Prüfer: Prof. Dr. Wanka, Beisitzer: Alexander Raß
Ich hatte die letzte Prüfung an dem Tag. Herr Wanka ist am Anfang ein wenig in seinem Sessel versunken, kam aber nachdem er die ersten Fragen gestellt hatte wieder „in Schwung“ und war wie gewohnt hoch motiviert.
Er hat ein paar Fragen (nachdem ich angefangen habe zu erklären) fast selbst beantwortet, bei anderen hat er solange weitergebohrt, bis ich sie so formuliert hatte, wie er sich die Antwort vorgestellt hatte.
Bewertung war sehr fair, er hat über ein paar Wackler und eine Verwechslung bei den Flüssen hinweggesehen. Ihm geht es offensichtlich darum, dass zum Schluss die richtigen Erklärungen und Begründungen kommen - Hilfestellung dazu gibt er wenn nötig.
Ich hatte das „Paket DFS + Flüsse“. Sind nur zwei Themen (in anderen Protokollen waren es meistens drei Themen), dafür wurden sie sehr detailliert besprochen.
DFS-2ZK:
Was haben wir für ungerichtete Graphen kennengelernt, was ist zweifache ZHK, was Artikulationspunkt? Hier haben wir uns durch die Definitionen gehangelt. Wichtig war ihm noch, dass die ZHK maximal ist und was das bedeutet.
Welche Mechanismen benutzt der Algo? → dfnr und tief-Funktion inkl. Beispiel auf Papier
Dann ging es noch genauer um Rückkanten und was sie eigentlich tun (Kreis schließen), wo sie auftauchen können und wo nicht (Rücksprung auf Ästen, …)
Woran erkennt man Artikulationspunkte und warum ist das zuverlässig?
Sonderbehandlung der DFS-Wurzel: Wie und warum?
Laufzeit inkl. Begründung (war ihm in der Vorlesung ja schon wichtig: Kanten sind ausschlaggebend!)
Flüsse:
Herleitung durch Herrn Wanka: Spezielles Optimierungsproblem ist ein „Flussproblem“. Was ist gegeben? Wichtig ist die Unterscheidung zwischen dem Problem selbst und der Definition eines Flusses. Hier hilft eine Skizze auf dem Papier. Er ging detailliert auf die Restriktionen ein und wollte die Flusserhaltung, Kapazitätsfunktion inkl. Schranken und den Fluss genau erklärt haben (er wollte u.a. darauf hinaus, dass Kapazität > 0 sein muss und Fluss >= 0 sein kann).
Genaue Erklärung und Unterscheidung: „Fluss vs. Wert des Flusses“, „Schnitt und Kapazität des Schnitts“
Herleitung erweiternde Wege und die Aussagen von Ford & Fulkerson (inkl. aller vorangegangener Definitionen zu nützlichen Kanten, Residualgraph, etc.). Hier ging es immer mal wieder zwischen erweiternden Wegen, maximalen Flüssen und minimalen Schnitten hin und her, bis die beiden Aussagen und deren Zusammenhang komplett durchleuchtet waren. Er wollte auch ein Beispiel gezeichnet haben, warum der Residualgraph nötig ist (Sperrfluss-Beispiel mit 4 Knoten aus der Vorlesung). Ich hab die Frage falsch verstanden und mit dem 4-Knoten-Beispiel die exponentielle Laufzeit bei Kapazität „c“ erklärt. Dann hat er mich wieder zurückgelenkt auf den Sperrfluss.
Zu Dinic kam gar nicht mal so viel, er ist dann eher auf das Beispiel mit unendlicher Laufzeit (Konstellation mit den Lambdas) abgedriftet. Ich sollte das Beispiel hinzeichnen und erklären, warum das ein Problem ist. Reihenfolge der Fluss-Belegung war nicht wichtig, nur wie das zustande kommt (Geometrische Reihe und Konvergenz!).