Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Approximationsalgorithmen, 2012-07-31   (Übersicht)

Approximationsalgorithmen, 2012-07-31

Fragen aus der Prüfung, in Klammern steht teils die Richtung der Antwort:

  • Was ist ein Kombinatorisches Optimierungsproblem?
  • Was ist ein Approximationsalgorithmus? (→ + Unterscheidung: absolute Güte, relative Güte)
  • Erkläre GreedyCol und dessen Güte; Definiere Knotenfärbung
  • Definiere das IndependentSet-Problem; Welchen Zusammenhang gibt es zur Knotenfärbung?
  • Erkläre den GreedyIS-Algorithmus. Unter Verwendung welcher Unbekannten wurde er analysiert? (→ Chromatische Zahl)
  • Es wird nach dem Maximierungsproblem zum Knotenfärbungsproblem gefragt, wie es auf einem Übungsblatt vorkam.
  • Frage nach Randomisierten Algorithmen insb. zu MaxSat, Indikatorvariable, Zusammenhang zwischen Wahrscheinlichkeit der Erfüllung einer Klausel und dem Erwartungswert der Anzahl erfüllter Klauseln.
  • Erkläre Derandomisierung von MaxSat; Was macht ein Problem+Algorithmus derandomisierbar?

Im Allgemeinen schadet es auch nicht, etliche relativen Güteschranken zu den Problemen zu kennen.