Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Probeklausur
Nachdem es ja leider keine Musterlösung geben wird, hier so weit ich bisher Ideen habe:
A2:
(2^O(n))^2 = 2^(2*O(n)) = 2^O(n)
Für LOGSPACE geht das nicht, da log^2 nicht in O(log(n))
A3:
Da NLOGSPACE unter Komplement abgeschlossen ist, suchen wir einen Zyklus ungerader Länge.
Seien K die Knoten und E die Ecken.
choose w in K;
v0 := w;
w:= x;
n := 1;
while w !0 v0 do
choose w->x in E
w:=x;
n := n+1;
if n mod 2 == 0
write true;
A5:
Betrachte für die eine Richtung einen bipartiten Graph mit einem Zyklus ungerade Länge (v1,v2)->(v2,v3)->…->(vn, v1) mit n ungerade, dann ist oE v1 in V1 → alle vi mit i ungerade in V1 → also vn in V1 → Graph ist nicht bipartit.
Für die andere nehme an ein Graph hat keinen Zyklus ungerader Länge und ist nicht bipartit. Dann können wir analog zu oben für jeden Zyklus ein solches Vi konstruieren dass die Bedingungen für die Bipartitheit erfüllt. Vereinigung von allen diesen Vi ergibt dann unser V1 (mit korrekter Wahl der Vi, also wenn ein vn in mehr als einem Zyklus vorkommt, muss dieses in allen zugehörigen Vi sein).
Für A4 und A1 hab ich noch nichts vernünftiges bisher.
A1
Sind die sich sicher, dass es bei der A1 in Zeit O(n) laufen soll? Wir hocken schon seit Stunden dran und wüssten nich, wie wir unter O(n*logn) kommen sollen…
Hat jemand ne Idee?
Die (soweit ich das sehe) gleiche Aufgabe gab es schon auf Blatt 9 (A1). Hatten wir allerdings nicht ganz richtig, und so ganz verstanden habe ichs auch im Nachhinein nicht. Wäre schön, wenn das jemand, der es richtig hatte, nochmal erklären könnte.
wie bereitet ihr euch eigentlich vor? kommt ja ganz auf die interpretation von “ähnlich” an, die man anlegt…
Mathe4-Altklausuren-aehnlich
2 „Gefällt mir“
^^made my day
aber mal im ernst, haben die tutoren bei euch noch irgendwas näheres gesagt, wie man sich eine zu dieser probeklausur „ähnliche“ vorstellen soll?
Ihr hatte doch Herrn Schröder in der Vorlesung, oder? Bei uns in GLoLoP hieß es auch, dass die richtige Klausur ähnlich wie die Probeklausur wird. Im Endeffekt waren die beiden bis auf die eigentlichen Werte genau gleich, die Aufgabenstellung kam also 1:1 genauso dran.
Vielleicht hilft’s ja was 
das hilft ne menge! glolop bei prof. schröder soll ja auch ungleich härter gewesen sein als beim görtz… da hätte man wahrscheinlich auch ne monsterklausur schreiben können, aber so ists natürlich toll! dankeschön, das ist jetzt die hoffnung:)
hätte vielleicht noch irgendjemand eine bearbeitung von übungsblatt 10 für mich?
guck mal hier: /home/cip/2010/********/pub/
da gibts ein Verzeichnis KompAlg-2012. Da das Verzeichnis “pub” heißt geh ich mal davon aus dass es für die breite Öffentlichkeit zur Verfügung steht und der Besitzer kein Problem damit hat dass ich es hier poste… steht glaub ich auch schon in anderen Threads.
Nicht sinnvoll… Zumindest fragen solltest du ihn, bevor du das veroeffentlichst.
möglicherweise hast du recht 
Schau mal rüber zu Probeklausur - A1 - Komplexität von Algorithmen - FSI Informatik Forum, da hab ich das Thema etwas ausgelagert, weil wir hier ein klein wenig vom ursprünglichen Thema abkommen. Ich hab mal nen Vorschlag, wie man auf O(n) kommen könnte drin, auch wenn ich mir da selbst nicht so ganz sicher bin.
man kann davon ausgehen, dass while, goto und all die anderen berechnungsmodelle (außer TM) nicht drankommen, weil sie auch in der probeklausur keine rolle gespielt haben, oder?
Darauf würde ich mich persönlich nicht 100%-tig verlassen, auch wenn die TM in meinen Augen ein klarer Favorit ist.
Da es mit anderen Zahlen schwer wird, kann ich mir auch vorstellen, dass ein ähnliches Programm in nem anderen Berechnungsmodell zB gefragt wird.