Vollständige Induktion, Rekursive Folgen, Algorithmen usw.?

lena. · Newbie Anmeldungsdatum: 12.07.2009 Beiträge: 29

Hallo miteinander!
Ich muss eine Arbeit/Referat zum Thema "Turm von Hanoi" schreiben und bin, was die Mathematik angeht, etwas überfordert. Embarassed

Man kann ja aus der Formel 2^n-1 die benötigten Züge auszurechnen. Ist "2^n-1" ein Algorithmus? Was darf ich unter einer rekursiven Folge verstehen? Und für was ist die vollständige Induktion gut? Beweise ich damit, dass 2^n-1 "wahr" ist? Question

Hab auch schon einiges gegooglet, aber bin immer noch so klug wie vorher. Vielleicht verstehe ich es besser, wenn man es mir mit eigenen Worten erklärt! Vielen Dank schon mal!!

Deniz · Senior Member Anmeldungsdatum: 08.07.2004 Beiträge: 2574

Du sollst nachweisen, dass 2^(n) -1 die Anzahl optimaler Züge ist, also die Türme von Hanoi in dieser Anzahl an Schritten zu lösen, wobei n die Höhe des Steines ist.

Spielen wir das doch mal:

Für einen Stein brauchst Du 1 Zug. Das ist trivial.
Für zwei Steine brauchst Du 3 Züge.
Für drei Steine brauchst Du 7 Züge. (nachspielen)

Du vermutest also, dass Du bei n Steinen 2^(n) -1 Züge brauchst.

Beweis: Induktion. Anfang ist klar, siehe oben.

Wir haben also n+1 Steine.
Was machst Du als 1. ?
Den Turm, bis auf den letzten unteren Stein, kannst Du nach Induktionsvorraussetzung in 2^n -1 Zügen umlegen.
Du machst einen weiteren Zug. (+1)
Nun musst Du den großen Turm wieder zurückbauen. Macht nach Ind. Vor. 2^n -1 Züge.

Zusammen also? Smile

Deniz · Senior Member Anmeldungsdatum: 08.07.2004 Beiträge: 2574

Ach ja:

Google "Türme von Hanoi" 1. Link

[url]http://de.wikipedia.org/wiki/Türme_von_Hanoi#Eigenschaften_optimaler_Zugfolgen[/url]

Sag mir nicht, dass Du das nicht gesehen hast. Dort wird es auch nochmal erklärt

Noch etwas:
Ich finde am Beispiel mit den Türmen von Hanoi sieht man sehr schön an etwas Greifbarem, wie die Induktion arbeitet und was eigentlich genau passiert. Smile

lena. · Newbie Anmeldungsdatum: 12.07.2009 Beiträge: 29

Deniz · Senior Member Anmeldungsdatum: 08.07.2004 Beiträge: 2574

Also eine Rekursion ist etwas, was über sich selbst definiert ist.
Z. B. eine Folge
a0 = 1
a1 = 1
a_n = a_(n-1) + a_(n-2) n>2

Das heißt, die Folgeglieder a3, a4, ... werden über die Vorgänger berechnet. Das ist eine Rekursion. (hier z. B. die Fibonacci-Folge)

Mit vollständiger Induktion kann man sowas z. B. beweisen, wenn Du eine Vermutung hast.

Z. B. bei den Türmen von Hanoi. Wir vermuten, dass man im Idealfall 2^n -1 Züge braucht, wobei n die Höhe des Turmes ist.
Das finden wir heraus, in dem wir das Spielchen spielen und notieren, wie die Folge aussieht.
In unserem Fall hatten wir
1
3
7
15
...

Vermutung: 2^n -1

Wie beweist man das. Klar, vollständige Induktion.
Weißt Du auch, was dahinter steckt?

Es geht um folgendes. Wir haben unendlich viele Aussagen und wollen zeigen, dass die für alle gilt.

Dabei nutzen wir die Transitivität der Implikation. Heißt:
Wenn A => B und B => C, dann A => C.

Wir bauchen also, um das Ganze dingfest zu machen, einen Induktionsanfang.
n = 1, also 1 Stein.
Wir brauchen 1 Zug. Damit ist unser Anfang getan und der passt auch zu
2^n -1 für n = 1. 2^1 -1 = 2-1 = 1.

Wenn uns jetzt gelingt von n => n+1 zu schließen, können wir mittels der Transitivität sagen.
Da es für 1 gilt, gilt es für 2. Weil es für 2 gilt, gilt es für 3. Usw.

Nun kommt der Induktionsbeweis. Den findest Du oben.
Ich hoffe, es ist klarer geworden, ansonsten melde Dich nochmal und ich versuche näher drauf einzugehen. Smile

Ach ja: Unterschied Rekursion und Iteration.

http://kfleischer.delphigl.com/files/Rekursion_und_Iteration.pdf

Hier wird das schön erklärt.

Ol@f · Full Member Anmeldungsdatum: 05.09.2007 Beiträge: 496

Sind die Begriffe denn jetzt geklärt?

Ich kann ja mal eine kleine (grobe) Einfühung geben:
Ein Algorithmus ist eine präzise Vorschrift zur Durchführung einer endlichen Folge von Elementaroperationen, um Probleme einer bestimmten Klasse zu lösen.

Kleines Beispiel: Lösen einer quadratischen Gleichung y^2-2py+q=0
Input: p,q € |R und p^2>= q
Output: y € IR, y<= p und y^2-2py+q=0

In- und Outputmenge müssen wir einschränken, weil wir die Existenz und Eindeutigkeit der Lösung garantieren möchten.

Ablauf:
1. x_1= p*p
2. x_2=x_1 - q
3. x_3= sqrt(x_2)
4. y= p - x_3

Fertig. Es ist zwar nicht der schönste Algorithmus dazu, aber dafür sehr verständlich (pq- Formel).

Nun den Unterschied zwischen rekursiven und iterativen Algorithmen:
Dafür finde ich die Fakultätsfunktion aus wiki schön.
Also n! ist definiert als n * (n-1) * (n-2) * ... * 1, mit n € IN. Also 4!=4*3*2*1=24

Betrachten wir nun die Funktionen, um die Fakultät zu berechnen.
Iterativ:
fakultät_iterativ(n)
{
fakultät = 1
faktor = 2
solange faktor <= n
{
fakultät = fakultät * faktor
faktor = faktor + 1
}
return fakultät
}

Wenn wir bspw. 4! berechnen wollen macht der Algorithmus folgendes:
Setze Fakultät auf 1 und Faktor auf 2
Prüfe, ob Faktor <= 4 ist. Ist erfüllt also gehe in die Schleife.
fakultät= 1 * 2 (=2)
faktor=2+1 (=3)
Prüfe, ob Faktor <= 4 ist. Erfüllt, also gehe in die Schleife.
fakultät= 2* 3 (=6)
faktor=3 + 1 (=4)
Prüfe ob Faktor <=4 ist. Erfüllt, also gehe in die Schleife.
fakultät = 6 * 4 (=24)
faktor = 4+1 (=5)
Prüfe ob Faktor <=4 ist. NICHT erfüllt, also überspringe Schleife.
Nun gebe fakultät aus. Also 24

Rekursiv:
fakultät_rekursiv(n)
{
wenn n <= 1
dann return 1
sonst return ( n * fakultät_rekursiv(n-1) )
}

Wir wollen wieder 4! - also für n=4 - berechnen.
Ist n<=1 ? Konkret: Ist 4 <= 1? Nein, also gehe in den Schritt sonst:
Nun Rechnen wir 4 * fakultät_rekursiv(3) aus. Dafür benötigen wir aber den Wert von fakultät_rekursiv(3). Also führen wir dafür, nochmal die Funktion aus:
Ist 3<=1? Nein, also rechne 3* fakultät_rekursiv(2) aus. Dafür benötigen wir aber fakultät_rekursiv(2). Also gehe nochmal in die Funktion rein.
Ist 2<=1? Nein, also rechne 2 * fakultät_rekursiv(1) aus. Brauchen wieder fakultät_rekursiv(1). Also nochmal in die Funktion:
Ist 1<=1? Ja, also gebe uns dafür den Wert 1 aus.
Also, wissen wir jetzt:
fakultät_rekursiv(1) = 1
fakultät_rekursiv(2) = 2 * 1 (=2)
fakultät_rekursiv(3) = 3 * 2 (=6)
fakultät_rekursiv(4) = 4 * 6 (=24)

Also erhalten wir 4! = 24

Das war die kleine Einführung zur Algorithmen.

So nun zu unseren Folgen. Eine Folge ist für dich einfach eine Funktion f: IN --> IR. statt f(n), schreibt man auch häufig f_n.

Geben wir mal eine explizite Folge an: Also g: IN ---> IR mit g(n)= (-1)^n
Schauen wir uns mal die ersten Glieder an:
g(0)= (-1)^0 = 1
g(1)=(-1)^1 = -1
g(2)= 1
g(3)= -1
....

In unseren "expliziten" Folge können wir also jedes Glied durch eine konkrete Rechenvorschrift erhalten. Also g(20)=(-1)^20 = 1.

Bei den "rekursiven" Folgen ist das alles ein bisschen umständlicher. Geben wir mal eine an:

f: IN --> IR mit f(n)=f(n-1)+ f(n-2) für n>=2 mit den Startwerten f(0)=0 und f(1)=1
Rechnen wir mal wieder ein paar Glieder aus:
f(2) = f(1) + f(0) = 1 + 0 =1
f(3) = f(2) + f(1) = 1 + 1 =2
f(4) = 2 + 1 =3
f(5) = 3 + 2 = 5
...
Um f(8) zu berechnen, müssen wir also voerst f(1), f(2), ..., f(7) berechnen und können nicht so einfach in eine geschlossene Formel einsetzen, um das Ergebnis zu erhalten. Erkennst du die Parallelen zum rekursiven Algorithmus?
In manchen Fällen kann man einfach aus einer rekursiven Formel eine explizite Formel finden, die gleich sind.
Im oberen Fall wäre das die Formel von Binet und Moivre (s. wiki). Kann man unter anterem auch mit Induktion beweisen.

Gruß Ol@f.

Edit. Huch, da komm ich ein bisschen spät, aber ist sicherlich auch hilfreich :D
_________________
Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch. (Bertrand Russell)

lena. · Newbie Anmeldungsdatum: 12.07.2009 Beiträge: 29

Vielen vielen herzlichen Dank Ol@f und Deniz !!! Ihr habt mir unheimlich weitergeholfen - war schon richtig am verzweifeln! Ich hoffe, ich darf euch bei Rückfragen kontaktieren Wink