Prüfung in Approximationsalgorithmen, Juli 2016:
Definition kombinatorisches Optimierungsproblem (4-Tupel)
Anforderungen an Approximationsalgorithmen (polynomielle Laufzeit, Vergleichbarkeit/Güte)
Was geben Approximationsalgorithmen aus?
Definitionen von absoluter/relativer Güte
GreedyCol inklusive Analyse (absolute Güte, Begründung dazu)
Zeuge für GreedyCol (wie in Übung)
GreedyCol2 (Güte, Rekursive Analyse, Begründungen)
Alles in allem sehr angenehme Prüfung, viel Hilfe, faire Benotung. Algorithmen und azugehörige Analyse sollte man allerdings schon sehr genau drauf haben. Bei überschaubarem Stoffumfang aber durchaus gut bis sehr gut machbar!