Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Approx 2020
Inhaltsverzeichnis
Approx 2020
Vorbereitung
- Vorlesungsaufzeichnungen nochmal in doppelter Geschwindigkeit angeguckt (Prof. Wanka spricht so schön langsam und deutlich), Notizen angefertigt
- Übungen erneut schriftlich durchgearbeitet
- Das Buch gelesen, die zur Vorlesung gehörenden Kapitel besonders intensiv
- Sämtliche Beweise aus der Vorlesung (manchmal mehrmals) schriftlich nachgerechnet bis ich’s verstanden hatte. Wurde mit jedem Beweis leichter.
- Während des Lernens alle vorstellbaren Fragen aufgeschrieben (und wichtige Punkte auf die er vermutlich hinaus wollen würde) (Viele DIN A4 Blätter)
- Prüfung anhand meiner Frageliste als Selbstgespräch simuliert
- Am Abend/Morgen vor der Prüfung mehrmals alle Notizen + meine Übungslösungen durchgelesen, geschaut ob mir das Lösen irgendeiner Übungsaufgabe noch Probleme/leichte Sorgen bereiten würde, Liste der potentiellen Fragen durchgegangen um zu sehen, ob ich noch vor irgendwelchen Fragen Angst hätte, Prüfung anhand meiner Frageliste simuliert
Über’s “Protokoll”:
- Wiedergabe nach bestem Gewissen,
- keine Garantie auf Vollständigkeit oder Korrektheit,
- nicht zwingend in chronologischer Reihenfolge,
- hab von mir aus immer gleich möglichst viel zum Thema gesagt, glaube das wollen Prüfer ja so,
- aber sicherheitshalber mal alles aufgeschrieben, denn ich weiß ja nicht, ob er das sonst noch gefragt hätte.
- [schriftlich]: Musste auf dem Blatt das vor mir lag schreiben, wo nicht [schriftlich] steht war die Antwort rein mündlich.
Allgemeine Anmerkungen
- Legt viel Wert auf Verständnis, er hat z.B. sogar gefragt was es beim Fj(alpha) bedeutet wenn j=0 ist :D
- Stimmung war angenehm, es ist Prof. Wanka.
- Prof. Wanka wirkte anfangs ein bisschen gestresst aber sonst entspannt (hatte als Studiendekan hyperviel um die Ohren).
- Mich hat überrascht, dass keine schwereren Fragen drankamen, ich dachte für ne 1.0 muss man mindestens irgendeinen halbwegs krassen Beweis runterschreiben oder ne Transferaufgabe lösen.
- Prof. Wanka hat irritierenderweise ab und zu nochmal nach Dingen gefragt, obwohl ich sie bereits gesagt hatte –> trotz Maske deutlich sprechen!
- Und: Dieses Semester hatte Prof. Wanka keine Zeit Lösungsvorschläge zu veröffentlichen, offiziell sind die Übungen Klausurstoff, inoffiziell weiß ich’s natürlich nicht, aber ich wurde zu keiner Übungsaufgabe gefragt (obwohl ich alles easy gekonnt hätte). Ich empfehle auf jeden Fall, die Übungen anzugucken und zu verstehen.
- Prof. Wanka hat immer nachgefragt wenn er noch was wissen wollte, bei ein paar stressbedingten Denkfehlern von mir hat er sofort reagiert, sodass ich Gelegenheit hatte zu erklären, dass es nur ein Denkfehler war, indem ich gezeigt habe, dass der Denkfehler im Widerspruch zu anderem Wissen steht, das ich habe.
- ACHTUNG: Die Prüfung läuft im Gegensatz zu den Vorlesungsaufzeichnungen nur in halber Geschwindigkeit ab! :)
Die Prüfung
- 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 :)