Petr Hliněný, FI MU Brno 1 FI: IB000: Důkazové postupy
10 Důkazové postupy pro algoritmy10 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 důkazům vybraných algoritmů. Dá se říci, že tato lekce je ,,vrcholem v
naší snaze o matematické dokazování algoritmů v informatice.
f(3)  if 3 then 3  f(3 - 1) else 1 fi  3  f(3 - 1) 
3  f(2)  3  (if 2 then 2  f(2 - 1) else 1 fi)  3  (2  f(2 - 1)) 
3  (2  f(1))  3  (2  (if 1 then 1  f(1 - 1) else 1 fi))  3(2(1 f(1-1))) 
3(2(1f(0)))  3(2(1(if 0 then 0  f(0-1) else 1 fi)))  3  (2  (1  1)) 
3  (2  1)  3  2  6
2
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ý, FI MU Brno 2 FI: IB000: Důkazové postupy
10.1 Technika ,,fixace parametru10.1 Technika ,,fixace parametru
Příklad 10.1. Uvažme deklaraci  obsahující pouze rovnici
g(x, y) = if x then y + g(x - 1, y) else 0 fi .
Věta. Pro každé m, n   platí g(m, n) 
z, kde z  m  n.2
Důkaz: Budiž n   libovolné ale pro další úvahy pevné. Dokážeme, že pro každé
m   platí g(m, n) 
z, kde z  m  n, indukcí vzhledem k m.2
* Báze m = 0. Platí g(0, n)  if 0 then n + g(0 - 1, n) else 0 fi  0.2
* Indukční 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. Dále
n + g(w, n) 
n + u  v, kde v  n + (m  n) = (m + 1)  n = k  n, a tím
jsme dohromady hotovi s důkazem g(k, n) 
v.
2
Petr Hliněný, FI MU Brno 3 FI: IB000: Důkazové postupy
10.2 Technika ,,indukce k součtu parametrů10.2 Technika ,,indukce k součtu parametrů
Příklad 10.2. Uvažme deklaraci  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   platí g(m, n) 
0.2
Tvrzení této věty přímo nelze dokázat indukcí vzhledem k m, ani indukcí vzhledem
k n, neboť u žádného z m, n nemáme zaručeno, že se vždy zmenší. 2Dů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é i   platí, že jestliže i = m + n pro kterákoliv m, n  ,
pak g(m, n) 
0. 2
Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, 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 4 FI: IB000: Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, 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)  if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 0 fi) else 0 fi  0 .2
* 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 .2
* 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) .2
Podle I.P. platí g(m - 1, n) 
0 a současně 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 důkazem matematickou indukcí hotovi. 2
Petr Hliněný, FI MU Brno 5 FI: IB000: Důkazové postupy
Zajímavější verze
Příklad 10.3. Uvažme deklaraci  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 .2
Věta. Pro každé m, n   platí g(m, n) 
k, kde k = m+n
m (kombinační
číslo).
Toto tvrzení opět budeme dokazovat indukcí vzhledem k i = m + n.2
Vzpoměňte si nejprve na známý Pascalův trojúhelník kombinačních čísel, který je definovaný
rekurentním vztahem
a + 1
b + 1
=
a
b + 1
+
a
b
.
Nepřipomíná to trochu naši deklaraci? Je však třeba správně ,,nastavit význam parametrů
a, b. 2
Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n  , neboli
m = n = 0. Dokazujeme tedy, že g(0, 0) 
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 6 FI: IB000: Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  . Opět rozlišíme stejné tři možnosti:
* Pro m = 0 platí
g(0, n)  if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 1 fi) else 1 fi  1 .2
* Pro m > 0, n = 0 platí
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 .2
* 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) .2
Podle I.P. platí g(m - 1, n) 
k1, kde k1  m+n-1
m-1 , a současně g(m, n -
1) 
k2, kde k2  m+n-1
m . 2Přitom z Pascalova trojúhelníka plyne
m + n - 1
m - 1
+
m + n - 1
m
=
m + n - 1 + 1
m
=
m + n
m
,
a proto
g(m - 1, n) + g(m, n - 1) 
k1 + k2 
k 
m + n
m
.
2
Petr Hliněný, FI MU Brno 7 FI: IB000: Důkazové postupy
10.3 Technika ,,zesílení dokazovaného tvrzení10.3 Technika ,,zesílení dokazovaného tvrzení
Příklad 10.4. Uvažme deklaraci  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   platí f(n) 
m, kde m = 2n
.
Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n. 2Ř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   platí f(n) 
m a h(n) 
m, kde m = 2n
. 2
Důkaz, již poměrně snadno indukcí vzhledem k n:
* Báze n = 0. Platí
f(0)  if 0 then h(0) else 1 fi  1,
h(0)  if 0 then f(0 - 1) + h(0 - 1) else 1 fi  1.
Petr Hliněný, FI MU Brno 8 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
. 2Zároveň také
(naše ,,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í část našeho tvrzení platí i pro n + 1  k. 2
Podobně je třeba ještě dokončit druhou část tvrzení.
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
, a také
h(w) 
m, a proto
f(w) + h(w) 
m + m  q ,
kde q = m + m = 2  2n
= 2n+1
= 2k
. Proto h(k)  q a i druhá část našeho
tvrzení platí pro n + 1  k.
2
Petr Hliněný, FI MU Brno 9 FI: IB000: Důkazové postupy
10.4 Dva ,,klasické algoritmy10.4 Dva ,,klasické algoritmy
Euklidův algoritmus
Věta 10.5. Uvažme deklaraci  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   platí g(m, n)  z, kde z je největší
společný dělitel čísel m, n.2
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  , m, n > 0, pak z je největší společný dělitel čísel m, n.) 2
V bázi pro i = 2 je m, n = 1 a platí
g(1, 1)  if 1 - 1 then g(1 - 1, 1) else (if 1 - 1 then g(1, 1 - 1) else 1 fi) fi 
 if 0 then g(1 - 1, 1) else (if 1 - 1 then g(1, 1 - 1) else 1 fi) fi 
 if 1 - 1 then g(1, 1 - 1) else 1 fi  if 0 then g(1, 1 - 1) else 1 fi  1 .
Petr Hliněný, FI MU Brno 10 FI: IB000: Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, 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 .2
* 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. 2Platí m+k = m+(n-m) = n  i, takže podle I.P. také
platí g(m, k)  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 m a n.
 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.2
 Buď d nějaký společný dělitel čísel m a n. 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 11 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 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 m a n.
2
2
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 = 0?
Co v takových případech selže při současném zápise?
Petr Hliněný, FI MU Brno 12 FI: IB000: Důkazové postupy
Inkrementace dekadického zápisu
Příklad 10.6. Mějme přirozené číslo m dekadicky zapsané pomocí číslic
(ck-1ck-2 . . . c1c0)10 (kde zleva se implicitně vyplňují nuly). Pak dekadický zápis čísla
m
= m + 1 získáme takto: 2
Algoritmus . Inkrementace.
k  počet číslic m;
p  1;
foreach i  0, 1, . . . , k - 1, k do
c
i  (ci+p) mod 10;
if c
i = 0 then p  0;
done
Zapišme tento kód formální deklarací našeho jazyka. 2
Řešení:
* Jelikož nyní nejsou k dispozici proměnné typu pole, ,,pomůžeme si funkčním
zápisem číslic g(i) a h(i) místo ci, c
i. 2
* Cyklus foreach nahradíme rekurzí (běžný postup).
* Nakonec ,,trikově nahradíme proměnnou p, která vyjadřuje přenos do i-tého řádu,
zavedením nové funkce p(i), což výrazně zjednoduší zápis deklarace. 2
Petr Hliněný, FI MU Brno 13 FI: IB000: Důkazové postupy
Celá formální deklarace  bude vypadat zhruba následovně:
h(i) = g(i) + p(i) mod 10
p(i) = if i then if h(i - 1) then 0 else p(i - 1) fi else 1 fi
g(0) = c0, g(1) = c1, . . . g(k - 1) = ck-1 2
Všimněte si zvláštního posledního řádku, kde jsou rovnice deklarující konstantní hodnoty
jednotlivých číslic vstupního čísla m. (Proč je to takto zapsáno?) 2
Pochopitelně je potřeba pro úplnou správnost řešení ještě rozepsat operaci ,,modulo
pomocí povolených aritmetických operací, což za domácí úkol vyzkoušejte.
Věta. Pro každé i   platí, že h(i) udává dekadickou číslici i-tého řádu zprava
čísla m + 1, kde m má dekadický zápis po číslicích (ck-1 . . . c1c0)10. 2
Dokažte si tvrzení sami za domácí úkol (diskutujte spolu na IS).
Je potřeba použít matematickou indukci se zesíleným předpokladem, který se bude
vhodně vyjadřovat i o významu hodnoty p(i) (,,přenos ). 2