Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » EffAlg 2024-04-09

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:hauptstudium:ls12:effi-2024-04 [09.04.2024 21:02] – angelegt xe60bura
+++ pruefungen:hauptstudium:ls12:effi-2024-04 [09.04.2024 21:12] – gelöscht xe60bura
@@ Zeile 1: / Zeile 1: @@
-====== EffAlg 09.04.2024 ======
-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 Notengebung 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)
-==== DFS ====
-** Was ist meine erste Frage denn immer? **(Hatte er in der Vorlesung schonmal erwähnt und hat sich bestimmt nicht auf die Note ausgewirkt)
-Welche Eigenschaften wir uns von Graphen angeschaut haben
-**Naja so ungefähr. Welche nichttrivialen 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 topologischere 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] erklärt
-**Warum ist das dann eine SZK?**
-(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")
-==== SAT ====
-**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 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 Klauseln 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 i betonen)
-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 berechnet sich 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)
-==== TSP ====
-**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 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 die vor mir zu sehen)
-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)