FSI-Zimmer: geschlossen
Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » approx_2019 (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| — | pruefungen:hauptstudium:ls12:approx_2019 [09.10.2019 10:27] (aktuell) – angelegt Anouk | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| + | * 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, | ||