Folien - Grundbegriffe der Informatik

Grundbegriffe der Informatik
Kapitel 6: Induktives Vorgehen
Thomas Worsch
KIT, Institut für Theoretische Informatik
Wintersemester 2015/2016
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
1 / 18
Wo sind wir?
Vollständige Induktion
Varianten vollständiger Induktion
Induktive Definitionen
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
2 / 18
Eine Erinnerung
Potenzen von Wörtern wurden so definiert
für jedes Wort w ∈ A∗ :
w0 = ε
für jedes n ∈ N0 : w n+1 = w n · w
Lemma. Für jedes Wort w ∈ A∗ gilt:
Für jedes n ∈ N0 ist |w n | = n · |w |.
Wie beweist man das?
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
3 / 18
Induktive Definitionen kann man zu Rechnen benutzen
Definition
w0 = ε
für alle n ∈ N0 : w n+1 = w n · w
Was ist w 1 ?
w 1 = w 0+1 = w 0 · w = ε · w = w
Was ist w 2 ?
w 2 = w 1+1 = w 1 · w = w · w
Was ist w 3 ?
w 3 = w 2+1 = w 2 · w = (w · w ) · w
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
4 / 18
Das Lemma über Wortlängen — einfache Fälle
n = 0: Das ist einfach: |w 0 | = |ε | = 0 = 0 · |w |.
n = 1: Man kann ähnlich rechnen wie bei w 1 = w:
|w 1 | = |w 0+1 | = |w 0 · w |
= |w 0 | + |w |
= 0|w | + |w |
siehe Fall n = 0
= 1|w |
weil für n = 0 richtig auch für n = 1 beweisbar
n = 2: Wir gehen analog zu eben vor:
|w 2 | = |w 1+1 | = |w 1 · w |
= |w 1 | + |w |
= 1|w | + |w |
siehe Fall n = 1
= 2|w |
weil für n = 1 richtig auch für n = 2 beweisbar
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
5 / 18
Vollständige Induktion — die Grundlage
Wenn eine Menge M
nur Zahlen aus N0 enthält,
0 ∈ M ist und
für jedes n ∈ N0 gilt: wenn n ∈ M, dann n + 1 ∈ M
dann ist M = N0 .
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
6 / 18
Vollständige Induktion — das Prinzip
es sei für jedes n ∈ N0 eine Aussage An festgelegt
Ziel: „Für jedes n ∈ N0 ist An wahr.“
zeige N0 = {n | An ist wahr}
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
7 / 18
Vollständige Induktion — das Prinzip
es sei für jedes n ∈ N0 eine Aussage An festgelegt
Ziel: „Für jedes n ∈ N0 ist An wahr.“
zeige N0 = {n | An ist wahr}
Grundlage:
wenn gilt
A0
für jedes n ∈ N0 : wenn An , dann An+1
dann gilt auch für jedes n ∈ N0 : An
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
7 / 18
Vollständige Induktion — das Prinzip
es sei für jedes n ∈ N0 eine Aussage An festgelegt
Ziel: „Für jedes n ∈ N0 ist An wahr.“
zeige N0 = {n | An ist wahr}
Grundlage:
wenn gilt
A0
für jedes n ∈ N0 : wenn An , dann An+1
dann gilt auch für jedes n ∈ N0 : An
Beweisstruktur im einfachsten Fall:
Induktionsanfang: zeige: A0 gilt.
Induktionsschritt: zeige
für jedes n ∈ N0 : wenn An , dann An+1
An Induktionsvoraussetzung
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
7 / 18
Vollständige Induktion — Beweis des Lemmas
Idee:
es sei M ⊆ N0 die Menge aller n ∈ N0 mit |w n | = n|w |
zeige: M = N0
An : die Aussage |w n | = n|w |
Induktionsanfang n = 0: Zu zeigen: |w 0 | = 0 · |w |.
|w 0 | = |ε |
nach Defintion von w 0
= 0 = 0 · |w | .
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
8 / 18
Vollständige Induktion — Beweis des Lemmas
Idee:
es sei M ⊆ N0 die Menge aller n ∈ N0 mit |w n | = n|w |
zeige: M = N0
An : die Aussage |w n | = n|w |
Induktionsanfang n = 0: Zu zeigen: |w 0 | = 0 · |w |.
|w 0 | = |ε |
nach Defintion von w 0
= 0 = 0 · |w | .
Induktionsschritt n → n + 1:
Zeige: für jedes n gilt:
wenn |w n | = n|w |, dann |w n+1 | = (n + 1)|w |.
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
8 / 18
Vollständige Induktion — Beweis des Lemmas
es sei n ∈ N0
zeige: wenn An wahr, dann An+1 wahr
Induktionsvoraussetzung: An ist wahr, also |w n | = n|w |.
zu zeigen: An+1 ist wahr, also |w n+1 | = (n + 1)|w |.
|w n+1 | = |w n · w |
= |w n | + |w |
= n|w | + |w |
nach Ind.vor.
= (n + 1)|w |
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
9 / 18
Wo sind wir?
Vollständige Induktion
Varianten vollständiger Induktion
Induktive Definitionen
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
10 / 18
Vollständige Induktion: Varianten
Induktionsanfang an „späterer“ Stelle, z. B.
für jedes n ≥ 1 : An
Induktionsanfang: zeige A1
Induktionsschritt: zeige, dass für jedes n ∈ N+ gilt:
wenn An wahr, dann auch An+1
im letzten Schritt Benutzung nicht nur von An , sondern
auch „frühere“ Aussagen
z. B. An−1 (falls n groß genug!?)
z. B. alle Aussagen A0 , A1 , . . . , An
manchmal „mehrere Induktionsanfänge“, z. B.
Induktionsanfang: zeige A0 , A1 und A2 sind wahr
diese Varianten kann man in das Originalschema pressen
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
11 / 18
Verallgemeinerung vollständiger Induktion —
mit Rückgriff auf viele frühere Formeln
für jedes n ∈ N0 sei Bn eine Aussage
wollen beweisen: für jedes n ∈ N0 ist B(n) wahr
definiere Aussage An so:
„Für jedes i ∈ N0 mit i ≤ n ist Bi wahr.“
beweise: für jedes n ∈ N0 ist An wahr
das reicht, denn aus An folgt Bn
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
12 / 18
Eine Verallgemeinerung vollständiger Induktion
Aussagen Bn für n ∈ N0
An : „Für jedes i ∈ N0 mit i ≤ n gilt Bi .“
Induktionsbeweis für „Für jedes n ∈ N0 ist An wahr.“
Induktionsanfang n = 0: müssen zeigen:
A0 , also „für jedes i ∈ N0 mit i ≤ 0 gilt Bi , also B0 .
Induktionsschritt n ; n + 1: es sei n ∈ N0 so, dass die
Induktionsvoraussetzung gilt:
An , also „für jedes i ∈ N0 mit i ≤ n gilt Bi “
zeige An+1 , also „für jedes i ∈ N0 mit i ≤ n + 1 gilt Bi “
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
13 / 18
Eine Verallgemeinerung vollständiger Induktion
Aussagen Bn für n ∈ N0
An : „Für jedes i ∈ N0 mit i ≤ n gilt Bi .“
Induktionsschritt n ; n + 1: es sei n ∈ N0 so, dass die
Induktionsvoraussetzung gilt:
An , also „Für jedes i ∈ N0 mit i ≤ n gilt Bi .“
zeige An+1 , also „Für jedes i ∈ N0 mit i ≤ n + 1 gilt Bi “.’
An+1 ist: „Für jedes i ∈ N0 mit i ≤ n gilt Bi und es gilt Bn+1 .“
– „Für jedes i ∈ N0 mit i ≤ n gilt Bi .“: gilt nach IV
– Bn+1 : hier muss man was tun, darf aber IV benutzen:
„Für jedes i ∈ N0 mit i ≤ n gilt Bi .“
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
14 / 18
Wo sind wir?
Vollständige Induktion
Varianten vollständiger Induktion
Induktive Definitionen
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
15 / 18
Beispiel — noch mal Potenzen von Wörtern
Definition:
w0 = ε
für jedes n ∈ N0 : w n+1 = w n · w
sinnvolle Festlegung?
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
16 / 18
Beispiel — noch mal Potenzen von Wörtern
Definition:
w0 = ε
für jedes n ∈ N0 : w n+1 = w n · w
sinnvolle Festlegung?
wird für jedes n etwas festgelegt, was w n sein könnte?
ist das immer eindeutig?
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
16 / 18
Beispiel — noch mal Potenzen von Wörtern
Definition:
w0 = ε
für jedes n ∈ N0 : w n+1 = w n · w
sinnvolle Festlegung?
wird für jedes n etwas festgelegt, was w n sein könnte?
ist das immer eindeutig?
vollständige Induktion:
für jedes n ∈ N0 wird w n festgelegt
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
16 / 18
Ackermann-Funktion — auch induktiv definiert
die Ackermann-Funktion A : N0 × N0 → N0
ist so definiert (Fassung von Rósza Péter)
für jedes y ∈ N0 :
für jedes x ∈ N0 :
für jedes x ∈ N0 , y ∈ N0 :
GBI — Grundbegriffe der Informatik
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
KIT, Institut für Theoretische Informatik
17 / 18
Ackermann-Funktion — auch induktiv definiert
die Ackermann-Funktion A : N0 × N0 → N0
ist so definiert (Fassung von Rósza Péter)
für jedes y ∈ N0 :
für jedes x ∈ N0 :
für jedes x ∈ N0 , y ∈ N0 :
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
Vorsicht beim Rechnen!
A(2, 2) = A(1, A(2, 1)) = A(1, A(1, A(2, 0)))
= A(1, A(1, A(1, 1))) = A(1, A(1, A(0, A(1, 0))))
= A(1, A(1, A(0, A(0, 1)))) = A(1, A(1, A(0, 2)))
= A(1, A(1, 3)) = A(1, A(0, A(1, 2)))
= A(1, A(0, A(0, A(1, 1)))) = A(1, A(0, A(0, A(0, A(1, 0)))))
= A(1, A(0, A(0, A(0, A(0, 1))))) = A(1, A(0, A(0, A(0, 2))))
= A(1, A(0, A(0, 3))) = A(1, A(0, 4)) = A(1, 5) = · · ·
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
17 / 18
Ackermann-Funktion — alles definiert?
A : N0 × N0 → N0
für jedes y ∈ N0 :
für jedes x ∈ N0 :
für jedes x ∈ N0 , y ∈ N0 :
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
A(x, y) für jedes x ∈ N0 und jedes y ∈ N0 definiert?
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
18 / 18
Ackermann-Funktion — alles definiert?
A : N0 × N0 → N0
für jedes y ∈ N0 :
für jedes x ∈ N0 :
für jedes x ∈ N0 , y ∈ N0 :
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
A(x, y) für jedes x ∈ N0 und jedes y ∈ N0 definiert?
x =0
x =1
x =2
..
.
GBI — Grundbegriffe der Informatik
y=0
A(0, 0)
A(1, 0)
A(2, 0)
..
.
y=1
A(0, 1)
A(1, 1)
A(2, 1)
..
.
y=2
A(0, 2)
A(1, 2)
A(2, 2)
..
.
y=3
A(0, 3)
A(1, 3)
A(2, 3)
..
.
y=4
A(0, 4)
A(1, 4)
A(2, 4)
..
.
···
···
···
KIT, Institut für Theoretische Informatik
18 / 18
Ackermann-Funktion — alles definiert?
A : N0 × N0 → N0
für jedes y ∈ N0 :
für jedes x ∈ N0 :
für jedes x ∈ N0 , y ∈ N0 :
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
A(x, y) für jedes x ∈ N0 und jedes y ∈ N0 definiert?
zwei Induktionsbeweise „ineinander geschachtelt“
„außen“ Induktion über x
„innen“ Induktion über y zweimal
im Induktionsanfang für x = 0
im Induktionsschritt für x ; x + 1
GBI — Grundbegriffe der Informatik
KIT, Institut für Theoretische Informatik
18 / 18

Download Report