lineare Kongruenzgenerator

11.12.2012, 17:14	deppensido	Auf diesen Beitrag antworten »
lineare Kongruenzgenerator hallo, bei der Aufgabe im Anhang weiß ich gar nicht was ich machen muss. Mit der Definition für lin. Kongr.generator hab ich versucht zu zeigen, dass die Periodenlänge = m ist. Stimmt das?
11.12.2012, 17:26	HAL 9000	Auf diesen Beitrag antworten »
Bitte mal vom Kopf auf die Füße: Du willst nicht mit Hilfe der Definition (die sieht anders aus!), sondern eher mit Hilfe dieser Aussage aus Aufgabe 5 beweisen, dass der Generator die Periodenlänge $\begin{eqnarray} m \end{eqnarray}$ hat? Oder wie sonst meinst du das?
11.12.2012, 18:18	deppensido	Auf diesen Beitrag antworten »
ich schreib mal hin, was ich mir notiert habe. zn ist lin. Kongruenzgenerator => (Def.) $\begin{eqnarray} z_0 > 0 \end{eqnarray}$ und $\begin{eqnarray} m, a, b > 0 \end{eqnarray}$ , wobei z_0, m, a, b natürliche Zahlen sind. Setze: $\begin{eqnarray} a_{zj} = a^n z_0 \end{eqnarray}$ für j = 1,...,n und $\begin{eqnarray} b_i = (a^n-1) / (a-1) b \end{eqnarray}$ für i = 1,...,n Dann erhält man eine Folge von Zahlen $\begin{eqnarray} z_{j+1} = (a_{zj} + b) mod m \end{eqnarray}$ mit $\begin{eqnarray} a_j = z_j / m \end{eqnarray}$ => $\begin{eqnarray} z_j+1 \end{eqnarray}$ Element $\begin{eqnarray} {0,1,...,m-1} \end{eqnarray}$ und $\begin{eqnarray} z_j \end{eqnarray*}$ periodisch => Periodenlänge m => Beh. Ist da irgenwas nützliches bei? Grüße
12.12.2012, 15:12	HAL 9000	Auf diesen Beitrag antworten »
Eigentlich hatte ich mit "vom Kopf auf die Füße" etwas mehr Klarheit erwartet, stattdessen bietest du nur mehr Wirrwarr, so nach dem Motto: "Ich schreib mal bunt und ungeordnet alles auf, was ich zu dem Thema so irgendwie mal gesehen habe, und ihr sucht mir dann was passendes da raus." Daher mal ein sauberer Start: Definiert ist der lineare Kongruenzgenerator für gegebene $\begin{eqnarray} a,b,m \end{eqnarray}$ sowie Startwert $\begin{eqnarray} z_0 \end{eqnarray}$ über die Rekursion $\begin{eqnarray} z_{j+1} \equiv az_j + b \bmod m \end{eqnarray}$ für $\begin{eqnarray} j=0,1,\ldots \end{eqnarray}$ Daraus kann man in die explizite Darstellung $\begin{eqnarray} z_n \equiv a^nz_0 + \frac{a^n-1}{a-1}b \bmod m \end{eqnarray}$ ableiten, beweisbar etwa durch vollständige Induktion. Nun zu der Frage, ob die Periodenlänge dieses Generators gleich $\begin{eqnarray} m \end{eqnarray}$ ist: Da kann man schlicht drauf antworten, dass dies i.a. falsch ist - es ist ein leichtes, Parameterwerte $\begin{eqnarray} a,b,m \end{eqnarray}$ anzugeben, wo dies nicht der Fall ist. Wenn du also Periodenlänge $\begin{eqnarray} m \end{eqnarray}$ beweisen willst, dann kann dies offenbar nur unter Nutzung von Zusatzbedingungen an $\begin{eqnarray} a,b,m \end{eqnarray}$ möglich sein, wie sie z.B. hier aufgelistet sind.
12.12.2012, 15:52	deppensido	Auf diesen Beitrag antworten »
hallo, dann war die Idee, nämlich Periodenlänge m zu beweisen falsch und da mein wirrwar der Beweis war, den ich heute abgegeben habe. Hat sich das dann erledigt. Hätte mich etwas früher damit beschäftigen sollen. Trotzdem danke.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »