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

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls12:effi-2024-04 [09.04.2024 21:02] – angelegt xe60burapruefungen:hauptstudium:ls12:effi-2024-04 [10.04.2024 15:19] (aktuell) – xe60bura
Zeile 1: Zeile 1:
-====== EffAlg 09.04.2024 ======+====== EffAlg 2024-04-09 ======
 Prüfer Rolf Wanka und Beisitzer Matthias Kergaßner Prüfer Rolf Wanka und Beisitzer Matthias Kergaßner
  
Zeile 5: Zeile 5:
 Bei DFS bin ich mir mit der Reihenfolge auch nicht mehr sicher. Bei DFS bin ich mir mit der Reihenfolge auch nicht mehr sicher.
  
-Die Atmosphäre war entspannt und die Notengebung ist sehr fair.+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). 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).
Zeile 14: Zeile 14:
 ==== DFS ==== ==== 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)+**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 Welche Eigenschaften wir uns von Graphen angeschaut haben
  
-**Naja so ungefähr. Welche nichttrivialen Eigenschaften haben wir uns von gerichteten Graphen angeschaut?**+**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 starke Zusammenhangskomponenten, über Äquivalenzrelation auf Knotenmenge uRv falls Pfad von u nach v und von v nach u existiert usw. erklärt
Zeile 36: Zeile 36:
 **Wie kann es sein, dass wir die Tief Nummer über SZKs definieren, wenn wir die gerade erst ausrechnen?** **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+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. 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.
Zeile 46: Zeile 46:
 **Was war unser Kriterium um eine SZK zu erkennen?** **Was war unser Kriterium um eine SZK zu erkennen?**
  
-tief(v) == dfnr[v] erklärt+tief(v) == dfnr[v] und warum es Sinn macht erklärt
  
-**Warum ist das dann eine SZK?**+**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) (Argumentiert ungefähr wie im Beweis im Skript)
Zeile 89: Zeile 89:
 Graph mit Literalen und Implikationen als Kanten aufbauen Graph mit Literalen und Implikationen als Kanten aufbauen
  
-Starke ZHKs berechnen dort gilt immer alles true alles false+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 Formel unerfüllbar falls eine Variable gemeinsam mit ihrer Negation in einer SZK ist
Zeile 97: Zeile 97:
 Es ist ja ein Kreis an Implikationen also muss alles true oder false sein sonst wären die Implikationen nicht erfüllt 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)+(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?** **Wie haben wir die Belegung dann berechnet falls es erfüllbar ist?**
Zeile 111: Zeile 111:
 **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?** **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.+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. Wenn S Eingangsgrad 0 ist und wir es dort alles auf false setzen, dann hat -S Ausgangsgrad 0 und wir setzen alles auf true.
Zeile 117: Zeile 117:
 Geht weil Implikation erfüllt, wenn rechte Seite true ist 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?**+**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. Ich hab dann local search für 3-SAT genannt und erklärt.
Zeile 145: Zeile 145:
 **Wie haben wir dann k-SAT gelöst?** **Wie haben wir dann k-SAT gelöst?**
  
-Monien Speckenmeyer erklärt (bei Ausprache von Monien das i betonen)+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) Klausel der Länge k rausnehmen (Ich wollte erst k=1, dann k=2, ... machen aber macht einfach direkt den allgemeinen Fall)
Zeile 159: Zeile 159:
 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 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?**+**Wie kommt man dann auf die Laufzeit?**
  
 Lineare Differenzengleichung erklärt Lineare Differenzengleichung erklärt
Zeile 176: Zeile 176:
 ==== TSP ==== ==== TSP ====
  
-**Sie hatten ja schon etwas mit Hamilton erwähnt - was haben wir denn gegen Ende des Semesters gemacht?**+**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 Das TSP mit dynamischer Programmierung gelöst
Zeile 186: Zeile 186:
 Wir haben einen vollständigen Graphen gegeben und wollen einen Hamiltonkreis mit minimalen Kosten berechnen.  Wir haben einen vollständigen Graphen gegeben und wollen einen Hamiltonkreis mit minimalen Kosten berechnen. 
  
-Hamilton Kreis erklärt.+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)  Brute Force Ansatz bei Knoten 1 anfangen und alle Permutationen von {2, ..., n} ausprobieren hat Laufzeit O*((n-1)!) = O*((n/e)^n) 
Zeile 192: Zeile 192:
 **Wie haben wir das dann besser gelöst?** **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)+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 Ich hab auch bei den rekursiven Definitionen mal den Begriff "Bellmansche Optimalitätsbeziehung" fallen lassen