% % 02-programove-schemy.tex % % Developed by Ondrej Jombik % Copyright (c) 2003-2005 Platon Group, http://platon.sk/ % Licensed under terms of GNU General Public License. % All rights reserved. % % Changelog: % 26/02/2003 - created % % $Platon: doc/ztp-zbierka/02-programove-schemy.tex,v 1.9 2007-04-29 22:07:52 nepto Exp $ \chapter{Programové schémy} \section{Štandardné programové schémy} \begin{definition}[Symboly] % /* Symbolmi sú individuálne premenné, funkčné symboly, predikátové symboly a~špeciálne symboly: \begin{itemize} \item Individuálne premenné sú $X = \{x, y, z, \dots\}$ \begin{itemize} \item vstupné premenné sú $X_x - \overline{x} = \{x_1, \dots, x_k\}$ \item výstupné premenné sú $X_z - \overline{z} = \{z_1, \dots, z_m\}$ \item pracovné premenné sú $X_y - \overline{y} = \{y_1, \dots, y_n\}$ \end{itemize} \item Funkčné symboly sú $F = \bigcup_{i=0}^{\infty} F^i$ \begin{itemize} \item pre $f \in F^n$ platí $arity(f) = n$ \item $F^n = \{f, g, h, \dots\}$ sú $n$-árne symboly \item $F^0 = \{a, b, \dots\}$ sú konštanty \end{itemize} \item Predikátové symboly sú $B = \bigcup_{i=0}^{\infty} B^i$ \begin{itemize} \item pre $p \in B^n$ platí $arity(p) = n$ \item $B^0 = \{0, 1\}$ sú logické konštantnty $true$ a $false$ \end{itemize} \item Špeciálne symboly sú $[, ], (, ), :=, :$ \end{itemize} \end{definition} % */ \begin{definition}[Výrazy a príkazy] % /* Základnými syntaktickými objektami sú výrazy a predikáty (tzv. booleovské výrazy). Z~nich sa konštruujú príkazy. \begin{itemize} \item Termy sú $T = {t, t_i, \dots}$ \begin{enumerate} \item $F^0 \subseteq T, X \subseteq T$ \item ak $f \in F^n, t_1, \dots, t_n \in T$ potom $f(t_1, \dots, t_n) \in T$ \end{enumerate} \item Predikáty sú $P = \{q\}$ \begin{enumerate} \item $B^0 \subseteq P$ \item ak $p \in B^n, t_1, \dots, t_n \in T$ potom $(p(t_1, \dots, t_n) \in P$ \end{enumerate} \item Príkazy sú $C = \{st, st_i, \dots\}$ \begin{enumerate} \item počiatočný príkaz je $\cmd{begin}~ [\overline{y}] := [t_1(\overline(x), \dots, t_n(\overline{x})]$ \item koncový príkaz je $\cmd{end}~ [\overline{z}] := [t_1(\overline{x}, \overline{y}), \dots, t_n(\overline{x}, \overline{y})]$ \item priraďovací príkaz je $[\overline{y}] := [t_1(\overline{x}, \overline{y}), \dots, t_n(\overline{x}, \overline{y})]$ \item príkaz skoku je $\cmd{goto}~ i$ \item podmienkový príkaz je $\cmd{if}~ p(\overline{x}, \overline{y}) ~\cmd{then}~ st$, kde $st$ je priradenie alebo príkaz skoku \item príkaz s návestím je $i: st$, kde $st$ je buď priradenie, podmienka alebo skok \end{enumerate} \end{itemize} \end{definition} % */ \begin{note} % /* Definícia syntaxe podmienkového príkazu určuje, že podmienku reprezentuje predikátový symbol. Takže podmienkou nemôže byť formula vytvorená pomocou logických spojok resp. operácií $not, and, or$, pretože tým by sme do schém zaviedli niektoré fixne interpretované symboly. \end{note} % */ \begin{definition}[Štandardná programová schéma] % /* Štandardnú programovú schému tvorí konečná postupnosť príkazov $S = \{st_0, st_1, \dots, st_n, st_{n+1}\}$, kde \begin{enumerate} \item $st_0$ je počiatočný príkaz \item $st_{n+1}$ je koncový príkaz \item $st_1$ $(1 \le i \le n)$ je podminekový, priraďovací alebo skokový príkaz s~návestím $i$ \item skok mieri na návestie z intervalu $\langle 1,n \rangle$, alebo na návestie $\cmd{end}$ \end{enumerate} \end{definition} % */ \begin{note} % /* Programová schéma nemusí obsahovať koncový príkaz $\cmd{end}$, keď podľa terminológie teórie grafov neexistuje žiadna hrana, ktorá do neho vedie. \end{note} % */ \begin{definition}[Interpretácia štandardnej programovej schémy] % /* Interpretáciou programovej schémy $S$ nazývame dvojicu $I = (D, i)$, kde \begin{itemize} \item $D$ je obor interpretácie \item $i$ je interpretačný morfizmus \begin{itemize} \item $\forall a \in F^0: i(a) \in D$ \item $\forall f \in F^n: i(f) \in D^n \mapsto D$ \item $\forall c \in B^0: i(c) \in \{0, 1\}$ \item $\forall p \in B^n: i(p) \in D^n \mapsto \{0, 1\}$ \end{itemize} \end{itemize} Pojem interpretácie sa dá primočiaro rozšíriť aj na termy a predikáty ($k$ premenných v terme): \begin{itemize} \item $i(t) \in D^k \mapsto D$ \item $i(q) \in D^k \mapsto \{0, 1\}$ \end{itemize} \end{definition} % */ \begin{definition}[Program] % /* Programom $P$ nazývame dvojicu $P = (S, I)$, kde $S$ je programová schéma a $I$ je interpretácia programovej schémy. \end{definition} % */ \begin{example} % /* P_1 -> S_1 Máme program $P_1$. Zistite, čo program počíta a napíšte jeho schému. $$ \begin{array}{lrl} P_1: & \cmd{begin} & [y_1, y_2] := [0, 0] \\ & 1: & \cmd{if}~ y_2 \ge x ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & [y_1, y_2] := [y_1 + 1, (y_1 + 1)^2] \\ & 3: & \cmd{goto}~1 \\ & \cmd{end} & [z] := [y_1] \\ \end{array} $$ \end{example} % */ \begin{solution} % /* Po krátkej analýze je zrejmé, že program počíta $\lceil\sqrt{x}\rceil$ (hornú celú časť odmocniny~$x$). Schéma $S$, abstrakcia programu vzhľadom na riadiace štruktúry, vyzerá takto: $$ \begin{array}{lrl} S: & \cmd{begin} & [y_1, y_2] := [a_1, a_2] \\ & 1: & \cmd{if}~p(y_2, x) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & [y_1, y_2] := [f_1(y_1), f_2(y_1)] \\ & 3: & \cmd{goto}~1 \\ & \cmd{end} & [z] := [y_1] \\ \end{array} $$ \end{solution} % */ \begin{example} % /* find I_1 Napíšte interpretáciu $I_1$ tak, aby sme pomocou nej a predchádzajúcej schémy $S$ dostali pôvodný program $P_1$, tj. aby platilo $P_1~=~(S,~I_1)$. \end{example} % */ \begin{solution} % /* Interpretácia $I_1 = (D_1, i_1)$: $$ \begin{array}{lrcl} I_1: & i_1(p(y, x)) & = & y \ge x \\ & i_1(f_1(y)) & = & y + 1 \\ & i_1(f_2(y)) & = & (y + 1)^2 \\ & i_1(a_1) & = & 0 \\ & i_1(a_2) & = & 0 \\ & D_1 & = & \mathbb{N} \\ \end{array} $$ \end{solution} % */ \begin{example} % /* find I_2 Nájdite interpretáciu $I_2$, ktorá spolu s predchádzajúcou schémou $S$ vytvorí program, ktorý bude počítať $\lceil log_{2} x \rceil$. \end{example} % */ \begin{solution} % /* Interpretácia $I_2 = (D_2, i_2)$: $$ \begin{array}{lrcl} I_2: & i_2(p(y, x)) & = & y \ge x \\ & i_2(f_1(y)) & = & y + 1 \\ & i_2(f_2(y)) & = & 2^{y + 1} \\ & i_2(a_1) & = & 0 \\ & i_2(a_2) & = & 1 \\ & D_2 & = & \mathbb{N} \\ \end{array} $$ Pomocou príkladu sme si ukázali, že nad jednou schémou $S$ môžu byť postavené viaceré programy $(S, I_1), (S, I_2) \dots (S, I_n)$ riešiace odlišné úlohy. \end{solution} % */ \begin{example} % /* Je daná programová schéma~$S$. $$ \begin{array}{lrl} S: & \cmd{begin} & [y_1, y_2] := [x, a] \\ & 1: & \cmd{if}~p(y_1) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & [y_1, y_2] := [f(y_1), g(y_1, y_2)] \\ & 3: & \cmd{goto}~1 \\ & \cmd{end} & [z] := [y_2] \\ \end{array} $$ Nájdite interpretácie: \begin{itemize} \item[--] $I_1$ takú, že program $(S, I_1)$ bude počítať $x!$ (faktoriál~$x$) \item[--] $I_2$ takú, že program $(S, I_2)$ bude počítať $\sum_{i=1}^{x}i$ (suma od~$1$ po~$x$) \end{itemize} \end{example} % */ \begin{solution} % /* Hľadané interpretácie sú zobrazené v nasledujúcich tabuľkách. $$ \begin{array}{@{~~} c @{~~} | @{~~} c @{~~}} I_1 & \mathbb{N} \\ \hline a & 1 \\ p & y_1 = 0 \\ f & y_1 - 1 \\ g & y_1y_2 \\ \end{array} $$ $$ \begin{array}{@{~~} c @{~~} | @{~~} c @{~~}} I_2 & \mathbb{N} \\ \hline a & 0 \\ p & y_1 = 0 \\ f & y_1 - 1 \\ g & y_1 + y_2 \\ \end{array} $$ \end{solution} % */ \begin{example} % /* history Napíšte históriu výpočtu pre program $P_2~=~(S,~I_2)$ s hodnotou vstupnej premennej $x~=~7$. Formálne sa ohodnotenie vstupných premenných zapisuje ako $v[x~\leftarrow~7]$. \end{example} % */ \begin{solution} % /* Je nutné si uvedomiť, že históriu výpočtu môžeme zapísať vzhľadom na stavy výpočtu, ale taktiež vzhľadom na konfigurácie. V našom riešení použijeme druhú možnosť, tj. históriu výpočtu vzhľadom na konfigurácie. $$ \begin{array}{l} {[1, 1]}_{begin} \\ {[1, 1]}_1 \\ {[2, 4]}_2 \\ {[2, 4]}_3 \\ {[2, 4]}_1 \\ {[3, 9]}_2 \\ {[3, 9]}_3 \\ {[3, 9]}_1 \\ {[3]}_{end} \\ \end{array} $$ \end{solution} % */ \begin{definition}[Herbrandovo univerzum] % /* Herbrandovo univerzum $\mathcal{H}$ pozostáva z reťazcov symbolov, zostrojených zo vstupných premenných a funkčných symbolov: \begin{itemize} \item ak $x_i \in X_x$ potom $"x_i" \in \mathcal{H}$ \item ak $a \in F^0$ potom $" a" \in \mathcal{H}$ \item ak $f \in F^n; "t_1", \dots, "t_n" \in \mathcal{H}$ potom $"f(t_1, \dots, t_n)" \in \mathcal{H}$ \end{itemize} \end{definition} % */ \begin{definition}[Herbrandova voľná interpretácia] % /* Herbrandovou interpretáciou štandardnej programovej schémy $S$ nazývame dvojicu $I_H = (\mathcal{H}, i_H)$, kde: \begin{itemize} \item $\mathcal{H}$ je Herbrandovo univerzum \item $i_H$ je interpretačný morfizumus: \begin{itemize} \item $\forall x \in X_x: i_H(x) = "x"$ \item $\forall a \in F^0: i_H(a) = "a"$ \item $\forall f \in F^n: i_H(f) \in \mathcal{H}^n \mapsto \mathcal{H}$ $n$-tici $"t_1", \dots, "t_n"$ priradí $"f(t_1, \dots, t_n)"$ \end{itemize} \item Interpretácia premenných a funkčných symbolov je "pevná", voľná je interpretácia predikátov. \item Existuje nekonečne veľa Herbrandových interpretácií danej netriviálnej schémy, odlišujúcich sa interpretáciou predikátových symbolov. \item Hebrandove interpretácie "zastupujú" triedu všetkých interpretácií. \end{itemize} \end{definition} % */ \begin{definition}[Zladenie výpočtov a symbolických výpočtov] % /* Interpretácia $I$ s ohodnotením $v$ je zladená s voľnou interpretáciou $I_H$ s ohodnotením predikátov práve vtedy, keď pre každé $p \in B^n$ platí $$ i_H(p)("t_1", \dots, "t_n") \iff i(p)(i^v(t_1), \dots, i^v(t_n)) $$ \end{definition} % */ \begin{example} % /* H universum Zostrojte Herbrandové univerzum pre predchádzajúcu schému~$S$. \end{example} % */ \begin{solution} % /* Herbrandovo univerzum je množina reťazcov symbolov zostrojených zo~vstupných premenných a funkčných symbolov. Riešenie začneme tým, že zoberieme všetky vstupné premenné schémy (v~našom prípade vstupnú premennú~$x$) a všetky použité konštanty (v~našom prípade~$a_1$ a~$a_2$). $$ "x", "a_1", "a_2" $$ Ďalej zoberieme funkcie $f_1$ a $f_2$ a aplikujeme na všetky dostupné termy, ktoré doteraz reprezentujú konštanty $a_1$, $a_2$ a vstupná premenná $x$. $$ "f_1(x)", "f_1(a_1)", "f_1(a_2)" $$ $$ "f_2(x)", "f_2(a_1)", "f_2(a_2)" $$ Týmto krokom sa nám teraz rozšírila množina termov, takže uvedeným spôsobom aplikovania funkcií $f_1$ a $f_2$ na termy pokračujeme ďalej. $$ \begin{array}{l} "f_1(f_1(x))", "f_1(f_1(a_1))", "f_1(f_1(a_2))" \\ "f_1(f_2(x))", "f_1(f_2(a_1))", \dots \\ "f_2(f_1(x))", "f_2(f_1(a_1))", \dots \\ "f_2(f_2(x))", \dots \\ \end{array} $$ Takto je možné pokračovať do nekonečna. Uvedeným postupom sa teda dá zostaviť množina reťazcov Herbrandového univerza vzhľadom na príslušnú schému. V našom prípade je táto množina spojená so schémou $S$. Keď bližšie preskúmame schému $S$, zistíme, že napríklad term $"f_1(f_2(a_2))"$ nemôže nikdy počas behu výpočtu vzniknúť. Napriek tomu sa však v~množine Herbrandového univerza nachádza. \end{solution} % */ \begin{example} % /* S stop <=> ... Schéma $S$ sa zastaví práve vtedy, keď sa zastaví výpočet pre každú Herbrandovú interpretáciu schémy $S$\HWwarn{1}. \end{example} % */ \begin{solution} ~ % /* \underline{$\Longrightarrow:$} Z definície vieme, že schéma $S$ sa zastaví, ak pre každú interpretáciu $I$ sa zastaví program $(S,~I)$. Program $P~=~(S,~I)$ sa zastaví, ak pre každé ohodnotenie $v$ vstupných premenných $\overline x$ je hodnota $val(S,~I,~v)$ definovaná. Keďže sme predpokladali, že schéma $S$ sa zastaví, tj. všetky výpočty na nej sa zastavia, zastavia sa aj všetky výpočty s Herbrandovými interpretáciami. \underline{$\Longleftarrow:$} Musíme dokázať, že výpočet sa zastaví pre ľubovoľnú interpretáciu $I$ a ľubovolné ohodnotenie $v$ vstupných premenných $\overline x$. Ku každej dvojici $I$ a $v$ existuje s nimi zladená Herbrandová interpretácia $I_H$. Z predpokladu sa ale výpočet pre $I_H$ zastaví, takže sa musí zastaviť aj výpočet $(S, I, v)$. Ak sa zastavia všetky výpočty na schéme $S$, zastavia sa aj všetky programy $(S,~I)$. Ak sa zastavia všetky programy, potom sa aj schéma $S$ zastaví. \end{solution} % */ \section{Nerozhodnuteľnosť vlastností schém} \begin{definition}[Rozhodnuteľnosť] % /* Problém je {\it rozhodnuteľný} ak existuje všeobecný algoritmus (musí sa zastaviť), ktorý pre ľubovoľnú schému z danej triedy schém odpovie, či schéma spĺňa danú vlastnosť alebo nespĺňa. Problém je {\it nerozhodnuteľný}, ak takýto všeobecný algoritmus pre danú vlasnosť neexistuje. \end{definition} % */ \begin{definition}[Čiastočná rozhodnuteľnosť] % /* Problém je {\it čiastočne rozhodnuteľný} ak existuje procedúra (nemusí sa zastaviť), ktorá pre ľubovoľnú schému z danej triedy schém odpovie kladne, keď schéma spĺňa danú vlastnosť a odpovie záporne alebo sa neskončí, keď schéma danú vlasnosť nespĺňa. \end{definition} % */ \begin{note} % /* Pre triedu štandardných programových schém $\mathcal{S}$ sa skúmajú štyri hlavné rozhodovacie problémy: \begin{itemize} \item problém zastavenia \item problém divergencie \item problém ekvivalencie \item problém izomorfizmu \end{itemize} \end{note} % */ \begin{example} % /* P_1 divergency Máme danú schému $S$. $$ \begin{array}{lrl} S: & \cmd{begin} & [y_1, y_2] := [a, a] \\ & 1: & \cmd{if}~ p(y_1) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & [y_1] := [f(y_1)] \\ & 3: & \cmd{if}~ p(y_1) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 4: & [y_1, y_2] := [f(y_1), f(y_1)] \\ & 5: & \cmd{if}~ p(y_1) ~\cmd{then}~\cmd{goto}~7 \\ & 6: & \cmd{goto}~\cmd{end} \\ & 7: & \cmd{if}~ p(y_2) ~\cmd{then}~\cmd{goto}~4 \\ & 8: & \cmd{goto}~2 \\ & \cmd{end} & [z] := [a] \\ \end{array} $$ Nájdite interpretáciu $I_1$ takú, že program $P_1 = (S, I_1)$ diverguje. \end{example} % */ \begin{solution} % /* Aby program divergoval, potrebujeme vytvoriť večný cyklus, čiže zabezpečiť beh programu bez dosiahnutia príkazu na návestí $\cmd{end}$. Smer behu programu ovplyvňujú predikáty. Pre náš zámer bude vhodné, ak predikát $p(x)$ bude dávať napríklad takéto výsledky. $$ \begin{array}{rcl} p(a) & = & false \\ p(f(a)) & = & false \\ p(f(f(a))) & = & true \\ \end{array} $$ Vždy po vykonaní príkazu na riadku $4$ obsahujú premenné $y_1$ a $y_2$ rovnaké hodnoty. Preto ak výsledok testu na riadku $5$ bude $true$, potom bude $true$ aj výsledok testu na riadku $7$. Pre večný cyklus teda stačí, aby ešte platila nasledujúca podmienka. \begin{center} $\forall n \ge 2: ~p(f^n(a)) = true$ \end{center} Hľadaná interpretácia $I_1~=~(D_1,~i_1)$ môže potom vyzerať takto: $$ \begin{array}{lrcl} I_1: & i_1(p(x)) & = & x \ge 2 \\ & i_1(f(x)) & = & x + 1 \\ & i_1(a) & = & 0 \\ & D_1 & = & \mathbb{N} \\ \end{array} $$ \end{solution} % */ \begin{example} % /* finite domain D_2 Dokážte alebo vyvráťte tvrdenie, že pre schému $S$ z predchádzajúceho príkladu, pre každú konečnú doménu $D_2$ a pre každý interpretačný morfizmus $i$ platí, že program $P_2~=~(S,~(D_2,~i_2))$ sa zastaví. \end{example} % */ \begin{solution} % /* Tvrdenie neplatí. Ak na konečnej doméne $D_2~=~\{0,~1,~2\}$ upravíme funkciu $f$ tak, že bude vstupný parameter inkrementovať najnajvýš po hodnotu $2$, dostávame dokonca divergentný program $P_2$. $$ \begin{array}{rcl} i_2(p(x)) & = & x \ge 2 \\ i_2(f(x)) & = & min(x + 1, 2) \\ i_2(a) & = & 0 \\ \end{array} $$ \end{solution} % */ \begin{example} % /* reachable command Rozhodnite, či je problém dosiahnuteľnosti príkazu v štandardnej schéme rozhodnuteľný. Svoje tvrdenie dokážte\HWwarn{2}. \end{example} % */ \begin{solution} % /* Problém je čiastočne rozhodnuteľný. \begin{enumerate} \item Nie je (úplne) rozhodnuteľný. Sporom. Predpokladajme, že je problém rozhodnuteľný. Potom vieme rozhodnúť aj to, či je dosiahnuteľný príkaz $\cmd{end}$. Takto by sme ale vedeli rozhodovať divergenciu schémy a to nasledovným spôsobom: \begin{itemize} \item[--] ak je $\cmd{end}$ dosiahnuteľný, tak schéma nie je divergentná, \item[--] ak $\cmd{end}$ dosiahnuteľný nie je, tak schéma je divergentná. \end{itemize} \item Je čiastočne rozhodnuteľný. Zostrojíme procedúru, ktorá povie, že je príkaz dosiahnuteľný ak je príkaz dosiahnuteľný. Ak je príkaz nedosiahnuteľný procedúra povie, že je príkaz nedosiahnuteľný alebo nepovie nič (bude bežať donekonečna). Procedúra simuluje výpočty programov na schéme reprezentovanej stromom. Pri predikátoch existujú dve hrany, inde je hrana len jedna. Čiže vrcholmi stromu s dvomi hranami sú miesta v schéme, kde sa testujú predikáty ($\cmd{if}~\dots~\cmd{then}~\dots$). Koreňom stromu je návestie $\cmd{begin}$. Strom prehľadávame do šírky, tj. po rozdelení sledujeme všetky vetvy stromu súčasne. Výpočet sa rozdelí na $n$ ciest, ale $n$ je vždy konečné číslo. Koniec behu procedúry môže nastať v dvoch možných prípadoch. \begin{enumerate} \item[a.] V niektorej z ciest prídeme na príkaz, ktorého dosiahnuteľnosť sme chceli zistiť. Odpovieme, že príkaz je dosiahnuteľný (aspoň jednou interpretáciou a vstupným ohodnotením). \item[b.] Všetkých $n$ ciest sa dostane do príkazu $\cmd{end}$ pričom ani jedna neprešla hľadaným príkazom. Odpovieme, že príkaz nie je dosiahnuteľný ani jednou interpretáciou s ľubovoľnými vstupnými hodnotami. \end{enumerate} V prípade, že daný príkaz nie je dosiahnuteľný a v programe sa vyskytuje cyklus, naša procedúra nikdy neskončí. \end{enumerate} \end{solution} % */ \begin{definition}[Syntakticky ohraničené podtriedy schém] ~ % /* \begin{itemize} \item {\it Stromové schémy} sú také, ktorých graf neobsahuje cyklus. \item {\it Janovove schémy} sú také, ktoré obsahujú monadické symboly nad jedinou pracovnou premennou. \item {\it Konzervatívne schémy} sú také, v ktorých sa premenná z ľavej strany priradenia vyskytuje aj na pravej strane priraďovacieho príkazu. \item {\it Progresívne schémy} sú také, v ktorých premenná z ľavej strany priraďovacieho príkazu je použitá na pravej strane nasledujúceho príkazu priradenia. \end{itemize} \end{definition} % */ \begin{definition}[Sémanticky ohraničené podtriedy schém] ~ % /* \begin{itemize} \item {\it Liberálne schémy} sú také, kde sa pri ľubovoľnej interpretácii $I_H$ ten istý výraz počíta nanajvýš jeden krát. \item {\it Voľné schémy} sú také, keď pre každú cestu vedúcu z počiatočného príkazu existujú interpretácia a ohodnotenie vstupných premenných také, že výpočet sleduje túto cestu. \item {\it Dosiahnuteľné schémy} sú také, ktoré obsahujú len dosiahnuteľné príkazy, tj. pre každý píkaz v schéme existuje interpretácia, pri ktorej sa príkaz vykoná. \item {\it Priechodné schémy} sú také, ktoré obsahujú len dosiahnuteľné hrany, tj. pre každú hranu v schéme existuje interpretácia, pri ktorej sa hranou prejde. \end{itemize} \end{definition} % */ \begin{example} % /* Uvažujme triedu dosiahnuteľných schém~$\mathcal{D}$. Je príslušnosť schémy k~triede~$\mathcal{D}$ rozhodnuteľný problém? Svoje tvrdenie zdôvodnite. \end{example} % */ \begin{solution} % /* Problém je čiastočne rozhodnuteľný. Z definície vieme, že dosiahnuteľná schéma obsahuje iba dosiahnuteľné príkazy. Pre každý príkaz v~dosiahnuteľnej schéme existuje interpretácia, pri ktorej sa príkaz vykoná. V~predchádzajúcom príklade sme dokázali, že problém dosiahnuteľnosti príkazu je čiastočne rozhodnuteľný. V~našej procedúre, ktorá bude skúmať príslušnosť schémy k~triede~$\mathcal{D}$, sa rovnakým spôsobom súčasne opýtame na dosiahnuteľnosť všetkých príkazov schémy. Množina príkazov schémy je konečná, takže sa v konečnom čase dozvieme,~že: \begin{itemize} \item[--] buď všetky príkazy schémy sú dosiahnuteľné, potom je aj schéma dosiahnuteľná a teda patrí do~triedy~$\mathcal{D}$, \item[--] alebo existuje príkaz, ktorý nie je dosiahnuteľný, potom aj schéma nie je dosiahnuteľná a teda nepatrí do~triedy~$\mathcal{D}$, \item[--] alebo sa beh procedúry neskončí a v tomto prípade schéma taktiež nepatrí do~triedy~$\mathcal{D}$. \end{itemize} \end{solution} % */ \begin{example} % /* Uvažujme triedu štrukturovaných schém $\mathcal{W}$. Je problém divergencie pre štruktúrované schémy rozhodnuteľný? Svoje tvrdenie zdôvodnite. \end{example} % */ \begin{solution} % /* Problém je rozhodnuteľný. Štruktúrované schémy obsahujú iba riadiace štruktúry $\cmd{if}$ a $\cmd{while}$ a neobsahujú riadiacu štruktúru $\cmd{goto}$. Pre každú štruktúrovanú schému sa dá vytvoriť interpretácia taká, že~pokiaľ návestie $\cmd{end}$ existuje, tak bude dosiahnuté. Konštrukcia interpretácie je triviálna -- výsledkom každého predikátu použitého v~riadiacej štruktúre $\cmd{while}$ musí byť $false$. Z toho ale vyplýva, že neexistuje divergentná štruktúrovaná schéma taká, že obsahuje návestie $\cmd{end}$. Naopak, ak schéma návestie $\cmd{end}$ neobsahuje, tak je určite divergentná. Preto je problém divergencie na $\mathcal{W}$ rozhodnuteľný. Odpoveďou pre každú štruktúrovanú schému je, že schéma je divergentná ak neobsahuje návestie $\cmd{end}$, inak nie je divergentná. \end{solution} % */ \section{Porovnávanie tried programových schém} \begin{definition} % /* Uvažujme triedy programových schém $\mathcal{S}_1$ a $\mathcal{S}_2$. Hovoríme, že: \begin{itemize} \item trieda $\mathcal{S}_1$ je {\bf silnejšia} ako trieda $\mathcal{S}_2$ (označenie $\mathcal{S}_2 \sqsubseteq \mathcal{S}_1$), ak ku každej schéme $S_2 \in \mathcal{S}_2$ existuje schéma $S_1 \in \mathcal{S}_1$ taká, že $S_1 \equiv S_2$ (trieda $\mathcal{S}_2$ je {\bf preložiteľná} do~$\mathcal{S}_1$) \item trieda $\mathcal{S}_1$ je {\bf ostro silnejšia} ako trieda $\mathcal{S}_2$ (označenie $\mathcal{S}_2 \sqsubset \mathcal{S}_2$), ak $\mathcal{S}_1$ je silnejšia ako $\mathcal{S}_2$ a existuje schéma $S_1 \in \mathcal{S}_1$, ku ktorej neexistuje ekvivalentná schéma $S_2 \in \mathcal{S}_2$ \item triedy $\mathcal{S}_1$ a $\mathcal{S}_2$ sú {\bf rovnocenné}, ak $\mathcal{S}_1 \sqsubset \mathcal{S}_2$ a $\mathcal{S}_2 \sqsubset \mathcal{S}_1$ \item trieda $\mathcal{S}_1$ je {\bf efektívne preložiteľná} do $\mathcal{S}_2$ ak existuje algoritmus, ktorý transformuje ľubovoľnú schému $S_1 \in \mathcal{S}_1$ do ekvivalentnej schémy $S_2 \in \mathcal{S}_2$ \item triedy $\mathcal{S}_1$ a $\mathcal{S}_2$ sú {\bf efektívne rovnocenné}, ak $\mathcal{S}_1$ je efektívne preložiteľná do $\mathcal{S}_2$ a $\mathcal{S}_2$ je efektívne preložiteľná do $\mathcal{S}_1$ \end{itemize} \end{definition} % */ \begin{example} % /* is volnost? Rozhodnite, či je schéma $S$ voľná. $$ \begin{array}{lrl} S: & \cmd{begin} & [y_1, y_2] := [a, a] \\ & 1: & \cmd{if}~ p(y_1) ~\cmd{then}~\cmd{goto}~4 \\ & 2: & [y_1] := [f(y_1)] \\ & 3: & \cmd{goto}~1 \\ & 4: & \cmd{if}~ p(y_2) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 5: & [y_1, y_2] := [g(y_1), f(y_2)] \\ & 6: & \cmd{goto}~4 \\ & \cmd{end} & [z] := [y_1] \\ \end{array} $$ \end{example} % */ \begin{solution} % /* Z definície vieme, že schéma $S$ je voľná, keď pre každú cestu vedúcu zo~začiatočného príkazu existuje interpretácia $I$ a ohodnotenie vstupných premenných $v$ také, že výpočet $(S, I, v)$ sleduje túto cestu. Schéma $S$ reprezentuje dva cykly. Na začiatku sa premenné $y_1$ a $y_2$ inicializujú na rovnakú hodnotu. V prvom cykle sa iteruje poďla $y_1$, v druhom cykle sa iteruje podľa $y_2$. V oboch prípadoch testuje ukončenie cyklu predikát $p$ aplikovaný na iteračnú premennú. Takže oba cykly budú mať vždy rovnaký počet opakovaní. To je ale v rozpore s voľnosťou schémy, pretože nie sú možné výpočty, kde počet opakovaní prvého cyklu nie je rovnaký ako pri druhom cykle. Takže sa nedá spraviť napríklad 3-násobné opakovanie prvého cyklu nasledované 2-násobným opakovaním cyklu druhého. Schéma $S$ teda nie je voľná. \end{solution} % */ \begin{example} % /* volnost Máme danú Janovovu schému $S_1$. $$ \begin{array}{lrl} S_1: & \cmd{begin} & [y] := [x] \\ & 1: & [y] := [f(y)] \\ & 2: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~6 \\ & 3: & [y] := [f(y)] \\ & 4: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~6 \\ & 5: & \cmd{goto}~2 \\ & 6: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~8 \\ & 7: & \cmd{goto}~4 \\ & 8: & [y] := [f(y)] \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ Nájdite ku~schéme~$S_1$ ekvivalentnú voľnú Janovovu schému~$S_{1_v}$. Schému napíšte a stručne zdôvodnite, prečo je schéma~$S_{1_v}$ voľná a ekvivalentná so~schémou~$S_1$. \end{example} % */ \begin{solution} % /* Riešením je schéma $S_{1_v}$. $$ \begin{array}{lrl} S_{1_v}: & \cmd{begin} & [y] := [x] \\ & 1: & [y] := [f(y)] \\ & 2: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~4 \\ & 3: & \cmd{goto}~1 \\ & 4: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~6 \\ & 5: & \cmd{goto}~5 \\ & 6: & [y] := [f(y)] \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ \underline{Voľnosť:} Ak predikát $p(y)$ platí, tak sa už ďalej netestuje. Ak neplatí, tak pred ďalším testom toho istého predikátu sa zmení premenná $y$. Predikát~$q(y)$ sa testuje len raz. Pre každú cestu existuje interpretácia $I_{1_v}$ a valuácia $v_{1_v}$ taká, že výpočet $(S_{1_v},~I_{1_v},~v_{1_v})$ sleduje túto cestu, takže schéma je voľná. \underline{Ekvivalencia:} Oproti pôvodnej schéme sme zmenili príkaz $7:\cmd{goto}~4$ na nový príkaz $5:\cmd{goto}~5$. V pôvodnej schéme bol tento príkaz dosiahnuteľný iba ak na riadku $4$ platil predikát $p(y)$ a na riadku $6$ neplatil predikát $q(y)$, čoho dôsledkom bol op\"ať skok na riadok $4$ a rovnaké testy s rovnakými hodnotami, čiže večný cyklus. Cyklusom $5:\cmd{goto}~5$ sme teda dosiahli ekvivalentnú schému. Taktiež sme vynechali podmienku na riadku $4$, pretože môže byť nahradená ekvivalentnou podmienkou na riadku $2$ pôvodnej schémy. Nakoniec sme zredukovali príkazy na riadkoch $1$ a $3$ pôvodnej schémy, pretože sa po malých úpravách novej schémy dajú nahradiť jedným príkazom. \end{solution} % */ \begin{example} % /* volnost II. Daná je štandardná schéma $S_2$. $$ \begin{array}{lrl} S_2: & \cmd{begin} & [y] := [x] \\ & 1: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~6 \\ & 3: & [y] := [f_1(y)] \\ & 4: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~2 \\ & 5: & \cmd{goto}~\cmd{end} \\ & 6: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~10 \\ & 7: & [y] := [f_2(y)] \\ & 8: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 9: & \cmd{goto}~1 \\ & 10: & [y] := [f_3(y)] \\ & 11: & \cmd{goto}~8 \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ Nájdite ku~schéme~$S_2$ ekvivalentnú voľnú schému~$S_{2_v}$\HWwarn{3}. \end{example} % */ \begin{solution} % /* Riešením je schéma $S_{2_v}$. $$ \begin{array}{lrl} S_{2_v}: & \cmd{begin} & [y] := [x] \\ & 1: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~6 \\ & 3: & [y] := [f_1(y)] \\ & 4: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~10 \\ & 5: & \cmd{goto}~\cmd{end} \\ & 6: & [y] := [f_2(y)] \\ & 7: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 8: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 9: & \cmd{goto}~3 \\ & 10: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~12 \\ & 11: & \cmd{goto}~3 \\ & 12: & [y] := [f_3(y)] \\ & 13: & \cmd{goto}~7 \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ Schému $S_{2_v}$ sme našli pomocou vytvorenia vývojového diagramu pôvodnej schémy~$S_2$ a jeho následných modifikácií vedúcich k zvoľneniu pri zachovaní ekvivalencie. Tento postup je štandardný. Nedoporučuje sa písať programový kód výslednej schémy priamo\footnote{pretože to ide naozaj len veľmi ťažko}. \end{solution} % */ \begin{example} % /* volnost III. Daná je štandardná schéma $S_3$. $$ \begin{array}{lrl} S_3: & \cmd{begin} & [y] := [x] \\ & 1: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~9 \\ & 2: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~5 \\ & 3: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~8 \\ & 4: & \cmd{goto}~2 \\ & 5: & [y] := [f_1(y)] \\ & 6: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~1 \\ & 7: & \cmd{goto}~\cmd{end} \\ & 8: & [y] := [f_2(y)] \\ & 9: & [y] := [f_3(y)] \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ Nájdite ku~schéme~$S_3$ ekvivalentnú voľnú schému~$S_{3_v}$. \end{example} % */ \begin{solution} % /* Riešením úlohy je teda schéma $S_{3_v}$. $$ \begin{array}{lrl} S_{3_v}: & \cmd{begin} & [y] := [x] \\ & 1: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~4 \\ & 2: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~8 \\ & 3: & \cmd{goto}~3 \\ & 4: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~8 \\ & 5: & [y] := [f_1(y)] \\ & 6: & \cmd{if}~ q(y) ~\cmd{then}~\cmd{goto}~1 \\ & 7: & \cmd{goto}~\cmd{end} \\ & 8: & [y] := [f_3(y)] \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ \end{solution} % */ \begin{example} % /* Máme danú štandardnú schému $S$. $$ \begin{array}{lrl} S: & \cmd{begin} & [y_1, y_2] := [x, a] \\ & 1: & \cmd{if}~ p(y_1) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & [y_1, y_2] := [f(y_1), g(y_1, y_2)] \\ & 3: & \cmd{goto}~1 \\ & \cmd{end} & [z] := [y_2] \\ \end{array} $$ Nájdite ku schéme $S$ ekvivalentnú rekurzívnu schému $R$. \end{example} % */ \begin{solution} % /* Ekvivalentnú rekurzívnu schému $R$ zostrojíme pomocou štandardného postupu. Návestia štandardnej schémy prepisujeme pomocou funkčných premenných $\phi_i$ (simulácia toku riadenia) tak, aby v ich rekurzívnych definíciach vektory vstupných argumentov $\overline{y}$ zodpovedali vektorom pracovných premenných (simulácia zmenu stavu výpočtu). $$ \begin{array}{lcl} \phi_b(y_1, y_2) & = & z = \phi_1(x, a) \\ \phi_1(y_1, y_2) & = & \cmd{if}~ p(y_1) ~\cmd{then}~ \phi_e(y_1, y_2) ~\cmd{else}~ \phi_2(y_1, y_2) \\ \phi_2(y_1, y_2) & = & \phi_3(f(y_1), g(y_1, y_2)) \\ \phi_3(y_1, y_2) & = & \phi_1(y_1, y_2) \\ \phi_e(y_1, y_2) & = & y_2 \\ \end{array} $$ Jednoduchým dosadením do funkčných premenných $\phi_i$ dosiahneme zjednodušenie systému rekurzívnych definícií a výslednú schému $R$. $$ \begin{array}{lrl} R: & \cmd{begin} & [y_1, y_2] := [x, a] \\ & & \phi_1(y_1, y_2) \Longleftarrow \cmd{if}~ p(y_1) ~\cmd{then}~ y_2 ~\cmd{else}~ \phi_1(f(y_1), g(y_1, y_2)) \\ & \cmd{end} & [z] := [\phi_1(x, a)] \\ \end{array} $$ \end{solution} % */ \begin{example} % /* Daná je štandardná schéma $S$. $$ \begin{array}{lrl} S: & \cmd{begin} & [y] := [x] \\ & 1: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 2: & [y] := [f(y)] \\ & 3: & \cmd{if}~ q(y) ~\cmd{then}~ [y] := [g(y)] \\ & 4: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~2 \\ & 5: & \cmd{goto}~1 \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ Nájdite rekurzívnu schému $R$, ktorá je ekvivalentná so schémou $S$. Upravte nájdenú schému tak, aby mala minimálny počet funkčných premenných\HWwarn{4}. \end{example} % */ \begin{solution} % /* Keďže ide o úlohu rovnakého typu ako v predchádzajúcom príklade, aj náš postup bude obdobný. Najskôr vytvoríme základnú sústavu rekurzívnych definícií. $$ \begin{array}{lcl} \phi_b(y) & = & z = \phi_1(x) \\ \phi_1(y) & = & \cmd{if}~ p(y) ~\cmd{then}~ \phi_e(y) ~\cmd{else}~ \phi_3(f(y)) \\ \phi_2(y) & = & \phi_3(f(y)) \\ \phi_3(y) & = & \cmd{if}~ q(y) ~\cmd{then}~ \phi_4(g(y)) ~\cmd{else}~ \phi_4(y) \\ \phi_4(y) & = & \cmd{if}~ p(y) ~\cmd{then}~ \phi_2(y) ~\cmd{else}~ \phi_5(y) \\ \phi_5(y) & = & \phi_1(y) \\ \phi_e(y) & = & y \\ \end{array} $$ Minimálny počet funčných premenných dosiahneme nasledovnými krokmi: \begin{itemize} \item[--] Zrušením $\phi_2$ a dosadením $\phi_3$ na príslušné miesta vo $\phi_1$ a $\phi_4$. \item[--] Zrušením $\phi_e$ a dosadením $y$ na príslušné miesto vo $\phi_1$. \item[--] Zrušením $\phi_5$ a dosadením $\phi_1$ na príslušné miesto vo $\phi_4$. \item[--] Zrušením $\phi_4$ a dosadením príkazu $\cmd{if}$ na príslušné miesta vo $\phi_3$. \end{itemize} Po týchto úpravách dostávame výslednú rekurzívnu schému $R$, ktorá je ekvivalentá so schémou $S$. $$ \begin{array}{lrl @{~} l} R: & \cmd{begin} & [y] := [x] & \\ & & \phi_1(y) \Longleftarrow \cmd{if}~ p(y) & \cmd{then}~ y \\ & & & \cmd{else}~ \phi_3(f(y)) \\ & & \phi_3(y) \Longleftarrow \cmd{if}~ q(y) & \begin{array}[t]{@{} l @{~} l} \cmd{then}~\cmd{if}~ p(g(y)) & \cmd{then}~ \phi_3(f(g(y))) \\ & \cmd{else}~ \phi_1(g(y)) \\ \end{array} \\ & & & \begin{array}[t]{@{} l @{~} l} \cmd{else}~\cmd{if}~ p(y) & \cmd{then}~ \phi_3(f(y)) \\ & \cmd{else}~ \phi_1(y) \\ \end{array} \\ & \cmd{end} & [z] := [\phi_1(x)] & \\ \end{array} $$ \end{solution} % */ \begin{example} % /* Máme danú štandardnú schému $S$. $$ \begin{array}{lrl} S: & \cmd{begin} & [y] := [x] \\ & 1: & [y] := [f(y)] \\ & 2: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~5 \\ & 3: & [y] := [g(y)] \\ & 4: & \cmd{goto}~1 \\ & 5: & \cmd{if}~ p(y) ~\cmd{then}~ [y] := [h(y)] \\ & 6: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 7: & \cmd{goto}~5 \\ & \cmd{end} & [z] := [y] \\ \end{array} $$ Nájdite ku schéme $S$ ekvivalentnú rekurzívnu schému $R$. \end{example} % */ \begin{solution} % /* R -> S III. Do tretice je uvedený príklad rovnakého typu, tj. úloha na prevod štandardnej schémy do rekurzívnej. Tentoraz však iba s výslednou podobou rekurzívnej schémy. Čitateľ si tak môže aspoň porovnať výsledok. $$ \begin{array}{lrl} R: & \cmd{begin} & [y] := [x] \\ & & \begin{array}[t]{@{} l @{~} l} \phi_1(y) \Longleftarrow \cmd{if}~ p(f(y)) & \cmd{then}~ \phi_5(f(y)) \\ & \cmd{else}~ \phi_1(g(f(y))) \\ \end{array} \\ & & \begin{array}[t]{@{} l @{~} l} \phi_5(y) \Longleftarrow \cmd{if}~ p(y) & \begin{array}[t]{@{} l @{~} l} \cmd{then}~\cmd{if}~ q(h(y)) & \cmd{then}~ h(y) \\ & \cmd{else}~ \phi_5(h(y)) \\ \end{array} \\ & \begin{array}[t]{@{} l @{~} l} \cmd{else}~\cmd{if}~ q(y) & \cmd{then}~ y \\ & \cmd{else}~ \phi_5(y) \\ \end{array} \end{array} \\ & \cmd{end} & [z] := [\phi_1(x)] \\ \end{array} $$ \end{solution} % */ \begin{example} % /* Máme danú rekurzívnu schému $R$. $$ \begin{array}{lrl} R: & \cmd{begin} & [\dots] := [\dots] \\ & & \phi(y) \Longleftarrow \cmd{if}~ p(y) ~\cmd{then}~ f(y) ~\cmd{else}~ h(\phi(g(y))) \\ & \cmd{end} & [z] := [\phi(a)] \\ \end{array} $$ Zistite, či existuje k tejto schéme štandardná schéma $S$. V prípade, že existuje, nájdite ju. \end{example} % */ \begin{solution} % /* Štandardným postupom hľadania ekvivalentnej rekurzívnej schémy k štandardnej schéme je: \begin{enumerate} \item Zistiť akého tvaru je výstupná premenná rekurzívnej schémy a rozhodnúť, či môže existovať štandardná schéma dávajúca rovnaké výsledky. \item V prípade kladnej odpovede v predchádzajúcom bode už ostáva iba túto schému nájsť. V mnohých prípadoch to ide, nie však vo všeobecnosti. \end{enumerate} Výstupná premenná $z$ schémy $R$ je tvaru $h^nfg^n(a)$, kde hodnota $n$ vyjadruje hĺbku rekurzívneho vnorenia. V triede štandardných schém $\mathcal{S}$ existuje schéma $S$ ekvivalentná s $R$ generujúca výstupné premenné uvedeného tvaru. $$ \begin{array}{lrl} S: & \cmd{begin} & [y_1, y_2] := [a, a] \\ & 1: & \cmd{if}~ p_1(y_1) ~\cmd{then}~\cmd{goto}~4 \\ & 2: & [y_1] := [g(y_1)] \\ & 3: & \cmd{goto}~1 \\ & 4: & [y_1] := [f(y_1)] \\ & 5: & \cmd{if}~ p(y_2) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ & 6: & [y_1, y_2] := [h(y_1), g(y_2)] \\ & 7: & \cmd{goto}~5 \\ & \cmd{end} & [z] := [y_1] \\ \end{array} $$ Obsah pracovných premenných $[y_1,~y_2]$ v~príkaze $\cmd{begin}$ bol $[a,~a]$, pred riadkom~$4$ bol $[g^n(a),~a]$, po riadku~$4$ bol $[fg^n(a),~a]$ a nakoniec v~príkaze $\cmd{end}$ bol obsah pracovných premenných $[h^nfg^n(a),~g^n(a)]$. Výstupnej premennej~$z$ sa priraďuje hodnota $y_1$, ktorej obsah je v~žiadanom tvare. \end{solution} % */ \begin{example} % /* W^b Uvažujme triedu štruktúrovaných schém~$\mathcal{W}^b$. Trieda~$\mathcal{W}^b$ je obohatená o~booleovské premenné a dobre otypované priradenie do~booleovských premenných. Ktorú z~uvedených konštrukcií je alebo nie je možné preložiť do~ekvivalentnej schémy z~triedy~$\mathcal{W}^b$? Zdôvodnite prečo. $$ \begin{array}{ll} W_1: & \cmd{while}~ b_1 \land b_2 ~\cmd{do}~ S ~\cmd{od} \\ W_2: & \cmd{while}~ b_1 \lor b_2 ~\cmd{do}~ S ~\cmd{od} \\ W_3: & \cmd{while}~ \lnot b ~\cmd{do}~ S ~\cmd{od} \\ \end{array} $$ \end{example} % */ \begin{solution} % /* Začneme konštrukciou~$W_2$, ktorá ide preložiť do~triedy~$\mathcal{W}$. Z~toho vyplýva, že určite pôjde preložiť aj do~triedy~$\mathcal{W}^b$. Použitie booleovských premenných a priradení je však v~tomto prípade nepotrebné. $$ \begin{array}{ll} W_2^{'}: & \cmd{while}~ b_1 ~\cmd{do}~ S ~\cmd{od} \\ & \cmd{while}~ b_2 ~\cmd{do} \\ & ~~~~~~S; \\ & ~~~~~~\cmd{while}~ b_1 ~\cmd{do}~ S; \\ & \cmd{od} \\ \end{array} $$ Pre~nasledujúce programové konštrukcie však už bude použitie booleovskej premennej nevyhnutné. Máme teda možnosť použitia premennej $bool$, do~ktorej môžeme priraďovať hodnoty iných booleovských premenných, ako je napr.~$b_1$ alebo~$b_2$. Tiež je možné priamo priraďovať booleovské konštanty $true$ a $false$. Je nutné si ale uvedomiť, že trieda~$\mathcal{W}^b$ nie je čiastočne interpretovaná vzhľadom na~použitie logických operátorov $\land$~(AND), $\lor$~(OR) alebo~$\lnot$~(NOT). Nájdime teda konštrukciu~$W_1^{'} \in \mathcal{W}^b$ ekvivalentnú s~$W_1$. $$ \begin{array}{ll} W_1^{'}: & [bool] := false; \\ & \cmd{if}~ b_1 ~\cmd{then} \\ & ~~~~~~\cmd{if}~ b_2 ~\cmd{then}~ [bool] := true; \\ % & \cmd{fi}; \\ & \cmd{while}~ bool ~\cmd{do} \\ & ~~~~~~S; \\ & ~~~~~~[bool] := false; \\ & ~~~~~~\cmd{if}~ b_1 ~\cmd{then} \\ & ~~~~~~~~~~~~\cmd{if}~ b_2 ~\cmd{then}~ [bool] := true; \\ % & ~~~~~~\cmd{fi} \\ & \cmd{od} \\ \end{array} $$ Viac elegancie v~riešení je možné získať nahradením konštrukcií $$ \begin{array}{l} [bool] := false; \\ \cmd{if}~ b_1 ~\cmd{then} \\ ~~~~~~\cmd{if}~ b_2 ~\cmd{then}~ [bool] := true; \\ % \cmd{fi} \\ \end{array} $$ za jednoduchšie $$ \begin{array}{r @{} l} \cmd{if}~ b_1 & ~\cmd{then}~ [bool] := [b_2] \\ & ~\cmd{else}~ [bool] := [b_1] \\ \end{array} $$ Uvedeným spôsobom sa dá dokonca vyhnúť použitiu konštánt $true$ a $false$. To už však nie je možné pri zostávajúcej konštrukcii~$W_3^{'} \in \mathcal{W}^b$, ktorá je ekvivalentná s~$W_3$. $$ \begin{array}{ll} W_3^{'}: & [bool] := true; \\ & \cmd{if}~ b ~\cmd{then}~ [bool] := false; \\ & \cmd{while}~ bool ~\cmd{do} \\ & ~~~~~~S; \\ & ~~~~~~[bool] := true; \\ & ~~~~~~\cmd{if}~ b ~\cmd{then}~ [bool] := false; \\ & \cmd{od} \\ \end{array} $$ \end{solution} % */ %ORIGEXAMPLE% \begin{example} % /* %ORIGEXAMPLE% %ORIGEXAMPLE% Uvažujme triedu štandardných schém~$\mathcal{S}$, triedu voľných %ORIGEXAMPLE% schém~$\mathcal{V}$, triedu dosiahnuteľných schém~$\mathcal{D}$, triedu %ORIGEXAMPLE% priechodných schém~$\mathcal{P}$, triedu Janovových schém~$\mathcal{J}$ a %ORIGEXAMPLE% triedu rekurzívnych schém~$\mathcal{R}$. Sformulujte a zdôvodnite vzťahy medzi %ORIGEXAMPLE% niektorými z uvedených tried na základe relácií podtrieda~$\subseteq$, %ORIGEXAMPLE% preložiteľná trieda~$\sqsubseteq$ a efektívne preložiteľná %ORIGEXAMPLE% trieda~$\efsubseteq$. %ORIGEXAMPLE% %ORIGEXAMPLE% \end{example} % */ \begin{example} % /* Uvažujme triedu voľných schém~$\mathcal{V}$, triedu rekurzívnych schém~$\mathcal{R}$ a triedu dosiahnuteľných schém~$\mathcal{D}$. Sformulujte a zdôvodnite vzťahy medzi uvedenými triedami schém a triedou štandardných schém~$\mathcal{S}$ na základe relácií podtrieda~$\subseteq$, preložiteľná trieda~$\sqsubseteq$ a efektívne preložiteľná trieda~$\efsubseteq$. \end{example} % */ \begin{solution} ~ % /* \underline{$\mathcal{S}$, $\mathcal{V}$ ~--~ porovnanie tried štandardných a voľných schém} \begin{itemize} % /* \item[$\mathcal{S} \notsubseteq \mathcal{V}$] Existuje štandardná schéma, ktorá nie je voľná. \item[$\mathcal{S} \notsqsubseteq \mathcal{V}$] Vo všeobecnosti neexistuje postup, pomocou ktorého sa dá spraviť ekvivalentná voľná schéma ku~každej štandardnej schéme, aj keď v~mnohých prípadoch to ide. Pre kontrapríklad pozri tvrdenie $\mathcal{D} \notsqsubseteq \mathcal{V}$. \item[$\mathcal{S} \notefsubseteq \mathcal{V}$] Priamo vyplýva z~tvrdenia $\mathcal{S} \notsqsubseteq \mathcal{V}$. \end{itemize} % */ \begin{list}{$\mathcal{V} \subseteq \mathcal{S},~ % /* \mathcal{V} \sqsubseteq \mathcal{S},~ \mathcal{V} \efsubseteq \mathcal{S}$} {\setlength{\leftmargin}{-3pt}} \item ~\\ \hspace*{29pt} Tvrdenia sú zrejmé, vyplývajú priamo z definícií. \end{list} % */ \underline{$\mathcal{S}$, $\mathcal{R}$ ~--~ porovnanie tried štandardných a rekurzívnych schém} \begin{itemize} % /* \item[$\mathcal{S} \notsubseteq \mathcal{R}$] Ide o syntakticky odlišné schémy, takže principiálne nemôžu byť navzájom podtriedami. \item[$\mathcal{S} \sqsubseteq \mathcal{R}$] Štandardná schéma sa dá previesť na ekvivalentnú rekurzívnu schému. \item[$\mathcal{S} \efsubseteq \mathcal{R}$] Existuje štandardný postup, pomocou ktorého sa dá previesť štandardná schéma na ekvivalentú rekurzívnu. Niekoľko ukážok sa nachádza aj v~tejto zbierke príkladov. \end{itemize} % */ \begin{itemize} % /* \item[$\mathcal{R} \notsubseteq \mathcal{S}$] Ide o syntakticky odlišné schémy, takže principiálne nemôžu byť navzájom podtriedami. \item[$\mathcal{R} \notsqsubseteq \mathcal{S}$] Existuje rekurzívna schéma ku ktorej neexistuje ekvivalentná štandardná schéma. V~niektorých prípadoch sa však rekurzívna schéma dá previesť na ekvivalentú štandardnú (viz. napríklad úlohu v~tejto zbierke). \item[$\mathcal{R} \notefsubseteq \mathcal{S}$] Priamo vyplýva z~tvrdenia $\mathcal{R} \notsqsubseteq \mathcal{S}$. \end{itemize} % */ \underline{$\mathcal{S}$, $\mathcal{D}$ ~--~ porovnanie tried štandardných a dosiahnuteľných schém} \begin{itemize} % /* \item[$\mathcal{S} \notsubseteq \mathcal{D}$] Existuje štandardná schém, ktorá nie je dosiahnuteľná. Kontrapríkladom je schéma obsahujúca jeden alebo viac komponetov nesúvislosti (tzv. ostrovčeky). \item[$\mathcal{S} \sqsubseteq \mathcal{D}$] Odstránením komponentov nesúvislosti zo~štandardnej schémy sa stane schéma dosiahnuteľnou. \item[$\mathcal{S} \notefsubseteq \mathcal{D}$] Odstraňovanie komponetov nesúvislosti však nemôže ísť spraviť efektívne. Ak by to išlo, vedeli by sme rozhodovať divergenciu štandardných schém. Každú schému z~triedy~$\mathcal{S}$ by sme previedli na ekvivalentnú schému z~triedy~$\mathcal{D}$ a spýtali sa na dosiahnuteľnosť návestia $\cmd{end}$. \end{itemize} % */ \begin{list}{$\mathcal{D} \subseteq \mathcal{S},~ % /* \mathcal{D} \sqsubseteq \mathcal{S},~ \mathcal{D} \efsubseteq \mathcal{S}$} {\setlength{\leftmargin}{-3pt}} \item ~\\ \hspace*{29pt} Tvrdenia sú zrejmé, vyplývajú priamo z definícií. \end{list} % */ \end{solution} % */ \begin{example} % /* Uvažujme triedu dosiahnuteľných schém~$\mathcal{D}$, triedu priechodných schém~$\mathcal{P}$ a triedu Janovových schém~$\mathcal{J}$. Sformulujte a zdôvodnite vzťahy medzi uvedenými triedami schém a triedou voľných schém~$\mathcal{V}$ na základe relácií podtrieda~$\subseteq$, preložiteľná trieda~$\sqsubseteq$ a efektívne preložiteľná trieda~$\efsubseteq$. \end{example} % */ \begin{solution} ~ % /* \underline{$\mathcal{V}$, $\mathcal{D}$ ~--~ porovnanie tried voľných a dosiahnuteľných schém} \begin{itemize} % /* \item[$\mathcal{V} \notsubseteq \mathcal{D}$] Komponenty nesúvislosti neodporujú voľnosti, nakoľko do nich nevedie cesta zo začiatku schémy. Odporujú však dosiahnuteľnosti schémy. Preto existuje schéma, ktorá je voľná, ale nie je dosiahnuteľná. \item[$\mathcal{V} \sqsubseteq \mathcal{D}$] Vyplýva z tvrdení $\mathcal{V}~\subseteq~\mathcal{S}~\land~\mathcal{S}~\sqsubseteq~\mathcal{D}$. \item[$\mathcal{V} \efsubseteq \mathcal{D}$] Keďže voľné schémy sú orientované grafy a na~orientovaných grafoch existuje algoritmus odstraňujúci komponenty nesúvislosti, potom sa dá každá voľná schéma efektívne preložiť do~ekvivalentnej dosiahnuteľnej schémy. Algoritmus je lineárny vzhľadom na~počet hrán a kvadratický vzhľadom na počet príkazov schémy. \end{itemize} % */ \begin{itemize} % /* \item[$\mathcal{D} \notsubseteq \mathcal{V}$] Existuje dosiahnuteľná schéma, ktorá nie je voľná. $$ \begin{array}{rl} i: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~i+2 \\ i+1: & \cmd{if}~ p(y) ~\cmd{then}~\cmd{goto}~i+3 \\ i+2: & [y] := [y] \\ i+3: & \dots \\ \end{array} $$ Všetky príkazy v načrtnutej časti schémy sú dosiahnuteľné, ale cesta z~$i+1$ do~$i+3$ nie je voľná. \item[$\mathcal{D} \notsqsubseteq \mathcal{V}$] Existuje dosiahnuteľná schéma, ktorá sa nedá previesť na voľnú. Príkladom môže byť napríklad nasledujúca schéma s~dvojitým cyklusom dávajúca na~výstupe $f^ng^n(a)$, kde $n$ je počet opakovaní prvého a druhého cyklu. $$ \begin{array}{rl} \cmd{begin} & [y_1, y_2] := [a, a] \\ 1: & \cmd{if}~ p(y_1) ~\cmd{then}~\cmd{goto}~4 \\ 2: & [y_1] := [f(y_1)] \\ 3: & \cmd{goto}~1 \\ 4: & \cmd{if}~ p(y_2) ~\cmd{then}~\cmd{goto}~\cmd{end} \\ 5: & [y_1, y_2] := [g(y_1), f(y_2)] \\ 6: & \cmd{goto}~4 \\ \cmd{end} & [z] := [y_1] \\ \end{array} $$ \item[$\mathcal{D} \notefsubseteq \mathcal{V}$] Priamo vyplýva z~tvrdenia $\mathcal{D} \notsqsubseteq \mathcal{V}$. \end{itemize} % */ \underline{$\mathcal{V}$, $\mathcal{P}$ ~--~ porovnanie tried voľných a priechodných schém} \begin{itemize} % /* \item[$\mathcal{V} \notsubseteq \mathcal{P}$] Existuje voľná schéma, ktorá nie je priechodná. Inkriminovaná schéma obsahuje také komponenty nesúvislosti, ktoré neodporujú voľnosti, ale odporujú priechodnosti schémy. \item[$\mathcal{V} \sqsubseteq \mathcal{P}$] Odstránením komponentov nesúvislosti voľnej schémy dostávame ekvivalentnú priechodnú schému. \item[$\mathcal{V} \efsubseteq \mathcal{P}$] Analogicky ako dôkaz tvrdenia $\mathcal{V}\efsubseteq\mathcal{D}$. Je nutné najdenie komponenty súvislosti orientovaného grafu s~vrcholom $\cmd{begin}$ reprezentujúceho voľnú schému a odstránenie ostatných komponentov nesúvislosti. \end{itemize} % */ \begin{itemize} % /* \item[$\mathcal{P} \notsubseteq \mathcal{V}$] Existuje priechodná schéma, ktorá nie je voľná. Pre kontrapríklad pozri tvrdenie $\mathcal{D} \notsqsubseteq \mathcal{V}$. \item[$\mathcal{P} \notsqsubseteq \mathcal{V}$] Existuje priechodná schéma, ktorá sa nedá preložiť do ekvivalentnej voľnej schémy. Pre kontrapríklad pozri tvrdenie $\mathcal{D} \notsqsubseteq \mathcal{V}$. \item[$\mathcal{P} \notefsubseteq \mathcal{V}$] Priamo vyplýva z~tvrdenia $\mathcal{P} \notsqsubseteq \mathcal{V}$. \end{itemize} % */ \underline{$\mathcal{V}$, $\mathcal{J}$ ~--~ porovnanie tried voľných a Janovových schém} \begin{itemize} % /* \item[$\mathcal{V} \notsubseteq \mathcal{J}$] Existuje voľná schéma, ktorá nie je Janovova. Je to jednoducho taká, ktorá obsahuje viac ako jednu pracovnú premennú. \item[$\mathcal{V} \notsqsubseteq \mathcal{J}$] Existuje voľná schéma, ktorá sa nedá preložiť do ekvivalentnej Janovovej schémy. Ako kontrapríklad poslúži voľná schéma, ktorá obsahuje dve pracovné premenné, pričom obe sú v~schéme využívané tak, že sa nedajú nahradiť jednou pracovnou premennou. \item[$\mathcal{V} \notefsubseteq \mathcal{J}$] Priamo vyplýva z~tvrdenia $\mathcal{V} \notsqsubseteq \mathcal{J}$. \end{itemize} % */ \begin{itemize} % /* \item[$\mathcal{J} \notsubseteq \mathcal{V}$] Existuje Janovova schéma, ktorá nie je voľná. \item[$\mathcal{J} \sqsubseteq \mathcal{V}$] Z každej Janovovej schémy sa dá spraviť ekvivalentná voľná Janovova schéma. Dôkaz tvrdenia sa nachádza v~skriptách. \item[$\mathcal{J} \efsubseteq \mathcal{V}$] Každá Janovova schéma sa dá efektívne preložiť do ekvivalentnej voľnej Janovovej schémy. Popis postupu sa opäť nachádza v~skriptách. \end{itemize} % */ \end{solution} % */ % vim: ts=4 % vim600: fdl=0 fdm=marker fdc=0 fmr=/*,*/ tw=78