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.
Klausurfragen
Da sicher noch andere Fragen hab ich mal diesen Thread erstellt und eröffne ihn gleich mit einer eigenen Frage 
Alte Klausuraufgabe;
Man hat eine Rekursion folgender Form gegeben: f(n) = 2f(n/2) +c*n, f(1)=0
Nun ist nach der exakten/expliziten Lösung gefragt.
Damit ist dann ja wohl nicht die Anwendung des Mastertheorems gemeint, sondern etwas anderes. Nur was? Wie kann ich die Rekursion exakt lösen?
Konnte im Skript dazu nichts finden…
Ich würde die Rekursionsgleichung analog zur Seite 128 aus dem Skript vom Vorjahr in eine homogene Rekursion überführen. Allerdings weiß ich nicht, ob es evtl. noch eine schnellere Lösung gibt.
Also wenn ich das so mach wie auf S. 128 im Skript, dann komm ich auf:
f(n) = (a + b * log(n) ) * n
f(1) = 0 = a
für b bräuchte man noch eine 2. Anfangsbedingung
edit: b = c, wie man durch einsetzen in die ursprüngliche rekursion herausfindet…
Hi, hier mal mein Ansatz
f(n) = 2*f(n/2)+cn
Subst n = 2^m, f(2^m) = f_m
=>
(1) f_m = 2 f_{m-1} + c2^m
Einen Schritt vorher =>
(2) f_{m-1} = 2 f_{m-2} + c2^{m-1}
Gleichung (2) * 2 =>
(3) 2 f_{m-1} = 4 f_{m-2} + c2^{m}
Gleichung (1)-(3) => f_m - 2 f_{m-1} = 2 f_{m-1} - 4 f_{m-2}
<=> f_m = 4 f_{m-1} - 4 f_{m-2} => Char. Pol. = z^2 - 4z + 4 = (z-2)^2 => \lambda_{1,2} = 2 doppelte Nst.
aus f(1) = 0 folgt 0 = \alpha * \lambda + 1 * \beta * \lambda <=> \alpha = \beta
Weiter kann man aber nix rechnen… (denk ich) nur folgern dass x_n ~ n \beta \lambda^n falls \alpha \neq \beta, sonst ist \underline x = (0, 0, …)
das ergebnis von oliver hab ich auch
also
f(n)=c*log(n)*n
kann ich bestätigen, hab dasselbe ergebnis wie oliver / crusty
Wenn man bei der Lösung einer Rekursion einen dominanten negativen Eigenwert rausbekommt: Kann man dann irgendwelche Aussagen zur Wachstumsordnung (in Landau Notation) machen außer, dann man einfach sagt, dass die Folge alterniert?
Laut Definition muss der Faktor c oder d, den man bei O bzw. w wählen darf größer 0 sein also hät ich auf Nein getippt. Was meint ihr?
Als das in der Übung in nem Quickie dran kam, hieß es einfach, dass die funktionen sich wie -blub^n verhält. Ohne Angabe einer Landdau-Notation. Von daher würde ich dir zustimmen.
Andere Frage: Wenn ich die Ordnung von 5 in Z_51 berechnen möchte (wie in der letzten Klausur), muss ich dann wirklich bis 5^16 mod 51 = 1 alles duchrprobieren? Geht das auch irgendwie schneller?
du musst nur die teiler von phi(n) probieren
Die Ordnung muss phi(n) teilen, d.h. du brauchst nur die Teiler von phi(51) = 32 ausprobieren.
besten dank, war nur verwundert, da wir in einem beispiel in der übung auch ewig gerechnet hatten
oder ueber primfaktorisierung und die multiplikativitaet: phi(51) = phi(3x17) = phi(3) x phi(17) = 2x16 = 32 und dann die faktoren der 32 testen
Die Teiler sind ja dann 1, 2, 4, 8, 16 und 32. D.h. einer davon MUSS es sein, also wenn x^16 mod 51 auch nicht passt, dann ist es automatisch 32? Selbst 5^8 und 5^16 dauert ja relativ lange zum berechnen, um das mal eben auf die Schnelle in der Klausur fehlerfrei hinzubekommen. Oder gibt’s da noch einen Trick?
also zum „trick“
wenn du 5^4 berechnet hast dann kannst du dass ja modulo 51 nehmen (5^4 = 625 mod 51 = 13)
5^8 = 5^(42) = (5^4)^2 = 13^2 = 169 (mod 51) = 16
5^16 = 5^82 = 16^2 = 256 (mod 51) = 1
ja, für a und n teilerfremd gilt: a^phi(n) = 1 (mod n) (Satz von Fermat)
reindrängel
Laut Website soll es ja irgendwo Lösungen zu den Altklausuren geben: weiß jemand wo? (v.a. die zwei Komplexität-Klausuren wären natürlich interessant)
laut website gibts so wie ich das verstanden hab nur Lösungen zu alten Übungsaufgaben.
Hat noch jemand die Loesung zur Aufgabe 7d? Man konnte sich durch einen Trick den Umweg sparen das Gleichungssystem nach alpha, beta, gamma aufzuloesen und dann nach einer Loesung zu suchen… irgendwo konnte man die Werte direkt ablesen.
Glaub nicht das es da einen Trick gab. Uns wurde der zumindest nicht gezeigt. Man hat ja in Aufgabenteil c das Asympt. Verhalten schon betrachtet in abhängigkeit von x0, x1 und x2. Bei Teil d musste man dann nur passende Werte finden.
Schade, aber trotzdem danke 