Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Approx 2020 (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
pruefungen:hauptstudium:ls12:approx_2020_2 [15.10.2020 09:30] – angelegt kissen | pruefungen:hauptstudium:ls12:approx_2020_2 [19.10.2020 08:54] (aktuell) – kissen | ||
---|---|---|---|
Zeile 3: | Zeile 3: | ||
===== Vorbereitung ===== | ===== Vorbereitung ===== | ||
- | * Vorlesungsaufzeichnungen nochmal in doppelter Geschwindigkeit angeguckt (Prof. Wanka spricht so schön langsam und deutlich), Notizen angefertigt | + | * Vorlesungsaufzeichnungen nochmal in doppelter Geschwindigkeit angeguckt (Prof. Wanka spricht so schön langsam und deutlich), Notizen angefertigt |
* Übungen erneut schriftlich durchgearbeitet | * Übungen erneut schriftlich durchgearbeitet | ||
* Das Buch gelesen, die zur Vorlesung gehörenden Kapitel besonders intensiv | * Das Buch gelesen, die zur Vorlesung gehörenden Kapitel besonders intensiv | ||
Zeile 23: | Zeile 23: | ||
* Legt viel Wert auf Verständnis, | * Legt viel Wert auf Verständnis, | ||
- | * Stimmung war angenehm, es ist Prof. Wanka. | + | * Stimmung war angenehm, es ist Prof. Wanka. |
- | * Prof. Wanka wirkte anfangs ein bisschen gestresst aber sonst entspannt (hatte als Studiendekan hyperviel um die Ohren). | + | * Prof. Wanka wirkte anfangs ein bisschen gestresst aber sonst entspannt (hatte als Studiendekan hyperviel um die Ohren). |
* Mich hat überrascht, | * Mich hat überrascht, | ||
- | * Prof. Wanka hat irritierenderweise ab und zu nochmal nach Dingen gefragt, obwohl ich sie bereits gesagt hatte –> trotz Maske deutlich sprechen! | + | * 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, | + | * Und: Dieses Semester hatte Prof. Wanka keine Zeit Lösungsvorschläge zu veröffentlichen, |
- | * 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. | + | * 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! :) | * ACHTUNG: Die Prüfung läuft im Gegensatz zu den Vorlesungsaufzeichnungen nur in halber Geschwindigkeit ab! :) | ||
Zeile 34: | Zeile 34: | ||
* Definition eines kombinatorischen Optimierungsproblems | * Definition eines kombinatorischen Optimierungsproblems | ||
- | * Def. Approximationsalgorithmus (Ganz streng nach Buch, also nur, dass eine zulässige Lösung ausgegeben wird, dann wollte er noch die nice to have’s hören) | + | * 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(!), | * Sämtliche(!), | ||
* Def. Rucksackproblem nach 4-Tupel | * Def. Rucksackproblem nach 4-Tupel | ||
* Beschreibung des exakten Algorithmus für Rucksack, inklusive Laufzeit und abgeschätzter Laufzeit (OPT(I) <= Pmax * n) | * 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. | * 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!) | + | * Bellmansche Optimalitätsgleichung (Fj(alpha), sowohl die allgemeine Definition als auch die rekursive, ausführlich erklären was was bedeutet!) |
* Approximationsschema für Rucksack, Laufzeit, warum man die Kommastellen abschneiden (=abrunden) muss | * 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] | + | * 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] | * 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) | + | * Ä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, | * Was ist ein Approximationsschema, | ||
* Kann es ein FPAS für IS geben? Wieso nicht? (Anspielung stark NP-vollständig) | * Kann es ein FPAS für IS geben? Wieso nicht? (Anspielung stark NP-vollständig) | ||
* Was heißt denn stark NP-vollständig? | * Was heißt denn stark NP-vollständig? | ||
* Wieso kann es für stark NP-vollständige Probleme kein FPAS geben? | * 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 :) | + | * 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 :) |