induktive/rekursive Definition < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo!
Wo liegt der Unterschied zwischen einer rekursiven Defintion und einer induktiven?
Lg
|
|
| |
|
In einer rekursiven Definition des allgemeinen Glieds [mm] a_n [/mm] kommen ein oder mehrere Glieder [mm] a_k [/mm] mit k<n vor.
In einer induktiven Definition des allgemeinen Glieds [mm] a_n [/mm] sind keine solchen Glieder enthalten (sondern nur n als Variable).
Allerdings werden Folgen oder Reihen, die auf eine der beiden Arten definiert sind, so gut wie immer induktiv überprüft bzw. bewiesen.
|
|
|
| |
|
hast du da vllt. noch ein beispiel für?
wäre super 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:09 Mi 12.11.2008 | | Autor: | fred97 |
> In einer rekursiven Definition des allgemeinen Glieds [mm]a_n[/mm]
> kommen ein oder mehrere Glieder [mm]a_k[/mm] mit k<n vor.
> In einer induktiven Definition des allgemeinen Glieds [mm]a_n[/mm]
> sind keine solchen Glieder enthalten (sondern nur n als
> Variable).
Das ist doch Unsinn. Mach Dich noch mal schlau.
>
> Allerdings werden Folgen oder Reihen, die auf eine der
> beiden Arten definiert sind, so gut wie immer induktiv
> überprüft bzw. bewiesen.
Was soll das denn heißen ??
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:35 Mi 12.11.2008 | | Autor: | reverend |
Ich warte mal ab, vielleicht hab ichs ja auch falsch verstanden. So hab ichs aber in Erinnerung.
Es wäre nett, fred, wenn Du die richtige Definition angäbst.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:14 Mi 12.11.2008 | | Autor: | Marcel |
Hallo,
> und was ist nun richtig?
richtig ist, dass die rekursive Definition auf dem Induktionsprinzip basiert. (![[]](/images/popup.gif) Siehe hier, Seite 6ff).
Bei einer Rekursion berechnet man (meist den Wert einer Formel) $A(n+1)$ ja eben mit [mm] $A(n)\,,$ [/mm] dann $A(n)$ mit $A(n-1)$ ... bis man hin zu $A(0)$ gelangt.
Das ist nun nur etwas grob angedeutet, ich hoffe, man erkennt, was ich meine.
Typisches Beispiel:
Direkte Berechnung von $n!$ und rekursive Berechnung von $n!$.
Ich mache es auch mal für einen festen Zahlenwert:
Direkte Berechnung [mm] ($n!=\produkt_{k=1}^n [/mm] k$):
[mm] $5!=1*2*3*4*5=120\,.$ [/mm]
Rekursive Berechnung (Im Sinne von: Berechnung mit einem rekursiven Algorithmus, ähnlich dem ersten Alg. (Fakultaet Demo.java) von hier (ich halte mich nicht ganz an diesen Algorithmus)) mit [mm] $n!\black{=}n*(n-1)!$:
[/mm]
1. Schritt: [mm] $5!=5*4!\,.$
[/mm]
Wir brauchen nun $4!$:
2. Schritt: [mm] $4!=4*3!\,.$
[/mm]
Wir brauchen nun $3!$:
3. Schritt: [mm] $3!=3*2!\,.$
[/mm]
Wir brauchen nun $2!$:
4. Schritt: [mm] $2!=2*1!\,.$
[/mm]
Wir brauchen nun $1!$:
5. Schritt: [mm] $1!=1*0!\,.$
[/mm]
Wir brauchen nun $0!$:
6. Schritt: Wisen [mm] $0!=1\,.$
[/mm]
7. Schritt: Mit Schritt 5. erkennen wir also [mm] $1!=1\,.$
[/mm]
8. Schritt: Mit Schritt 4. (und 7.) erkennen wir also [mm] $2!=2\,.$
[/mm]
9. Schritt: Mit Schritt 3. (und 8.) erkennen wir also [mm] $3!=6\,.$
[/mm]
10. Schritt: Mit Schritt 2. (und 9.) erkennen wir also [mm] $4!=24\,.$
[/mm]
11. Schritt: Mit Schritt 1. (und 10.) erkennen wir also [mm] $5!=120\,.$
[/mm]
Du siehst hier also:
Man hat hier die Berechnung von $n!$ zunächst auf die Berechnung von $(n-1)!$ zurückgeführt. Die Berechnung von $(n-1)!$ wieder auf die von $(n-2)!$ etc...
So grob kann man sagen: Mithilfe der Induktion läßt sich ein rekursiver Algorithmus zur "Berechnung" von $A(n)$ aufstellen. Dass dieser für jedes $n [mm] \in \IN$ [/mm] terminiert, liegt eben an der Induktion.
Und schau' Dir in dem Skript oben ruhig auch mal das Beispiel mit den Binomialkoeffizienten an.
Gruß,
Marcel
|
|
|
| |
|
hmmm du schreibst oben, dass du A(n+1) berechnen willst, mittels (A(n)...(n-1)) aber im Prinzip nutzt du doch nur A(n), oder?
und zu der induktiven Methode, hat da jmd noch ein Beispiel für mich?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:19 Do 13.11.2008 | | Autor: | Loddar |
Hallo Fuchsschwanz!
> hmmm du schreibst oben, dass du A(n+1) berechnen willst,
> mittels (A(n)...(n-1)) aber im Prinzip nutzt du doch nur
> A(n), oder?
Ja, aber für A(n) benötigst Du wiederum A(n-1). Und für A(n-1) musst Du A(n-2) kennen usw. bis hin zu einem Startwert wie z.B. A(1).
Gruß
Loddar
|
|
|
| |
|
ja klar, aber wie komme ich zu A(n+1) wenn ich mit A(n) anfange?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:03 Do 13.11.2008 | | Autor: | Loddar |
Hallo Fuchsschwanz!
> ja klar, aber wie komme ich zu A(n+1) wenn ich mit A(n) anfange?
Durch die entsprechende vorgegebene Rekursionsvorschrift.
Ein Beispiel habe ich Dir hier genannt.
Gruß
Loddar
|
|
|
| |
|
Bei einer Rekursion berechnet man (meist den Wert einer Formel) A(n+1) ja eben mit $ [mm] A(n)\,, [/mm] $ dann A(n) mit A(n-1) ... bis man hin zu A(0) gelangt.
das hat Marcel geschrieben, dein Beispiel ist mir schon klar, aber du nimmst doch das 17. Glied für [mm] A_n [/mm] an...und Marcel schrieb oben, dass ich A(n+1) berechnen möchte, wie passt das zusammen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:23 Fr 14.11.2008 | | Autor: | Loddar |
Hallo Fuchsschwanz!
Aber es ist doch prinzipiell dasselbe, ob man nun A(n+1) aus (An) berechnet ... oder aber A(n) aus A(n-1).
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:04 Do 13.11.2008 | | Autor: | Loddar |
Hallo reverend!
> In einer induktiven Definition des allgemeinen Glieds [mm]a_n[/mm]
> sind keine solchen Glieder enthalten (sondern nur n als Variable).
Das nennt sich doch "explizite Darstellung", wo man jedes Folgenlied [mm] $a_n$ [/mm] direkt ausrechnen kann.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:21 Do 13.11.2008 | | Autor: | reverend |
Da muss ich Dir wohl explizit Recht geben, Loddar.
Danke für die Korrektur!
Trotzdem verstehe ich Freds Reaktion nicht ganz, aber vielleicht erklärt er die ja noch selbst...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:55 Do 13.11.2008 | | Autor: | fred97 |
Du hast folgendes geschrieben:
"In einer induktiven Definition des allgemeinen Glieds $ [mm] a_n [/mm] $
sind keine solchen Glieder enthalten (sondern nur n als
Variable)"
und das ist Unsinn.
Z.B. def. ich eine Folge [mm] (a_n) [/mm] durch:
[mm] a_1 [/mm] =1 und [mm] a_{n+1} [/mm] = [mm] 2a_n
[/mm]
FRED
Ist das denn keine induktive Def. ?
|
|
|
| |
|
> Z.B. def. ich eine Folge [mm](a_n)[/mm] durch:
>
> [mm]a_1[/mm] =1 und [mm]a_{n+1}[/mm] = [mm]2a_n[/mm]
>
>
> FRED
>
>
> Ist das denn keine induktive Def. ?
Hallo,
ich "empfinde" diese Definition als induktiv, und ich hätte keinen Zweifel daran, daß hier eine rekursiv definierte Folge vorliegt.
Gibt es denn nun einen Unterschied zwischen einer rekursiven und einer induktiven Definition? Falls ja: könntest Du mal für jedes ein Beispiel sagen?
Kann es sein, daß Informatiker irgendwelche Unterschiede machen, die man in der Mathematik gar nicht macht?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:22 Do 13.11.2008 | | Autor: | fred97 |
>
> > Z.B. def. ich eine Folge [mm](a_n)[/mm] durch:
> >
> > [mm]a_1[/mm] =1 und [mm]a_{n+1}[/mm] = [mm]2a_n[/mm]
> >
> >
> > FRED
> >
> >
> > Ist das denn keine induktive Def. ?
>
> Hallo,
>
> ich "empfinde" diese Definition als induktiv, und ich hätte
> keinen Zweifel daran, daß hier eine rekursiv definierte
> Folge vorliegt.
>
> Gibt es denn nun einen Unterschied zwischen einer
> rekursiven und einer induktiven Definition?
Nein.
Gruß FRED
>Falls ja:
> könntest Du mal für jedes ein Beispiel sagen?
>
> Kann es sein, daß Informatiker irgendwelche Unterschiede
> machen, die man in der Mathematik gar nicht macht?
>
> Gruß v. Angela
>
>
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:27 Do 13.11.2008 | | Autor: | reverend |
Hallo Fred,
Zugegeben, der Satz war falsch.
Aber an dem Rest halte ich fest, auch daran, dass in einer rekursiven Definition verschiedene [mm] a_k [/mm] mit k<n vorkommen können (nachträgliche, aber wesentliche Einfügung. Ich war wieder zu schnell).
Einfachstes Beispiel dürfte die Fibonaccifolge sein, [mm] a_1=1, a_2=1, a_n=a_{n-1}+a_{n-2} [/mm] für [mm] n\ge3
[/mm]
Ich war nur verwundert, dass Du meinen Beitrag so in Bausch und Bogen verworfen hast, und das, ohne zu berichtigen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:46 Do 13.11.2008 | | Autor: | fred97 |
> Hallo Fred,
>
> Zugegeben, der Satz war falsch.
>
> Aber an dem Rest halte ich fest, auch daran, dass in einer
> rekursiven Definition verschiedene [mm]a_k[/mm] mit k<n vorkommen
> können (nachträgliche, aber wesentliche Einfügung. Ich war
> wieder zu schnell).
Das ist aber auch eine induktive Def.
FRED
> Einfachstes Beispiel dürfte die Fibonaccifolge sein,
> [mm]a_1=1, a_2=1, a_n=a_{n-1}+a_{n-2}[/mm] für [mm]n\ge3[/mm]
>
> Ich war nur verwundert, dass Du meinen Beitrag so in Bausch
> und Bogen verworfen hast, und das, ohne zu berichtigen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:10 Do 13.11.2008 | | Autor: | Marcel |
Hallo,
> Hallo Fred,
>
> Zugegeben, der Satz war falsch.
>
> Aber an dem Rest halte ich fest, auch daran, dass in einer
> rekursiven Definition verschiedene [mm]a_k[/mm] mit k<n vorkommen
> können (nachträgliche, aber wesentliche Einfügung. Ich war
> wieder zu schnell).
auch das ist ein Induktionsverfahren.
> Einfachstes Beispiel dürfte die Fibonaccifolge sein,
> [mm]a_1=1, a_2=1, a_n=a_{n-1}+a_{n-2}[/mm] für [mm]n\ge3[/mm]
>
> Ich war nur verwundert, dass Du meinen Beitrag so in Bausch
> und Bogen verworfen hast, und das, ohne zu berichtigen.
Die Definition der Fibonaccifolge ist ebenso eine induktive Definition (es gibt auch die Induktion, wo man beim Schritt $n [mm] \mapsto [/mm] n+1$ gewisse (bis hin zu allen) $A(k)$, $k [mm] \le [/mm] n$ benutzen darf).
Siehe dazu auch hier (Stichwort: starke Induktion).
Und auch Wiki: Vollst. Induktion.
Also es scheint noch nicht ganz angekommen zu sein:
Induktion und Rekursion gehen Hand in Hand. Insbesondere beinhaltet jede Induktionsdefinition einen Rekursionsalgorithmus.
Beim Rekursionsalgorithmus läuft man (im Programm) erstmal rückwärts, bis man einen Startwert hat und ab dann wieder vorwärts.
(Siehe oben: $5!$: Computer erhält: Berechne 5!. Algorithmus sagt: Es gilt 5!=5*4! -> Algorithmus sagt: Wir brauchen 4!. Nun gilt 4!=4*3! -> ... bis man zu einem "Startwert gelangt". Jetzt wird das alles benutzt und der Algorithmus terminiert, genauer: siehe oben!)
Wegen der Induktion terminiert dieser Algorithmus aber. Er gelangt nämlich irgendwann zu einem Startwert und kommt auch wieder zurück zu dem zu berechnenden Term, und, grob gesagt: Alle Lückenwerte werden dabei eingefügt.
Siehe auch Wiki: Rekursive Programmierung oder auch hier (interessant ist das "Verschachtelungsbild" ganz am Ende).
Und zu guter Letzt:
Siehe hier.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:01 Do 13.11.2008 | | Autor: | reverend |
Hallo Marcel,
danke für die recht ausführliche Erläuterung und die hilfreiche Verlinkung. ![[hut]](/images/smileys/hut.gif "[hut]")
Zugleich gibst Du auch einen Hinweis darauf, der mich an Angelas Frage erinnert - ob es da nicht Unterschiede im terminologischen Gebrauch der Informatik und der Mathematik gibt. So sieht es doch jetzt aus.
Ich hatte die ursprüngliche Frage übrigens gar nicht als Informatik-Frage betrachtet...
...und beginne wieder daran zu zweifeln, ob sich jetzt alle über die Definition der Begriffe wirklich einig sind.
Vielleicht reicht es aber auch, die verschiedenen Betrachtungsweisen einfach zur Kenntnis zu nehmen. Dem Mathematiker darf dabei egal sein, ob die rekursive Definition auch einen Algorithmus bereitstellt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:14 Do 13.11.2008 | | Autor: | Marcel |
Hallo zusammen,
> Hallo reverend!
>
>
> > In einer induktiven Definition des allgemeinen Glieds [mm]a_n[/mm]
> > sind keine solchen Glieder enthalten (sondern nur n als
> Variable).
>
> Das nennt sich doch "explizite Darstellung", wo man jedes
> Folgenlied [mm]a_n[/mm] direkt ausrechnen kann.
explizit ginge dann wohl Hand in Hand mit der iterativen Programmierung.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:16 Do 13.11.2008 | | Autor: | Loddar |
Hallo Fuchsschwanz!
> Wo liegt der Unterschied zwischen einer rekursiven Defintion und einer
> induktiven?
In welchem Zusammenhang hast Du das vorliegen? Denn m.E. gibt es keinen Unterschied, sondern ist beides im Grunde genommen dasselbe.
Denn Du benötigst hier zur Berechnung des n-ten Gliedes [mm] $a_n$ [/mm] mindestens eine vorheriges Glied. Wichtig bei der rekursiven / indujtiven Darstellung ist, dass ein Startwert gegeben ist.
Beispiel:
[mm] $$a_n=\begin{cases} a_1 \ = \ 1, & \mbox{} \mbox{ } \\ a_{n-1}+n, & \mbox{ } \mbox{ } \end{cases}$$
[/mm]
Du siehst z.B., dass man zur Berechnung von [mm] $a_{17} [/mm] \ = \ [mm] a_{16}+17$ [/mm] erst das 16. Glied [mm] $a_{16}$ [/mm] kennen muss.
Und für [mm] $a_{16} [/mm] \ = \ [mm] a_{15}+16$ [/mm] brauche ich [mm] $a_{15}$ [/mm] ...
Im Gegensatz dazu gibt es die "explizite Darstellung", bei welcher man das n-te Glied [mm] $a_n$ [/mm] direkt berechnen kann, ohne irgendeines der vorherigen Glieder zu kennen.
Das o.g. Beipsiel lässt sich explizit wie folgt darstellen:
[mm] $$a_{n} [/mm] \ = \ [mm] \bruch{n*(n+1)}{2}$$
[/mm]
Hier kann ich also ganz schnell das 17. Glied [mm] $a_{17}$ [/mm] direkt berechnen.
Gruß
Loddar
|
|
|
|
