IBOOO Úvod do informatiky — příklady na procvičení Sada 10 — Řešení Upozornění Vzorová řešení dostáváte k dispozici, abyste mohli zkontrolovat správnost svých řešení. Můžete je použít i jako návody k řešení jednotlivých příkladů tak, že je budete číst po částech a budete se snažit další krok provést vždy sami. Příklady ztratí veškerý svůj smysl, pokud se je budete učit jako básničku. Snažte se nad nimi přemýšlet a vyřešit je sami, než se podíváte do vzorových řešení. Téma Induktivní definice. Výpočet programu v deklarativním jazyce, výpočetní krok. Dokazování vlastností programů. Příklad 1. Uvažme deklaraci obsahující rovnici g(x,y) = if y then x * g(x,y — 1) else 1. a) Dokážte, že g(2, 3) ^* 8. b) Dokažte, že pro každé m, n G No platí g(m, n) i—►* z, kde m = m, n = n & z = rrŕ. Řešení a) Při výpočtu se budeme striktně držet definice kroku výpočtu. 0(2,3) h^ if 3 then 2 * g(2, 3-1) else 1 h^ 2*0(2,3- 1) h^ 2*0(2,2) h^ 2 * if 2 then 2 * g(2, 2-1) else 1 h^ 2* (2*0(2,2- 1)) h^ 2* (2*0(2,1)) h^ 2 * (2 * if 1 then 2 * g(2,1-1) else 1) h^ 2* (2* (2*0(2,1 - 1))) h^ 2* (2* (2*0(2,0))) h^ 2 * (2 * (2 * if 0 then 2 * 0(2, 0-1) else 1)) h^ 2 * (2 * (2 * 1)) h^ 2 * (2 * 2) h^ 2*4 ^8 b) Protože se první argument v rovnici nemění, použijeme k důkazu techniku „fixace parametru". Buď m G No libovolné ale pro další úvahy pevné. Indukcí vzhledem k n dokážeme, že pro každé n G No platí g(m, n) i—►* z, kde m = m, n = n & z = mn. Základní krok: n = 0. Pak 0(m,O) i-^ if 0 then m * g(m, 0—1) else 1 i-> 1 1 Indukční krok. Nechť k = n + 1. Platí g(m,k) i-^ if k then m * g(m, k — 1) else 1 i—► m * g(m, k — 1) i—► m * g(m, u) kde u = n. Podle LP. platí g (m, u) i—►* v, kde v = mn. Proto m * g(m, u) i—►* m * v I—► w kde w = m * mn = mn+1. Příklad 2. Uvažme deklaraci obsahující rovnici g(x, y) = if x then (if y then (2 + g(x, y — 1)) + m + n. Řešení Protože se v dokazované vlastnosti vyskytuje součet argumentů, může být výhodné vést indukci také k součtu argumentů. Indukcí vzhledem k i E No dokážeme následující tvrzení: Jestliže i = m + n kde m, n E No, pak g(m,n) i—►* z, kde m = m, n = n a z = z > m + n. Základní krok: i = 0. Pak m = n = 0 a platí 0(0,0) h^ if 0 then (if 0 then (2 + g(0, 0 - 1)) + g(0 - 1, 0) else 0) else 0 ^0 Jelikož 0 > 0 + 0, tvrzení platí. Indukční krok. Nechť i + 1 = m + n, kde m, n E No- Musíme rozlišit tři možnosti. Jestliže m = 0, pak 0(0, n) h^ if 0 then (if n then (2 + g(0, n - 1)) + g(0 - 1, n) else 0) else 0 h^ n a jelikož n > 0 + n, tvrzení platí. Jestliže m > 0 a n = 0, pak #(m,0) i-^ if m then (if 0 then (2 + g (m, 0 — 1)) + g (m —1,0) else m) else 0 h^ if 0 then (2 + g (m, 0 — 1)) + g (m —1,0) else m i-^ m a jelikož m > m + 0, tvrzení platí. 2 Jestliže m > O a n > O, pak g(m,n) i—► if m then (if n then (2 + g (m, n — 1)) + g (m — 1, n) else m) else n i-^ if n then (2 + g (m, n — 1)) + g (m — 1, n) else m i—► (2 + g (m, n — 1)) + g (m — 1, n) i—► (2 + g (m, u)) + m + n— 1. Proto (2 + g(m,u))+g(m- l,n) ^* (2 + p)+#(m- l,n) i—► r + (/(m — 1, n) i—► r + g(y, n) kde r = r = 2+pav = m— 1. Jelikož p > m + n — 1, platí r > m + n + 1. Podle LP. dále g (v, n) i—►* q, kde q = q > m — 1 + n. Proto r + #(v,n) i—► r + q i->t kde t = r + g. Jelikož r > m + n + 1 & q > m — 1 + n, platí r + g > (m + n + 1) + (m — 1 + n) = 2(m + n) >m + n Příklad 3. Uvažme deklaraci obsahující rovnice /(x) = x + if 2 * x then /i(x — 1) + f (x — 1) else 3 h(x) = if x then /i(x — 1) * f(x — 1) else 1 Zapište výpočet výrazu /(2) jako posloupnost kroků výpočtu. Řešení /(2) ^2 + if 2 * 2 then fr(2 - 1) + /(2 - 1) else 3 ^2 + if 4 then h(2 - 1) + /(2 - 1) else 3 i-> 2 + (fr(2 - 1) +/(2 - 1)) ^ 2 + (h(l) + /(2 - 1)) ^ 2 + ((if 1 then fr(l - 1) * /(l - 1) else 1) + /(2 - 1)) -2 + ((fc(l-l)*/(l-l)) + /(2-l)) _► 2 + ((fc(0) */(l - 1)) +/(2 - 1)) ^ 2 + (((if 0 then h(0 - 1) * /(O - 1) else 1) * /(l - 1)) + /(2 - 1)) -2 + ((l*/(l-l)) + /(2-l)) _► 2 + ((1 */(O)) +/(2 - 1)) ^ 2 + ((1 * (0 + if 2 * 0 then h(0 - 1) + /(O - 1) else 3)) + /(2 - 1)) ^ 2 + ((1 * (0 + if 0 then fr(0 - 1) + /(O - 1) else 3)) + /(2 - 1)) i->2 + ((l*(0 + 3)) + /(2-l)) 3 2 + ((l*3) + /(2-l)) 2 + (3 + /(2-l)) 2+ (3 +/(l)) 2 + (3 + (1 + if 2 * 1 then h(l - 1) + /(l - 1) else 3)) 2 + (3 + (1 + if 2 then h(l - 1) + /(l - 1) else 3)) 2 + (3 + (l + (fc(l-l) + /(l-l)))) 2 + (3 + (1 + (h(0) + /(l - 1)))) 2 + (3 + (1 + ((if O then h(0 - 1) * /(O - 1) else 1) + /(l - 1)))) 2 + (3 + (l + (l + /(l-l)))) 2 + (3 + (l + (l + /(0)))) 2 + (3 + (1 + (1 + (O + if 2 * O then h (O - 1) + /(O - 1) else 3)))) 2 + (3 + (1 + (1 + (O + if O then h(0 - 1) + /(O - 1) else 3)))) 2 + (3 + (l + (l + (0 + 3)))) 2 + (3 + (l + (l + 3))) 2+ (3+ (1 + 4)) 2 + (3 + 5) 2 + 8 10 Příklad 4. Uvažme deklaraci obsahující rovnice f(x) = if x then x + h(x — 1) else O h(x) = if x then x + f (x — 1) else O Dokažte, že pro každé n E No platí f (n) i—►* m, kde n = n a m = ^"=0 i- Řešení Indukcí vzhledem k n dokážeme následující silnější tvrzení: Pro každé n E No platí /(n) h^* m a h(n) i—►* m, kde n = n a m = Yľi=o *• Základní krok: n = 0. Platí /(O) h^ if O then O + fr(0 - 1) else O ^0 a podobně h(0) ^ if 0 then 0 + /(O - 1) else 0 ^0 Indukční krok: Nechť k = n + 1. Potom platí /(k) i-^ if k then k + h(\í — 1) else 0 ^k + h(k- 1) i—► k + /?,(w) kde w = n. Podle LP. platí h(w) i—►* p, kde p = ^"=0*- Proto 4 k + h(w) ^* k + p i—► q kde q = n + 1 + Eľ=o * = ZSo i- Celkem jsme tedy dokázali, že /(k) i—►* q, kde q = Yľi=o i- Podobně platí h(k) ^ if k then k + /(k - 1) else 0 -k + /(k-l) i->k + /(w) kde w = n. Podle LP. platí /(w) i—►* p, kde p = ^"=0i Proto k + /(w) ^* k + p i—► q n+l kde q = n + 1 + Ei=0* = Ei=o í. Celkem jsme tedy dokázali, že h(k) i—►* q, kde q = E"=0 i Uvědomte si, proč jsme museli zesílit dokazované tvrzení: Abychom mohli dokázat tvrzení indukčního kroku pro funkci /, museli jsme využít indukční předpoklad pro funkci h. Abychom mohli dokázat tvrzení indukčního kroku pro funkci h, museli jsme využít indukční předpoklad pro funkci /. Nebylo proto možné tvrzení dokázat nejprve pro jednu a potom pro druhou funkci. Museli jsme současně dokazovat tvrzení o obou funkcích. 5