' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": 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  3  f(3 - 1) 
3  f(2)  3  (if 2 then 2  f(2 - 1) else 1)  3  (2  f(2 - 1)) 
3  (2  f(1))  3  (2  (if 1 then 1  f(1 - 1) else 1))  3(2(1 f(1-1))) 
3(2(1f(0)))  3(2(1(if 0 then 0  f(0-1) else 1)))  3  (2  (1  1)) 
3  (2  1)  3  2  6
' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": 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  3  f(3 - 1) 
3  f(2)  3  (if 2 then 2  f(2 - 1) else 1)  3  (2  f(2 - 1)) 
3  (2  f(1))  3  (2  (if 1 then 1  f(1 - 1) else 1))  3(2(1 f(1-1))) 
3(2(1f(0)))  3(2(1(if 0 then 0  f(0-1) else 1)))  3  (2  (1  1)) 
3  (2  1)  3  2  6
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 IB000 "Úv. Inf.": 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 .
Věta. Pro každé m, n  N platí g(m, n) 
z, kde z  m  n.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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 .
Věta. Pro každé m, n  N platí g(m, n) 
z, kde z  m  n.
Důkaz: Budiž n  N libovolné ale pro další úvahy pevné. Dokážeme, že pro každé
m  N platí g(m, n) 
z, kde z  m  n, indukcí vzhledem k m.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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 .
Věta. Pro každé m, n  N platí g(m, n) 
z, kde z  m  n.
Důkaz: Budiž n  N libovolné ale pro další úvahy pevné. Dokážeme, že pro každé
m  N platí g(m, n) 
z, kde z  m  n, indukcí vzhledem k m.
ˇ Báze m = 0. Platí g(0, n)  if 0 then n + g(0 - 1, n) else 0  0.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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 .
Věta. Pro každé m, n  N platí g(m, n) 
z, kde z  m  n.
Důkaz: Budiž n  N libovolné ale pro další úvahy pevné. Dokážeme, že pro každé
m  N platí g(m, n) 
z, kde z  m  n, indukcí vzhledem k m.
ˇ Báze m = 0. Platí g(0, n)  if 0 then n + g(0 - 1, n) else 0  0.
ˇ Indukční krok. Nechť m + 1  k. Pak
g(k, n)  if k then n + g(k - 1, n) else 0  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 IB000 "Úv. Inf.": 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) else 0 .
Věta. Pro každé m, n  N platí g(m, n) 
0.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": 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) else 0 .
Věta. Pro každé m, n  N platí g(m, n) 
0.
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ší.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": 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) else 0 .
Věta. Pro každé m, n  N platí g(m, n) 
0.
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ší. 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é i  N platí, že jestliže i = m + n pro kterákoliv m, n  N,
pak g(m, n) 
0.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": 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) else 0 .
Věta. Pro každé m, n  N platí g(m, n) 
0.
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ší. 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é i  N platí, že jestliže i = m + n pro kterákoliv m, n  N,
pak g(m, n) 
0.
Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n  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) else 0  0 .
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 0  0 .
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 0  0 .
ˇ 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) else 0 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0  0 .
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 0  0 .
ˇ 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) else 0 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0  0 .
ˇ 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) else 0 
 if n then g(m - 1, n) + g(m, n - 1) else 0  g(m - 1, n) + g(m, n - 1) .
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 0  0 .
ˇ 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) else 0 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 0  0 .
ˇ 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) else 0 
 if n then g(m - 1, n) + g(m, n - 1) else 0  g(m - 1, n) + g(m, n - 1) .
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 IB000 "Úv. Inf.": 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) else 1 .
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": 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) else 1 .
Věta. Pro každé m, n  Nplatí g(m, n)
k, kde k = m+n
m (kombinační číslo).
Toto tvrzení opět budeme dokazovat indukcí vzhledem k i = m + n.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": 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) else 1 .
Věta. Pro každé m, n  Nplatí g(m, n)
k, kde k = m+n
m (kombinační číslo).
Toto tvrzení opět budeme dokazovat indukcí vzhledem k i = m + n.
Vzpoměňte si nejprve na známý Pascalův trojúhelník kombinačních čísel, který je defi-
novaný 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 para-
metrů a, b.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": 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) else 1 .
Věta. Pro každé m, n  Nplatí g(m, n)
k, kde k = m+n
m (kombinační číslo).
Toto tvrzení opět budeme dokazovat indukcí vzhledem k i = m + n.
Vzpoměňte si nejprve na známý Pascalův trojúhelník kombinačních čísel, který je defi-
novaný 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 para-
metrů a, b.
Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n  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) else 1  1 .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 1  1 .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 1  1 .
ˇ 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) else 1 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 1  1 .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 1  1 .
ˇ 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) else 1 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 1  1 .
ˇ 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) else 1 
 if n then g(m - 1, n) + g(m, n - 1) else 1  g(m - 1, n) + g(m, n - 1) .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 1  1 .
ˇ 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) else 1 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 1  1 .
ˇ 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) else 1 
 if n then g(m - 1, n) + g(m, n - 1) else 1  g(m - 1, n) + g(m, n - 1) .
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 .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i+1 = m+n, kde m, n  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) else 1  1 .
ˇ 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) else 1 
 if 0 then g(m - 1, 0) + g(m, 0 - 1) else 1  1 .
ˇ 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) else 1 
 if n then g(m - 1, n) + g(m, n - 1) else 1  g(m - 1, n) + g(m, n - 1) .
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 . Př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 IB000 "Úv. Inf.": 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
h(x) = if x then f(x - 1) + h(x - 1) else 1
Věta. Pro každé n  N platí f(n)
m, kde m = 2n
.
Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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
h(x) = if x then f(x - 1) + h(x - 1) else 1
Věta. Pro každé n  N platí f(n)
m, kde m = 2n
.
Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n. Řešením je přefor-
mulování dokazovaného tvrzení do silnější podoby, kterou již indukcí dokázat lze:
Věta. Pro každé n  N platí f(n) 
m a h(n) 
m, kde m = 2n
.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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
h(x) = if x then f(x - 1) + h(x - 1) else 1
Věta. Pro každé n  N platí f(n)
m, kde m = 2n
.
Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n. Řešením je přefor-
mulování dokazovaného tvrzení do silnější podoby, kterou již indukcí dokázat lze:
Věta. Pro každé n  N platí f(n) 
m a h(n) 
m, kde m = 2n
.
Důkaz, již poměrně snadno indukcí vzhledem k n:
ˇ Báze n = 0. Platí
f(0)  if 0 then h(0) else 1  1,
h(0)  if 0 then f(0 - 1) + h(0 - 1) else 1  1.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Důkazové postupy
ˇ Indukční krok: Nechť n + 1  k, pak platí
f(k)  if k then h(k) else 1  h(k) 
 if k then f(k-1)+h(k-1) else 1  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
.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Důkazové postupy
ˇ Indukční krok: Nechť n + 1  k, pak platí
f(k)  if k then h(k) else 1  h(k) 
 if k then f(k-1)+h(k-1) else 1  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
. Zároveň také
(naše ,,zesílení ) platí i h(w) 
m, a proto
f(w) + h(w) 
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.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Důkazové postupy
ˇ Indukční krok: Nechť n + 1  k, pak platí
f(k)  if k then h(k) else 1  h(k) 
 if k then f(k-1)+h(k-1) else 1  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
. Zároveň také
(naše ,,zesílení ) platí i h(w) 
m, a proto
f(w) + h(w) 
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.
Podobně je třeba ještě dokončit druhou část tvrzení.
h(k)  if k then f(k - 1) + h(k - 1) else 1 
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 IB000 "Úv. Inf.": 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) .
Pak pro každé nenulové m, n  N platí g(m, n)  z, kde z je největší
společný dělitel čísel m, n.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": 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) .
Pak pro každé nenulové m, n  N platí g(m, n)  z, kde z je největší
společný dělitel čísel m, n.
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  N, m, n > 0, pak z je největší společný dělitel čísel m, n.)
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": 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) .
Pak pro každé nenulové m, n  N platí g(m, n)  z, kde z je největší
společný dělitel čísel m, n.
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  N, m, n > 0, pak z je největší společný dělitel čísel m, n.)
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) 
 if 0 then g(1 - 1, 1) else (if 1 - 1 then g(1, 1 - 1) else 1) 
 if 1 - 1 then g(1, 1 - 1) else 1  if 0 then g(1, 1 - 1) else 1  1 .
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, n  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if 0 then g(m, n - m) else m  m .
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, n  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if 0 then g(m, n - m) else m  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if z then g(m, n - m) else m 
g(m, n - m)  g(m, k) ,
kde k  n - m.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, n  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if 0 then g(m, n - m) else m  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if z then g(m, n - m) else m 
g(m, n - m)  g(m, k) ,
kde k  n - m. Platí 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.
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Důkazové postupy
Indukční krok. Nechť i + 1 = m + n kde m, n  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if 0 then g(m, n - m) else m  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)
if 0 then g(m - n, n) else (if n - m then g(m, n - m) else m) 
if n - m then g(m, n - m) else m  if z then g(m, n - m) else m 
g(m, n - m)  g(m, k) ,
kde k  n - m. Platí 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.
 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 IB000 "Úv. Inf.": 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
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": 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
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 IB000 "Úv. Inf.": 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:
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": 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:
Algoritmus . Inkrementace.
k  počet číslic m;
p  1;
for i  0, 1, . . . , k - 1, k do
ci  (ci+p) mod 10;
if ci = 0 then p  0;
done
Zapišme tento kód formální deklarací našeho jazyka.
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": 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:
Algoritmus . Inkrementace.
k  počet číslic m;
p  1;
for i  0, 1, . . . , k - 1, k do
ci  (ci+p) mod 10;
if ci = 0 then p  0;
done
Zapišme tento kód formální deklarací našeho jazyka.
Řešení:
ˇ Jelikož nyní nejsou k dispozici proměnné typu pole, ,,pomůžeme si funkčním
zápisem číslic g(i) a g (i) místo ci, ci.
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": 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:
Algoritmus . Inkrementace.
k  počet číslic m;
p  1;
for i  0, 1, . . . , k - 1, k do
ci  (ci+p) mod 10;
if ci = 0 then p  0;
done
Zapišme tento kód formální deklarací našeho jazyka.
Řešení:
ˇ Jelikož nyní nejsou k dispozici proměnné typu pole, ,,pomůžeme si funkčním
zápisem číslic g(i) a g (i) místo ci, ci.
ˇ Cyklus for 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.
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": 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:
Algoritmus . Inkrementace.
k  počet číslic m;
p  1;
for i  0, 1, . . . , k - 1, k do
ci  (ci+p) mod 10;
if ci = 0 then p  0;
done
Zapišme tento kód formální deklarací našeho jazyka.
Řešení:
ˇ Jelikož nyní nejsou k dispozici proměnné typu pole, ,,pomůžeme si funkčním
zápisem číslic g(i) a g (i) místo ci, ci.
ˇ Cyklus for 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.
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Důkazové postupy
Celá formální deklarace  bude vypadat například následovně:
g (i) = g(i) + p(i) mod 10
p(i) = if i then if g (i - 1) then 0 else 1 else 1
g(0) = c0, g(1) = c1, . . . g(k - 1) = ck-1
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Důkazové postupy
Celá formální deklarace  bude vypadat například následovně:
g (i) = g(i) + p(i) mod 10
p(i) = if i then if g (i - 1) then 0 else 1 else 1
g(0) = c0, g(1) = c1, . . . g(k - 1) = ck-1
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č to tak je zapsáno?)
Věta. Pro každé i  N platí, že g (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.
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Důkazové postupy
Celá formální deklarace  bude vypadat například následovně:
g (i) = g(i) + p(i) mod 10
p(i) = if i then if g (i - 1) then 0 else 1 else 1
g(0) = c0, g(1) = c1, . . . g(k - 1) = ck-1
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č to tak je zapsáno?)
Věta. Pro každé i  N platí, že g (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.
Dokažte si tvrzení sami za domácí úkol (diskutujte 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 ).
Pochopitelně je třeba pro úplnou správnost řešení ještě rozepsat operaci ,,modulo
pomocí povolených aritmetických operací, což si také za úkol vyzkoušejte. 2