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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls12:approx_9_10_2019 [09.10.2019 10:08] – NotMyNamepruefungen:hauptstudium:ls12:approx_9_10_2019 [09.10.2019 10:25] (aktuell) – NotMyName
Zeile 26: Zeile 26:
   * 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.   * W: Ok, wir hatten uns ja auch das Rucksackproblem angeschaut. Was war denn da mit der absoluten Güte.
Zeile 59: Zeile 59:
   * 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, macht eine Laufzeit von O(n^2 * P_max)   * P: Wir hatten OPT(I) zu n * P_max abgeschätzt, macht eine Laufzeit von O(n^2 * P_max)
-  * 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, konnte es aber tun wenn man will. Man musste nichts zwingend hinschreiben, konnte es aber tun wenn man will.