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

Pruefung in Approximationsalgorithmen, Juli 2014

  • Was ist ein kombinatorisches Optimierungsproblem? (→ 4-Tupel, die Komponenten nennen)
  • Welche Anforderungen an Approximationsalgorithmen werden gestellt? (→polynomielle Laufzeit, beweisbare Guete)
  • Die ganzen Definitionen zu relativer Guete (individuelle relative Guete, relative worst-case Guete, …)
  • 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?
  • 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!)
  • MaxSAT Problem definieren
  • 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)