O-Notation Extremaufgaben (Landau-Symbolik)

07.08.2019, 16:12

HansDampf994

Auf diesen Beitrag antworten »

O-Notation Extremaufgaben (Landau-Symbolik)

Hallo Freunde, hier bin ich wiedermal und brauche erneut Hilfe... traurig

traurig

Die O-Notation an sich ist ja eigentlich nichts schweres, nur hat unser Matheprof wieder mal wahnsinnig schwere Aufgaben mitgegeben, so schwierig dass ich nirgends Beispielrechnungen im Netz finde. Vermutlich bin ich zu blöd um das zu finden, denn im Netz gibt es ja fast alles.

Hier im Anhang die Aufgaben 1 & 2: (Meine Lösungswege sind so fehlerhaft, dass das Posten nichts bringen würde)

Grundsätzlich bitte ich hier nur um Hilfe zum Verständnis der Aufgabe, Lösungen wären nett, sind aber natürlich kein Muss. Bin dankbar um jede Hilfe.
Da Aufgabe 1 etwas länger dauert, geht es mir hier primär um Aufgabe 2

Liebe Grüße,

euer Hans!

07.08.2019, 17:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HansDampf994
Die O-Notation an sich ist ja eigentlich nichts schweres,

Das wichtigste Wort in dem Satz ist "eigentlich"... smile

smile

------------------------------------------------------

1a) solltest du selbst können: Schleifenzahl $\begin{eqnarray*} n \end{eqnarray*}$ und 3 Operationen pro Schleife (je eine Addition, Subtraktion, Multiplikation).

1b) $\begin{eqnarray*} \sum_{k=1}^n (2k-1) = n^2 \end{eqnarray*}$

------------------------------------------------------

2a) $\begin{eqnarray*} 2^{\cos(n)} \frac{(n+2)^2}{\sqrt{n^3+1}} = 2^{\cos(n)} \frac{\left(1+\frac{2}{n}\right)^2}{\sqrt{1+\frac{1}{n^3}}} \cdot \frac{n^2}{\sqrt{n^3}} \end{eqnarray*}$ zusammen mit $\begin{eqnarray*} \frac{n^2}{\sqrt{n^3}} = \sqrt{n} \end{eqnarray*}$ sollte helfen.

2b) Das basiert auf dem Grenzwertnachweis $\begin{eqnarray*} \lim_{n\to\infty} \sqrt[n]{n} = 1 \end{eqnarray*}$ .

2c) Der Binomische Satz liefert direkt $\begin{eqnarray*} \sum_{k=0}^n {n\choose k}2^k = \sum_{k=0}^n {n\choose k}2^k 1^{n-k} = (2+1)^n = 3^n \end{eqnarray*}$

2d) Integral ausrechnen, man muss hier ja nicht mal abschätzen bei dem einfachen Integranden:

$\begin{eqnarray*} \int\limits_1^n \left( \frac{1}{\sqrt{t}} + t\right) dt = \left[ 2\sqrt{t} + \frac{t^2}{2} \right]_1^n = 2\sqrt{n} + \frac{n^2}{2} - \frac{5}{2} \end{eqnarray*}$

07.08.2019, 18:07

HansDampf994

Auf diesen Beitrag antworten »

Danke dir HAL 9000! Kannst du mir deine Adresse oder ein Paypal Konto nennen (über Privatnachricht)? Ich möchte dir Schokolade senden, oder zumindest eine kleine Spende überweisen, ich finde das äußerst bewundernswert.

Das hilft mir sehr weiter, die 2a,b und d habe ich mittlerweile gemeistert und wie ich an deiner Lösung sehe, sogar richtig. Da fühl ich mich immer ein wenig schlecht wenn ich Aufgaben selber löse nachdem ich sie in aller Panik gepostet habe.

Hier ist übrigens noch die zweite Seite, wo ich 3a), dessen Aufgabenstellung nicht verstehe.

Vielen Dank und Liebe Grüße,

Hans

edit: Morgen werde ich noch spezielle Fragen stellen, für heute bin ich (geistig) fertig.

07.08.2019, 18:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HansDampf994
Danke dir HAL 9000! Kannst du mir deine Adresse oder ein Paypal Konto nennen (über Privatnachricht)?

Danke für das Angebot, aber die mündliche Wertschätzung ist mir Lohn genug. Außerdem schätze ich meine Anonymität. Augenzwinkern

Augenzwinkern

Zu 3a) Aufgrund der Dreiecksungleichung sowie der Definition von $\begin{eqnarray*} \max(f,g) \end{eqnarray*}$ gilt

$\begin{eqnarray*} \left|\alpha f(n)+\beta g(n)\right| \leq |\alpha| f(n) + |\beta|g(n) \leq (|\alpha|+|\beta|) \max(f,g)(n) \end{eqnarray*}$ .

08.08.2019, 16:11

HansDampf994

Auf diesen Beitrag antworten »

Das ist sehr ehrenwert HAL 9000, meine Bewunderung hast du definitiv.

Kannst du mir erklären wie du bei 2c) vorgegangen bist? Ich verstehe vorallem die Aufgabenstellung mit der 2x1 Matrize innerhalb des Summenzeichens nicht, wie hast du das umgangen? Diese Schreibweise ist mir nur als Matrize bekannt, was kann man sonst daraus erkennen?

Der Binomsche Satz sagt mir als Stichwort hier leider nicht viel, wie hast du den eingesetzt?

08.08.2019, 16:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HansDampf994
Ich verstehe vorallem die Aufgabenstellung mit der 2x1 Matrize innerhalb des Summenzeichens nicht, wie hast du das umgangen? Diese Schreibweise ist mir nur als Matrize bekannt, was kann man sonst daraus erkennen?

Ja, da ist wohl zunächst dieses Missverständnis zu klären: Mit $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ ist hier nicht ein zweidimensionaler Vektor (bzw. eine 2x1-Matrix) gemeint, sondern ein Binomialkoeffizient, wie er dann auch in dem von mir oben erwähnten Binomischen Satz auftaucht.

--------------------------------------------------------------------

Aber du hast da einen interessanten Aspekt aufgeworfen. Was kommt raus, wenn man es tatsächlich als Vektor auffasst? Rechnen wir es spaßeshalber mal aus:

Erste Komponente: $\begin{eqnarray*} \sum_{k=0}^n n2^k = n\left(2^{n+1}-1\right) \end{eqnarray*}$
Zweite Komponente: $\begin{eqnarray*} \sum_{k=0}^n k2^k = 2^{n+1}(n-1)+2 \end{eqnarray*}$

D.h., es ergibt sich dann

$\begin{eqnarray*} \sum_{k=0}^n \begin{pmatrix}n\\ k\end{pmatrix} 2^k = \begin{pmatrix}n\left(2^{n+1}-1\right)\\ 2^{n+1}(n-1)+2\end{pmatrix} \end{eqnarray*}$

Das kann man sogar durch $\begin{eqnarray*} O(a^n) \end{eqnarray*}$ für jede reelle Zahl $\begin{eqnarray*} a>2 \end{eqnarray*}$ abschätzen, speziell also auch $\begin{eqnarray*} a=3 \end{eqnarray*}$ . smile

smile

Ehrlich, wer sich erfolgreich durch diese andere (Auf-)Fassung quält, dem würde ich auch alle Punkte für das erfolgreiche Nachweisen von $\begin{eqnarray*} O(3^n) \end{eqnarray*}$ geben. Big Laugh

Big Laugh

P.S.: Den Symbolunterschied zwischen Binomialkoeffizient $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ und Vektor $\begin{eqnarray*} \begin{pmatrix}n\\ k\end{pmatrix} \end{eqnarray*}$ dürfte wohl nicht jeder sofort mitkriegen - im LaTeX-Quellcode ist es deutlicher. Augenzwinkern

Augenzwinkern

Anzeige

08.08.2019, 18:23

HansDampf994

Auf diesen Beitrag antworten »

Super, dankeschön! smile

smile

Also das Ganze als Vektor zu sehen erschwert das unglaublich, da komm ich gar nicht mehr mit. Hammer

Hammer

Ich habe mir das jetzt durchgelesen und frage mich wie du (bei 2c)) auf die 1 kommst, bzw. woher du weißt, dass x 1 und y 2 ist, wie konntest du die so eindeutig zuordnen?

Und könntest du mir eventuell einen Tipp für die 2e) geben?

Ich suche verzweifelt in den Summenzeichen Rechenregeln nach irgendeiner Umformung für die Division aber das klappt nicht, ich kann das in keiner Weise auseinanderziehen und in die Gausssche Summenformel bringen, geschweige denn die geometr. Summenformel...

08.08.2019, 18:43

HAL 9000

Auf diesen Beitrag antworten »

2e) ist eine sogenannte Teleskopsumme:

$\begin{eqnarray*} \sum_{k=1}^n \frac{1}{k(k+1)} = \sum_{k=1}^n \frac{(k+1)-k}{k(k+1)} = \sum_{k=1}^n \left( \frac{1}{k} - \frac{1}{k+1}\right) = 1 - \frac{1}{n+1} \end{eqnarray*}$

Ist aber eigentlich gar nicht so wichtig, dass man den Summenwert ausrechnen kann: Für das Ziel $\begin{eqnarray*} O(1) \end{eqnarray*}$ würde es reichen nachzuweisen, dass die Summe beschränkt bleibt (d.h. mit einer von $\begin{eqnarray*} n \end{eqnarray*}$ unabhängigen oberen Schranke).

08.08.2019, 20:06

HansDampf994

Auf diesen Beitrag antworten »

Abermals vielen Dank HAL 9000!

Ich habe die Aufgabe auf eigener Faust gelöst, dank deinem Tipp, endlich mal ein Erfolgserlebnis! Wie einfach das ist wenn man das nötige Vorwissen hat. Ich vermute mein Matheprof hat uns die Aufgaben zu früh überlassen, das nötige Wissen habe ich von dir vermittelt bekommen, nicht durch die Skripte und Vorlesungen wie gedacht.

Die Menschheit braucht mehr Menschen (oder Roboter?) wie dich. Freude

Freude

Ich verstehe aber immer noch nicht wie du direkt auf (2+1)^n gekommen bist bei der 2c oder genauer gesagt auf die 1^n-k davor. Gibt es einen Zwischenschritt dazu oder sind das reine Erfahrungswerte? Für ich sieht das wie aus dem Nichts gezaubert aus, das würde ich gerne auch können.

Vielen Dank und einen schönen Abend noch,

Beste Grüße,

Hans

08.08.2019, 20:33

HAL 9000

Auf diesen Beitrag antworten »

Es fällt auch mir nicht alles in den Schoß. Ja, was ich hier zu den Aufgaben gesagt habe, basiert zum allergrößten Teil auf Erfahrungswerten. Wenn man die (noch) nicht hat, gibt es aber auch andere Möglichkeiten:

Z.B. könntest du die Summen $\begin{eqnarray*} \sum_{k=0}^n \binom{n}{k}2^k \end{eqnarray*}$ in 2c) oder auch die Summen $\begin{eqnarray*} \sum_{k=1}^n \frac{1}{k(k+1)} \end{eqnarray*}$ für "kleine" $\begin{eqnarray*} n=1,2,3,4,5 \end{eqnarray*}$ konkret ausrechnen und aus den Ergebnissen schon mal eine Vermutung für allgemeine $\begin{eqnarray*} n \end{eqnarray*}$ aufstellen. Ob man diese Behauptung dann direkt oder durch Vollständige Induktion beweist, muss man dann von Fall zu Fall sehen.

09.08.2019, 18:07

HansDampf994

Auf diesen Beitrag antworten »

OK, ich habe mir die 2c) nun mal ausführlich bearbeitet, laut Wikipedia und deiner Lösung weiter oben, kann man diese einfache Umformung in (x+y)^n machen.

Die Summe an sich gibt mir aber immer einen anderen Wert raus, ob bei n=4 oder n=5.

Ist das eine gültige Behauptung, dass 3^n falsch ist? Ich habe vermutlich irgendwo einen Fehler, aber wo genau? Ich habe das Gefühl, dass ich alles richtig gemacht habe, bin es mehrfach durchgegangen.

Meine Bearbeitung ist im Anhang:
Bei n=4, 3^4 sollte ich ja 81 rausbekommen, jedoch komme ich auf 64.
Dasselbe bei n=5.

Liebe Grüße,

Hans

09.08.2019, 18:54

URL

Auf diesen Beitrag antworten »

$\begin{eqnarray*} {n \choose 0 }= {n \choose n} = 1 \end{eqnarray*}$ und auch $\begin{eqnarray*} 0!=1 \end{eqnarray*}$

09.08.2019, 21:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HansDampf994
Ist das eine gültige Behauptung, dass 3^n falsch ist?

D.h., du sagst mir auf den Kopf zu, dass ich oben falsch lag? Mutig, mutig. smile

smile

Zum Thema "Binomialkoeffizient" schaust du dir am besten mal das Pascalsche Dreieck an.

12.08.2019, 15:42

HansDampf994

Auf diesen Beitrag antworten »

@HAL 9000
Quatsch so ist das nicht gemeint, das wäre ja absurd. smile

smile

Deine Umrechnung stimmt zu 100% aber ich bekomme durch das Einsetzen von den Zahlen n=5 und n=4, nicht das richtige Ergebnis raus... auch (2+1)^n mit dem Pascal'schen Dreieck ergibt 81,

das heißt mein Fehler liegt in der Umsetzung der Summenformel mit den Fakultäten... Ich kriege das bei Zeiten noch raus, danke für deine Hilfe und Unterstützung nochmals smile

smile

@URL
Danke sehr! Das ist gut zu wissen, kommt direkt auf meine Formelsammlung.

12.08.2019, 20:30

URL

Auf diesen Beitrag antworten »

In deinen Aufschrieben steht für k=0 und k=n immer ein n.def, was wohl nicht definiert heißen soll. Die entsprechenden Ausdrücke sind sehr wohl definiert. Für k=4 ist etwa $\begin{eqnarray*} {4 \choose 0}2^0=1 \end{eqnarray*}$ und $\begin{eqnarray*} {4 \choose 4}2^4=16 \end{eqnarray*}$ . In Summe ist das gerade deine Differenz $\begin{eqnarray*} 81-64 \end{eqnarray*}$

13.08.2019, 09:31

HAL 9000

Auf diesen Beitrag antworten »

So genau hatte ich mir das Gekrakel oben gar nicht angeschaut, aber stimmt: Wenn man durch Weglassen der beiden Randsummanden statt $\begin{eqnarray*} \sum_{k=0}^n \binom{n}{k}2^k \end{eqnarray*}$ dann nur $\begin{eqnarray*} f(n)=\sum_{k=1}^{n-1} \binom{n}{k}2^k \end{eqnarray*}$ berechnet, dann gilt natürlich nur $\begin{eqnarray*} f(n)=3^n-2^n-1 \end{eqnarray*}$ , speziell dann $\begin{eqnarray*} f(4)=64 \end{eqnarray*}$ und $\begin{eqnarray*} f(5)=210 \end{eqnarray*}$ . Augenzwinkern

Augenzwinkern

21.08.2019, 18:38

HansDampf994

Auf diesen Beitrag antworten »

@URL & @HAL9000

Oh mein Gott... Wie peinlich...

Danke dass ihr das für mich aufgedeckt habt! Wirklich sehr nett, ich danke vielmals.

Beste Grüße smile

smile

,

Hans

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »