Prüfer: Prof. Dr. Wanka, Beisitzer: Bernd Bassimir

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
• 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?
• Beweis-Skizze von: für Kante (u-v) ist u ist AP ⇔ tief(v) ≥ dfnr(u)
• Sonderbehandlung der DFS-Wurzel: Wie und warum?
• Laufzeit inkl. Begründung (war ihm in der Vorlesung ja schon wichtig: Kanten sind ausschlaggebend!)
• Warum Aufwand pro Kante konstant? Was ist der Aufwand pro Kante vor rekursivem Abstieg? (Knoten bereits besucht, wenn ja tief aktualisieren, wird pro Aufruf/Kante gemacht, daher konstant)

SAT:

• Definieren sie SAT.
• Erklären sie den Algoritmus von M&S
• Wie ist die Laufzeit. ⇒ Rekursionsgleichung aufstellen und charakteristisches Polynom inkl. Nullstelle für k=3
• Wir haben auch einen randomisierten Algorithmus für 2SAT gemacht? ⇒ Random Walk für 2SAT erklären. Markov Kette hinmalen und LGS aufstellen
• Was genau sind die Zustände hj? ⇒ Anzahl Schritte bis zum Endzustand („hitting“)
• Schreiben sie das lineare Gleichungssystem hin ⇒ hj = 1/2 (hj-1, hj+1) + 1; h0 = h1 + 1; hn = 0
• Warum kann man das Lösen? Wissen Sie die Lösung ⇒ n+1 Variablen, n+1 Gleichungen (Matrix hat vollen Rang), hj = n^2 - j^2 daher schlechtestenfalls quadratische Laufzeit

Ich wurde noch nach dem Algorithmus Local_Search für 3-SAT aus der Übung mit Hamming-Balls gefragt, da war ich blank, war aber nicht weiter tragisch. Insgesamt dadurch dann „nur“ 1.3 – sonst sehr angenehme Stimmung, wie ja auch den anderen Protokollen zu entnehmen ist.