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.