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

  • Die vier Kennzeichen eines kombinatorischen Optimierungsproblems
  • Warum Approximationsalgorithmen (polynomielle Laufzeit, Beziehung zu optimaler Lösung)
  • TSP mit den vier Kennzeichen beschreiben
  • Erklärung, warum TSP nicht mit relativer Güte approximiert werden kann (Reduktion von Hamilton-Kreis auf TSP, Gedankengang der Reduktion beschreiben)
  • Erläuterung vom metrischen TSP anhand der vier Kennzeichen
  • Christofides Algorithmus erklären und Analyse durchführen
  • In der Übung besprochene Alternative zu Christofides vorstellen (Verdopplung der Kanten statt leichtestes Matching, analysieren und Zeugen angeben)

Insgesamt eine gute Prüfungsatmosphäre und es gibt Hilfestellungen, wenn man mal nicht weiter kommt.