Einfacher Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
| |
|
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.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | 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.
|
|
|
| |
|
> 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.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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.
|
|
|
| |
|
> 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"?
|
|
|
|
![[]](/images/popup.gif){kind=small}
geometrische Reihe