DFS:

• Was ist eine nichttrivale Eigenschaft die wir auf gerichteten Graphen mit Tiefensuche berechnet haben? ⇒ Starke Zusammenhangskomponenten erkennen
• Was ist eine starke Zusammenhangskomponenten? ⇒ Jeder Knoten von jedem anderen erreichbar und maximal groß. Evtl. auf äquivalenzrelation eingehen.
• Wie macht man das? ⇒ Tiefnummer etc. erklären. Erster Knoten mit tief == dfnr. Superstrukturgraph und Knoten mit Ausgangsgrad 0 der Reihe nach abgehen (Tiefensuche macht das automatisch).
• Wie war das mit Crosskanten? ⇒ Werden ignoriert, weil andere SCC.
• Was waren 2 Anwendungen die wir in der Übung gemacht haben? ⇒ Entscheiden ob ein endlicher Automat eine endliche Sprache akzeptiert und topologische Sortierung. (Hier waren explizit Anwendungen aus der Übung gefordert. 2SAT gilt nicht)

SAT:

• Definieren sie SAT.
• Erklären sie den Algoritmus von M&S
• Wie ist die Laufzeit. ⇒ Rekursionsgleichung aufstellen und charakteristisches Polynom. Es wurde gefragt welche Nullstelle es für k=3 hat, aber ist nicht schlimm wenn man das nicht weiß.
• Wir haben auch einen randomisierten Algorithmus für 2SAT gemacht? ⇒ Random Walk für 2SAT erklären. Markov Kette hinmalen.
• Was genau sind die Zustände hj? ⇒ Anzahl Schritte bis zum Endzustand.
• 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, hj = n^2 - j^2

DP:

• Manche NP vollständigen Probleme kann man besser machen als Holzhammer wie? ⇒ Dynamische Programmierung.
• Definieren Sie TSP.
• Wie geht das mit DP?
• Wie nennt man diese Gleichungen? ⇒ Bellmansche Optimalitätsbeziehung.
• Wie ist die Laufzeit?

Ich habe ziemlich schnell geantwortet und bei einigen Fragen deshalb auch etwas ungenau bzw. falsch geantwortet, aber alles an sich gewusst. Die Atmosphäre war sehr angenehm und Professor Wanka hat auch viel selber geredet. Alles in allem eine angenehme und humane Prüfung. Es kommt tatsächlich auf das Verständnis an, aber man sollte auch die wichtigen Formeln und Abhängikeiten auswendig parat haben.