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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

pruefungen:hauptstudium:ls12:approx_2014 [30.07.2014 15:15] – angelegt limespruefungen:hauptstudium:ls12:approx_2014 [30.07.2014 15:18] (aktuell) – limes
Zeile 6: Zeile 6:
   * Definition von TSP und metrischem TSP angeben (das Tupel)   * Definition von TSP und metrischem TSP angeben (das Tupel)
   * Christophides Algorithmus, erst alle 5 Schritte, dann die Analyse zu jedem einzelnen Schritt und damit die Guete herleiten? (-> \rho <= 3/2-1/n), dabei auch kleinere Zwischenfragen wie: wann kann man eine Eulertour berechnen? Was ist ein leichtestes Matching?   * Christophides Algorithmus, erst alle 5 Schritte, dann die Analyse zu jedem einzelnen Schritt und damit die Guete herleiten? (-> \rho <= 3/2-1/n), dabei auch kleinere Zwischenfragen wie: wann kann man eine Eulertour berechnen? Was ist ein leichtestes Matching?
 +  * Wo benutzt der Dreiecksungleichung (-> nirgends, nur fuer die Analyse braucht man sie an zwei Stellen)
   * geht das auch besser? (-> nein, gibt entsprechenden Zeugen, den muss man auch beschreiben koennen!)   * geht das auch besser? (-> nein, gibt entsprechenden Zeugen, den muss man auch beschreiben koennen!)
   * MaxSAT Problem definieren   * MaxSAT Problem definieren
   * Wie funktioniert Algorithmus A? Was ist sein Erwartungswert? (-> Wahrscheinlichkeit fuer Erfuellung einer Klausel, Indikatorvariable einfuehren, entsprechende Summe fuer Erwartungswert bilden)   * Wie funktioniert Algorithmus A? Was ist sein Erwartungswert? (-> Wahrscheinlichkeit fuer Erfuellung einer Klausel, Indikatorvariable einfuehren, entsprechende Summe fuer Erwartungswert bilden)
   * Wie kann man das deterministisch machen? (-> Derandomisierung erklaeren, erklaeren warum der Algorithmus keine "schlechteren" Erwartungswerte finden kann)   * Wie kann man das deterministisch machen? (-> Derandomisierung erklaeren, erklaeren warum der Algorithmus keine "schlechteren" Erwartungswerte finden kann)