Insgesamt wie immer beim Professor Wanka eine sehr lockere und angenehme Stimmung. Wenn man mal etwas nicht direkt weiß hilft er einem dann noch ein wenig weiter. Die Note war auch sehr gut (1.0). Ich habe mal versucht jede (wichtigere) Frage hier aufzuschreiben, aber ein, zwei sind mir sicher entgangen. W ist Professor Wanke und P der Prüfling (also in diesem Fall leider ich).
W: Was war denn eine nicht-triviale Eigenschaft die wir mittels Tiefensuche auf gerichteten Graphen berechnet haben
P: Starke Zusammenhangskomponenten. Bedeuted dass jeder Knoten darin von jedem anderen erreichbar ist. Das hatten wir durch eine Aquivalenzrelation definiert, die sagt dass Knoten a von b aus und umgekehrt erreichbar ist.
W: Was sind denn die Eigenschaften die eine Äquivalenzrelation hat?
P: (Nach etwas nachdenken) Transitivität, Symmetrie und reflexivität
W: Und sind die hier erfüllt?
P: Ja (kurze Erklärung folgt warum das so ist)
W: Ok, und wie berechnet man das ganze dann?
P: <Erzählt von Tiefensuche, dfnr, Arten von Kanten, Definition der tief Funktion>
W: Für die Crosskanten muss jetzt ja noch etwas weiteres gelten?
P: Muss in gleicher SZHK liegen
W: Welches Hilfskonstrukt haben wir denn jetzt für den Beweis verwendet?
P: Den Superstrukturgraph
W: Und wo kommt jetzt hier die Tiefensuche ins Spiel, warum nicht mit Breitensuche?
P: Tiefensuche ist wichtig damit wir die Komponenten mit Ausgangsgrad 0 vollständig durchsuchen bevor wir sie verlassen, das würde mit BFS nicht gehen.
W: Wie erkennen wir jetzt die Starken Zusammenhangskomponenten?
P: dfnr[v] = tief(v)
W: Aber warum funktioniert das?
P: Vom Knoten v aus ist natürlich alles erreichbar, anders herum weil v der erste Knoten ist für den das gilt (noch etwas mehr erzählt)
W: Und was ist jetzt die tief Funktion genau?
P: Tiefensuchnummer eines Knotens, der über Umwege erreichbar ist
W: Und wie verhält sich die jetzt wenn wir der folgen?
P: Innerhalb der Komponente (abgesehen von v) ist die dann strikt monoton fallend wenn wir den Knoten folgen, da sie nur bei Gleichheit mit der dfnr Enden kann ist dann von jedem Knoten aus v auch erreichbar
W: Und wie verhält sich das hier mit der Laufzeit?
P: O(|V| + |E|), muss man Kantenbasiert argumentieren
W: Wir hatten dann ja in der Vorlesung deutlich später die starken Zusammenhangskomponenten für etwas verwendet, was war das denn?
P: Zum lösen von 2-SAT in linearer Zeit
W: Definieren sie das mal
P: <Definiert es>
W: Und wie hat das mit dem lösen jetzt funktioniert?
P: l_1 v l_2 kann man ja umschreiben zu Implikationen, die können wir dann in einem gerichteten Graphen einmalen
W: Was hat der Graph denn für Knoten?
P: Jedes Literal (also alle Variablen, normal und negiert)
W: Und was bedeutet denn jetzt ein Pfad in diesem Graphen
P: Implikationskette, wenn ich erstes auf wahr setze, muss ich alle auf wahr setzen. Insbesondere, wenn ich eine Kette von x_i zu negiert x_i finde und umgekehrt ist die Formel natürlich nicht erfüllbar, weil dann x_i ⇒ ~x_i >= x_i gelten müsste. Das haben wir dann mit den starken Zusammenhangskomponenten erkannt, falls x_i und ~x_i in gleicher Komponente ist die Formel nicht erfüllbar
W: Das ist ja aber nur eine Richtung, wir hatten ja noch etwas stärkeres gemacht?
P: Falls das nicht der Fall ist haben wir dann ja auch noch eine Erfüllende Belegung berechnet. Gehe in topologischer Reihenfolge durch den Superstrukturgraphen und weise jeweils allen Literalen in einem Knoten Falsch zu, entferne den und den negierten Knoten
W: Ok, das war dann ja 2-SAT, wie ist das denn zum Beispiel mit 3-SAT?
P: Das geht dann leider nicht ganz so einfach, das ist ja NP vollständig
W: Und was haben wir da zum Beispiel gemacht?
P: Algorithmus von Monien/Speckenmayer (oder so ähnlich), der nimmt sich eine Klausel und prüft zuerst wenn man das erste Literal auf Wahr setzt, dann wenn man es auf Falsch setzt und das zweite auf Wahr setzt und so weiter
W: Und warum kann man dann im zweiten Aufruf das erste Literal auf Falsch setzen?
P: Nachdem es beim ersten Aufruf ja bereichts nicht erfüllbar war wissen wir dass wir es nicht auf Wahr setzen können
W: Und wie haben wir das dann analysiert?
P: Lineare Rekurrenzen, t(n) ⇐ t(n-1) + t(n-2) + t(n-3) + poly(n), charakteristisches Polynom aufstellen, lösen nach größter Nullstelle, die dominiert dann die Komplexität
W: Wir haben uns dann ja noch mit parametrisierter Komplexität beschäftigt, was wäre denn hier der Parameter?
P: Länge der längsten Klausel
W: Wie ist denn genau parametrisierte Komplexität definiert?
P: <erklärt Definition>
W: Und in der Vorlesung hatten wir das ja an einem anderen Beispiel betrachtet?
P: Das Vertex Cover Problem
W: Definieren Sie das mal
P: <definiert es>
W: Da hatten wir dann ja einen parametrisierten Algorithmus kennengelernt, zuerst einmal: von wem ist der denn?
P: Buss & Goldsmith (Notiz: ich nehme mal an das war nur eine Frage so nebenbei, das nicht zu wissen kostet sicher keine Punkte)
W: Und das ist das jetz parametrisiert mit dem k, was wir gewissermaßen kostenlos aus der Aufgabe bekommen.
W: Erlären Sie den Algorithmus mal?
P: Basiert auf zwei Einsichten, zum Einen muss jeder Knoten mit Grad > k im VC sein (kurze Erklärung warum) und das die Anzahl der Knoten dann auch limitiert ist wenn wir den maximalen Grad ja kennen (kurze Erklärung warum)
W: Wie verwenden wir das dann im Algorithmus?
P: Erzählt wie man dadurch Knoten wegwirft etc.
W: Und wie groß wir dann der verbleibende Problemkern?
P: So in der Größe n^2, das können wir dann mit einem beliebigen Algorithmus lösen
W: Da hatten wir dann ja in der Vorlesung noch einen anderen Algorithmus aus der Vorlesung für das Vertex Cover, wie tief ist denn dabei die Rekursion?
P: (erst einmal falch beantwortet): k^2? So viele Knoten haben wir ja
W: Erklären Sie lieber noch einmal kurz den Algorithmus, und wie das mit dem k interagiert
P: Wähle eine Kante, entweder der eine Knoten oder der andere muss im Vertex Cover sein. Dadurch haben wir dann natürlich höchstens eine Rekursionstiefe von k
W: Und weil wir einen branching Faktor von 2 haben haben wir dann natürlich eine Laufzeit von 2^k
W: Das ist ja jetzt parametrisiert, aber wir haben ja damit dann noch das Optimierungsproblem gelöst
P: Erklärt wie man die beiden Algorithmen kombiniert um eine insgesamt bessere Laufzeit zu bekommen weil der Worst Case halt wo anders liegt
W: Malen Sie mal das Bild dazu hin
P: <malt die Laufzeitkurven der Algorithmen hin und zeichnet den Schnittpunkt ein>