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




Vollständige InduktionBearbeiten

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.

VorgehenBearbeiten

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 1Bearbeiten

 

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 2Bearbeiten

 

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  

LiteraturBearbeiten

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.