Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Vollständige Induktion

Vollständige Induktion

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

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

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für}}\ n\leq 1\\4\cdot T({\frac {n}{2}})+\Theta (n^{3})&sonst\end{array}}\right.$

Nun wollen wir die obere Grenze für den Aufwand bestimmen. Unsere Vermutung ist, dass $T(n)\in O(n^{3})$ . Nun müssen wir zeigen, dass $\exists n_{0},c:\forall n\geq n_{o}:T(n)\leq c\cdot n^{3}$ ( siehe Definition der O-Notation). Die vereinfachte Annahme lautet $n=2^{k}$ . Hierbei werden keine Spezialfälle behandelt und im Induktionsschritt wird von ${\frac {n}{2}}$ nach n gegangen.

Induktionsvermutung: $T({\frac {n}{2}})\leq c\cdot ({\frac {n}{2}})^{3}$

Induktionsschritt: Wir beweisen von ${\frac {n}{2}}~nach~n$

zu zeigende obere Grenze:

T(n)\leq c\cdot n^{3}\ \ \ |T(n)=4\cdot T({\frac {n}{2}})+n^{3}

Rekursionsgleichung einsetzen:

$\Leftrightarrow 4\cdot T({\frac {n}{2}})+n^{3}\leq c\cdot n^{3}|T({\frac {n}{2}})\leq c\cdot ({\frac {n}{2}})^{3}$

Induktionsvermutung einsetzen:

$\ \Leftarrow 4\cdot c\cdot ({\frac {n}{2}})^{3}+n^{3}\leq c\cdot n^{3}$

$\ \Leftrightarrow 4\cdot c\cdot ({\frac {n^{3}}{8}})+n^{3}\leq c\cdot n^{3}|-c\cdot n^{3}$

$\ \Leftrightarrow -{\frac {1}{2}}\cdot c\cdot n^{3}+n^{3}\leq 0|:n^{3}$

$\ \Leftrightarrow -{\frac {1}{2}}\cdot c+1\leq 0|+{\frac {1}{2}}\cdot c$

$\ \Leftrightarrow 1\leq {\frac {1}{2}}\cdot c|\cdot 2$

$\ \Leftrightarrow 2\leq c$

Somit ist der Induktionsschritt erfolgreich, wenn $c\geq 2$ .

Induktionsanfang

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

Zu zeigende obere Grenze:

T(1)\leq c\cdot 1^{3}|T(1)=1

Rekursionsgleichung einsetzen:

$\Leftrightarrow 1\leq c$

Der Induktionsanfang ist erfolgreich, wenn $c\geq 1$ ist. Doch wann können wir zeigen, dass $T(n)\leq c\cdot n^{3}$ ist? Für den Wert, den wir im Induktionsanfang gezeigt haben, also für $n_{0}=1$ und wenn $(c\geq 2\land c\geq 1)\Rightarrow c\geq 2$ .

Beispiel 2

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für}}\ n\leq 1\\4\cdot T({\frac {n}{2}})+\Theta (n)&sonst\end{array}}\right.$

Nun wollen wir die obere Grenze für den Aufwand bestimmen. Unsere Vermutung ist, dass $T(n)\in O(n^{2})$ . Nun müssen wir zeigen, dass $\exists n_{0},c:\forall n\geq n_{0}:T(n)\leq c\cdot n^{2}$ . Die vereinfachte Annahme lautet $n=2^{k}$ .

Induktionsvermutung: $T({\frac {n}{2}})\leq c\cdot ({\frac {n}{2}})^{2}$

Induktionsschritt: Wir beweisen von ${\frac {n}{2}}~nach~n$

T(n)\leq c\cdot n^{2}|T(n)=4\cdot T({\frac {n}{2}})+n

$\Leftrightarrow 4\cdot T({\frac {n}{2}})+n\leq c\cdot n^{2}|T({\frac {n}{2}})\leq c\cdot ({\frac {n}{2}})^{2}$

$\Leftarrow 4\cdot c\cdot ({\frac {n}{2}})^{2}+n\leq c\cdot n^{2}$

$\Leftrightarrow 4\cdot c\cdot ({\frac {n^{2}}{4}})+n\leq c\cdot n^{2}|-c\cdot n^{2}$

$\Leftrightarrow n\leq 0$

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.

$T({\frac {n}{2}})\leq c_{1}\cdot ({\frac {n}{2}})^{2}+c_{2}\cdot {\frac {n}{2}}$

Induktionsschritt: Wir beweisen von ${\frac {n}{2}}~nach~n$

T(n)\leq c_{1}\cdot n^{2}+c_{2}\cdot n

$\Leftrightarrow 4\cdot T({\frac {n}{2}})+n\leq c_{1}\cdot n^{2}+c_{2}\cdot n$

$\Leftarrow 4\cdot (c_{1}\cdot ({\frac {n}{2}})^{2}+c_{2}\cdot {\frac {n}{2}})+n\leq c_{1}\cdot n^{2}+c_{2}\cdot n$

$\Leftrightarrow c_{1}\cdot n^{2}+2\cdot c_{2}\cdot n+n\leq c_{1}\cdot n^{2}+c_{2}\cdot n|-c_{1}\cdot n^{2};-c_{2}\cdot n$

$\Leftrightarrow c_{2}\cdot n+n\leq 0$

$\Leftrightarrow c_{2}+1\leq 0$

$\Leftrightarrow c_{2}\leq -1$

Induktionsanfang für n=1

T(1)\leq c_{1}\cdot 1^{2}+c_{2}\cdot 1|T(1)=1

$\Leftrightarrow 1\leq c_{1}+c_{2}|-c_{2}$

$\Leftrightarrow 1-c_{2}\leq c_{1}$

Wann können wir nun zeigen, dass $T(n)\leq c_{1}\cdot n^{2}+c_{2}\cdot n$ ?

Für $n_{0}=1~und~wenn~(c_{2}\leq -1\land c_{1}\geq 1-c_{2})$ . Somit haben wir gezeigt, dass $T(n)\in O(n^{2}+n)\Rightarrow T(n)\in O(max(n^{2},n))\Rightarrow T(n)\in O(n^{2})$

Literatur

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.