IBOOO Úvod do informatiky -- príklady na procvičení
Sada 10 -- Zadání
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) Dokažte, že g(2, 3) ^ * 8.
b) Dokažte, že pro každé m,n eNo platí g(m, n) i--ˇ* z, kde m = m, n = n a z = mn
.
Příklad 2.
Uvažme deklaraci obsahující rovnici
g(x, y) = if x then (if y then (2 + g(x, y -- 1)) + g(x -- 1, y) else x) else y
Dokažte, že pro každá m, n G No platí g(m, n) i--ˇ* z, kde m = m,n = n&z = z> m + n.
Příklad 3.
Uvažme deklaraci obsahující rovnice
f (x) = x + if 2 * x then h(x -- 1) + /(x -- 1) else 3
h(x) = if x then /i(x -- 1) * /(x -- 1) else 1
Zapište výpočet výrazu /(2) jako posloupnost kroků výpočtu.
Příklad 4.
Uvažme deklaraci obsahující rovnice
f(x) = if x then x + h(x -- 1) else 0
h(x) = if x then x + f (x -- 1) else 0
Dokažte, že pro každé n e N o platí f (n) i--ˇ* m, kde n = n a m = ^ " = 0 i