An einigen Stellen sind längere Hin- und Her weggelassen, nur die korrekte und gewünschte Lösung die dann am Ende mit ein wenig Hilfe noch kam ist hier niedergeschrieben.
W: Ok. In der Vorlesung haben wir ja jetzt das Graphfärbungsproblem kennengelernt. Definieren Sie das mal.
P: <definiert das Problem mit dem 4-Tupel>
W: Und wie approximiert man das jetzt zum Beispiel? (Frage war abgezielt auf den Greedy Algorithmus)
P: <Den ersten Greedy Algorithmus kurz erklärt>
W: Und wie gut ist der jetzt?
P: deg(G) + 1 kann er potentiell zurückgeben, 2 ist die optimale Lösung, also absolute Güte von deg(G) - 1 (kurze Erklärung warum das auch richtig ist war natürlich dabei)
W: Und wenn ich jetzt sage ich kann die Analyse noch besser machen?
P: Das geht nicht (malt Zeugen dafür hin, zusammen mit Ausführungsreihenfolge der Knoten)
W: So, in der Übung hatten wir ja auch noch planare Graphen behandelt, was haben wir denn dabei verwendet?
P: (wusste es erst nicht) Den Eulerschen Polyedersatz
W: Und was konnte man damit zeigen?
P: (wusste es erst ebenfalls nicht) Dass es in einem planaren Graphen immer einen Knoten mit Grad < = 5 geben muss
W: Und wie kann man jetzt daraus einen Algorithmus zum Färben machen?
P: Den Knoten mit Grad < = 5 rausnehmen, den Rest rekursiv färben, den herausgenommenen Knoten Färben. Da Grad < = 5 muss unter den 6 Farben immer eine übrig sein.
W: Ok, wir hatten uns ja auch das Rucksackproblem angeschaut. Was war denn da mit der absoluten Güte.
P: Denn kann man nicht mit absoluter Güte approximieren
W: Und wie beweist man das dann?
P: Kurz den Beweis erklärt; nehme an es existiert Approx. Algo mit abs. Güte k, blase Preise auf um k+1, führe Approx. Algo aus und gebe dessen Lösung zurück. Diese muss dann die optimale Lösung sein.
W: Ok, aber wir haben das ja trotzdem approximiert. Wie?
P: Kurz die definition eines Approximationsschemas gesagt.
W: Und was ist da der relative Fehler?
P: |OPT(I) - A(I)| / OPT(I)
W: Und was ist der Teil der hier im Zähler steht?
P: Das ist die absolute Güte
W: Also erlaubt die Division durch OPT(I) das zu approximieren.
W: Wie ist das denn jetzt mit dem Rucksackproblem?
P: Da hatten wir als ersten einen exakten Algorithmus betrachtet. Der ist basiert auf einer rekursiven Beziehung…
W: Da hatten wir aber zuerst eine nicht-rekursive Beziehung gehabt
P: <Mit etwas Schwierigkeiten das hergeleitet>
W: Ok, und wie sah dann die rekursive Beziehung aus?
P: rekursive Beziehung hingeschrieben und erklärt, auch am Beispiel des Tableaus
W: Da fehlen jetzt aber noch die Randfälle
P: Randfälle mit ein paar kleineren Schwierigkeiten gebaut
W: Und was ist mit der Zelle (0, 0), steht da jetzt 0 oder unendlich drin
P: 0
W: Und wo lesen wir jetzt die optimale Lösung ab?
P: Hier in dieser Zelle rechts unten
W: Und wo schaut man jetzt genau nach?
P: Man muss runter gehen bis zur Zelle OPT(I) + 1 (deren Index man natürlich noch nicht kennt), bei der sieht man dann das man keine Lösung mehr finden kann und hat dann die richtige Lösung bei OPT(I)
W: Ok, und was resultiert dann für eine Laufzeit für den Algorithmus?
P: O(n * OPT(I))
W: Das hatten wir dann noch abgeschätzt?
P: Wir hatten OPT(I) zu n * P_max abgeschätzt, macht eine Laufzeit von O(n^2 * P_max)
W: Ok, und wie haben wir das jetzt approximiert?
P: Wir haben jeden Preis durch einen Faktor k geteilt so dass nun das Tableau eine polynomielle Groesse bekommt. Kurz die Formel zur Berechnung des k hingeschrieben
W: Machen Sie das mal von vorne. Womit fangen Sie denn genau?
P: Teile alle Preise durch k, rufe dann damit den exakten Algorithmus auf
W: Und was wird dann zurueckgegeben
P: Genau das was aus dem exakten Algorithmus rauskommt
W: Und woher wissen Sie dass das eine zulaessige Loesung ist?
P: Nachdem an den Volumina nichts geaendert wurde, ist jede Loesung immer noch zulaessig
W: Und wie leiten wir jetzt den Fehler daraus her?
P: Erzaehlt etwas ueber Abschaetzung des Fehlers beim runden
W: Ok, aber noch mal ganz vorne, wenn wir da stehen haben sum p^_i, was machen wir als erstes? Da hatten wir einen fiesen Trick verwendet.
P: Kommt nicht darauf, war anscheinend etwas mit in Relation stellen zum unmodifierten Problem
Insgesamt etwas nervig, wenn man etwas nicht wusste hat Prof. Wanka solange Hinweise gegeben und weiter gefragt bis dann das korrekte kam. Dafür war die Note aber erstaunlich gut.
Man musste nichts zwingend hinschreiben, konnte es aber tun wenn man will.