10   Důkazové postupy pro algoritmy
Nyní si ukážeme, jak formální deklarativní jazyk z Lekce 9 využít k formálně přesným induktivním dUkazUm vybraných algoritmU. Da se říci, že tato lekce je „vrcholem" v naSí snaze o matematicke dokazovaní algoritmU v informatice.
Stručný přehled lekce
* Důkaz indukcí s „fixací parametrů".
* Důkaz indukcí vzhledem k souCtu parametrů.
* Důkaz indukcí se „zesílením tvrzení".
etr Hliněný.  FI MU Brno
FI: IB000: Důkazově postupy
_
r.
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 0 fi .c
Veta. Pro každe m, n G N platí g(m, n) —* z, kde z = m • n.c
DUkaz: Budiž n G N libovolne ale pro dalSÍ uvahy pevne. Dokážeme, že pro každe m G N platí g(m, n) i—z, kde z = m • n, indukcí vžhledem k m.c
• Baže m = 0. Platí g(0, n) — if 0 then n + g(0 — 1, n) else 0 fi — 0.c
• IndukCnÍ krok. Nechť m +1 = k. Pak
g(k, n) — if k then n + g(k — 1, n) else 0 fi — n+g(k—1, n) — n+g(w, n),
kde je w = m. Podle I.P. platí g(w, n) —* u pro u = m • n. Dale n + g(w, n) —* n + u — v, kde v = n + (m • n) = (m +1) • n = k • n, a t ím jsme dohromady hotovi s dukažem g(k, n) —* v.
□
Petr Hliněný,  FI MU Brno
FI: IB000: Důkazové postupy
r.
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 .
Veta. Pro každe m, n G N platí g(m, n) —* 0.c
Tvrzení teto vety přímo nelže dokažat indukcí vzhledem k m, ani indukcí vzhledem k n, neboť u žadneho z m,n nemáme zaručeno, že se vždy zmenSí. DUkaz lze ovSem postavit na faktu, že se vždy zmenSí alespon jeden z m, n, neboli se vždy zmenSí souCet m a n. To znamena, že výse uvedene tvrzení nejprve přeformulujeme do na sleduj íc í (matematicky ekvivalentní) podoby:
Veta. Pro každe i G N plat í, že jestliže i = m + n pro kterakoliv m,n G N, pak g(m, n) i—0. c
Důkaz indukc í vzhledem k i: Baze i = 0 znamena, že 0 = m + n pro m, n G N, neboli m = n = 0. Dokazujeme tedy, že g(0, 0) —* 0. Plat í
g(0, 0) — if 0 then (if 0 then g(0 — 1, 0) + g(0, 0 — 1) else 0 fi) else 0 fi — 0 .
Petr Hliněný,  FI MU Brno
FI: IB000: Důkazové postupy
Indukční krok. Nechť i +1 = m + n, kde m, n G N. Nyní rozlišíme tři možnosti (z nichž první dve jsou svym zpUsobem jen rozšířeními předchozí baze indukce): • Pro m = 0 platí
g(0, n) — if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 0 fi) else 0 fi — 0 .c
• Pro m > 0, n = 0 platí
g(m, 0) — if m then (if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0 fi) else 0 fi -— if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0 fi — 0 .c
• Pro m > 0, n > 0 platí
g(m, n) — if m then (if n then g(m - 1, n) + g(m, n - 1) else 0 fi) else 0 fi -— if n then g(m - 1, n) + g(m, n - 1) else 0 fi — g(m-1, n)+g(m, n-1)c Podle I.P. platí g(m - 1, n) —* 0 a současne g(m, n - 1) —* 0, proto
g(m - 1, n) + g(m, n - 1) —* 0 + g(m, n - 1) —* 0 + 0 — 0 . Tím jsme s dUkazem matematickou indukcí hotovi. g
Petr Hliněný,  FI MU Brno__=I: IB000: Důkazové postupy
r.
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 .c
Věta. Pro kazde m, n G N platí g(m, n) —* k, kde k = ("""") (kombinační číslo).
Toto tvrzení opet budeme dokazovat indukcí vzhledem k i = m + n.c
Vzpomeňte si nejprve na znamý PascalUv trojúhelník kombinačních čísel, který je definovaný rekurentním vztahem
Nepňipomína to trochu nasi deklaraci? Je vsak treba spravne „nastavit" význam parametrU a, b. c
Důkaz indukcí vzhledem k i: Baze i = 0 znamena, ze 0 = m + n pro m, n G N, neboli m = n = 0. Dokazujeme tedý, ze g(0, 0) i—1. Platí
g(0, 0) — 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
FI: IB000: Důkazové postupy
Indukční krok. Necht i + 1 = m + n, kde m, n £ N. Opět rozlišíme stejné tři možnosti:
• Pro m = 0 platí (£) = 1 a
g(0, n) — if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 1 fi) else 1 fi — 1 .c
• Pro m > 0, n = 0 platí (m) = 1 a
g(m, 0) — if m then (if 0 then g(m — 1, 0) + g(m, 0 — 1) else 1 fi) else 1 fi — — if 0 then g(m — 1, 0) + g(m, 0 — 1) else 1 fi — 1 .c
• Pro m > 0, n > 0 plat í
g(m, n) — if m then (if n then g(m — 1, n) + g(m, n — 1) else 1 fi) else 1 fi — — if n then g(m — 1, n) + g(m, n — 1) else 1 fi — g(m—1, n)+g(m, n—1)c
Podle I.P. platí g(m — 1, n) —* k.i, kde k1 = (mmi+n), a současne g(m, n — 1) —* k2, kde k2 = (m+m_1 . cPřitom z Pascalova trojUhelníka plyne
'm + n — 1\     ím + n — 1\      /(m + n — 1) + 1\      ím + n m — 1 m m m
a proto
/ mm _|_ n
g(m — 1, n) + g(m, n — 1) —* ki + k2 —* k =
m □
Petr Hliněný.  FI MU Brno__:I: IB000: Důkazové postupy
r.
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žde n G N platí f (n) i—m, kde m = 2n.
Požadovane tvržen í bohužel nelže přímo dokažat indukcí podle n. nŘeSen ím je přeformulován í dokažovaneho tvržen í do silnejSí podoby, kterou již indukcí dokažat
Věta. Pro každé n G N plat í /(n) i—m a h(n) i—m, kde m = 2™. c
Důkaz, již pomerné snadno indukcí vžhledem k n: • Baže n = 0. Plat í
lže:
/(0) — if 0 then h(0) else 1 fi — 1, kde 20 = 1, h(o) — if 0 then /(o - 1) + h(0 - 1) else 1 fi — 1.
Petr Hliněný.  FI MU Brno
FI: IB000: Důkazové postupy
• Indukční krok: Nechť n +1 = k, pak platí
f (k) — if k then h(k) else 1 fi —
h(k) —
— if k then f (k - 1) + h(k - 1) else 1 fi — f (k-1)+h(k-1) — f (w)+h(k-1),
kde w = k - 1 = n. Podle I.P. platí f (w) —* m, kde m = 2n. nZaroven take (naSe „zesílení") platí i h(w) —* m, a proto
f (w) + h(k - 1) —* m + h(k - 1) —* m + h(w) —* m + m — q,
kde q = m + m = 2m = 2 • 2n = 2n+1 = 2k. Proto tranzitivně f (k) — q a první cast naSeho tvrzení platí i pro n +1 = k. c
Podobne je treba jeste dokončit druhou cast tvrzení.
kde w = k - 1 = n. Podle I.P. platí /(w) i—m, kde m = 2™, a také /i(w) —* m, tudíz opét
/(w) + h(k - 1) —* m + h(k - 1) —* m + h(w) —* m + m — q,
kde q = m + m = 2 • 2™ = 2n+1 = 2k. Proto h(k) — q a i druha cast našeho tvrzení platí pro n +1 = k.
3etr Hliněný.  FI MU Brno__FI: IB000: Důkazové postupy
h(k) — if k then f (k - 1) + h(k - 1) else 1 fi — f (k - 1) + h(k - 1) —* f (w) + h(k - 1),
10.4   Dva dobře známé školní algoritmy Číslice dekadického zápišu
Příklad 10.5. Mějme přirozené číslo x. Jednotlivé číslice i-tého řádu jeho dekadického zápisu získáme deklarací
c(x, i) = if i then c(x 4 10, i — 1) else x — 10 * (x 4 10) fi . c
DokaZte:
Véta. Pro každá m, i G N platí c(m, i) —* s, kde s je číslice řádu i (počítáno od nultého žprava) v dekadickem žápise čísla m, nebo s = 0 v případe, že dekadický žápis čísla m mí mene než i + 1 číslic.
Petr Hliněný.  FI MU Brno
FI: IB000: Důkazové postupy
Veta. Pro každa m, i G N platí c(m, i) —* s, kde s je číslice řídu i (počítíno od nulteho žprava) v dekadickem žapise čísla m, nebo s = 0 v případe, že dekadický žapis čísla m mí mene než i + 1 číslic.
Důkaz: Použijeme techniku fixace parametru m při indukci podle i.
• Baže i = 0. Platí
c(m, 0) —* m — 10 * (m 4 10) —* t, kde t = m mod 10 .
V tomto výsledku mod žnamení žnamou funkci modulo definovanou vžtahem x = [x/yj • y + (x mod y). Tudíž t je poslední číslicí dekadickeho žapisu m.
• Indukční krok: Necht i +1 = j, pak platí
c(m, j) — if j then c(m 4 10, j — 1) else m — 10 * (m 4 10) fi — — c(m 4 10, j — 1) —* c(p, w),
kde p = [m/10j a w = j — 1 = i. nPodle I.P. platí c(p, w) —* t a t je číslice i-teho radu dekadickeho žapisu čísla p. Jelikož m = 10p + (m mod 10) a nasobení deseti v dekadicke soustavě žnamena posun číslic v žapise „o jedno doleva", je t žaroven číslice i + 1 = j-teho řadu dekadickeho žapisu čísla m. To je presne co bý1° treba dokažat. g
Petr Hliněný.  FI MU Brno
FI: IB000: D ukazovýe postupy
Euklidův algoritmus
Veta 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 € N platí g(m, n) —* z, kde z je největsí společný dělitel čísel m, n.c
Důkaz indukcí k i = m + n.
(Tj. dokazujeme nasleduj ící tvrzen í: Pro kaZde i > 2 plat í, Ze jestliZe i > m + n, kde m, n € N, m, n > 0, pak z je nejvetsí společný delitel c ísel m, n.) c V bazi pro i = 2 je m, n = 1 a plat í
1) — if 1 - 1 then g(1 - 1,1) else (if 1 - 1 then       1 - 1) else 1 fi) fi —
— if 0 then g(1 - 1,1) else (if 1 - 1 then       1 - 1) else 1 fi) fi —
— if 1 - 1 then       1 - 1) else 1 fi — if 0 then       1 - 1) else 1 fi — 1.
Petr Hliněný.  FI MU Brno
FI: IB000: D ukazovýe postupy
Indukcn í krok. Necht: i + 1 = m + n kde m, n G N. Probereme tři možnosti:
• m = n. Pak
g(m, n) — if m — n then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi — if 0 then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi — if n — m then g(m, n — m) else m fi — if 0 then g(m, n — m) else m fi — m .
• m < n. Pak
g(m, n) — if m — n then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi — if 0 then g(m — n, n) else (if n — m then g(m, n — m) else m fi) fi — if n — m then g(m, n — m) else m fi — if z then g(m, n — m) else m fi —
g(m, n — m) — g(m, k),
kde k = n — m. Platí m + k = m + (n — m) = n < i, takže podle I.P. take plat í g(m, k) —* z, kde z je nejvetsí spolecny delitel c ísel m a n — m. Oveř íme, že z je nejvets í spolecny delitel c ísel m a n.
* Jelikož císlo z del ícísla m a n — m, del í i jejich soucet (n — m)+ m = n. Celkem z je spolecnym dělitelem m a n.c
* Bud' d nejaky spolecny delitel c ísel m a n. Pak d del í take rozd íl n — m. Tedy d je spolecny delitel c ísel m a n — m. Jelikož z je nejvetsí spolecny delitel c ísel m a n — m, nutne d del í z a zaver plat í.
s.__Petr Hliněný, FI MU Brno_12_FI: IB000: Důkazově postupy
m > n. Pak
g(m, n) — * g(m - n, n) — g(k, n).
kde k = m — n. Podle I.P. platí g(k, n) —* z, kde z je nejvetSí spolecny dělitel Čísel m — n a n. Podobně jako výše overíme, že z je take nejvetsí spolecny delitel Čísel m a n.
c
Poznámka: Jak byste výSe uvedený žapis Euklidova algoritmu vylepSili, aby spravne „počítal" nejvetsího spoleCneho delitele i v případech, že m = 0 nebo n = 0? Co v takových případech selže při současnem žapise?
Petr Hliněný.  FI MU Brno
FI: IB000: D ukazovýe postupy