Kurs:Algorithmen und Datenstrukturen/Vorlesung/Vollständige Induktion

Aus Wikiversity




Vollständige Induktion[Bearbeiten]

Auf dieser Seite wird die vollständige Induktion behandelt. Es handelt sich hierbei um eine rekursive Beweistechnik aus der Mathematik. Sie ist gut geeignet, um Eigenschaften von rekursiv definierten Funktionen zu beweisen.

Vorgehen[Bearbeiten]

Zunächst vermutet man eine Eigenschaft (z.B. Aufwandsklasse einer Rekursionsgleichung). Nun folgt der Induktionsanfang: Eigenschaft hält für ein kleines n. Als nächstes folgt der Induktionsschritt: Die Annahme ist, dass wir es bereits für ein kleineres n gezeigt haben und wenn die Eigenschaft für kleinere n hält, dann hält sie auch für das nächstgrößere n!

Beispiel 1[Bearbeiten]

Nun wollen wir die obere Grenze für den Aufwand bestimmen. Unsere Vermutung ist, dass . Nun müssen wir zeigen, dass ( siehe Definition der O-Notation). Die vereinfachte Annahme lautet . Hierbei werden keine Spezialfälle behandelt und im Induktionsschritt wird von nach n gegangen.

Induktionsvermutung:

Induktionsschritt: Wir beweisen von

zu zeigende obere Grenze:

Rekursionsgleichung einsetzen:

Induktionsvermutung einsetzen:

Somit ist der Induktionsschritt erfolgreich, wenn .

Induktionsanfang

Wir zeigen die Induktionsvermutung für einen Anfangswert, am einfachsten ist es, dies für den Rekursionsabbruch zu zeigen.

Zu zeigende obere Grenze:

Rekursionsgleichung einsetzen:

Der Induktionsanfang ist erfolgreich, wenn ist. Doch wann können wir zeigen, dass ist? Für den Wert, den wir im Induktionsanfang gezeigt haben, also für und wenn .

Beispiel 2[Bearbeiten]

Nun wollen wir die obere Grenze für den Aufwand bestimmen. Unsere Vermutung ist, dass . Nun müssen wir zeigen, dass . Die vereinfachte Annahme lautet .

Induktionsvermutung:

Induktionsschritt: Wir beweisen von

Das Problem ist nun, dass wir den Induktionsschritt für positive n zeigen wollen und nicht für negative, daher müssen wir neu ansetzen.

Induktionsvermutung:

Dabei gibt es folgenden Trick: Modifiziere die Induktionsvermutung, in dem ein kleineres Polynom addiert wird.

Induktionsschritt: Wir beweisen von

Induktionsanfang für n=1

Wann können wir nun zeigen, dass ?

Für . Somit haben wir gezeigt, dass

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.2.5 zu finden.


Discussion