Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » approx_2020 (Übersicht)
Professor Wanka hilft recht viel, wenn man etwas ungenau ist oder mal ein bisschen hängt. Das wurde kaum negativ angerechnet. Man sollte allerdings die Algorithmen der Vorlesung und die dazugehörigen Beweise schon können. Die mathematischen Feinheiten sind nicht zwingend erforderlich, aber zumindest die Beweisidee muss kommen. Sonst war die Stimmung ganz gut.
Wanka: Was ist denn die erste Frage hier?
Prüfling: Was ist ein kombinatorisches Optimierungsproblem? 4 Tupel D, S(I), f, ziel.
W: Da fehlt noch was. Was suchen wir denn?
P: Die optimale Lösung.
W: Was machen denn jetzt Approximationsalgorithmen?
P: Eine zulässige Lösung ausgeben in poly Zeit.
W: Und was wünschen wir uns da noch?
P: Soll analysierbar sein mit abs oder rel Güte.
W: Definiere doch mal absolute güte.
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?
P: worst case Güte.
W: Wovon hängt die denn jetzt ab.
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.
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…
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.
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.
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.
P: Jede belegung ist zulässige Lsg. Wir wollen nur möglichst viel erfüllen.
W: Was hatten wir denn zuerst gemacht
P: wir hatten Belegungen gewürfelt…
W: Nein. Vorher.
P: …?
W: geradezu trivial…
P: …
W: Wie viele Klauseln werden denn mind erfüllt?
P: ah. Alles auf true alles auf false → mind die hälfte.
W: So. Da müssen wir jetzt erstmal drüber kommen.
P: (Erkläre Algo A)
W: wie analysieren wir das denn jetzt. Welchen Trick gibts denn da.
P: Indikatorvariablen für die Klauseln. (Erkläre Analyse)
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)
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.
W: Ja wo kommen die eigentlich her?
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?
P: Hybrider Ansatz. Beide laufen lassen und besseres Ergebnis nehmen.
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.
W: Jein. (er wollte genau das mit dem Schnittpunkt der Erwartungswerte hören)
W: Wie ist denn die rel güte?
P: Weiß nicht…
W: 4/3.
Ergebnis war OPT(I)