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.
Zusammenarbeit für TIVorprüfung09.2003
Ich gehe jetzt los! :motz:
III-1 1. n;
2. ???
III-2 1 → Theta(logN*logN)
2 → Theta(NlogN)
3 → Theta(N hoch log7)
komm mit!!! 
bei der III-1 2. kommt 2 hin, da gibts die formel n/n-1 für n-elementige Alphabete.
woher kommt diese formel?? 8-(
die kommt aus irgendner übungsaufgabe, irgendwann hab ich mir das mal in ner übung notiert, keine ahnung ob die auf den folien ist ich glaub nicht, in der aufgabe musste man die irgendwie herleiten …
Hmm - ich habe da → Theta(logN)
Wie bist Du denn darauf gekommen?
Also ich denk mal so:
n-> 2^k
T(2^k) = T (2^k-1) + clog(2^k)
= [summe von i=0 bis k] clog(2^i)
= c * [summe von i=0 bis k] i
= c * (k*(k+1))/2
= c/2 * logn * (logn + 1) Theta(logn*logn)
falls jemand zu viel zeit hat, kann er doch mal die ii-8 erklären 
sonst:
III-2 2. im skript steht ≈2. steht auch die ganze ausrechnerei!
III-3
- ggT(18,24) | (a-b)
- -13 mod 36
i-1) start bei s0, ende s3
s0,b->s0 s0,a->s1
s1,b->s0 s1,a->s2
s2,b->s3 s2,a->s1
s3,a|b->s3
iii-4 1. 1531
Wie macht man das genau?
Ich glaube das stimmt naemlich nicht, da -13 mod 36 = 23 mod 36 und 23 mod 24 != 11 …
Auf jeden fall wenn ich daraus mach:
11 mod 24 und 5 mod 18
3 mod 4 und 5 mod 18
3 mod 4 und 5 mod 9
komm ich auf die -13 und dann muss man denk ich mod kgv(18,24)=72 nehmen, dann stimmts.
ABER:
11 mod 24 und 5 mod 18
11 mod 24 und 2 mod 3
3 mod 8 und 2 mod 3
krieg ich 27 - 16 = 11 mod 72 raus und dass stimmt ja wohl nicht.
Gibts da ne Regel, dass man den ggT immer erst aud dem groesseren der beiden rauszieht oder so?
Warum gehst du von s2,a zu s1? aaab wuerde dann nicht akzeptiert. Also statt s2,a → s1 lieber s2,a → s2, sonst sieht meiner genauso aus.
Und zur II-8
Die Loesung ist 3 * l(Kaktusstachel)
wie rechnest du das?
I-2
Geht nur indeterministisch:
s0,a → s0,,R
s0,a → sa,x,R
s0,b → sb,x,R
sa,a → sa,a,R
sa,b → sa,b,R
sb,a → sb,a,R
sb,b → sb,b,R
sa,a → z,x,L
sb,b → z,x,L
z,a/b/x → z,a/b/x,L
z, → s0,,R
s0, → ENDE,N
Muss ich den Automaten angeben, wenn ich schon zeige dass das Ding kontextfrei ist? Eigentlich nicht, oder?
Da musst nix rechnen, steht in divconq4.pdf.
Da is ne Tabelle, in der du in abhaengigkeit von a und b ablesen kannst wie der Aufwand ist. Geht aber nur wenn f(n) von der Form c * n^irgendwas ist.
fuer c-d-rekur-gleichung bitte verwenden Sie die Formel, bitten nicht rechne!!!
die loesung bin ich ganz sicher!!!
es ist ganz wichtig. (3punkte)
Zur III-3:
Ich hab’ da auch ne ganze Weile rumgerechnet, bis ich auf -13 gekommen bin. Ich denke, daß man beim Umformen der Modulgleichungen darauf achten muß, daß die zerlegten Moduln immer relativ prim zueinander sind.
Zum Beispiel ist
(x = 11 mod 24) äquivalent zu (x = 2 mod 3 und x = 3 mod 8)
Jedoch ist die Gleichung nicht äquivalent mit dem System (x = 3 mod 4 und x = 5 mod 6) da ggt(4, 6) = 2.
Die Klausuraufgabe habe ich dann so gelöst:
x = 11 mod 24
x = 5 mod 18
gdw.
x = 2 mod 3
x = 3 mod 8
x = 5 mod 9
x = 1 mod 2
gdw.
x = 3 mod 8
x = 5 mod 9
→ Lösung mit eeA: x = -13 + k*72
a^n ist reg. ww^rev ist kfrei. → 1. ja 2.ja 3.ja.(abgeschlossenheit) 4.nein
wenn 3 ja, dann 1,2 auch ja 
[quote]
fuer c-d-rekur-gleichung bitte verwenden Sie die Formel, bitten nicht rechne!!![/quote]
die sind ja eigentlich echt eklig, die formeln :motz:
iii-5
- mittl. länge = 2,25
- (-1+√5)/2 < p < 1
i-4
f(0,n) = c0 = n
f(succ(m),n) = h(m,n, f(m,n))
h(x,y,z)= pro(4,1) (0,x,y,z)
was bedeutet es?
Kannst du mir bitte erklaeren wie du da drauf gekommen bist?
Und wegen der I-4
Geht das auch so:
h(m,n) = (1-m) * n
Und dann zeigen dass - und * auch prim-rek sind.