www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Induktion" - Einfacher Induktionsbeweis
Einfacher Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Einfacher Induktionsbeweis: Hilfe, Tipp
Status: (Frage) beantwortet Status 
Datum: 23:09 Fr 31.10.2014
Autor: DieNase

Aufgabe
Finden sie für den Rekursiven Algorithmus getmax(i,j) eine asymptotische Obere Schranke.



Hallo, die rekursive Funktion getmax(i,j) habe ich analysiert und bin dabei auf folgende gleichung gestoßen am ende:

T(u) = [mm] \summe_{i=0}^{u} 3^{u} [/mm]  (Das hier ist die benötigte Zeit in der der Algorithmus das größte Element von n = [mm] 3^{u} [/mm] elementen findet.)

Ich muss jetzt eine möglichst knappe obere Schranke finden. Eine obere schranke ist wie folgt definiert.

f(n) = O(g(n)) : [mm] \exists [/mm] c [mm] \in \IN [/mm] ,  [mm] n>n_{0} \in \IN [/mm] : f(n) <= c * g(n)

Ich möchte jetzt folgendes zeigen durch induktion :-)

[mm] 3^{x} [/mm] > [mm] \summe_{i=0}^{x-1} 3^{i} [/mm]

Was ich mir erhoffe :-) Wenn ich das zeigen kann kann ich sehr leicht argumentieren das ein c von 3 dazu führt das ich mit einer oberen schranken von [mm] O(3^{x}) [/mm] automatische größer bin als [mm] \summe_{i=0}^{x} 3^{i} [/mm]

Mein Ansatz das ganze zu beweisen:
Basis: 1
[mm] 3^1 [/mm] > [mm] \summe_{i=0}^{1-1} 3^{i} [/mm]
3 > 1
Behauptung
[mm] 3^{x+1} [/mm] > [mm] \summe_{i=0}^{x} 3^{i} [/mm]
Schritt
[mm] 3^{x} [/mm] > [mm] \summe_{i=0}^{x-1} 3^{i} [/mm]    |Gleichung mal 3
[mm] 3^{x+1} [/mm] > 3 * [mm] \summe_{i=0}^{x-1} 3^{i} [/mm]
[mm] 3^{x+1} [/mm] > [mm] \summe_{i=1}^{x} 3^{i} [/mm]

Und da hab ich jetzt ein problem ... Und zwar brauch ich auf der rechten seite + 1 da ich das i=0 Element verloren habe.  Aber einfach dazu addieren ist nicht. Weil ichdan nnicht mehr sagen kann es ist kleiner. Ich brauch also ne argumentation warum +1 nicht dazu führt das es größer als [mm] 3^{x+1} [/mm] wird. Für hilfe wäre ich sehr dankbar. Bzw. was ich übersehe.


[EDIT1:]
[mm] 3^{x+1} [/mm] > [mm] \summe_{i=1}^{x} 3^{i} [/mm]

Da mein x [mm] \in \IN [/mm] ist und auch 3 [mm] \in \IN [/mm] ist und beide ergebnisse sowohl linke als auch rechte seite in [mm] \IN [/mm] sind.
Könnte ich dann nicht einfach sagen, mein [mm] 3^{x+1} [/mm] ist größer als [mm] \summe_{i=1}^{x} 3^{i}. [/mm] Und muss somit mindestens um 1 größer sein. Wenn ich jetzt auf der rechten seite + 1 addiere. Dann weiß ich zwar nicht mehr obs größer ist Aber ich weiß das es zumindest noch gleich sein muss da es davor größer war. Und für meine Obere Schranke würde mir dieses wissen reichen.

        
Bezug
Einfacher Induktionsbeweis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:42 Fr 31.10.2014
Autor: justdroppingby

Hallo,

> Finden sie für den Rekursiven Algorithmus getmax(i,j) eine
> asymptotische Obere Schranke.
>  
>
> Hallo, die rekursive Funktion getmax(i,j) habe ich
> analysiert und bin dabei auf folgende gleichung gestoßen
> am ende:
>
> T(u) = [mm]\summe_{i=0}^{u} 3^{u}[/mm]  (Das hier ist die benötigte
> Zeit in der der Algorithmus das größte Element von n =
> [mm]3^{u}[/mm] elementen findet.)

Damit wäre [mm] $T(u)=(u+1)\cdot 3^u$. [/mm] Ich nehme nicht an , dass das gemeint ist.
Ich sehe hier aber auch nirgends wirklich eine Aufgabenstellung.

> Ich muss jetzt eine möglichst knappe obere Schranke
> finden. Eine obere schranke ist wie folgt definiert.
>
> f(n) = O(g(n)) : [mm]\exists[/mm] c [mm]\in \IN[/mm] ,  [mm]n>n_{0} \in \IN[/mm] :
> f(n) <= c * g(n)
>  
> Ich möchte jetzt folgendes zeigen durch induktion :-)
>
> [mm]3^{x}[/mm] > [mm]\summe_{i=0}^{x-1} 3^{i}[/mm]
>  
> Was ich mir erhoffe :-) Wenn ich das zeigen kann kann ich
> sehr leicht argumentieren das ein c von 3 dazu führt das
> ich mit einer oberen schranken von [mm]O(3^{x})[/mm] automatische
> größer bin als [mm]\summe_{i=0}^{x} 3^{i}[/mm]
>  
> Mein Ansatz das ganze zu beweisen:
> Basis: 1
>  [mm]3^1[/mm] > [mm]\summe_{i=0}^{1-1} 3^{i}[/mm]

>  3 > 1

> Behauptung
>  [mm]3^{x+1}[/mm] > [mm]\summe_{i=0}^{x} 3^{i}[/mm]

>  Schritt
>  [mm]3^{x}[/mm] > [mm]\summe_{i=0}^{x-1} 3^{i}[/mm]    |Gleichung mal 3

> [mm]3^{x+1}[/mm] > 3 * [mm]\summe_{i=0}^{x-1} 3^{i}[/mm]
>  [mm]3^{x+1}[/mm] >

> [mm]\summe_{i=1}^{x} 3^{i}[/mm]
>  
> Und da hab ich jetzt ein problem ... Und zwar brauch ich
> auf der rechten seite + 1 da ich das i=0 Element verloren
> habe.  Aber einfach dazu addieren ist nicht. Weil ichdan
> nnicht mehr sagen kann es ist kleiner. Ich brauch also ne
> argumentation warum +1 nicht dazu führt das es größer
> als [mm]3^{x+1}[/mm] wird. Für hilfe wäre ich sehr dankbar. Bzw.
> was ich übersehe.

Du übersieht, dass du den Induktionschritt halt schlicht und ergreifend nicht so zeigen kannst wie du es versuchst.
Ganz billiges Schema F funktioniert hier.
  

> [EDIT1:]
>  [mm]3^{x+1}[/mm] > [mm]\summe_{i=1}^{x} 3^{i}[/mm]

>  
> Da mein x [mm]\in \IN[/mm] ist und auch 3 [mm]\in \IN[/mm] ist und beide
> ergebnisse sowohl linke als auch rechte seite in [mm]\IN[/mm] sind.
> Könnte ich dann nicht einfach sagen, mein [mm]3^{x+1}[/mm] ist

Nein, Wunschdenken ist kein Beweis.

> größer als [mm]\summe_{i=1}^{x} 3^{i}.[/mm] Und muss somit
> mindestens um 1 größer sein. Wenn ich jetzt auf der
> rechten seite + 1 addiere. Dann weiß ich zwar nicht mehr
> obs größer ist Aber ich weiß das es zumindest noch
> gleich sein muss da es davor größer war. Und für meine
> Obere Schranke würde mir dieses wissen reichen.  



Bezug
        
Bezug
Einfacher Induktionsbeweis: Antwort
Status: (Antwort) fertig Status 
Datum: 02:15 Sa 01.11.2014
Autor: reverend

Hallo Nase,

warum so kompliziert? Da brauchst Du keine Induktion.

> Finden sie für den Rekursiven Algorithmus getmax(i,j) eine
> asymptotische Obere Schranke.
>  
>
> Hallo, die rekursive Funktion getmax(i,j) habe ich
> analysiert und bin dabei auf folgende gleichung gestoßen
> am ende:
>
> T(u) = [mm]\summe_{i=0}^{u} 3^{u}[/mm]  (Das hier ist die benötigte
> Zeit in der der Algorithmus das größte Element von n =
> [mm]3^{u}[/mm] elementen findet.)

Wurde ja schon angemerkt: da stimmt wohl etwas nicht.

> Ich muss jetzt eine möglichst knappe obere Schranke
> finden. Eine obere schranke ist wie folgt definiert.
>
> f(n) = O(g(n)) : [mm]\exists[/mm] c [mm]\in \IN[/mm] ,  [mm]n>n_{0} \in \IN[/mm] :
> f(n) <= c * g(n)
>  
> Ich möchte jetzt folgendes zeigen durch induktion :-)
>
> [mm]3^{x}[/mm] > [mm]\summe_{i=0}^{x-1} 3^{i}[/mm]

Möglichst knapp geht aber noch viel besser.

> Was ich mir erhoffe :-) Wenn ich das zeigen kann kann ich
> sehr leicht argumentieren das ein c von 3 dazu führt das
> ich mit einer oberen schranken von [mm]O(3^{x})[/mm] automatische
> größer bin als [mm]\summe_{i=0}^{x} 3^{i}[/mm]
>  
> Mein Ansatz das ganze zu beweisen:
> Basis: 1
>  [mm]3^1[/mm] > [mm]\summe_{i=0}^{1-1} 3^{i}[/mm]

>  3 > 1

> Behauptung
>  [mm]3^{x+1}[/mm] > [mm]\summe_{i=0}^{x} 3^{i}[/mm]

>  Schritt
>  [mm]3^{x}[/mm] > [mm]\summe_{i=0}^{x-1} 3^{i}[/mm]    |Gleichung mal 3

> [mm]3^{x+1}[/mm] > 3 * [mm]\summe_{i=0}^{x-1} 3^{i}[/mm]
>  [mm]3^{x+1}[/mm] >

> [mm]\summe_{i=1}^{x} 3^{i}[/mm]

Mal ganz ehrlich - warum rechnest Du die Summe nicht einfach aus? Das ist doch nichts weiter als eine []geometrische Reihe.

Grüße
reverend

> Und da hab ich jetzt ein problem ... Und zwar brauch ich
> auf der rechten seite + 1 da ich das i=0 Element verloren
> habe.  Aber einfach dazu addieren ist nicht. Weil ichdan
> nnicht mehr sagen kann es ist kleiner. Ich brauch also ne
> argumentation warum +1 nicht dazu führt das es größer
> als [mm]3^{x+1}[/mm] wird. Für hilfe wäre ich sehr dankbar. Bzw.
> was ich übersehe.
>  
> [EDIT1:]
>  [mm]3^{x+1}[/mm] > [mm]\summe_{i=1}^{x} 3^{i}[/mm]

>  
> Da mein x [mm]\in \IN[/mm] ist und auch 3 [mm]\in \IN[/mm] ist und beide
> ergebnisse sowohl linke als auch rechte seite in [mm]\IN[/mm] sind.
> Könnte ich dann nicht einfach sagen, mein [mm]3^{x+1}[/mm] ist
> größer als [mm]\summe_{i=1}^{x} 3^{i}.[/mm] Und muss somit
> mindestens um 1 größer sein. Wenn ich jetzt auf der
> rechten seite + 1 addiere. Dann weiß ich zwar nicht mehr
> obs größer ist Aber ich weiß das es zumindest noch
> gleich sein muss da es davor größer war. Und für meine
> Obere Schranke würde mir dieses wissen reichen.  


Bezug
                
Bezug
Einfacher Induktionsbeweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 07:47 So 02.11.2014
Autor: DieNase

Zur aussage das meine rekursive Zeitgleichung nicht stimmt...

T(n) = O(1) + 3 * T(n/3)

Das ist der anfang:

T(N) = (1+ 3 + 9) * O(1) + 27 * T(n/27)

Mit T(1)  =  O(1)

T(n) = [mm] \summe_{i=0}^{k-1} 3^{i} [/mm] + [mm] 3^k [/mm] * O(1)

T(n) = [mm] \summe_{i=0}^{k} 3^{i} [/mm]

Also meine analyse stimmt nicht ... ISt klar. Ich wusste ich hätte auf das verzichten sollen und einfach nur um ein beweis fragen wie man eine geometrische Reihe Sauber abschätzen kann.  Verwirrt nur und bringt nix.

Bezug
                        
Bezug
Einfacher Induktionsbeweis: Antwort
Status: (Antwort) fertig Status 
Datum: 10:07 So 02.11.2014
Autor: justdroppingby


> Zur aussage das meine rekursive Zeitgleichung nicht
> stimmt...

Welche Aussage meinst du?
Über deine rekursive Zeitgleichung (was ist das überhaupt? Was ist eine Zeitgleichung?) lässt sich schwer sagen, da du hier den ALgorithmus nicht vorstellst: Du hast nur dessen Namen hingeschrieben.
Mal ganz abgesehen sollte die Zeit, die nötig ist um max(i,j) zu bestimmen doch irgendwie von i,j abhängen und die kommen bei dir nirgends vor.

> T(n) = O(1) + 3 * T(n/3)

Wo kommt das her, was soll das bedeuten?
Was ist das?

> Das ist der anfang:

Der Anfang von was?

> T(N) = (1+ 3 + 9) * O(1) + 27 * T(n/27)
> Mit T(1)  =  O(1)
>  
> T(n) = [mm]\summe_{i=0}^{k-1} 3^{i}[/mm] + [mm]3^k[/mm] * O(1)

Das ist wieder der selbe murks wie im Ausgangspost.
In der rechten Seite kommt kein n vor, d.h. die Funktion ist konstant, dafür aber ein unerklärtes k.


> T(n) = [mm]\summe_{i=0}^{k} 3^{i}[/mm]
>  
> Also meine analyse stimmt nicht ... ISt klar. Ich wusste
> ich hätte auf das verzichten sollen und einfach nur um ein
> beweis fragen wie man eine geometrische Reihe Sauber
> abschätzen kann.  Verwirrt nur und bringt nix.

Hier ist nirgendwo eine geometrische Reihe. Und geom. reihen kann man berechnen, da ist es völlig unnötig abzuschätzen.
Was du hier hast ist eine geom. Summe und auch die kann man berechnen.

Die Formel für geom. Summe und Reihe sind elementares Grundwissen (mein AnaI-Dozent bezeichnet letztere als wichtigste Reihe der Mathematik) und wenn du die nicht kennst dann rate ich dazu dich damit auseinanderzusetzen.

P.S. Selber denken bringt immer mehr als andere für sich denken lassen.

Bezug
                                
Bezug
Einfacher Induktionsbeweis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:18 So 02.11.2014
Autor: DieNase

wie gesagt das eigentlich problem wurde nicht eingegangen statt dessen probiert ihr krampfhaft auf was zu pochen was schlicht und ergreifend außerhalb des eigentlichen problems liegt.

Ist aber wurscht ich frag morgen studienkollegen udn werd mich mit denen über das eigentliche problem kurz schließen. Gegangen ist es nie um die obere formel sondern um den induktionsbeweis. ABer da kommt ja keine antwort wie man das beweist wenn man weiß das es stimmt :-) Und das hätte mich interessiert.

ABer wie ich schon gesagt habe. MEin fehler das ich euch zuviel information gegeben habe. Das erweist sich immer als fehler bei solchen foren.

Bezug
                                        
Bezug
Einfacher Induktionsbeweis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:39 So 02.11.2014
Autor: justdroppingby


> wie gesagt das eigentlich problem wurde nicht eingegangen
> statt dessen probiert ihr krampfhaft auf was zu pochen was
> schlicht und ergreifend außerhalb des eigentlichen
> problems liegt.

VIELLEICHT BEGREIFST DU ES IN GROßBUCHSTABEN:
ICH WEIß NACH WIE VOR NICHT WAS DAS EIGENTLICHE PROBLEN IST; DA DU ES NICHT HINSCHREIBST: WAS DU SCHREIBST IST ZIEMLICH SINNLOSES KAUDERWELSCH:

> Ist aber wurscht ich frag morgen studienkollegen udn werd
> mich mit denen über das eigentliche problem kurz
> schließen. Gegangen ist es nie um die obere formel sondern
> um den induktionsbeweis. ABer da kommt ja keine antwort wie
> man das beweist wenn man weiß das es stimmt :-)

WELCHEN INDUKTIONSBEWEIS.DU HAST NACH WIE VOR NICHT HINGESCHRIEBEN WAS DU ÜBERHAUPT BEWEISEN WILLST.

> Und das
> hätte mich interessiert.
>  
> ABer wie ich schon gesagt habe. MEin fehler das ich euch
> zuviel information gegeben habe. Das erweist sich immer als
> fehler bei solchen foren.  

NEIN. DU HAST GAR KEINE INFORMATIONEN GEGEBEN.

Und was sind denn eigentlich "solche Foren"?


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]