Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2019-01 (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
— | pruefungen:hauptstudium:ls12:effi-2019-01 [19.02.2020 09:24] (aktuell) – angelegt NotMyName | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | 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, | ||
+ | |||
+ | **DFS**: | ||
+ | * 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, | ||
+ | * 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: < | ||
+ | * 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 | ||
+ | |||
+ | **2-SAT**: | ||
+ | * 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: < | ||
+ | * W: Und wie hat das mit dem lösen jetzt funktioniert? | ||
+ | * P: l_1 v l_2 kann man ja umschreiben zu Implikationen, | ||
+ | * 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, | ||
+ | * 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 | ||
+ | |||
+ | **Sonstiges SAT**: | ||
+ | * 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/ | ||
+ | * 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, | ||
+ | |||
+ | **Parametrisierte Komplexität/ | ||
+ | * W: Wir haben uns dann ja noch mit parametrisierter Komplexität beschäftigt, | ||
+ | * P: Länge der längsten Klausel | ||
+ | * W: Wie ist denn genau parametrisierte Komplexität definiert? | ||
+ | * P: < | ||
+ | * 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: < | ||
+ | * W: Da hatten wir dann ja einen parametrisierten Algorithmus kennengelernt, | ||
+ | * 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): | ||
+ | * W: Erklären Sie lieber noch einmal kurz den Algorithmus, | ||
+ | * 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, | ||
+ | * 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> | ||