1    Cvičenie 1
1.1    Opakovanie: Funkcie
(Totálna) funkcia / z množiny A do množiny B, / : A —> B: Zobrazenie prvkov množiny A na prvky množiny B. Pre každé a G A existuje práve jedno b e B t.ž. f (a) = b.
f (x) = x — 5 (kde / : N —> N) je totálna funkcia.
Ak nie je uvedené inak, predpokladáme že všetky premenné a funkcie pracujú s prirodzenými číslami (N).
Parciálna (čiastočná) funkcia: Zobrazenie prvkov z A na B, avšak nie pre každý prvok z A musí existovat obraz.
f(x) =      ! / nie Je definovaná napr. pre x = 5 kvôli deleniu nulou.
Injektívna funkcia (prostá): Dva rôzne prvky sa vždy zobrazia na dve rôzne hodnoty (formálne: f (x) = f (y) => x = y). Injektivita je "opačnou" vlastnostou k vlastnosti "byt funkciou" - nie len že má každý vzor maximálne jeden obraz (/ je funkcia), ale zároveň má aj každý obraz maximálne jeden vzor (injektivita). Injektivita je nutná ak k funkcií / zostrojujeme inverznú funkciu.
Inkrement (na N) je injektívny (rôzne čísla majú rôznych následníkov). Dekrement nie je injektívny: 1 — 1 = 0 a 0 - 1 = 0 (0 má dva vzory).
Surjektívna funkcia: Pre každý prvok z B existuje prvok z A ktorý sa naň zobrazí (formálne: V& G B. 3a G A. f (a) = b). Surjektivita je "opačnou" vlastnostou k totálnosti. Nie len že má každý prvok z A nejaký obraz (totálnost), ale aj každý provok z B má nejaký vzor (surjektivita).
Dekrement je surjektívny (pre každé x existuje x + 1 ktoré sa naň zobrazí). Inkrement nie je surjektívny: neexistuje x t.ž. x + 1 = 0, teda 0 nemá vzor.
Bijekcia: Totálna funkcia ktorá je injektívna a surjektívna. Bijekcia je mapovanie "jedna-k-jednej", teda pokrýva úplne obe množiny (totálnost a surjektivita), je funkciou a má inverznú funkciu (injektivita). Bijekcia je užitočná keď chceme prvky jednej množiny "previest" alebo "kódovat" prvkami inej množiny.
/ : N —> Z taká že:
f(x) = h    x je sudé
1 —        x je liché je bijekciou medzi prirodzenými a celými číslami.
1
1.2   While programy: Syntax a sémantika
Aby sme sa mohli vyjadřovat o vyčíslitelnosti, potrebujeme najskôr definovat výpočetný model ktorým sa budeme zaoberat. V tomto prípade ide o while-programy. Tie nám dovolujú písat jednoduché imperatívne programy (podobné ako napríklad v Pythone), teda by mali poskytovat lepšiu intuíciu ako napr. Turingove stroje, ktoré sa človeku "programujú" pomerne tažko.
While program predpokladá konečne vela (neohraničených) celočíselných premenných, pričom každá premenná má svoj identifikátor (identifikátor môže byt prakticky lubovolný retazec, napríklad xi, foo, alebo is-valid). Množinu všetkých takýchto identifikátorov budeme označovat ako Var.
While program vždy začína klučovým slovom begin a končí klučovým slovom end, pričom medzi týmito slovami je (potenciálne prázdna) sada príkazov:
<program> ::= begin end | begin <sequence> end
Sada príkazov je potom tvorená bud jedným samostatným príkazom alebo klasickým zretazením príkazov pomocou znaku " ;".
<sequence> ::= <statement> | <statement> ; <sequence>
Príkazy sú bud priradenia alebo while cykly alebo nové vnorené begin/end bloky. Dôležité je si všimnut, že while cyklus dokáže testovat len nerovnost dvoch premenných:
<statement> ::= <assignment> | while <var> 7^ <var> do <statement> | <program>
While programy umožňujú modifikovat premenné tromi základnými priradeniami: nastavením na nulu, inkrementom a dekrementom.
<assignment> ::= var := 0 | var := var + 1 | var := var — 1
Takýto programovací jazyk je samozrejme značne obmedzený, asi by sme chceli minimálne možnost vykonávat klasickú aritmetiku, logické operácie, prípadne nejaké if-else konštrukcie. Z dôvodu zachovania jednoduchosti si tieto operácie definujeme ako tzv. makrá, teda kusy kódu ktoré vložíme do našich programov miesto požadovaných operácií.
2
Príklad: Makro program P\ pre príkaz a := a + b: begin
b'   := b + 1; b'   := b' - 1;
zero := 0;
while b'   != zero do
begin
b'  := b' - 1; a := a + 1
end
end
Dôležité je si uvědomit, že premenné v makro príkazoch (a obecne while programoch) sú vždy globálne naprieč celým programom. Teda ak by nejaký program ktorý využíva toto naše makro ukladal iné medzivýsledky do premennej zero, použitím makra by sa tieto medzivýsledky stratili. Pri definícií makra je teda často dobré spomenutí napr. že premenná zero je takzvaná čerstvá premenná, tj. premenná ktorá sa inde v programe nevyskytuje. Taktiež si môžeme všimnut že z toho istého dôvodu kopírujeme obsah premennej b do premennej b' - aby sme sa vyhli nepožadovanej modifikácií "vstupnej" premennej b.
To je jeden z dôležitých aspektov while programov ktorý sa nedá obsiahnut len pomocou hore uvedenej syntaxe. Na to aby sme sa o while programoch mohli exaktne formálne vyjadřovat, potrebujeme vediet aká je ich sémantika. Cielom teda bude formálne definovat čo to znamená že program niečo počíta.
Ako už sme naznačili, všetky premenné v našich programoch sú globálne, teda stav, alebo inak povedané prostredie v ktorom sa náš program vykonáva budeme uvažovat ako valuáciu premenných. To bude v našom prípade totálna funkcia Var —> N. Teda funkcia ktorá dostane identifikátor premennej a vráti jej celočíselnú hodnotu.
Aby sme si prácu s programami ulahčili (a aby mohli byt takéto valuácie vždy totálne), predpokladáme že všetky premenné ktoré nie sú explicitne nastavené na nejakú hodnotu majú hodnotu nula. Množinu všetkých možných valuácií budeme označovat ako Env.
Príklad: v\ = {xi —> 16; foo —> 4} je valuácia v\ ktorá premennej xi priraďuje hodnotu 16 a premennej foo hodnotu 4. Všetky ostatné premenné (napr. a) majú hodnotu nula. Keďže v\ je funkcia, môžem použit aj nasledujúci zápis «i(foo) = 4 (tu je ale dôležité si uvědomit, že foo je identifikátor premennej).
Akonáhle vieme aké je prostredie v ktorom sa budú naše programy vyhodnocovat, môžeme interpretovat program P ako čiastočnú (program môže cyklit) funkciu ktorá ako vstup berie počiatočnú valuáciu pred spustením programu a na výstupe vracia novú koncovú valuáciu ktorá je platná po vykonaní celého programu: [P] : Env —> Env.
Nebudeme presne definovat ako získat túto funkciu zo syntaktického predpisu programu a budeme předpokládat že každý študent už má intuitívnu predstavu o fungovaní while cyklu, inkrementu a dekrementu (naviac sa tomu venujú iné predmety na tejto fakulte).
Príklad: Uvažujme program P'i-
3
begin
a := b + 1;
while b != zero do b := b - 1
end
Pre iniciálnu valuáciu v\ = {b —> 5} platí, že [ŕ^K^i) = {a —> 6} (b je nula, teda ju nemusíme uvádzat). Všimnime si tiež že iniciálna valuácia nedefinuje premennú zero, teda sa automaticky predpokladá že má hodnotu nula.
Pre iniciálnu valuáciu «2 = {b —> 6; zero —> 3} platí [P'2\{v'2) = {a —> 7; b —> 3; zero —> 3}. No a nakoniec, pre iniciálnu valuáciu «3 = {b —> 1; zero —> 5} je hodnota [P'2\{vz) nedefinovaná (program cyklí).
Takáto funkcia nám stačí na popis toho "ako" program počíta (ako sa iniciálna valuácia mení na koncovú valuáciu), ale nehovorí nám to "čo" program počíta. Na to sa musíme zhodnút čo sú vstupy a výstupy programu, keďže ako sme videli v predchádzajúcom príklade, program môže počítat rôzne podia toho čo sú jeho vstupné parametre, a čo je považované za jeho výstup.
K programu P potom definujeme tzv. sémantickú funkciu nasledovne:
(pp(a1: ...an) = [P](«)(xi) kde v(xí) = a4
Samozrejme, pokial program pre danú valuáciu cyklí, je aj hodnota ipp nedefinovaná. Ďalej si môžeme všimnút dve veci: Prvá, že iniciálnu vauáciu tvoríme pomocou argumentov sématickej funkcie, pričom prvý argument vkladáme do premennej xi, druhý do X2, atd. Druhá, že návratová hodnota je vždy uložená v prvej premennej, teda xi.
Toto je často krát nepraktické z hladiska čitateľnosti a nie je teda na škodu definovat si "makro" ktoré nám umožní povedat čo sú vstupné a výstupné premenné programu (takéto "makro" potom len do nich skopíruje hodnoty z xi,...x„ a po skončení programu zase prekopíruje hodnotu z návratovej premennej). V našom zápise budeme takúto skutočností uvádzat na začiatku programu pomocou príznakov input a output.
Príklad: Striktne vzaté, sémantická funkcia programu P2, <fip2, bude pre lubovolný počet vstupných premenných vždy konštantná funkcia 0, keďže program nepoužíva premenné Xi a tým pádom bude na konci x\ vždy nula (a program vždy skončí, keďže ostatné premenné použité v programe sú nula). Pokial ale použijeme konvenciu z hore uvedeného makra a povieme že vstupnou premennou programu je & a výstupnou premennou programu je a, potom ipp2 (b) = b + 1. Pokial by sme povedali že vstupnými premennými sú & a zero, pričom výstupnou zostáva premenná a, dostávame o niečo zložitejšiu sémantiku
I b + 1    b > zero     - . ífip2(b, zero) = < kedže P% môže začat cyklit.
I _L inak
Poznámka: Pokial hladáme while program ktorý niečo počíta, typicky nás nebude v tomto predmete zaujímat zložitost takéhoto riešenia, teda sa nemusíte trápit tým že váš program je extrémne neefektívny. Ovela radšej budeme
4
opravovat krátky zrozumitelný program ktorý by ale teoreticky počítal až do vyhasnutia slnka (ale musí sa dat samozrejme ukázat že skončí a spočíta správny výsledok) ako komplikovaný optimalizovaný kód nad ktorým opravujúci strávi pár bezsenných nocí. Príklad:
a) Zostrojte program Qi ktorého sémantická funkcia bude ipQ1(n) = 3n+ 1:
input: n; output n; begin
b := n + 1; b := b - 1; while b != zero do begin
n	: = n	+ 1
n	: = n	+ 1
b	:= b	- 1
end;
n := n + 1
end
b) Zostrojte program Q2 ktorého sémantická funkcia bude ipQ2(n) = ^:
input: n; output: n; begin
b := n + 1; b := b - 1; while b != zero do begin
n : = n - 1; b := b - 1; b := b - 1
end
end
II   ti je liché
c) Zostrojte program Q3 ktorého sémantická funkcia bude LpQ3 (n) = <
I 0   n je sudé
input: n; output p; begin
p := 0;
n'   := n + 1; n'   := n' - 1;
while n'   != 0 do
begin
n'   := n' - 1; if p != zero do
p := p - 1
else
p := p + 1
end
end
5
Poznámka: Pre zlepšenie čitatelnosti sme v tomto programe použili makro If-else definované na prednáške.
d) Zostrojte program Q4 ktorého sémantická funkcia bude:
í 3n + 1   n je liché
tPQÁn) = \n .
I ^ n je sude
Na zostrojenie programu použijeme programy z predchádzajúcich cvičení (bez input/output makier). Najskôr spustíme program Q3 aby sme do premennej p uložili paritu čísla n, následne vyhodnotíme vhodnú funkciu programami Qi alebo Q'2:
input: n; output: n; begin
Q3; if p != zero do Ql else Q2
end
Všimnime si že programy vkladáme čisto "syntakticky". Teda nenastáva žiadne volanie funkcie ani nič podobné, kód programu sa jednoducho skopíruje na danú pozíciu. Taktiež stále platí že všetky premenné sú globálne naprieč celým takto vzniknutým programom (preto napr. v programe Q3 vytvárame kópiu premennej n).
e) Aká je sémantika programu Q5?
input: n; output: n; begin
one := 0; one := one + 1; while n != one do Q3
end
Prvým pozrovaním by mohlo byt, že sémantikou tohoto programu je funkcia ipQ5(n) = 1, keďže ak while cyklus skončí, hodnota n je 1. Bohužial sa zatial ale nikomu nepodarilo dokázat že takýto program aj vždy skončí (zatial sa ale ani nenašla hodnota nad ktorou by cyklil). Konrétne tento program generuje tzv. Collatzovu postupnost a je jednoduchou ukážkou toho ako aj velmi krátky program (ak by sme si nemuseli písat vlastné makrá na násobenie/podmienky/etc. dá sa napísat prakticky na jeden riadok) môže narazit na súčasné hranice analýzy programov. Napriek tomu že sémantika programu Q3 je triviálna, jeho opakovaným volaním vzniká netriviálne správanie ktoré v súčasnosti nevieme dobre popísat.
1.3   Iné príklady
Príklad: Napíšte while program počítajúci funkciu xy bez použitia makier (okrem testu na rovnost):
6
input: x,y; output: result; begin
result := 0; result := result + 1;
while y != zero do
begin
y == y - i;
m := result + 1; m : = m - 1;
while m != zero do
begin
m : = m - 1;
a : = x + 1; a : = a - 1; while a != 0 do
a := a - 1;
result := result + 1
end
end
end
Stručná myšlienka: Umocnenie je y-krát zopakované násobenie, kde násobenie je result-krát zopakované sčítavanie, no a sčítavanie je ru-krát zopakovaný inkre-ment, pričom všetko sa to kumuluje do premennej result.
Príklad: Ako vo while programoch implementovat celé čísla? Pomocou bi-jekcie uvedenej na konci prvej sekcie dokážeme celé číslo kódovat pomocou jednoho prirodzeného čísla, pričom samotnú bijekciu vieme určite tiež implementovat vhodným while programom (teda vieme otestovat či je číslo kladné alebo záporné a dostat jeho absolútnu hodnotu).
Všetko čo nám zostáva je nejakým vhodným spôsobom naimplementovat makrá pre inkrement a dekrement (ostatné aritmetické operácie potom vyrobíme podobne ako pre prirodzené čísla). Keďže naša bijekcia mapuje kladné čísla na sudé a záporné na liché, môžeme ako operáciu inkrementu/dekrementu použit +/ — 2, s tým že je nutné nejak vhodne vyriešit problém prechodu medzi zápornými a kladnými číslami (teda že dekrement od 0 je —1, teda v našej bijekcií 1 a pre inkrement naopak). To sa dá ale zabezpečnit obyčajnou podmienkou keďže ide len o konečný počet špecifických prípadov.
7