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.
Klausurvorbereitung
Hi, ich hab mir mal die drei letzten Klausuren angeschaut… Hier mal meine Ergebnisse zur Aufgabe 1, waer super wenn das jemand verifizieren koennte:
H10
1.
a = 2 => n^(log_a 3)
a = 3 => n log n
a > 3 => n
R(n) = 5^(n-1)+2^n
R(n) \in \Theta (5^n)
S(n) = n2^(n-1)
S(n) \in \Theta (n2^n)
F10
1.
a < 3 => n
a = 3 => n log n
a > 3 => n^(log_3 a)
R(n) = 3^n - 2
R(n) \in \Theta (3^n)
S(n) = n2^(n-1)
S(n) \in \Theta (n2^n)
H09
1.
a < 2 => n
a = 2 => n log n
a > 2 => n^(log_2 a)
R(n) = -3^n+2^(n+1)
R(n) \in \Theta (3^n)
S(n) = 2*3^(n-2)+n3^(n-2)
S(n) \in \Theta (n3^n)
Dyck-Sprachen
Hi, vielleicht kann mir jemand weiterhelfen. Wir hatten in der VL mal folgende Definition
w \in D <=> \delta(w) = 0 und w = u * v => \delta (u) >= 0.
So weit, so gut. Alternativ gibts jetzt im Skriptum und in den Folien (cat4.pdf) folgende Definition
w \in D <=> |w|_a = |w|_b und w = u * v => |u|_a >= |u|_v
Die 1. Bedingung ist klar, aber mit dem 2. Teil kann ich leider nichts anfangen… was soll |u|_v bedeuten?
|u|_b wuerde mir einleuchten, weil ich damit garantiere, dass die hoehenfunktion nie unter 0 kommt, aber was heisst hier |u|_v?
Tippfehler schliesse ich mal aus, weils in beiden PDFs mehrfach so erwaehnt wird. Hat jemand ne Idee?
[quote=el doktore]Die 1. Bedingung ist klar, aber mit dem 2. Teil kann ich leider nichts anfangen… was soll |u|_v bedeuten?
|u|_b wuerde mir einleuchten, weil ich damit garantiere, dass die hoehenfunktion nie unter 0 kommt, aber was heisst hier |u|_v?
Tippfehler schliesse ich mal aus, weils in beiden PDFs mehrfach so erwaehnt wird. Hat jemand ne Idee?[/quote]So wie ich das sehe, ist das ein Tippfehler. Da müsste |u|_b stehen.
Ok, dann werd ich einfach die Hoehenfunktion verwenden falls nach einer Definition gefragt wird 
Haette noch eine Frage zu binaeren Baeumen: In den Altklausuren war oefters mal nach der Begruendung fuer die Rekursionsformel fuer die Catalan-Zahlen gefragt…
Wir haben in der VL zwar 3 unterschiedliche Beweise besprochen, die waren aber eigentlich fuer die Catalan-Formel, und nicht fuer Segners Rekursionsformel und es hiess definitiv: “Das muss nicht auswendig gelernt werden.”
Wie wuerdet ihr das Ganze dann begruenden? Oder ist hier nur Ableiten aus den Ausfuehrungen ueber die ‘strukturelle Aussage’ (von Binaerbaeumen) gemeint?
Bischen wenig fuer 6P, oder?
Meiner Meinung nach sollte das rauskommen:
a = 2 => n
a = 3 => n log n
a > 3 => n^(log_a 3)
Gruß
Hi, hier mal meine Ueberlegung zum 1 Fall:
a = 2 => 3 > 2 => 3 dominierender EW
3^m => 3^(log_a n) (nach ruecksubst.)
3^(log_a n) = n ^ (log_a 3)
Wenn mans lieber nach der auswendig gelernten Formel macht, muss man aufpassen das man mit den verschiedenen a nicht durcheinander kommt (a im Mastertheorem != a in der Rekursion).
Jo, ich meine du hast recht ;)!
Habs mir grad nochmal angeschaut.
Gruß
Hi, noch zwei Sachen:
-
Primzahltests waren nicht klausurrelevant, oder?
-
Und zu den Ringhomomorphismen bei Determinanten haett’ ich auch noch eine Frage: Woher kommen in den Folien die Moduln? Und warum sind das grade vier? Nehm ich z.B. nur die 29, 31, 37 und versuchs damit kommt ne ganz andere Determinante raus – oder ich hab mich verrechnet
Hab dann: (11 * (-9) * 31 * 37) + (20 * (-13) * 29 * 37) + (11 * (-10)* 29 * 31) mod 29 * 31 * 37
=> det A = 12617 ?
Hey, ich denke hier sollte es: n3^(n-1) und n3^n sein.
Lg Crypton
Jo, copy&paste-Fail, sind die Ergebnisse von H10 
Ich haette dann auch S(n) \in \Theta (n3^n)
Bei S(n) haett ich aber 23^(n-1)+n3^(n-2) im Angebot statt n3^(n-1).
(mein alpha war 2/9, mein beta 1/9, ist bei dir eins 0?)
ist so richtig, stand auch schonmal in nem anderen thread so im forum
Kann mir jemand kurz erklären wie die Aufgabe 1.2 und 1.3 aus den alten Klausuren geht?
Also z.b. H09 1.2:
R(n) = 5R(n - 1) + 6R(n - 2) (n >= 3) R(1) = 1 R(2) = 5
Bestimmen Sie die explizite Lösung.
Also char. Polynom aufstellen, Nullst. sind 2 und 3.
Allg. Lösung ist also: R(n) = c1 * 3^n + c2 * 2^n (?)
Mit den Anfangswerten finde ich für c1=1 und c2=-1
Also Allg. Lsg: R(n) = 3^n -2^n
Wie kommt OP auf -3^n + 2^(n+1) ?
Wenn ich c1/c2 vertausche komm ich immerhin auf -3^n + 2^n, aber woher das ^(n+1) ?
(Ich hab das nach Skript S. 128 gemacht)
ich denke mal, dass er sich bei der aufgabe irgendwie verrechnet hat.
ich hab bei der h09 auch 3^n - 2^n raus.
bei den anderen klausuren stimmt meine lösung aber mit der oben genannten überein.
anders kann ich mir das sonst auch nicht erklären…
Wie schauts eigentlich mit Hilfsmitteln für die Klausur aus?
Alles, eine DinA4-Seite, Taschenrechner, usw … ?
So weit ich weiß nichts davon.
Bei der F10 A1.3 hab ich zwar selbes alpha und beta, aber wenn ich des in meine Gleichung einsetz komm ich auf:
S(n) = 23^(n-2) + n3^(n-2)
und nicht auf
S(n) = 23^(n-1) + n3^(n-2)
EDIT
Ok… irgendwie kann da was nich stimmen… In der H10) A1.3) hab ich auch was anderes:
S(n) = 2^n
Die Formel in die man alpha und beta einsetzen muss is doch
S(n) = alpha * 2^n + beta * n * 2^n
und alpha = 1 und beta = 0?
F10 1.3
komm ich auf
2/9 * 3^n + 1/9 * n * 3^n
und wenn man das umformt ergibt das
2 * 3^(n-2) + n * 3^(n-2)
F10 1.3
“Bestimmen Sie das asymptotische Verhalten von S(n) für n → unendlich”
Die Nullst. sind 3 und 3 (doppelt).
Laut Skript also,
da a = b^d (also beide Nullst. gleich): S(n) element Theta( n^d * log(n) )
Ok, aber wie komm ich auf d?
Ich weiss b^d = 3, das bringt aber nicht wirklich was.
Muss man die Umformung von S.128 rückwärts machen und die Rekursion in der Form S(n) = a * S(n/b) + c * n^d darstellen, um dann d auszulesen?
Ne, das ist hier viel einfacher zu sagen:
Du hast einen Term mit Vorfaktor != 0 mit 3^(n-2) und einen Term mit Vorfaktor != 0 mit n3^(n-2) => letzerer wächst schneller => S(n) \in Theta(n3^(n-2))