diskrete mathe b

23.04.2010, 20:11

gzm

diskrete mathe b

Meine Frage:
hey leute..muss bis sonntag folgende aufgabe lösen aber hab echt gar keine ahnung wie es gehen soll :S wäre echt sehr nett wenn mir jmd.helfen würde...

Geben Sie zwei Funktionen f;g : N->N an, so dass weder f(n) =O(g(n)) noch g(n)=O(f(n)) gilt.

Meine Ideen:
alles was ich zu dieser aufgabe weiß ist die definition von
o(g(n))... :S

23.04.2010, 21:50

wisili

Auf diesen Beitrag antworten »

RE: diskrete mathe b
$\begin{eqnarray*} f(n) =\frac{1+(-1)^{n}}{n} \end{eqnarray*}$ und $\begin{eqnarray*} g(n) =2^{-n} \end{eqnarray*}$

Formuliere die Argumente.

Edit: Alles falsch (s. unten den Hinweis von papahuhn)

23.04.2010, 22:06

papahuhn

Auf diesen Beitrag antworten »

RE: diskrete mathe b
gzm möchte N als Wertebereich.

23.04.2010, 22:10

wisili

Auf diesen Beitrag antworten »

RE: diskrete mathe b
Ja, da habe ich mich bös vertan, sorry.

23.04.2010, 22:19

kiste

Auf diesen Beitrag antworten »

Definiere die Funktionen stückweise, wähle z.B. für gerade Argumente eine andere als für ungerade

24.04.2010, 11:48

gzm

Auf diesen Beitrag antworten »

danke erstmal an euch alle für eure antworten smile

)

bloß weiß ich jetzt nicht was ihr damit meint, dass ich funktionen von wisili stückweise definieren soll?!

kann es mir jmd. viellecht deutlicher erklären??

wäre echt seeeehhhrr liieeb ...

24.04.2010, 12:11

wisili

Auf diesen Beitrag antworten »

$\begin{eqnarray*} f(n) = n^{1+(-1)^{n} } \end{eqnarray*}$

$\begin{eqnarray*} g(n) = n \end{eqnarray*}$

Die Folge f beginnt so: 1, 4, 1, 16, 1, 36, 1, 64, 1, 100, ...

24.04.2010, 12:56

gzm

Auf diesen Beitrag antworten »

dankeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee dankeee dankeeee wisili smile

)

24.04.2010, 16:20

gzm

Auf diesen Beitrag antworten »

induktionsbeweis
hab wieder ne frage..undzwar:

Die Summe der Kehrwerte der ersten n natürlichen Zahlen bezeichnet man als n-te harmonische Zahl Hn(n=index), also Hn=(summenzeichen) i=1 bis n: 1/i

beweisen oder widerlegen sie:

H(2^n) <(gleich) n+1 (für alle n element N)

die zahl neben H ist immer der index...

(sry wegen der darstellung..bin neu hier smile

)

also ich weiß dass die aussage richtig ist habs auch versucht zu beweisen aber bin mir nicht sicher obs stimmt.

Ind.anfang: n=1 H(2^n) <(gleich) n+1
H(2) <gleich 2
1+1/2 <gleich 2
1,5 <gleich 2
was korrekt ist.

IND.schritt: H(2^n+1) muss <gleich H(2^n) + 1 sein

summe von H(2^n+1)= summe von H(2^n)+ 1/(2^n+1) und das ist ja kleiner gleich n+2 was ich beweisen soll.

ist das korrekt? oder ist mein ind.schritt nicht ausführlich genug?!

24.04.2010, 18:50

wisili

Auf diesen Beitrag antworten »

RE: induktionsbeweis

Zitat:

Original von gzm
... ist das korrekt? oder ist mein ind.schritt nicht ausführlich genug?!

Der Induktionsschritt ist bei dir zu knapp. Ich mache einen Vorschlag:

Behauptung:
$\begin{eqnarray*} H_{2^{n} } :=\sum\limits_{k=1}^{2^{n}}\frac{1}{k} \ \ \leq \ \ n+1 \end{eqnarray*}$ für alle natürlichen Zahlen n.

Beweis induktiv:
Verankerung bei n=1: $\begin{eqnarray*} H_{2} := 1 + \frac{1}{2} \ \ \leq \ \ 2 \end{eqnarray*}$ ist erfüllt.
Vererbung: (Bei * wird die Induktionsvoraussetzung angewendet.)

$\begin{eqnarray*} H_{2^{n+1} } =\sum\limits_{k=1}^{2^{n+1}}\frac{1}{k} = \sum\limits_{k=1}^{2^{n}}\frac{1}{k} \ \ + \sum\limits_{k=2^{n}+1}^{2^{n+1}}\frac{1}{k} \ \leq^{*} \ \ n+1 \ + \sum\limits_{k=1}^{2^{n}}\frac{1}{2^{n}+k} \ \leq \ \ n+1 \ + \sum\limits_{k=1}^{2^{n}}\frac{1}{2^{n}} = n+1 + 1 \ \ = \ \ n+2 \end{eqnarray*}$

24.04.2010, 18:58

gzm

Auf diesen Beitrag antworten »

ich habs mir gedacht dass meins zu knapp ist smile

aber wusste nicht mehr weiter...

vielen dank für deine mühe wisili smile

habs jetzt auf jeden fall verstanden...

LG

Neue Frage »

Antworten »

diskrete mathe b

Verwandte Themen