EffAlg 2024-04-09

Prüfer Rolf Wanka und Beisitzer Matthias Kergaßner

Alles nicht im Originalton sondern nur vom Sinn her und sehr wahrscheinlich habe ich ein paar Kleinigkeiten vergessen. Bei DFS bin ich mir mit der Reihenfolge auch nicht mehr sicher.

Die Atmosphäre war entspannt und die Bewertung ist sehr fair.

Teilweise hat er schon während ich etwas erklärt habe eine kleine Bemerkung gemacht (bspw. wie wir tief über SZKs die wir doch erst berechnen wollen definieren können). Da ist es wichtig erst die eigene Erklärung zu beenden und dann erst darauf einzugehen (Ich hab das dann übersprungen und dann musste ich tief doch nochmal erklären)

Was ist meine erste Frage denn immer? (Er hatte in der Vorlesung schon gesagt, dass er, genau wie es in den Protokollen steht, immer mit nicht trivialen Eigenschaften von Graphen anfängt, aber so genau wusste ich es nicht mehr. Hat sich auch bestimmt nicht auf die Note ausgewirkt)

Welche Eigenschaften wir uns von Graphen angeschaut haben

Naja so ungefähr. Welche nicht trivialen Eigenschaften haben wir uns von gerichteten Graphen angeschaut?

starke Zusammenhangskomponenten, über Äquivalenzrelation auf Knotenmenge uRv falls Pfad von u nach v und von v nach u existiert usw. erklärt

Welche Eigenschaften hat denn eine Äquivalenzrelation und wieso sind die erfüllt?

reflexiv, symmetrisch, transitiv und warum das gilt erklärt

Wie haben wie dann die starken ZHKs berechnet?

dfnr und tief Nummer erklärt:

dfnr: Reihenfolge in der die Knoten bei DFS durchlaufen werden

tief(u): kleinste Zahl dfnr[v] von einem Knoten v in derselben SZK der von u aus auf einem Pfad nur über Baumkanten gefolgt von höchstens einer Rück/Crosskante erreicht werden kann

Wie kann es sein, dass wir die Tief Nummer über SZKs definieren, wenn wir die gerade erst ausrechnen?

Mit Blättern usw. im Superstrukturgraphen erklären, teilweise kleine Nachfragen also am besten selber sagen es ist ein DAG und man geht ihn in umgekehrt topologischer Reihenfolge durch

Ich hab etwas viel geredet aber auch gesagt die SZKs räumen sich selber auf, aber er wollte es so hören, dass es dann so ist als wären die nie dagewesen.

Was gilt denn für Cross/Rückkanten in einem Blatt im Superstrukturgraph? (Nachfrage, weil meine Antwort nicht so ganz perfekt war)

Die verlaufen nur in diesem Blatt und gehen nicht darüber hinaus.

Was war unser Kriterium um eine SZK zu erkennen?

tief(v) == dfnr[v] und warum es Sinn macht erklärt

Warum ist das dann eine SZK, also warum kann man von jedem Knoten darin jeden anderen erreichen?

(Argumentiert ungefähr wie im Beweis im Skript)

Richtung von v aus alle im Tiefensuchbaum darunterliegenden zu erreich ist ja trivial.

Für Knoten unter v im Tiefensuchbaum argumentieren warum man wieder hoch kommt:

Es gilt dann tief < dfnr, da tief != dfnr sonst hätte das Kriterium vorher geschaltet und allgemein für jeden Knoten gilt tief < = dfnr

somit kommt man immer zu einem niedrigeren Knoten und da ist dann auch wieder tief < dfnr

⇒ streng monoton fallende Folge bis man wieder bei v ist

Was ist denn die Laufzeit und wieso?

O(|V| + |E|) weil wir jeden Knoten nur einmal besuchen und jede Kante auch nur einmal benutzen.

Da es meist mehr Kanten als Knoten gibt sind die Kanten ausschlaggebend

(hat nicht so ganz gepasst, es wäre noch wichtig zu sagen, dass der Aufwand mit min Prüfung etc. pro Kante konstant ist und nicht nur „einmal benutzt“)

Wofür haben wir den Algorithmus dann später benutzt?

Für 2 SAT

Was ist SAT überhaupt?

Ein NP vollständiges Entscheidungsproblem, SAT erklärt

Wie haben wir 2SAT dann gelöst?

Algorithmus erklärt

Klauseln l1 v l2 als Implikationen -l1 ⇒ l2 und -l2 ⇒ l1 lesen

Graph mit Literalen und Implikationen als Kanten aufbauen

Starke ZHKs berechnen dort gilt immer alles true oder alles false

Formel unerfüllbar falls eine Variable gemeinsam mit ihrer Negation in einer SZK ist

Wie nennt man das dann in einer SZK?

Es ist ja ein Kreis an Implikationen also muss alles true oder false sein sonst wären die Implikationen nicht erfüllt

(Er wollte hören, dass alle Literale in einer SZK äquivalent sind li ⇔ lj aber ich stand etwas auf dem Schlauch und hab das erst nach ein paar Hinweisen gesagt)

Wie haben wir die Belegung dann berechnet falls es erfüllbar ist?

Superstrukturgraph topologisch sortiert durchgehen.

Alle Literale in einer SZK mit Ausgangsgrad 0 auf false setzen.

Dann raustun und nächste mit Ausgangsgrad 0 anschauen.

Geht weil aus falschem alles folgen darf

Die SZKs treten doch immer in Paaren S und -S auf, wenn wir eins auf false setzen, wie sieht es dann bei dem anderen aus?

Treten immer in Paaren auf, weil wir pro Klausel immer 2 Implikationen mit den entgegengesetzten Literalen haben.

Wenn S Eingangsgrad 0 ist und wir es dort alles auf false setzen, dann hat -S Ausgangsgrad 0 und wir setzen alles auf true.

Geht weil Implikation erfüllt, wenn rechte Seite true ist

Was ist dann mit SAT wenn wir mehr als 2 Literale pro Klausel haben. Wie haben wir das gelöst?

Ich hab dann local search für 3-SAT genannt und erklärt.

Also Hamming Abstand und Hamming Kugeln genannt (Ich hab ausversehen mal Hamilton gesagt war aber nicht weiter schlimmt)

Eine unerfüllt Klausel anschauen und dort eines der Literale auf true setzen und rekursiv mit d-1 aufrufen (d-1 zu sagen ist wichtig)

Laufzeit O*(3^d), ich hatte erst nur 3^d gesagt und wusste dann nicht so ganz wieso er noch weiter fragt, aber man muss es natürlich mit O* Notation angeben

Wie haben wir local search dann benutzt um 3 SAT zu lösen?

Einmal mit 0…0 und 1…1 aufgerufen und immmer mit Distanz n/2

→ durchsucht ganze Hamming Kugel

Laufzeit O*(3^(n/2)) also O*(sqrt(3)^n) = O*(1,733^n)

Was ist der Durchmesser von der Hamming Kugel?

n (nach kurzem Überlegen inwiefern Durchmesser für sowas Sinn macht)

Wenn wir das mit 4-SAT machen wie sieht es dann aus?

dann haben wir O*(sqrt(4)^n) = O*(2^n) da lohnt es sich also nicht mehr

Wie haben wir dann k-SAT gelöst?

Monien Speckenmeyer erklärt (bei Ausprache von Monien das e nicht ausprechen)

Klausel der Länge k rausnehmen (Ich wollte erst k=1, dann k=2, … machen aber macht einfach direkt den allgemeinen Fall)

l1=True setzen, Formel dementsprechend vereinfachen und rekursiven Aufruf machen

falls das nicht klappt l1=false, l2=true

falls das nicht klappt l1=false, …=false, li=true und so weiter

Warum können wir l1 nach dem 1. Schritt auf false setzen?

Weil wir es mit true ja schon probiert haben und wenn es da eine erfüllende Belegung gäbe dann hätten wir die schon gefunden

Wie kommt man dann auf die Laufzeit?

Lineare Differenzengleichung erklärt

t(n) < = poly(n) + t(n-1) + t(n-2) + … + t(n-k)

Für 3-SAT hat man dann λ^3 = λ^2 + λ + 1 und die größte Lösung ist etwas weniger als 1,84 also O*(1,84^n)

Wie sieht das dann für größere k aus?

Wird immer größer und geht dann gegen O*(2^n)

(Er hat dann noch wie in der Volesung erzählt, dass ja die allgemeine Vermutung ist, dass SAT sich nicht besser als O*(2^n) lösen lässt, aber ist denke ich nicht wichtig das selber zu sagen)

Sie hatten ja schon etwas mit Hamilton erwähnt. Was haben wir denn gegen Ende des Semesters gemacht?

Das TSP mit dynamischer Programmierung gelöst

Was ist denn das TSP?

Ein kombinatorisches Optimierungsproblem.

Wir haben einen vollständigen Graphen gegeben und wollen einen Hamiltonkreis mit minimalen Kosten berechnen.

Hamilton Kreis/Pfad erklärt.

Brute Force Ansatz bei Knoten 1 anfangen und alle Permutationen von {2, …, n} ausprobieren hat Laufzeit O*((n-1)!) = O*((n/e)^n)

Wie haben wir das dann besser gelöst?

Gelöst mit DP, c(S, k) erklärt und Formeln hingeschrieben (weiß nicht ob das notwendig war aber hat mir auch geholfen)

Ich hab auch bei den rekursiven Definitionen mal den Begriff „Bellmansche Optimalitätsbeziehung“ fallen lassen

Laufzeit erklärt O(n^2 * 2^n) = O*(2^n) (wobei O*(2^n) sagen wahrscheinlich gereicht hätte)