Definition eines kombinatorischen Optimierungsproblems
Def. Approximationsalgorithmus (also nur, dass eine zulässige Lösung ausgegeben wird, dann wollte er noch die nice to have’s hören)
Sämtliche(!), siehe Buch, Definitionen der relativen Güte, hab dabei noch erläutert, dass wir versuchen mit garantierter relativer Güte und relativer Abweichung (=Zeugen) die relative worst case Güte einzugrenzen und dass die Analyse nicht mehr besser werden kann, wenn sich die beiden treffen + auch deutlich erklärt, dass ich weiß, was die Definitionen bedeuten und warum sie so aussehen.
Def. Rucksackproblem nach 4-Tupel
Beschreibung des exakten Algorithmus für Rucksack, inklusive Laufzeit und abgeschätzter Laufzeit (OPT(I) ⇐ Pmax * n)
Wollte ganz konkret wissen, dass die dritte Zeile der rekursiven Fj(alpha) Beschreibung für die Entscheidung steht, ob man etwas einpackt oder nicht.
Bellmansche Optimalitätsgleichung (Fj(alpha), sowohl die allgemeine Definition als auch die rekursive, ausführlich erklären was was bedeutet!) [schriftlich]
Approximationsschema für Rucksack, Laufzeit, warum man die Kommastellen abschneiden (=abrunden) muss
Rechnung zur Fehlerabschätzung (A(I) >= … >= OPT(I) - kn), habe dabei ausführlich alles nebenher erklärt, da Prof. Wanka das Blatt nicht sehen konnte [schriftlich]
Was brauchen wir noch damit wir ein Approximationsschema für’s Rucksackproblem haben? –> Abschätzung des relativen Fehlers [schriftlich]
Ärgerlicherweise hat das nebenher-erklären dazu geführt, dass ich einen kleinen Rechenfehler gemacht habe (jedoch wenige Schritte später bemerkt und korrigiert hatte, hat Prof. Wanka glaub ich nicht gekümmert)
Was ist ein Approximationsschema, PAS, FPAS, inklusive Laufzeiten, hab noch das mit dem ganz strengem Approximationsschema erklärt und warum es das nicht geben kann (Übungsaufgabe) und warum man sich überhaupt die Mühe macht zwischen PAS und FPAS zu unterscheiden.
Kann es ein FPAS für IS geben? Wieso nicht? (Anspielung stark NP-vollständig)
Was heißt denn stark NP-vollständig? (Wenn man alle Zahlen beschränken würde wär’s immer noch NP-vollständig)
Wieso kann es für stark NP-vollständige Probleme kein FPAS geben?
Evtl. noch ein paar wenige Fragen mehr die mir aber grad nicht einfallen. Dann war die Zeit um, wurde vor die Tür geschickt, überraschenderweise ging die, ich glaub nich mal ne halbe Minute danach, gleich wieder auf, ich bin rein, und Prof. Wanka hat mir verkündet, dass ich Approx mit der relativen Güte 1.0 approximiert habe :)