10   Důkazové postupy pro algoritmy
Na podkladu jednotlivých variant důkazů matematickou indukcí z Lekce 2 si ukážeme přehled formálních indukčních důkazových technik aplikovaných na vybrané algoritmy (v zápisech deklarativního jazyka). Dá se říci, že tato lekce je „vrcholem" v naší snaze o matematické dokazování algoritmů v informatice.
vou want proof? i'll sive vou proof)
C
Stručný přehled lekce
* Důkaz indukcí s „fixací parametrů".
* Důkaz indukcí vzhledem k součtu parametrů.
* Důkaz indukcí se „zesílením tvrzení".
Petr Hliněný, Fl MU Brno, 2011
1/13
Fl: IB000: Důkazové postupy
10.1   Technika „fixace parametru"
Příklad 10.1. Uvažme deklaraci A obsahující pouze rovnici
g(x, y) — if x then y + g(x — 1, y) else O fi .c
Věta. Pro každé m, n e N platí g(m, n) i—>■* z, kde z = m ■ n.c
Důkaz: Budiž n e N libovolné ale pro další úvahy pevné. Dokážeme, že pro každé m e N platí g(m, n) i—>■* z, kde z = m ■ n, indukcí vzhledem k m.c
• Báze m — 0. Platí g(0, n) i—>■ if 0 then n + g(0 — 1, n) else 0 fi i—y O.c
• Indukční krok. Necht m + 1 = k. Pak
g(k, n) i—>■ if k then n + g(k — 1, n) else 0 fi i—y n+g(k— l,n) i—>■ n+g(w, n).
kde je w = m. Podle I.P. platí g(w,n) i—>■* u pro u = m ■ n. Dále n + g(w, n) i—>■* n + u i—y v, kde v = n + (m ■ n) — (m + 1) • n — k ■ n, a tím jsme dohromady hotovi s důkazem g(k, n) i—>■* v.
C
Petr Hliněný, FI MU Brno, 2011
2/13
FI: IB000: Důkazové postupy
10.2   Technika „indukce k součtu parametrů"
Příklad 10.2. Uvažme deklaraci A obsahující pouze rovnici
g(x, y) — if x then (if y then g(x — 1, y) + g(x, y — 1) else 0 fi) else 0 fi.
Věta. Pro každé m, n e N platí g (m., n) i—>■* O.c
Tvrzení této věty přímo nelze dokázat indukcí vzhledem k to, ani indukcí vzhledem k n, neboť u žádného z m, n nemáme zaručeno, že se vždy zmenší. Důkaz lze ovšem postavit na faktu, že se vždy zmenší alespoň jeden z m, n, neboli se vždy zmenší součet m a n. To znamená, že výše uvedené tvrzení nejprve přeformulujeme do následující (matematicky ekvivalentní) podoby:
Věta. Pro každé z e N platí, že jestliže i — m + n pro kterákoliv m,n e N, pak g(m, n) i—>•* 0. c
Důkaz indukcí vzhledem k i: Báze i — 0 znamená, že 0 — m + n pro m, n e N, neboli m — n — 0. Dokazujeme tedy, že g(0, 0) i—>■* 0. Platí
g(0, 0) i—^ if 0 then (if 0 then g(0 -1,0)+ g(0, 0-1) else 0 fi) else 0 fi i->- 0 .
Petr Hliněný, FI MU Brno, 2011
3/13
FI: IB000: Důkazové postupy
Indukční krok. Nechť i + í — m + n, kde m, n e N. Nyní rozlišíme tři možnosti (z nichž první dvě jsou svým způsobem jen rozšířeními předchozí báze indukce):
• Pro m — 0 platí
g(0, n) i->- if 0 then (if n then g(0 - 1, n) + g(0, n    1) else 0 fi) else 0 fi i->- 0 .c
• Pro m > 0, n — 0 platí
g(m, 0) i—>■ if m then (if 0 then g(m —1,0)+ g(m, 0 — 1) else 0 fi) else 0 f i i—>■ i->- if 0 then g(m - 1,0) + g(m, 0 - 1) else 0 fi i-^- O.c
• Pro m > 0, n > 0 platí
g(m, n) i—>■ if m then (if n then g(m — 1, n) + g(m, n — 1) else 0 fi) else 0 f i i—>■ i—>- if n then g(m — 1, n) + g(m, n — 1) else 0 f i i—>- g(m—l, n)+g(m, n—1), Podle I.P. platí g(m— l,n) i—>■* 0 a současně g(m, n— 1) i—>■* 0, proto
g(m — 1, n) + g(m, n — 1) i—>•* 0 + g(m, n— 1) i—>•* 0 + 0 i—y 0. Tím jsme s důkazem matematickou indukcí hotovi. r-
Petr Hliněný, FI MU Brno, 2011
4/13
FI: IB000: Důkazové postupy
Zajímavější verze
Příklad 10.3. Uvažme deklaraci A obsahující pouze rovnici
g(x, y) — if x then (if y then g(x — 1, y) + g(x, y — 1) else 1 fi) else 1 fi.
Věta. Pro každé to, n e N platí g (m, n) i—>■* k, kde /j = C™^™) (kombinační číslo).
Toto tvrzení opět budeme dokazovat indukcí vzhledem k i — m + n.c
Vzpomeňte si nejprve na známý Pascalův trojúhelník kombinačních čísel, který je definovaný rekurentním vztahem
'a+ 1\ _ /  a  \ ía>
t+i) ~ [b+ij+ U
Nepřipomíná to trochu naši deklaraci? Je však třeba správně „nastavit" význam parametrů a, b. c
Důkaz indukcí vzhledem k i: Báze i — 0 znamená, že 0 — to + n pro to, n e N, neboli m — n — 0. Dokazujeme tedy, že g(0,0) i—>■* 1. Platí
g(0, 0) 1—^ if 0 then (if 0 then g(0 -1,0)+ g(0, 0-1) else 1 fi) else 1 fi       1.
Petr Hliněný, FI MU Brno, 2011
5/13
FI: IB000: Důkazové postupy
Indukční krok. Nechť i + 1 — m + n, kde m, n e N. Opět rozlišíme stejné tři možnosti:
• Pro m = 0 platí (™) = 1 a
g(0, n) i—>• if 0 then (if n then g(0 — 1, n) + g(0, n    1) else 1 fi) else 1 fi i—>- 1 .iz
• Pro m > 0, n = 0 platí (™) = 1 a g(m, 0) i—>■ if m then (if 0 then g(m —1,0)+ g(m, 0 — 1) else 1 fi) else 1 fi i—>■
i->- if 0 then g(m — 1, 0) + g(m, 0 — 1) else 1 fi i—>• 1 .c
• Pro m > 0, n > 0 platí g(m, n) i—>■ if m then (if n then g(m — 1, n) + g(m, n — 1) else 1 fi) else 1 fi i—>
i—>■ if n then g(m — 1, n) + g(m, n — 1) else 1 fi i—>■ g(m—l, n)+g(m, n—1),
Podle I.P platí g(m - l,n) i-)-* ki, kde kx = (mmit™)' a soucasně g(m, n—1) i—>■* k2, kde k2 = (m^_1). nPřitom z Pascalova trojúhelníka plyne
m + n —1\     /m + n — 1\      /(m + n— 1) + 1\      /m + n m — 1   y     \      m      J     \ m J     \ m
a proto
g(m - 1, n) + g (m, n - 1) i->-* ki + k2 >->■* k =
m
Z
Petr Hliněný, FI MU Brno, 2011
6/13
FI: IB000: Důkazové postupy
10.3   Technika „zesílení dokazovaného tvrzení"
Příklad 10.4. Uvažme deklaraci A obsahující tyto rovnice:
f(x) — if x then h(x) else 1 fi
h(x) — if x then f(x — 1) + h(x — 1) else 1 fi
Věta. Pro každé n e N platí /(n) i—>•* m, kde m — 2™.
Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n. Řešením je přeformulování dokazovaného tvrzení do silnější podoby, kterou již indukcí dokázat lze:
Věta. Pro každé n e N platí /(n) i—>•* m a h(n) t-t* m, kde m — 2™. c
Důkaz, již poměrně snadno indukcí vzhledem k n: • Báze n — 0. Platí
/(O) 1-4- if 0 then h(0) else 1 fi i->- 1, kde 2° = 1, h(0) ^ if 0 then /(O - 1) + h(0 - 1) else 1 fi i->- 1.
Petr Hliněný, FI MU Brno, 2011
7/13
FI: IB000: Důkazové postupy
• Indukční krok: Nechť n + 1 = k, pak platí
/(k) i->- if k then h(k) else 1 fi i—^ h(k) >->■
h->- ifkthen /(k - 1) +/i(k - 1) else 1 fi ^ /(k-l)+/i(k-l) ^ /(w)+/i(k-l);
kde w = k — 1 = n. Podle I.P. platí /(w) i—>■* m, kde m — 2™. nZároveň také (naše „zesílení") platí i h(w) i—>■* m, a proto
/(w) + /i(k—1) i—>■* m + /i(k—1) i—>•* m + /i(w) i—>•* m + m i—y q,
kde q — m + m — 2m — 2 ■ 2™ — 2n+1 — 2k. Proto tranzitivně /(k) i—>■ q a první část našeho tvrzení platí i pro n + 1 = k. c
Podobně je třeba ještě dokončit druhou část tvrzení.
h(k)       if k then /(k - 1) + h(k - 1) else 1 fi >->■
/(k-l) + Mk-l) ^* /(w) + /i(k - 1),
kde w = k — 1 — n. Podle I.P. platí /(w) i—>■* m, kde m — 2™, a také /i(w) i—>■* m, tudíž opět
/(w) + /i(k—1) i—>•* m + /i(k—1) i—>•* m + /i(w) i—>•* m + m i—y q,
kde í| = to + to = 2-2™ = 2™+1 — 2k. Proto /i(k) i—y q a i druhá část našeho tvrzení platí pro n + 1 = k.
Petr Hliněný, FI MU Brno, 2011
8/13
FI: IB000: Důkazové postupy
10.4 Dva dobře známé školní algoritmy Číslice dekadického zápisu
Příklad 10.5. Mějme přirozené číslo x. Jednotlivé číslice í-tého řádu jeho dekadického zápisu získáme deklarací
c(x, í) — if i then c(x -z- 10, i — 1) else x — 10 * (x -z- 10) fi. c
Dokažte:
Věta. Pro každá ra,íeN platí c(m, i) i—>■* s, kde s je číslice řádu i (počítáno od nultého zprava) v dekadickém zápise čísla m, nebo s = 0 v případě, že dekadický zápis čísla m má méně než i + 1 číslic.
Petr Hliněný, FI MU Brno, 2011
9/13
FI: IB000: Důkazové postupy
Věta. Pro každá ra,íeN platí c(m, i) i—>■* s, kde s je číslice řádu i (počítáno od nultého zprava) v dekadickém zápise čísla m, nebo s = 0 v případě, že dekadický zápis čísla m má méně než i + 1 číslic.
c
Důkaz: Použijeme techniku fixace parametru m při indukci podle i.
• Báze i = 0. Platí
c(m, 0) i->-* m    10 * (m ^ 10) i->-* t, kde t — m mod 10 .
V tomto výsledku mod znamená známou funkci modulo definovanou vztahem x — \x/y\ ■ y + (x mod y). Tudíž t je poslední číslicí dekadického zápisu m.
• Indukční krok: Nechť i + 1 = j, pak platí
c(m, j) i—>■ if j then c(m -z-10, j — 1) else m — 10 * (m    10) fi i—>■
i-^- c(m    10, j - 1)       c(p, w),
kde p = |_7tz./ 10j a w = j — 1 = i. Podle I.P. platí c(p, w) i—>* t a t je číslice z-tého řádu dekadického zápisu čísla p. Jelikož m — ÍOp + (m mod 10) a násobení deseti v dekadické soustavě znamená posun číslic v zápise „o jedno doleva", je t zároveň číslice i + 1 — j-tého řádu dekadického zápisu čísla m. To je přesně co bylo třeba dokázat.
Petr Hliněný,  FI MU Brno, 2011
10/13
FI: IB000: Důkazové postupy
Euklidův algoritmus
Věta 10.6. Uvažme deklaraci A obsahující pouze rovnici
g(x, y) = if x — y then g{x — y, y) else (if y — x then g(x, y — x) else x fi) fi.
Pak pro každé nenulové m, n G N platí g(m, n) i—>* z, kde z je nejvétší společný dělitel čísel m,n.c
Důkaz indukcí k i = m + n.
(Tj. dokazujeme následující tvrzení: Pro každé i > 2 platí, že jestliže i > m + n, kde m, n G N, m,n > 0, pak zje největší společný dělitel čísel m,n.) c V bázi pro i = 2 je m,n = 1 a platí
g(l, 1) 1-4- if 1    1 then #(1 - 1,1) else (if 1 - 1 then g(l, 1-1) else 1 fi) fi >->■ i->- if 0 then g(l - 1,1) else (if 1 - 1 then g(l, 1-1) else 1 fi) fi i->-i->- if 1    1 then g(l, 1-1) else 1 fi i->- if 0 then g(l, 1-1) else 1 fi i->- 1.
Petr Hliněný,  FI MU Brno, 2011
11/13
FI: IB000: Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, n G N. Probereme tři možnosti:
• m = n. Pak
g(m, n) i—>■ if m — n then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi i—> if 0 then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi i—> if n — m then g(m, n — m) else m fi i—>■ if 0 then g(m, n — m) else m fi i—>■ m .i
• m < n. Pak
g(m, n) i—>■ if m — n then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi i—> if 0 then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi i—> if n — m then g(m, n — m) else m fi i—>■ if z then g(m, n — m) else m fi i—>■ g(m, n — m) i—>■ g(m, k),
kde k = n — m. nPlatím + A: = m + {n — m) = n < i, takže podle I.P. také platí g(m, k) i—>* z, kde z je největší společný dělitel čísel m a n — m. Ověříme, že z je největší společný dělitel čísel man.
* Jelikož číslo z dělí čísla m a n — m, dělí i jejich součet (n — m) +m = n. Celkem z je společným dělitelem m a n.c
* Bud' d nějaký společný dělitel čísel man. Pak d dělí také rozdíl n — m. Tedy d je společný dělitel čísel m a n — m. Jelikož z je největší společný dělitel čísel m a n — m, nutně d dělí z a závěr platí.
Petr Hliněný,  FI MU Brno, 2011
12/13
FI: IB000: Důkazové postupy
• m > n. Pak
g(m,n) h^* p(m-n,n)       g(k,n).
kde k = m — n. Podle I.P. platí g (k, n) t—y* z, kde z je největší společný dělitel čísel m — n a n. Podobně jako výše ověříme, že z je také největší společný dělitel čísel man.
c
Poznámka: Jak byste výše uvedený zápis Euklidova algoritmu vylepšili, aby správně „počítal" největšího společného dělitele i v případech, že m — 0 nebo n — 01 Co v takových případech selže při současném zápise?
Petr Hliněný,  FI MU Brno, 2011
13/13
FI: IB000: Důkazové postupy