Probeklausur Lösungen

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 Lösungen
Hat jemand die Aufgabe 2 schon gemacht und mag hier vielleicht mal sein Ergebnis reinstellen? Ich hab irgendwie damit Probleme, wie ich genau die Anzahl der primitiven Operationen rechnen soll weil bei einer Addition/Multiplikation hängt das ja immer von der Länge der Zahlen ab… soll man dann sagen okay die maximale Länge einer Zahl die überhaupt vorkommt bezeichnet man mit m und rechnet dann immer als hätte jede Zahl diese Länge?

1 „Gefällt mir“

Unter der Annahme, dass die Addition zweier rationaler Zahlen genau eine primitive Operation darstellt (und damit Laufzeit 1 benoetigt), komme ich auf folgende Rekurrenzgleichung fuer den Fall n = 2^k:
C(n) = 1 fuer n = 1
C(n) = 18n^2 + 7C(n/2) fuer n > 1
Wenn ich das richtig sehe, koennen wir diese mit dem Mastertheorem, wie wir es in der Vorlesung behandelt haben gar nicht loesen, da
18n^2 \notin O(n)
Mit dem allgemeinen Mastertheorem (siehe Wikipedia oder AuD) geht es aber.

Mit C(n) = f(n) + aT(n/b) gilt:
f(n) = 18n^2 und n^{log_b (a)} = n^{log_2 (7)}
n^{log_2 (7)} ist polynomiell groesser als 18n^2
also: Es existiert ein \epsilon > 0 so dass 18n^2 \in O(n^{log_2 (7)-\epsilon}
=> wir sind in Fall 1 des Mastertheorems: C(n) \in O(n^{log_2(7)})

Nun haben wir noch das Problem, dass wir das Einfuegen zusaetzlicher Nullen in die Laufzeit mit einbeziehen muessen. Ich wuerde hier argumentieren, dass dies sofern n sich nicht als Zweierpotenz darstellen laesst, lediglich auf Stufe 0 der Rekursion erforderlich ist.
Damit kostet das hinzufuegen weiterer Nullzeilen und -spalten maximal (2^{\lceil log(2) \rceil} - n)^2 \in O(n^2) Laufzeit.
Da wie oben bereits erwaehnt n^2 polynomiell kleiner als n^{log_2 (7)} ist, haelt unsere asymptotische Schranke auch mit dem Vergroessern der Matrix. Ob diese Argumentation reicht, bin ich mir allerdings nicht so ganz sicher.


Danke für deine Antwort.
ich komme auch auf n^{log_2 (7)}, aber nicht unter der Annahme, dass für eine Addition von zwei rationalen Zahlen man nur eine primitive Operation braucht. Dadurch wird mein C(n) anders.
Ich habe auch eine Rekurrenzgleichung für n=2^k aufgestellt wobei eben bei mir m die Länge der größten überhaupt in der Rechnung vorkommenden Zahl ist.
21m²+32m für n<=2
C(n)={
(10m/4)n^2 + 7C(n/2) für n>2

Auf diese Rekurrenzgleichung bin ich wie folgt gekommen:
Für k=1 tritt der Basisfall ein. Somit muss dafür n<=2 gelten und meine ganzen Teilmatrizen sind jeweils nur eine Zahl groß. Also erhalte ich dann 18 Additionen/Subtraktionen und 7 Multiplikationen. Dafür brauch man 7*(3m²+2m)+18m= 21m²+32m primitive Operationen.
Befindet man sich nicht im Basisfall, so braucht man 7 rekursive Funktionsaufrufe und 10 Matrixadditionen. Wobei ich die Matrixadditionen noch weiter unterteilen muss. Diese Matrizen sind 2^(k-1)x2^(k-1) groß also enthalten sie 2^(2k-2) Einträge. Wnn ich für k=log(n) einsetze erhält man 2^(2k-2)=(1/4)*n² Additionen in einer Matrix deren Zahlen jeweils m lang sind. Also (10m/4)*n^2 Additionen.
Kann man das auch so angeben?

Raskolnikow wieso hast du denn die Unterteilung für dein n in der Rekurrenz bei n=1 gewählt und nicht n=2?
Und glaubt ihr echt wir dürfen einfach das Mastertheorem allgemein verwenden, auch wenn wir es hierfür gar nicht gemacht haben?!? Ist doch dann irgendwie komisch, das da sowas dran kommt oder? Und wieso darf man annehmen, dass für eine Addition von zwei rationalen Zahlen man nur eine primitive Operation braucht? Und muss man noch etwas über den Fall n!=2^k extra sagen?


Naja mit n=1=2^k ist ja k=0 und man hat die Multiplikation zweier 2^0 x 2^0, also 1 x 1 - Matrizen, d.h. die Multiplikation zweier Rationaler Zahlen. Wenn ich das als Basisfall nehme hab ich halt auch schon fuer n=2 => k=1 einen rekursiven Aufruf. Das erschien mir naheliegender.
Dann bin ich weiter davon ausgegangen, dass die Addition und Subtraktion zweier n x n Matrizen jeweils n^2 primitive Operationen benoetigt. So komm ich dann auf die 18n^2.
Ob und wenn ja welche unser beiden Loesungen akzeptabel ist, kann ich dir leider auch nicht sagen. Die beiden Loesungen unterscheiden sich ja nur in den Details, so lang die Begruendung stimmt sollten die unwesentlich sein.

Ich weiss nicht ob wir das anwenden duerfen, aber hier steht loesen sie die Rekurrenzgleichung mit Mastertheorem und mit dem Mastertheorem wie wir es in der VL gemacht haben ist das ja offensichtlich nicht moeglich. Ich vermute mal das wurde bei der Erstellung der Probeklausur uebersehen^^


Okay danke. Aber zum Basisfall: ich würde hier n<=2 nehmen da auf der Probeklausur steht: für k-1=0 wird das durch einfache Multiplikation gelöst. die bedeutet dann aber k=1 also n<=2 oder nicht?


Hm, also ich komme ja auf:


Ich habe 4er statt 2er weil eine Halbierung von n ja eine Viertelung von m zur Folge hat… oder sehe ich das falsch?

Ich bin auch von einer primitiven Operation pro Addition/Multiplikation ausgegangen, weil ja die Zahlenlänge unbekannt ist. Gibt es noch andere Lösungen oder Bestätigungen?


Ja also mit den 4ern hast du denk ich recht… die Angabe wurde ja noch irgendwie geändert, sodass es jetzt von m und nicht von n abhängt.
Im Basisfall der meines Erachtens für m<=8 ist, weil ja k=1 gelten muss dann muss n=2 und somit m=8 sein hat man denke ich 25 primitive Operationen (18 Additionen und 7 Multiplikationen)
Wie du auf den Wert 2.5m/sqrt(2) kommst weiß ich leider nicht, dort habe ich jetzt 9m/4 stehen.


Warum?
Die kleinste mögliche Matrix besteht nur aus einem Element, also n = 1. D.h. m = 2 * n² = 2

Das klingt natürlich realistischer…
Auf den Wert komme ich wegen… okay, während dem Abtippen ist mir aufgefallen, dass ich zwischendurch ein 2² unterschlagen habe. Damit komme ich jetzt auf:

3 * 2^(2k-1) + 4 * 2^(2k-2) + 7 * C(\ceil{m/4}) = 3 * 2^(2k) * 0,5 + 4 * 2^(2k) * 0.25 + 7 * C(\ceil{m/4}) = 2,5 * 2^(2k) + 7 * C(\ceil{m/4}) = 2,5 * 2^(\ceil{log_2(\sqrt{m/2})}) + 7 * C(\ceil{m/4})= 2,5 * 2^(2 * 0,5 * \ceil{log_2(m / 2)}) + 7 * C(\ceil(m/4)) = 2,5 * m/2 + 7 * C(\ceil{m/4}) = 5/4 * m + 7 * C(\ceil{m/4})

Woher kriegst du denn die 9 im Zähler?


Aber es steht explizit im Text, dass wenn k-1=0 ist man dann den Basisfall hat.

Ich bin wie folgt vorgegangen: Ich habe 18 Matrixadditionen jeweils der Dimension von 2^(k-1). Also habe ich insgesamt 18* 2^(k-1)2^(k-1)=(182^2k)/4=(18*n²)/4=18m/8=9m/4


Dann hast du mit den 9 wahrscheinlich recht. Ich sehe auf meinen Blatt eine wunderschöne Auflistung der Operationen im 4. Schritt, von denen ich keine in die spätere Rechnung aufgenommen habe :rolleyes:

[quote=???]Aber es steht explizit im Text, dass wenn k-1=0 ist man dann den Basisfall hat.
[/quote]
Du hast Recht, es steht da, aber das kann doch irgendwie nicht stimmen? Wenn k 1 ist, damit die Basisfallbedingung erfüllt ist, dann hätte man ja immer noch 2^1 x 2^1- Matrizen. Und die lassen sich nicht, wie es da so schön steht, „durch einfache Multiplikation rationaler Zahlen“ berechnen. Übersehe ich was oder ist die Aufgabe in dem Punkt einfach falsch? Es müsste doch für k = 0 gelten…


Du hast Recht, es steht da, aber das kann doch irgendwie nicht stimmen? Wenn k 1 ist, damit die Basisfallbedingung erfüllt ist, dann hätte man ja immer noch 2^1 x 2^1- Matrizen. Und die lassen sich nicht, wie es da so schön steht, „durch einfache Multiplikation rationaler Zahlen“ berechnen. Übersehe ich was oder ist die Aufgabe in dem Punkt einfach falsch? Es müsste doch für k = 0 gelten…
[/quote]

Nein k=1 stimmt schon weil dann ist k-1=0 und somit hat man nurnoch rationale Zahlen


Damn! Schon wieder verlesen… hast recht…


Auf Wunsch einer einzelnen Person hier MiriTheRings Lösung zur Probeklausur, selbstverständlich OHNE Anspruch auf Korrektheit / Vollständigkeit.
https://mega.co.nz/#!nYhhlaSY!ZfvNRFxRU7SiaL0mkKwexnKvFGlUIvruuxzWX-YVRCY

10 „Gefällt mir“

Wie kommt MiriTheRing denn bei Aufgabe 1 auf die 25 im Basisfall?


18 Additionen und 7 Multiplikationen rationaler Zahlen.

1 „Gefällt mir“

Das ist jetzt vielleicht eine dumme Frage, aber wie kommst du in Aufgabe 2 bei der Rekurrenz mit C(2n^2) im sonst-Fall auf den Term ?


Das ist das neue m. Ich hab erst m=2n^2, dann wird aufgefüllt auf Matrizen der Seitenlänge 2^log n, dann geviertelt also neue Seitenlänge 2^(log n -1). Dann bilde ich das neue m also 2*Seitenlänge^2.

1 „Gefällt mir“

Ah, jetzt seh ichs, vielen Dank. :smiley: