Fachrat Informatik - Forum

Jo, die ist schon online.

Ist bereits drin. Mit großzügiger Bewertung bin ich hoffentlich durch, ich ärgere mich gerade, dass ich in Aufgabe 5 den Schritt zu in der Klausur dick und fett wieder durchgestrichen habe.

Bei Aufgabe 5 habe ich limes genutzt, um zu zeigen, das space(n^log(n)) stärker wächst. Ist das völlig die falsche Richtung?
Ansonsten bin ich zufrieden diesmal :-)

Hab ich auch versucht. Müsste eigentlich auch gehen, so weit ich das überblicke?

Also bei genauerem Hinsehen war die ja echt easy. Verdammt. Gnade bitte, liebe Korrektoren..

Zu Aufgabe 5: Warum "das mit dem limes" alleine nicht reicht: Weil PSPACE nicht definiert ist als SPACE(f(n)) für eine Funktion f, sondern als unendliche Vereinigung von SPACE(f_k(n)) für f_k(n):=n^k und k =1... unendlich. Der Hierarchiesatz funktioniert nur für einzelne Funktionen, aber nicht für unendliche Mengen von Funktionen.
Deshalb braucht man den Zwischenschritt unbedingt. Das zu erkennen war ein wesentlicher Teil der Aufgabenstellung und ist auch schon mal in einer Übungsaufgabe vorgekommen.

Okay, das kann ich nachvollziehen. O(1) ist aber doch Konstant, so hab ich zumindest argumentiert, und damit lieg ich doch nicht ganz falsch dann, oder?
Teilpunkte? ;-)

Ja, Teilpunkte gibt es ja fast immer, wenn was Richtiges dabei ist Allerdings: Falsch ist es zwar "nicht ganz", aber doch "ziemlich". Also leider nicht allzu viele Teilpunkte. Ich gebe zu, dass diese Aufgabe eher teilpunktfeindlich war, denn ohne das entscheidende Problem zu erkennen, kam es einem vielleicht immer noch als genügend schwierig vor, obwohl halt das Entscheidende fehlte. Somit hat man dann eigentlich was ganz anderes gemacht und dafür kann es halt leider keine Teilpunkte geben, auch wenn man die veränderte Fragestellung richtig bearbeitet hat. Reine Folgefehler sind zwar ok, aber wenn durch den Ausgangsfehler die Aufgabe stark vereinfacht wird (wie in diesem Fall), dann leider nicht mehr.

Ich weiß nicht ob ichs richtig hab, aber ich hatte vorher 2 Aufgaben gerechnet die einen ähnlichen zwischenschritt erforderten, daher wusst ich dass beim pspace erstmal n "zwischending" reinmuss wenn man hirarchiesatz benutzen will.

ansonsten wars lustig:
freitag mittag 0 ahnung von kva
samstag mittag die hälfte der aufgabenstellungen verstanden
sonntag mittag großteil der musterlösungen halbwegs nachvollziehbar
montag mittag prüfung :-)