Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursive Folgen, vollständige Induktion usw.??

Rekursive Folgen, vollständige Induktion usw.??

Universität / Fachhochschule

Folgen und Reihen

Funktionenfolgen

Tags: Folgen, Funktionenfolgen, Reihen, Vollständig Induktion

emilie aktiv_icon

20:02 Uhr, 09.07.2012

Hallo miteinander!
Ich muss eine Arbeit/Referat zum Thema "Turm von Hanoi" schreiben und bin, was die Mathematik angeht, etwas überfordert. 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?
Hab auch schon einiges gegooglet, aber bin immer noch nicht klüger. Vielleicht verstehe ich es besser, wenn man es mir mit eigenen Worten erklärt! Vielen Dank schon mal!!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Underfaker aktiv_icon

20:21 Uhr, 09.07.2012

"Ist "

2^{n} - 1

" ein Algorithmus? "

2^{n} - 1

ist ein Ausdruck, hier könnte man es wohl Formel nennen da sie die Zahl der benötigten Züge je Platten angibt (nehme ich an, ich weiß es selbst nicht)

Ein Algorithmus ist eher ein Plan, eine theoretische vorgehensweise um ein Problem zu lösen (insbesondere aus der Informatik bekannt).

"Was darf ich unter einer rekursiven Folge verstehen?"

Eine Rekursion existiert genau dann wenn sich bspw. eine Funktion selbst aufruft, wie bspw. die Fakultätsfunktion

n! = 1

wenn

n = 0

oder

n \cdot (n - 1)!

wenn

n > 0

Ein anderes Beispiel ist die Fibonaccifolge

http//de.wikipedia.org/wiki/Fibonacci-Folge

f_{n} = f_{n - 1} + f_{n - 2}

mit

f_{0} = 1

und

f_{1} = 1

"Informatisch" gesprochen: Die Funktion der Fibonaccizahlen beinhaltet als Argumente wieder die Funktion selbst und zwar wird sie solange rekursiv wiede selbst aufgerufen wenn der Anker

f_{0}

(und

f_{1})

erreicht wird.

Vollständige Induktion ist ein Beweisverfahren, dass für günstige Strukturen auf Basis der natürlichen zahlen funktioniert.

Du hast einen Ausdruck und zeigst (bspw. per einsetzen) dass der Ausdruck für einen Eingabewert (nennen wir ihn allgemein

n)

wahr ist.

Nun zeigst du noch, dass er für

n + 1

ebenfalls wahr ist.

Ein (Parade-)Beispiel:

1 + 2 + 3 + 4 + 5 + ... + n = \sum_{i = 1}^{n} i = \frac{n \cdot (n + 1)}{2}

Induktionsanfang mit

n = 1

Einsetzen ergibt:

\frac{1 \cdot 2}{2} = 1

Ist also wahr nun noch:

Induktionsschrit:

n \to n + 1

z

z

1 + 2 + 3 + 4 + 5 + ... + n + n + 1 = \sum_{i = 1}^{n + 1} i = \frac{(n + 1) \cdot (n + 2)}{2}

Dazu benutzt man die Induktionsvoraussetzung, dass für ein

n

(nämlich

1)

ja bereits die Ausgangsformel gilt also Iv.

: \sum_{i = 1}^{n} i = \frac{n \cdot (n + 1)}{2}

Nach Iv. gilt

\sum_{i = 1}^{n + 1} i = \frac{n \cdot (n + 1)}{2} + n + 1 = \frac{n (n + 1) + 2 n + 2}{2} = \frac{n (n + 1) + 2 (n + 1)}{2} = \frac{(n + 2) (n + 1)}{2}

:-)

Hat man das gezeigt hat man insgesamt:

Gilt für

n = 1

gilt für

n + 1

also für

1 + 1 = 2

gilt für

n + 1

also

2 + 1 = 3

. .

.

Mit vollständiger Induktion kann man also beweisen, dass Gleichungen bspw. helten, allerdings benötigt es dafür natürlich auch zwei Seiten (hier wäre es die Summe links und der geschlossene Ausdruck rechts).

Allerdings befürchte ich, dass du Probleme beim Verständnis haben wirst, da dir das offenkundig unbekannt ist, lies dich dort lieber erstmal ein.

"nur" mit

2^{n} - 1

kommt man dort nicht weit

Googles erster Eintrag liefert einen Vorschlag wie das zu lösen ist, offenbar mit zum Teil ausprobieren.

http//www.zum.de/Foren/mathematik/archiv/a231.html

emilie aktiv_icon

20:35 Uhr, 09.07.2012

Vielen Dank, dass du dir Zeit genommen hast, um meine Fragen zu beantworten!

"Ein Algorithmus ist eher ein Plan, eine theoretische vorgehensweise um ein Problem zu lösen (insbesondere aus der Informatik bekannt)."

Ah okay, also so etwas wie eine Bauanleitung eines Regals zum Beispiel?
Ich hab auch etwas über iterative und rekursive Algorithmen gelesen. Wo liegen da die Unterschiede? Kann man den Turm von Hanoi iterativ lösen?

"Eine Rekursion existiert genau dann wenn sich bspw. eine Funktion selbst aufruft"

Wie meinst du das? Also, wie ruft sich eine Funktion selber auf?

Das mit der vollständigen Funktion habe ich soweit kapiert - danke!

Underfaker aktiv_icon

20:55 Uhr, 09.07.2012

Der Unterschied ist liegt genau in der Sache Iterativ ist das sukzessive nacheinander Abarbeiten von Anweisungen.

Rekursion bedeutet rufe dich selbst auf, um zu deiner Frage zu kommen greife ich nochmals die Fakultätsfunktion auf.

Nehmen wir

n = 3

und geben wir sie ein:

3 > 0

also:

3 \cdot (3 - 1)! \to

hier ruft sich die Funktion ewieder selbst auf denn was bedeutet

(3 - 1)! = 2!

? es bedeutet:

2! = 2 \cdot (2 - 1)!

und was bedeutet der zweite Faktor hier?

(2 - 1)! = 1! = 1 \cdot (1 - 1)!

und jetzt wirds spannend:

(1 - 1)! = 0!

und nun ist das

n = 0

und hier rufen wir nicht (siehe oben) wieder die Fakultätsfunktion auf sondern es ist defieniert, dass wir für

n = 01

erhalten.

Was passiert nun?

Wir wissen

0! = 1

dann

1! = 1 \cdot 0! = 1 \cdot 1 = 1

dann

2! = 2 \cdot 1! = 2 \cdot 1 = 2

dann

3! = 3 \cdot 2! = 3 \cdot 2 = 6

Das bedeutet erst ruft sich die Funktion solange selbst auf bis sie beim Anker

n = 0

angelangt ist und erst dann gibt sie die Ergebnise Schrittweise immer weiter zurück.

Programmcode in Java:

public "int fak(int

n) / /

Ohne Anführungszeichen!

{

(n = = 0)

return

1;

else

r e t u r n n \cdot

fak(n-1);

}

Iterativ müsste man das jedesmal komplett hinschreiben (jeden Berechnungsschritt), das ist nicht so aufwändig bei der Fakultätsfunktion aber es gibt schlimmere, so ruft die Funktion sich selbst immer wieder auf und macht die meiste Arbeit selbst.

Vorteil:

Bei beherschen kürzerer Code der viel umsetzen kann

Nachteil:

Salopp ausgedrückt das kann sich ziemlich aufblähen und es kostet entsprechend Zeit und Speicher bis wir ein Ergebnis erhalten.

Die Fibonaccizahlen kann man sehr leicht so ressourcenfressend implementieren.

ich könnte sicher nun Seiten darüber schrieben und beispiele angeben aber besser du googlest mal ein wenig dannach.

Ich bin auch kein Fachmann für Algorithmen vor allem kenne ich mich nciht mit den Türmen von Hannoi aus aber offenbar liefert Google mit den Stichworten "Türme von Hannoi itterativ" ein paar Ergebnisse.

emilie aktiv_icon

22:35 Uhr, 09.07.2012

Nun fühle ich mich schon etwas klüger! Vielen Dank!

1016711

1016689

	Status: nicht eingeloggt	Noch nicht registriert?