FSI-Zimmer: geschlossen
Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Vorbereitung
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | |||
| pruefungen:hauptstudium:ls12:approx_2021 [27.07.2021 21:23] – letmesee2 | pruefungen:hauptstudium:ls12:approx_2021 [28.07.2021 08:54] (aktuell) – letmesee2 | ||
|---|---|---|---|
| Zeile 9: | Zeile 9: | ||
| * relative worst-case Güte (p_a^wc)? | * relative worst-case Güte (p_a^wc)? | ||
| * relative Gütegarantie (p_a(n)) | * relative Gütegarantie (p_a(n)) | ||
| + | |||
| + | **Was ist ein Approximationsalgorithmus? | ||
| + | |||
| + | **Welche zusätzlichen Bedingungen hatten wir an einen Approximationsalgorithmus gestellt?** | ||
| + | * t(n) muss polynomiell sein | ||
| + | * Abschätzung gegen eine optimale Lösung muss möglich sein | ||
| **Wie ist das TSP definiert? | **Wie ist das TSP definiert? | ||