Indexshift bei zwei Summen

18.01.2017, 16:33

Hinterbichler

Indexshift bei zwei Summen

Hallo,
für die Berechnung einer Aufgabe, bin ich der Meinung einen Indexshift durchführen zu müssen. Da meine Mathefähigkeiten mit meinem Studium mehr als eingerostet sind, wollte ich nachfragen ob dieser so funktioniert:

$\begin{eqnarray*} \sum_{i=2}^{logn}\sum_{j=1}^{logi}c \end{eqnarray*}$ --> $\begin{eqnarray*} \sum_{i=1}^{logn-1}\sum_{j=1}^{logi+1}c \end{eqnarray*}$

Hier bin ich mir nicht sicher ob ich das i von logi der zweiten Summe mit (i+1) ersetzen oder ob der Indexshift nur bei allen Variablen der ersten Summe durchgeführt werden muss. Also so:

$\begin{eqnarray*} \sum_{i=1}^{logn-1}\sum_{j=1}^{logi}c \end{eqnarray*}$

18.01.2017, 17:18

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Indexshift bei zwei Summen
Willkommen im Matheboard!

Wenn c eine Konstante, also nicht von i oder j abhängig ist, ist die zweite Formel richtig, die erste nicht. Die erste Summe hat ja logn-1 Summanden, die zweite hat logi Summanden. Die obere Umformung führt aber zu logi+1 Summanden bei der zweiten!

Ist c allerdings von i und j abhängig, kann man keine Aussage treffen.

Viele Grüße
Steffen

18.01.2017, 17:30

Hinterbichler

Auf diesen Beitrag antworten »

Vielen dank für die Antwort. Also ist $\begin{eqnarray*} \sum_{i=1}^{logn-1}\sum_{j=1}^{logi}c \end{eqnarray*}$ richtig? Das hilft mir schon mal um einiges weiter.

Ich hätte gleich noch eine Folgefrage zur selben Aufgabe. Kann ich auf $\begin{eqnarray*} \sum_{i=1}^{logn-1}{logi}\cdot c \end{eqnarray*}$ die Gaußsche Summenformel anwenden um dann $\begin{eqnarray*} \frac{logn(logn-1)}{2}\cdot c \end{eqnarray*}$ zu erhalten? Oder muss ich zuvor das logi irgendwie "behandeln".

EDIT: Ich habe dazu eine Notiz in meinen Unterlagen das ich wohl in dem Fall logi einfach als i behandeln kann. Ich kann mich aber beim besten willen nicht mehr daran erinnern woher diese Notiz kommt und ob sie überhaupt stimmt verwirrt

18.01.2017, 17:41

Steffen Bühler

Auf diesen Beitrag antworten »

Du addierst doch hier logi*c einfach auf, und zwar (logn-1)-mal. Also...

Oder geht es die ganze Zeit nicht um irgendwelche natürlichen Zahlen logi und logn, sondern etwa um log(i) und log(n)? Das wäre natürlich ein riesiger Unterschied!

18.01.2017, 17:43

Hinterbichler

Auf diesen Beitrag antworten »

Es geht um log(i) und log(n) also mit logi ist nicht irgendeine Variable x gemeint sondern schon log(i). Entschuldigung wenn das grad falsch verstanden wurde.

18.01.2017, 17:48

Steffen Bühler

Auf diesen Beitrag antworten »

Dann gilt allerdings Deine erste Umformung:

$\begin{align*} \sum_{i=2}^{ \log(n)}\sum_{j=1}^{ \log(i)}c = \sum_{i=1}^{ \log (n)-1}\sum_{j=1}^{\log (i+1)}c \end{align*}$

Allerdings frage ich mich, wie eine reelle Zahl als Obergrenze einer Summe genommen werden kann.

18.01.2017, 17:55

Hinterbichler

Auf diesen Beitrag antworten »

Gut, dann habe ich das also doch richtig verstanden Big Laugh

. An der zweiten Frage ändert das aber grad nichts. Ich denke aber ich bin jetzt darauf gekommen warum ich die Gauße Summenformel anwenden darf. Bei log(i) log(n) fehlen bei mir die ceil bzw floor Klammern (ich weiß grad nicht wie ich diese hier darstellen kann), damit das Ergebnis von log zur nächst größeren/kleineren Zahl aufgerundet wird. So bekomme ich ja natürliche Zahlen und kann die Gauße Summenformel anwenden.

EDIT: Bei dem ganzen handelt es sich übrigens um Schleifendurchläufe innerhalb eines Programms.

18.01.2017, 18:01

HAL 9000

Auf diesen Beitrag antworten »

$\begin{align*} \left\lfloor \log(n) \right\rfloor \end{align*}$ für abrunden

$\begin{align*} \left\lceil \log(n) \right\rceil \end{align*}$ für aufrunden

Welchen $\begin{align*} \log \end{align*}$ meinst du eigentlich: Den natürlichen $\begin{align*} \log_e = \ln \end{align*}$ oder (wie in der Informatik häufig) den binären $\begin{align*} \log_2 = \operatorname{lb} \end{align*}$ (manchmal auch $\begin{align*} \operatorname{ld} \end{align*}$ ) ?

18.01.2017, 18:02

Hinterbichler

Auf diesen Beitrag antworten »

Hier geht es um $\begin{align*} \log_2 \end{align*}$ . Kann so meine Vermutung mit der Gaußschen Summenformel bestätigt werden oder liege ich da komplett daneben?

18.01.2017, 19:16

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hinterbichler
Hier geht es um $\begin{align*} \log_2 \end{align*}$ . Kann so meine Vermutung mit der Gaußschen Summenformel bestätigt werden oder liege ich da komplett daneben?

Komplett daneben. geschockt

Ok, es geht dir um $\begin{align*} f(m) = \sum_{i=1}^m \log_2(i) \end{align*}$ speziell für $\begin{align*} m= \left\lfloor \log_2(n) \right\rfloor-1 \end{align*}$ (o.ä., das $\begin{align*} m \end{align*}$ kannst du ja noch korrigieren).

Es ist $\begin{align*} f(m) = \log_2\left( \prod_{i=1}^m i \right) = \log_2\left( m! \right) \end{align*}$ . Gemäß Stirlingscher Näherungsformel ist das

$\begin{align*} f(m) \approx \frac{1}{2}\log_2(2\pi) + \left(m+\frac{1}{2}\right) \log_2(m) - \frac{m}{\ln(2)} \end{align*}$ .

18.01.2017, 19:27

Hinterbichler

Auf diesen Beitrag antworten »

Au Backe, das ist ja voll am Ziel vorbei verwirrt

. Gibt es hier im Forum einen Bereich in dem ich die Java Schleifen Posten kann, aus denen letztendlich die Summenformeln entstanden sind? Ich schätze gerade das ich da bereits einen Fehler drin habe.

EDIT: Es geht mir nicht ganz um $\begin{align*} f(m) = \sum_{i=1}^m \log_2(i) \end{align*}$ sondern um $\begin{align*} f(m) = \sum_{i=1}^m \left\lfloor \log_2(i) \right\rfloor \end{align*}$ falls das einen unterschied macht.

18.01.2017, 20:17

Steffen Bühler

Auf diesen Beitrag antworten »

Du kannst den Code gerne hier im Thread posten, wir sprechen diese Sprache auch. Augenzwinkern

Nimm am besten Code-Tags.

18.01.2017, 20:54

Hinterbichler

Auf diesen Beitrag antworten »

Also Sinn der Aufgabe ist es die asymptotische Laufzeit herauszufinden.

for (int =2; i < n; i *=2)
for (int j = 1; j < i; j *= 2)
summe++;

Ich bin nun davon ausgegangen das die erste Schleife $\begin{eqnarray*} \sum_{i=2}^{log(n)} \end{eqnarray*}$ mal und die zweite Schleife $\begin{eqnarray*} \sum_{j=1}^{log(i)} \end{eqnarray*}$ mal durchlaufen wird. Inzwischen denke ich aber das die zweite Schleife $\begin{eqnarray*} \sum_{j=1}^{log(2^i)-1} \end{eqnarray*}$ mal durchlaufen wird. Dies bringt mich zu:

$\begin{eqnarray*} \sum_{i=2}^{log(n)}\sum_{j=1}^{log (2^i)-1}\cdot c \end{eqnarray*}$

Nach dem Shift zu:

$\begin{eqnarray*} \sum_{i=1}^{log(n)-1}\sum_{j=1}^{log(2^{i+1})-1}\cdot c \end{eqnarray*}$

Laut meinem Skript kann ich nun $\begin{eqnarray*} \sum_{j=1}^{log(2^{i+1})-1} \end{eqnarray*}$ einfach als $\begin{eqnarray*} \sum_{j=1}^{i+1-1} \end{eqnarray*}$ also $\begin{eqnarray*} \sum_{j=1}^{i} \end{eqnarray*}$ schreiben (warum ist mir leider nicht ganz klar :/ ). und so komme ich nun zu:

$\begin{eqnarray*} \sum_{i=1}^{log(n)-1}\cdot i \cdot c \end{eqnarray*}$

und hier sollte ich ja dann in der Lage sein den Gauß anzuwenden um schließlich hierauf zu kommen:

$\begin{eqnarray*} \frac{log^2(n) - log(n)}{2} \cdot c \end{eqnarray*}$

Falls das soweit Sinn macht weiß ich dann, dass das ganze Element von O $\begin{eqnarray*} log^2(n) \end{eqnarray*}$ ist, welches auch das Vorgegebene Ergebnis meines Profs ist.

18.01.2017, 21:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hinterbichler
Es geht mir nicht ganz um $\begin{align*} f(m) = \sum_{i=1}^m \log_2(i) \end{align*}$ sondern um $\begin{align*} f(m) = \sum_{i=1}^m \left\lfloor \log_2(i) \right\rfloor \end{align*}$ falls das einen unterschied macht.

Nun, ein wenig schon.

Neue Frage »

Antworten »

Indexshift bei zwei Summen

Verwandte Themen