Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » approx_2020   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

pruefungen:hauptstudium:ls12:approx_2020 [13.10.2020 23:13] – angelegt KMBpruefungen:hauptstudium:ls12:approx_2020 [13.10.2020 23:16] (aktuell) – KMB
Zeile 3: Zeile 3:
  
 Wanka: Was ist denn die erste Frage hier? Wanka: Was ist denn die erste Frage hier?
 +
 Prüfling: Was ist ein kombinatorisches Optimierungsproblem? 4 Tupel D, S(I), f, ziel. Prüfling: Was ist ein kombinatorisches Optimierungsproblem? 4 Tupel D, S(I), f, ziel.
 +
 W: Da fehlt noch was. Was suchen wir denn? W: Da fehlt noch was. Was suchen wir denn?
 +
 P: Die optimale Lösung. P: Die optimale Lösung.
 +
 W: Was machen denn jetzt Approximationsalgorithmen? W: Was machen denn jetzt Approximationsalgorithmen?
 +
 P: Eine zulässige Lösung ausgeben in poly Zeit. P: Eine zulässige Lösung ausgeben in poly Zeit.
 +
 W: Und was wünschen wir uns da noch? W: Und was wünschen wir uns da noch?
 +
 P: Soll analysierbar sein mit abs oder rel Güte. P: Soll analysierbar sein mit abs oder rel Güte.
 +
 W: Definiere doch mal absolute güte. W: Definiere doch mal absolute güte.
 +
 P: abs(A(I) - OPT(I)). P: abs(A(I) - OPT(I)).
-W: das ist ja nur für eine Eingabe. Das hilft ja jetzt noch nicht so viel weiter, was gibts denn da noch?+ 
 +W: das ist ja nur für eine Eingabe. Das hilft ja jetzt noch nicht so viel weiter, was gibts denn da  
 +noch? 
 P: worst case Güte. P: worst case Güte.
 +
 W: Wovon hängt die denn jetzt ab. W: Wovon hängt die denn jetzt ab.
 +
 P: einem n, sodass I<n. P: einem n, sodass I<n.
-W: Ok. Als erstes hatten wir uns ja die Färbungsproblematik angeschaut. Definiere doch mal das Knotenfärbung und was wir da gemacht haben.+ 
 +W: Ok. Als erstes hatten wir uns ja die Färbungsproblematik angeschaut. Definiere doch mal das  
 +Knotenfärbung und was wir da gemacht haben. 
 P: (Knotenfärbung definiert, wichtig: der Graph braucht mind eine Kante, hatte ich vergessen zu erwähnen)), (GREEDYCOL erklärt + Analyse). P: (Knotenfärbung definiert, wichtig: der Graph braucht mind eine Kante, hatte ich vergessen zu erwähnen)), (GREEDYCOL erklärt + Analyse).
 +
 W: Und wenn ich jetzt sage ich kann das besser analysieren... W: Und wenn ich jetzt sage ich kann das besser analysieren...
 +
 P: ... Dann geht das nicht wegen des Zeugen(hinzeichnen und färben). P: ... Dann geht das nicht wegen des Zeugen(hinzeichnen und färben).
 +
 W: Wir hatten ja schon relative Güte angesprochen. Was ist denn die relative Güte von GREEDYCOL. W: Wir hatten ja schon relative Güte angesprochen. Was ist denn die relative Güte von GREEDYCOL.
 +
 P: irgendwas mit O(n), bisschen erklärt (war auch nicht so wichtig nur dass es eben schlecht ist) P: irgendwas mit O(n), bisschen erklärt (war auch nicht so wichtig nur dass es eben schlecht ist)
 +
 W: Da hatten wir ja gedanklich eine 1 an den Algorithmus geschrieben. Da gabs ja noch eine 2. W: Da hatten wir ja gedanklich eine 1 an den Algorithmus geschrieben. Da gabs ja noch eine 2.
 +
 P: (Erkläre GREEDYCOL2 und GREEDYIS mit Analyse, bei beiden muss man nicht jede Zahl genau wissen, aber die Idee muss klar werden. Man zählt in t die Schleifendurchläufe und somit die Farben) P: (Erkläre GREEDYCOL2 und GREEDYIS mit Analyse, bei beiden muss man nicht jede Zahl genau wissen, aber die Idee muss klar werden. Man zählt in t die Schleifendurchläufe und somit die Farben)
 +
 W: Ok. Wir hatten ja noch ein paar andere Techniken kennengelernt und das MaxSAT Problem betrachtet. SAT ist ja NP vollst und ein Entscheidungsproblem. Wo liegt denn jetzt der Unterschied. W: Ok. Wir hatten ja noch ein paar andere Techniken kennengelernt und das MaxSAT Problem betrachtet. SAT ist ja NP vollst und ein Entscheidungsproblem. Wo liegt denn jetzt der Unterschied.
 +
 P: Jede belegung ist zulässige Lsg. Wir wollen nur möglichst viel erfüllen. P: Jede belegung ist zulässige Lsg. Wir wollen nur möglichst viel erfüllen.
 +
 W: Was hatten wir denn zuerst gemacht W: Was hatten wir denn zuerst gemacht
 +
 P: wir hatten Belegungen gewürfelt... P: wir hatten Belegungen gewürfelt...
 +
 W: Nein. Vorher. W: Nein. Vorher.
 +
 P: ...? P: ...?
 +
 W: geradezu trivial... W: geradezu trivial...
 +
 P: ... P: ...
 +
 W: Wie viele Klauseln werden denn mind erfüllt? W: Wie viele Klauseln werden denn mind erfüllt?
 +
 P: ah. Alles auf true alles auf false -> mind die hälfte. P: ah. Alles auf true alles auf false -> mind die hälfte.
 +
 W: So. Da müssen wir jetzt erstmal drüber kommen. W: So. Da müssen wir jetzt erstmal drüber kommen.
 +
 P: (Erkläre Algo A) P: (Erkläre Algo A)
 +
 W: wie analysieren wir das denn jetzt. Welchen Trick gibts denn da. W: wie analysieren wir das denn jetzt. Welchen Trick gibts denn da.
 +
 P: Indikatorvariablen für die Klauseln. (Erkläre Analyse) P: Indikatorvariablen für die Klauseln. (Erkläre Analyse)
 +
 W: Ok. Was haben wir denn da noch gemacht bei dem zweiten Algorithmus. W: Ok. Was haben wir denn da noch gemacht bei dem zweiten Algorithmus.
 +
 P:(hatte kurzen Brainlag) (erkläre algo B und hänge bisschen bei der Analyse) P:(hatte kurzen Brainlag) (erkläre algo B und hänge bisschen bei der Analyse)
 +
 W: Ja so ungefähr. Da kommen dann so zj und die befreien wir dann sehr kompliziert. Warum denn eigentlich? W: Ja so ungefähr. Da kommen dann so zj und die befreien wir dann sehr kompliziert. Warum denn eigentlich?
 +
 P: sum(zj) ist optimale Lösung von xrel. P: sum(zj) ist optimale Lösung von xrel.
 +
 W: Ja wo kommen die eigentlich her? W: Ja wo kommen die eigentlich her?
 +
 P: stehen auf der rechten Seite der Nebenbedingung für jede Klausel. P: stehen auf der rechten Seite der Nebenbedingung für jede Klausel.
 +
 W: jetzt haben wir zwei Algorithmen, beide in polyzeit. Was kann man denn jetzt machen? W: jetzt haben wir zwei Algorithmen, beide in polyzeit. Was kann man denn jetzt machen?
 +
 P: Hybrider Ansatz. Beide laufen lassen und besseres Ergebnis nehmen. P: Hybrider Ansatz. Beide laufen lassen und besseres Ergebnis nehmen.
 +
 W: Ja. Wie seiht denn da dann der worstcase aus? W: Ja. Wie seiht denn da dann der worstcase aus?
 +
 P: naja a ist besser für große k, b besser für kleine. P: naja a ist besser für große k, b besser für kleine.
 +
 W: Jein. (er wollte genau das mit dem Schnittpunkt der Erwartungswerte hören) W: Jein. (er wollte genau das mit dem Schnittpunkt der Erwartungswerte hören)
 +
 W: Wie ist denn die rel güte? W: Wie ist denn die rel güte?
 +
 P: Weiß nicht... P: Weiß nicht...
 +
 W: 4/3. W: 4/3.