10
D˚ ukazov´ e postupy pro algoritmy
Nyn´ı si uk´aˇzeme, jak form´aln´ı deklarativn´ı jazyk z Lekce 9 vyuˇz´ıt k form´alnˇe pˇresn´ym induktivn´ım d˚ ukaz˚ um vybran´ych algoritm˚ u. D´a se ˇr´ıci, ˇze tato lekce je vrcholem“ v ” naˇs´ı snaze o matematick´e dokazov´an´ı algoritm˚ u v informatice.
2
Struˇ cn´ y pˇrehled lekce * D˚ ukaz indukc´ı s fixac´ı parametr˚ u“. ” * D˚ ukaz indukc´ı vzhledem k souˇctu parametr˚ u. * D˚ ukaz indukc´ı se zes´ılen´ım tvrzen´ı“. ” Petr Hlinˇ en´ y, FI MU Brno
1
FI: IB000: D˚ ukazov´ e postupy
10.1
Technika fixace parametru“ ”
Pˇr´ıklad 10.1. Uvaˇzme deklaraci ∆ obsahuj´ıc´ı pouze rovnici g(x, y) = if x then y + g(x − 1, y) else 0 fi .2
Vˇ eta. Pro kaˇzd´e m, n ∈
N
N plat´ı g(m, n)
7→∗ z, kde z ≡ m · n.2
D˚ ukaz: Budiˇz n ∈ libovoln´e ale pro dalˇs´ı ´ uvahy pevn´e. Dok´aˇzeme, ˇze pro kaˇzd´e m ∈ plat´ı g(m, n) 7→∗ z, kde z ≡ m · n, indukc´ı vzhledem k m.2
N
• B´aze m = 0. Plat´ı g(0, n) 7→ if 0 then n + g(0 − 1, n) else 0 fi 7→ 0.2 • Indukˇcn´ı krok. Necht’ m + 1 ≡ k. Pak g(k, n) 7→ if k then n + g(k − 1, n) else 0 fi 7→ n+g(k−1, n) 7→ n+g(w, n) , kde je w ≡ m. Podle I.P. plat´ı g(w, n) 7→∗ u pro u ≡ m · n. D´ale n + g(w, n) 7→∗ n + u 7→ v, kde v ≡ n + (m · n) = (m + 1) · n = k · n, a t´ım jsme dohromady hotovi s d˚ ukazem g(k, n) 7→∗ v. 2
Petr Hlinˇ en´ y, FI MU Brno
2
FI: IB000: D˚ ukazov´ e postupy
10.2
Technika indukce k souˇ ctu parametr˚ u“ ”
Pˇr´ıklad 10.2. Uvaˇzme 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ˇ eta. Pro kaˇzd´e m, n ∈
N plat´ı g(m, n)
7→∗ 0.2
Tvrzen´ı t´eto vˇety pˇr´ımo nelze dok´azat indukc´ı vzhledem k m, ani indukc´ı vzhledem ukaz lze ovˇsem k n, nebot’ u ˇz´adn´eho z m, n nem´ame zaruˇceno, ˇze se vˇzdy zmenˇs´ı. 2D˚ postavit na faktu, ˇze se vˇzdy zmenˇs´ı alespoˇ n jeden z m, n, neboli se vˇzdy zmenˇs´ı souˇcet m a n. To znamen´a, ˇze v´yˇse uveden´e tvrzen´ı nejprve pˇreformulujeme do n´asleduj´ıc´ı (matematicky ekvivalentn´ı) podoby:
N
Vˇ eta. Pro kaˇzd´e i ∈ plat´ı, ˇze jestliˇze i = m + n pro kter´akoliv m, n ∈ pak g(m, n) 7→∗ 0. 2 D˚ ukaz indukc´ı vzhledem k i: B´aze i = 0 znamen´a, ˇze 0 = m + n pro m, n ∈ m = n = 0. Dokazujeme tedy, ˇze g(0, 0) 7→∗ 0. Plat´ı
N,
N, neboli
g(0, 0) 7→ if 0 then (if 0 then g(0 − 1, 0) + g(0, 0 − 1) else 0 fi) else 0 fi 7→ 0 . Petr Hlinˇ en´ y, FI MU Brno
3
FI: IB000: D˚ ukazov´ e postupy
N
Indukˇcn´ı krok. Necht’ i + 1 = m+ n, kde m, n ∈ . Nyn´ı rozliˇs´ıme tˇri moˇznosti (z nichˇz prvn´ı dvˇe jsou sv´ym zp˚ usobem jen rozˇs´ıˇren´ımi pˇredchoz´ı b´aze indukce): • Pro m = 0 plat´ı g(0, n) 7→ if 0 then (if n then g(0 − 1, n) + g(0, n − 1) else 0 fi) else 0 fi 7→ 0 .2 • Pro m > 0, n = 0 plat´ı g(m, 0) 7→ if m then (if 0 then g(m − 1, 0) + g(m, 0 − 1) else 0 fi) else 0 fi 7→ 7→ if 0 then g(m − 1, 0) + g(m, 0 − 1) else 0 fi 7→ 0 .2 • Pro m > 0, n > 0 plat´ı g(m, n) 7→ if m then (if n then g(m − 1, n) + g(m, n − 1) else 0 fi) else 0 fi 7→ 7→ if n then g(m − 1, n) + g(m, n − 1) else 0 fi 7→ g(m−1, n)+g(m, n−1)2. Podle I.P. plat´ı g(m − 1, n) 7→∗ 0 a souˇcasnˇe g(m, n − 1) 7→∗ 0, proto g(m − 1, n) + g(m, n − 1) 7→∗ 0 + g(m, n − 1) 7→∗ 0 + 0 7→ 0 .
T´ım jsme s d˚ ukazem matematickou indukc´ı hotovi. Petr Hlinˇ en´ y, FI MU Brno
4
2 FI: IB000: D˚ ukazov´ e postupy
Zaj´ımavˇ ejˇs´ı verze Pˇr´ıklad 10.3. Uvaˇzme 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ˇ eta. Pro kaˇzd´e m, n ∈ ˇc´ıslo).
N plat´ı g(m, n) 7→∗ k, kde k =
m+n m
(kombinaˇcn´ı
Toto tvrzen´ı opˇet budeme dokazovat indukc´ı vzhledem k i = m + n.2 Vzpomˇeˇ nte si nejprve na zn´am´y Pascal˚ uv troj´ uheln´ık kombinaˇcn´ıch ˇc´ısel, kter´y je definovan´y rekurentn´ım vztahem a+1 a a = + . b+1 b+1 b Nepˇripom´ın´a to trochu naˇsi deklaraci? Je vˇsak tˇreba spr´avnˇe nastavit“ v´yznam ” parametr˚ u a, b. 2 D˚ ukaz indukc´ı vzhledem k i: B´aze i = 0 znamen´a, ˇze 0 = m + n pro m, n ∈ m = n = 0. Dokazujeme tedy, ˇze g(0, 0) 7→∗ 1. Plat´ı
N, neboli
g(0, 0) 7→ if 0 then (if 0 then g(0 − 1, 0) + g(0, 0 − 1) else 1 fi) else 1 fi 7→ 1 . Petr Hlinˇ en´ y, FI MU Brno
5
FI: IB000: D˚ ukazov´ e postupy
Indukˇcn´ı krok. Necht’ i + 1 = m + n, kde m, n ∈ • Pro m = 0 plat´ı n0 = 1 a
N. Opˇet rozliˇs´ıme stejn´e tˇri moˇznosti:
g(0, n) 7→ if 0 then (if n then g(0 − 1, n) + g(0, n − 1) else 1 fi) else 1 fi 7→ 1 .2 • Pro m > 0, n = 0 plat´ı m m =1 a g(m, 0) 7→ if m then (if 0 then g(m − 1, 0) + g(m, 0 − 1) else 1 fi) else 1 fi 7→ 7→ if 0 then g(m − 1, 0) + g(m, 0 − 1) else 1 fi 7→ 1 .2 • Pro m > 0, n > 0 plat´ı g(m, n) 7→ if m then (if n then g(m − 1, n) + g(m, n − 1) else 1 fi) else 1 fi 7→ 7→ if n then g(m − 1, n) + g(m, n − 1) else 1 fi 7→ g(m−1, n)+g(m, n−1)2. Podle I.P. plat´ı g(m − 1, n) 7→∗ k1 , kde k1 ≡ m−1+n , a souˇcasnˇe m−1 m+n−1 ∗ g(m, n − 1) 7→ k2 , kde k2 ≡ . 2Pˇritom z Pascalova troj´uheln´ıka plyne m m+n−1 m+n−1 (m + n − 1) + 1 m+n + = = , m−1 m m m a proto m+n g(m − 1, n) + g(m, n − 1) 7→∗ k1 + k2 7→∗ k ≡ . m 2 Petr Hlinˇ en´ y, FI MU Brno
6
FI: IB000: D˚ ukazov´ e postupy
10.3
Technika zes´ılen´ı dokazovan´ eho tvrzen´ı“ ”
Pˇr´ıklad 10.4. Uvaˇzme 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ˇ eta. Pro kaˇzd´e n ∈
N plat´ı f (n) 7→∗ m, kde m = 2n.
ˇ sen´ım je Poˇzadovan´e tvrzen´ı bohuˇzel nelze pˇr´ımo dok´azat indukc´ı podle n. 2Reˇ pˇreformulov´an´ı dokazovan´eho tvrzen´ı do silnˇejˇs´ı podoby, kterou jiˇz indukc´ı dok´azat lze: Vˇ eta. Pro kaˇzd´e n ∈
N plat´ı f (n)
7→∗ m a h(n) 7→∗ m, kde m = 2n .
2
D˚ ukaz, jiˇz pomˇernˇe snadno indukc´ı vzhledem k n: • B´aze n = 0. Plat´ı f (0) 7→ if 0 then h(0) else 1 fi 7→ 1, kde 20 = 1, h(0) 7→ if 0 then f (0 − 1) + h(0 − 1) else 1 fi 7→ 1.
Petr Hlinˇ en´ y, FI MU Brno
7
FI: IB000: D˚ ukazov´ e postupy
• Indukˇcn´ı krok: Necht’ n + 1 ≡ k, pak plat´ı f (k) 7→ if k then h(k) else 1 fi 7→ h(k) 7→ 7→ if k then f (k − 1) + h(k − 1) else 1 fi 7→ f (k−1)+h(k−1) 7→ f (w)+h(k−1) , kde w ≡ k − 1 = n. Podle I.P. plat´ı f (w) 7→∗ m, kde m = 2n . 2Z´aroveˇn tak´e (naˇse zes´ılen´ı“) plat´ı i h(w) 7→∗ m, a proto ” f (w) + h(k − 1) 7→∗ m + h(k − 1) 7→∗ m + h(w) 7→∗ m + m 7→ q , kde q = m + m = 2m = 2 · 2n = 2n+1 = 2k . Proto tranzitivnˇe f (k) 7→ q a prvn´ı ˇc´ast naˇseho tvrzen´ı plat´ı i pro n + 1 ≡ k. 2 Podobnˇe je tˇreba jeˇstˇe dokonˇcit druhou ˇc´ast tvrzen´ı. h(k) 7→ if k then f (k − 1) + h(k − 1) else 1 fi 7→ f (k − 1) + h(k − 1) 7→∗ f (w) + h(k − 1) , kde w ≡ k − 1 = n. Podle I.P. plat´ı f (w) 7→∗ m, kde m = 2n , a tak´e h(w) 7→∗ m, tud´ıˇz opˇet f (w) + h(k − 1) 7→∗ m + h(k − 1) 7→∗ m + h(w) 7→∗ m + m 7→ q , kde q = m + m = 2 · 2n = 2n+1 = 2k . Proto h(k) 7→ q a i druh´a ˇc´ast naˇseho tvrzen´ı plat´ı pro n + 1 ≡ k. 2 Petr Hlinˇ en´ y, FI MU Brno
8
FI: IB000: D˚ ukazov´ e postupy
10.4
Dva dobˇre zn´ am´ e ˇskoln´ı algoritmy
ˇ ıslice dekadick´ C´ eho z´ apisu Pˇr´ıklad 10.5. Mˇejme pˇrirozen´e ˇc´ıslo x. Jednotliv´e ˇc´ıslice i-t´eho ˇr´adu jeho dekadick´eho z´apisu z´ısk´ame deklarac´ı c(x, i) = if i then c(x ÷ 10, i − 1) else x − 10 ∗ (x ÷ 10) fi .
2
Dokaˇzte:
N
Vˇ eta. Pro kaˇzd´a m, i ∈ plat´ı c(m, i) 7→∗ s, kde s je ˇc´ıslice ˇr´adu i (poˇc´ıt´ano od nult´eho zprava) v dekadick´em z´apise ˇc´ısla m, nebo s ≡ 0 v pˇr´ıpadˇe, ˇze dekadick´y z´apis ˇc´ısla m m´a m´enˇe neˇz i + 1 ˇc´ıslic.
Petr Hlinˇ en´ y, FI MU Brno
9
FI: IB000: D˚ ukazov´ e postupy
N
Vˇ eta. Pro kaˇzd´a m, i ∈ plat´ı c(m, i) 7→∗ s, kde s je ˇc´ıslice ˇr´adu i (poˇc´ıt´ano od nult´eho zprava) v dekadick´em z´apise ˇc´ısla m, nebo s ≡ 0 v pˇr´ıpadˇe, ˇze dekadick´y z´apis ˇc´ısla m m´a m´enˇe neˇz i + 1 ˇc´ıslic. 2
D˚ ukaz: Pouˇzijeme techniku fixace parametru m pˇri indukci podle i. • B´aze i = 0. Plat´ı c(m, 0) 7→∗ m − 10 ∗ (m ÷ 10) 7→∗ t, kde t = m mod 10 . V tomto v´ysledku mod znamen´a zn´amou funkci modulo definovanou vztahem x = ⌊x/y⌋ · y + (x mod y). Tud´ıˇz t je posledn´ı ˇc´ıslic´ı dekadick´eho z´apisu m. • Indukˇcn´ı krok: Necht’ i + 1 ≡ j, pak plat´ı c(m, j) 7→ if j then c(m ÷ 10, j − 1) else m − 10 ∗ (m ÷ 10) fi 7→ 7→ c(m ÷ 10, j − 1) 7→∗ c(p, w), kde p ≡ ⌊m/10⌋ a w ≡ j − 1 = i. 2Podle I.P. plat´ı c(p, w) 7→∗ t a t je ˇc´ıslice it´eho ˇr´adu dekadick´eho z´apisu ˇc´ısla p. Jelikoˇz m = 10p + (m mod 10) a n´asoben´ı deseti v dekadick´e soustavˇe znamen´a posun ˇc´ıslic v z´apise o jedno doleva“, je t ” z´aroveˇn ˇc´ıslice i + 1 = j-t´eho ˇr´adu dekadick´eho z´apisu ˇc´ısla m. To je pˇresnˇe co bylo tˇreba dok´azat. 2 Petr Hlinˇ en´ y, FI MU Brno
10
FI: IB000: D˚ ukazov´ e postupy
Euklid˚ uv algoritmus Vˇ eta 10.6. Uvaˇzme 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ˇzd´e nenulov´e m, n ∈ spoleˇcn´y dˇelitel ˇc´ısel m, n.2
N plat´ı g(m, n)
7→∗ z, kde z je nejvˇetˇs´ı
D˚ ukaz indukc´ı k i = m + n. (Tj. dokazujeme n´asleduj´ıc´ı tvrzen´ı: Pro kaˇzd´e i ≥ 2 plat´ı, ˇze jestliˇze i ≥ m + n, kde m, n ∈ , m, n > 0, pak z je nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel m, n.) 2 V b´azi pro i = 2 je m, n = 1 a plat´ı
N
g(1, 1) 7→ if 1 − 1 then g(1 − 1, 1) else (if 1 − 1 then g(1, 1 − 1) else 1 fi) fi 7→ 7→ if 0 then g(1 − 1, 1) else (if 1 − 1 then g(1, 1 − 1) else 1 fi) fi 7→ 7→ if 1 − 1 then g(1, 1 − 1) else 1 fi 7→ if 0 then g(1, 1 − 1) else 1 fi 7→ 1 .
Petr Hlinˇ en´ y, FI MU Brno
11
FI: IB000: D˚ ukazov´ e postupy
Indukˇcn´ı krok. Necht’ i + 1 = m + n kde m, n ∈ • m = n. Pak
N. Probereme tˇri moˇznosti:
g(m, n) 7→ if m − n then g(m − n, n) else (if n − m then g(m, n − m) else m fi) fi → 7 if 0 then g(m − n, n) else (if n − m then g(m, n − m) else m fi) fi 7→ if n − m then g(m, n − m) else m fi 7→ if 0 then g(m, n − m) else m fi 7→ m .2
• m < n. Pak g(m, n) 7→ if m − n then g(m − n, n) else (if n − m then g(m, n − m) else m fi) fi 7→ if 0 then g(m − n, n) else (if n − m then g(m, n − m) else m fi) fi 7→ if n − m then g(m, n − m) else m fi 7→ if z then g(m, n − m) else m fi 7→ g(m, n − m) 7→ g(m, k) ,
kde k ≡ n − m. 2Plat´ı m + k = m + (n − m) = n ≤ i, takˇze podle I.P. tak´e plat´ı g(m, k) 7→∗ z, kde z je nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel m a n − m. Ovˇeˇr´ıme, ˇze z je nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel m a n. ∗ Jelikoˇz ˇc´ıslo z dˇel´ı ˇc´ısla m a n − m, dˇel´ı i jejich souˇcet (n − m) + m = n. Celkem z je spoleˇcn´ym dˇelitelem m a n.2 ∗ Bud’ d nˇejak´y spoleˇcn´y dˇelitel ˇc´ısel m a n. Pak d dˇel´ı tak´e rozd´ıl n − m. Tedy d je spoleˇcn´y dˇelitel ˇc´ısel m a n − m. Jelikoˇz z je nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel m a n − m, nutnˇe d dˇel´ı z a z´ avˇer plat´ı. Petr Hlinˇ en´ y, FI MU Brno
12
FI: IB000: D˚ ukazov´ e postupy
• m > n. Pak g(m, n) 7→∗ g(m − n, n) 7→ g(k, n) , kde k ≡ m − n. Podle I.P. plat´ı g(k, n) 7→∗ z, kde z je nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel m − n a n. Podobnˇe jako v´yˇse ovˇeˇr´ıme, ˇze z je tak´e nejvˇetˇs´ı spoleˇcn´y dˇelitel ˇc´ısel m a n. 2 2
Pozn´ amka: Jak byste v´yˇse uveden´y z´apis Euklidova algoritmu vylepˇsili, aby spr´avnˇe poˇc´ıtal“ nejvˇetˇs´ıho spoleˇcn´eho dˇelitele i v pˇr´ıpadech, ˇze m = 0 nebo n = 0? ” Co v takov´ych pˇr´ıpadech selˇze pˇri souˇcasn´em z´apise?
Petr Hlinˇ en´ y, FI MU Brno
13
FI: IB000: D˚ ukazov´ e postupy
