Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » approx_9_10_2019 (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:hauptstudium:ls12:approx_9_10_2019 [09.10.2019 10:01] – angelegt NotMyName | pruefungen:hauptstudium:ls12:approx_9_10_2019 [09.10.2019 10:25] (aktuell) – NotMyName | ||
---|---|---|---|
Zeile 4: | Zeile 4: | ||
An einigen Stellen sind längere Hin- und Her weggelassen, | An einigen Stellen sind längere Hin- und Her weggelassen, | ||
- | * W: Was wird denn hier immer zuerst gefragt? | + | |
- | * P: Was ist ein kombinatorischen Optimierungsproblem. Dann den 4-Tupel aufgezählt | + | * P: Was ist ein kombinatorischen Optimierungsproblem. Dann den 4-Tupel aufgezählt |
- | * W: Das sagt ja jetzt aber noch nicht was das Problem wirklich ist (?) | + | * W: Das sagt ja jetzt aber noch nicht was das Problem wirklich ist (?) |
- | * P: Definition mit finde korrekte Ausgabe sodass ziel{f(Ausgabe)} optimiert wird | + | * P: Definition mit finde korrekte Ausgabe sodass ziel{f(Ausgabe)} optimiert wird |
- | * W: Ok. Und was wird dann immer als zweites gefragt? | + | * W: Ok. Und was wird dann immer als zweites gefragt? |
- | * P: Was ist ein Approximationsalgorithmus. Hier ist die Definition recht offen, muss nur eine korrekte Ausgabe produzieren | + | * P: Was ist ein Approximationsalgorithmus. Hier ist die Definition recht offen, muss nur eine korrekte Ausgabe produzieren |
- | * W: Und was hätten wir dann gerne für den Algorithmus? | + | * W: Und was hätten wir dann gerne für den Algorithmus? |
- | * P: polynomielle Laufzeit, beweisbare Güte (absolut oder relativ) | + | * P: polynomielle Laufzeit, beweisbare Güte (absolut oder relativ) |
- | * W: Dann definieren Sie mal die absolute Güte | + | * W: Dann definieren Sie mal die absolute Güte |
- | * P: < | + | * P: < |
- | * W: Ok. In der Vorlesung haben wir ja jetzt das Graphfärbungsproblem kennengelernt. Definieren Sie das mal. | + | |
- | * P: < | + | * P: < |
- | * W: Und wie approximiert man das jetzt zum Beispiel? (Frage war abgezielt auf den Greedy Algorithmus) | + | * W: Und wie approximiert man das jetzt zum Beispiel? (Frage war abgezielt auf |
- | * P: <Den ersten Greedy Algorithmus kurz erklärt> | + | * P: <Den ersten Greedy Algorithmus kurz erklärt> |
- | * W: Und wie gut ist der jetzt? | + | * W: Und wie gut ist der jetzt? |
- | * P: deg(G) + 1 kann er potentiell zurückgeben, | + | * P: deg(G) + 1 kann er potentiell zurückgeben, |
- | * W: Und wenn ich jetzt sage ich kann die Analyse noch besser machen? | + | * 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) | + | * 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? | + | * 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 | + | * P: (wusste es erst nicht) Den Eulerschen Polyedersatz |
- | * W: Und was konnte man damit zeigen? | + | * 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 | + | * 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? | + | * 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. | + | * 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 | + | * P: Denn kann man nicht mit absoluter Güte approximieren |
- | * W: Und wie beweist man das dann? | + | * 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. | + | * 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? | + | * W: Ok, aber wir haben das ja trotzdem approximiert. Wie? |
- | * P: Kurz die definition eines Approximationsschemas gesagt. | + | * P: Kurz die definition eines Approximationsschemas gesagt. |
- | * W: Und was ist da der relative Fehler? | + | * W: Und was ist da der relative Fehler? |
- | * P: |OPT(I) - A(I)| / OPT(I) | + | * P: |OPT(I) - A(I)| / OPT(I) |
- | * W: Und was ist der Teil der hier im Zähler steht? | + | * W: Und was ist der Teil der hier im Zähler steht? |
- | * P: Das ist die absolute Güte | + | * P: Das ist die absolute Güte |
- | * W: Also erlaubt die Division durch OPT(I) das zu approximieren. | + | * W: Also erlaubt die Division durch OPT(I) das zu approximieren. |
- | * W: Wie ist das denn jetzt mit dem Rucksackproblem? | + | * 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... | + | * 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 | + | * W: Da hatten wir aber zuerst eine nicht-rekursive Beziehung gehabt |
- | * P: <Mit etwas Schwierigkeiten das hergeleitet> | + | * P: <Mit etwas Schwierigkeiten das hergeleitet> |
- | * W: Ok, und wie sah dann die rekursive Beziehung aus? | + | * W: Ok, und wie sah dann die rekursive Beziehung aus? |
- | * P: rekursive Beziehung hingeschrieben und erklärt, auch am Beispiel des Tableaus | + | * P: rekursive Beziehung hingeschrieben und erklärt, auch am Beispiel des Tableaus |
- | * W: Da fehlen jetzt aber noch die Randfälle | + | * W: Da fehlen jetzt aber noch die Randfälle |
- | * P: Randfälle mit ein paar kleineren Schwierigkeiten gebaut | + | * 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 | + | * W: Und was ist mit der Zelle (0, 0), steht da jetzt 0 oder unendlich drin |
- | * P: 0 | + | * P: 0 |
- | * W: Und wo lesen wir jetzt die optimale Lösung ab? | + | * W: Und wo lesen wir jetzt die optimale Lösung ab? |
- | * P: Hier in dieser Zelle rechts unten | + | * P: Hier in dieser Zelle rechts unten |
- | * W: Und wo schaut man jetzt genau nach? | + | * 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) | + | * 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? | + | * W: Ok, und was resultiert dann für eine Laufzeit für den Algorithmus? |
- | * P: O(n * OPT(I)) | + | * P: O(n * OPT(I)) |
- | * W: Das hatten wir dann noch abgeschätzt? | + | * W: Das hatten wir dann noch abgeschätzt? |
- | * P: Wir hatten OPT(I) zu n * P_max abgeschätzt, | + | * P: Wir hatten OPT(I) zu n * P_max abgeschätzt, |
- | * W: | + | * 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. | 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, | Man musste nichts zwingend hinschreiben, |