www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Analysis des R1" - Rekursionsgleichung lösen
Rekursionsgleichung lösen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursionsgleichung lösen: .. und beweisen
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:55 Di 17.10.2017
Autor: pc_doctor

Aufgabe
Lösen Sie die folgenden Rekursionsgleichungen. Beweisen Sie jeweils die Richtigkeit ihrer Lösung (z.B. durch vollstände Induktion)

a)

T(1) = 0

T(n) = [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n    für n > 1

Sie dürfen annehmen, dass n eine Zweierpotenz ist.



Hallo,

ich habe Probleme bei dieser Aufgabe.

Also normale Rekursionsgleichungen mittels charak. Polynom ist eigentlich kein Problem, aber die Gaußklammern stören mich etwas.

Ich habe mal testweise Werte eingesetzt, um ein System zu erkennn, doch vergebens:

T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2
T(3) = 5
T(4) = 8

T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24

T(9)  = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59

Ich erkenne, dass für n  = 2,3 und 4 die Differenz immer 3 beträgt

von n = 5 bis 8 ist die Differenz 4

und ab n = 8 bis ?? ist die Differenz 5

Ich werde aber daraus nicht schlau. Oder gibt es einen anderen Ansatz?

Ich würde mich über einen Tipp freuen.

Vielen Dank im Voraus.


        
Bezug
Rekursionsgleichung lösen: Tipp
Status: (Antwort) fertig Status 
Datum: 20:48 Di 17.10.2017
Autor: HJKweseleit

Du solltest den Zahlenwert von [mm] \lfloor log_2(n)\rfloor [/mm] betrachten.

Damit kannst du einerseits die sich ändernden Stufenabstande in den Griff bekommen und andererseits eine Korrektur zu den richtigen Werten finden (dazu brauchst du dann aber [mm] 2^{\lfloor log_2(n)\rfloor}). [/mm]

Bezug
                
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:58 Di 17.10.2017
Autor: pc_doctor

Danke für den Tipp, mit dem komme ich weiter!

Bezug
                
Bezug
Rekursionsgleichung lösen: Neuer Anlauf
Status: (Frage) beantwortet Status 
Datum: 19:35 So 22.10.2017
Autor: pc_doctor

Hallo,

ich habe mal bisschen anders gerechnet, um die Rekursionsgleichung zu lösen. Ich komme auf log(n), allerdings fehlt da etwas, aber ich weiß nicht was.

Also wir hatten:

T(1) = 0 , das ist der Anker


T(n) = $ [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] $ + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n   für n > 1

Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also so aussieht n = [mm] 2^{a} [/mm] , a [mm] \in \IN [/mm]

Damit ändert sich T(n) zu:

T(n) = [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{2} [/mm] + n , für n > 1, n Zweierpotenz.

So, dann versuche ich die Rekursionsgleichung aufzulösen, indem ich immer rekursiv einsetze. Ich setze jetzt also [mm] \bruch{n}{2} [/mm] ein für den Anfang.


[mm] T(\bruch{n}{2}) [/mm] = [mm] T(\bruch{n}{4}) [/mm] + [mm] T(\bruch{n}{4}) [/mm] + n + [mm] \bruch{n}{2} [/mm]

Jetzt setzen wir [mm] \bruch{n}{4} [/mm] ein

[mm] T(\bruch{n}{4}) [/mm] = [mm] T(\bruch{n}{8}) [/mm] + [mm] T(\bruch{n}{8}) [/mm] + n + [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{4} [/mm]

=
..

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

So, so sieht wohl die Rekursion für k Schritte aus.

Wir setzen [mm] \bruch{n}{2^k} [/mm] = 1
Formen nach k um:

k = [mm] log_2(n) [/mm]  mit k [mm] \le log_2(n) [/mm]

Naja, daraus folgt:

[mm] T(\bruch{n}{2^k}) [/mm] = T(1) = 0

Jetzt müssen wir ja k in die Summe einsetzen, k ist ja k = [mm] log_2(n) [/mm]

Aus der Summe wird nun also [mm] \summe_{i=0}^{log_2(n)} \bruch{n}{2^{log_2(n)}} [/mm] und das ist gleich


[mm] \summe_{i=0}^{log_2(n)} [/mm] 1 = [mm] log_2(n) [/mm] + 1 ( laut Wolframalpha ? )


Also erhalten wir

T(n) = T(1)+ T(1) + [mm] log_2(n) [/mm] +1
T(n) = 0+0+ [mm] log_2(n) [/mm] +1 = [mm] log_2(n) [/mm] +1

Das funktioniert aber irgednwie nicht, wenn ich Testeinsetzungen mache. Wo ist mein Fehler ?

Bezug
                        
Bezug
Rekursionsgleichung lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:29 So 22.10.2017
Autor: HJKweseleit


> Hallo,
>  
> ich habe mal bisschen anders gerechnet, um die
> Rekursionsgleichung zu lösen. Ich komme auf log(n),
> allerdings fehlt da etwas, aber ich weiß nicht was.
>  
> Also wir hatten:
>  
> T(1) = 0 , das ist der Anker
>  
>
> T(n) = [mm]T(\lfloor\bruch{n}{2}\rfloor)[/mm] +
> [mm]T(\lceil\bruch{n}{2}\rceil)[/mm] +n   für n > 1
>  
> Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also
> so aussieht n = [mm]2^{a}[/mm] , a [mm]\in \IN[/mm]
>  



Sorry, aber ich hatte bei meinem Tipp vergessen, dich auf Folgendes aufmerksam zu machen:

n=Zweierpotenz ist völlig unsinnig, wenn n die natürlichen Zahlen durchlaufen soll.

Wenn T nur für Zweierpotenzen definiert werden soll, müsste es heißen:

T(1)=0

[mm] T(2^n)=[/mm] [mm]T(\lfloor\bruch{2^n}{2}\rfloor)[/mm] + [mm]T(\lceil\bruch{2^n}{2}\rceil)[/mm] [mm] +2^n [/mm]
= [mm]T(2^{n-1})[/mm] + [mm]T(2^{n-1})[/mm] [mm] +2^n [/mm] = [mm]2*T(2^{n-1})[/mm]  [mm] +2^n. [/mm]


Man würde also immer nur 2-er-Potenzen addieren.
T(3), T(5),... wären gar nicht definiert, und das Ergebnis wäre auch trivial. Es wäre [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung damit sinnlos.


Nehmen wir an, es wäre doch so gemeint, wie es sich anhört. Wenn n eine Zweierpotenz wäre, wäre [mm] \bruch{n}{2} [/mm] ganzzahlig und damit [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung gäbe, wie in meinem obigen Gesagten, wieder keinen Sinn.

Was müsste man nun für n=7 rechnen? [mm]\lfloor\bruch{n}{2}\rfloor[/mm]=3, [mm]\lceil\bruch{n}{2}\rceil[/mm]=4, und dann 7 addieren? 7 ist aber keine 2-er-Potenz, n sollte aber eine sein!

Man merkt, dass die Bemerkung so unsinnig ist. Sie hätte heißen müssen:
Hinweis: Betrachten sie die 2-er-Potenzen, zwischen denen n liegt.
Dann wäre man auch sehr schnell auf die Funktion [mm] log_2 [/mm] gestoßen...

Bezug
                                
Bezug
Rekursionsgleichung lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:34 So 22.10.2017
Autor: pc_doctor

Danke für die Antwort.

Sofern ich weiß, soll davon ausgegangen werden, dass n eine Zweierpotenz ist. Nehmen wir an, als geschlossene Formel kommt [mm] log_2(n) [/mm] raus, dann wäre dieser Logarithmus für nicht-Zweierpotenzen nicht definiert, habe ich das richtig verstanden?

Bezug
                                        
Bezug
Rekursionsgleichung lösen: Korrigiert
Status: (Antwort) fertig Status 
Datum: 15:15 Mo 23.10.2017
Autor: HJKweseleit

Natürlich ist [mm] log_2(n) [/mm] für alle n definiert.

Ich schreibe mal auf, was ich für die von dir gebildete Reihe herausgefunden habe.

T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2

T(3) = 5
T(4) = 8

T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24

T(9)  = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59
T(16) = 64

T(17) = 70

Die einzelnen Abschnitte bilden jeweils für sich eine arithmetische Folge und sind damit beschreibbar durch jeweils eine lineare Funktion der Form y=a*x+b, wobei a und b jeweils angepasst werden müssen. An den Nahtstellen kommt es zu überlappungen, die 8 kann man auch schon zur nächsten Reihe zählen, ebenso 24 und 64.

Man erhält so die Funktionen

y = 2x - 2      für x = 1   bis 2             mit [mm]\lfloor log_2(x) \rfloor[/mm]= 0
y = 3x - 4      für x von 2 bis 4 3           mit [mm]\lfloor log_2(x) \rfloor[/mm]= 1
y = 4x - 8      für x von 4 bis 8 7           mit [mm]\lfloor log_2(x) \rfloor[/mm]= 2
y = 5x - 16     für x von 8 bis 16 15         mit [mm]\lfloor log_2(x) \rfloor[/mm]= 3
y = 6x - 32     für x von 16 bis 32 31        mit [mm]\lfloor log_2(x) \rfloor[/mm]= 4
usw.

Allgemein erkennt man: Der Faktor a ist [mm]\lfloor log_2(x) \rfloor[/mm]  + 2, der Summand b ist [mm]-2^{\lfloor log_2(x) \rfloor+1}[/mm],

Somit [mm]T(n)=(\lfloor log_2(n) \rfloor \red{+} 2)*x - 2^{\lfloor log_2(x) \rfloor+1 [/mm]

Viel Spass beim Beweis durch vollständige Induktion ...


Bezug
                                                
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:59 Mo 23.10.2017
Autor: pc_doctor

Hallo nochmal,

vielen Dank für die Antwort.

Oh man, das kann ja mal was werden mit der Induktion. Ich versuche es :)

Bezug
                                                        
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:39 Mo 23.10.2017
Autor: HJKweseleit

Sorry, habe noch einen Schreibfehler gehabt und ihn nun mit rot korrigiert.

Bezug
                
Bezug
Rekursionsgleichung lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:04 Do 26.10.2017
Autor: vancouver

Hallo,
darf ich fragen wie du auf $ [mm] \lfloor log_2(n)\rfloor [/mm] $ gekommen bist?
LG

Bezug
                        
Bezug
Rekursionsgleichung lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 21:29 Do 26.10.2017
Autor: HJKweseleit

Der Wechsel bei den Abständen der Folgeglieder geschieht immer an einer Zweierpotenz, also bei n = 2, 4, 8, 16,...
Somit brauche ich die Information, zu welchem Abschnitt z.B. die 10 gehört. [mm] 2^3\le 10<2^4. [/mm] somit muss mir die 10 irgendwie den Exponenten 3 liefern, und alle Zahlen zwischen 8 und 15 ebenfalls.

Der [mm] log_2(n) [/mm] fragt: [mm] 2^{wieviel}=n, [/mm] und so kommt für die Zahlen von 8 bis 15 der Wert 3,... heraus, den ich dann abrunde.

Den [mm] log_2 [/mm] von x bekommst du, indem du einen beliebigen log (z.B. ln oder lg=log_10) nimmst und den Wert durch log(2) dividierst, wobei log(2) mit dem selben log genommen werden muss. Also:

[mm] log_2(x)=\bruch{ln(x)}{ln(2)}=\bruch{lg(x)}{lg(2)}=\bruch{log_5(x)}{log_5(2)}=... [/mm]

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de