Platon Technologies
not logged in Login Registration
EnglishSlovak
open source software development celebrating 10 years of open source development! Friday, March 29, 2024

File: [Platon] / doc / ztp-zbierka / 02-programove-schemy.tex (download)

Revision 1.10, Sun May 27 16:38:21 2007 UTC (16 years, 10 months ago) by nepto


Changes since 1.9: +6 -6 lines

Fixed bugs & typos, corrections by Dusan Guller

%
% 02-programove-schemy.tex
%
% Developed by Ondrej Jombik <nepto@platon.sk>
% 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


Platon Group <platon@platon.org> http://platon.org/
Copyright © 2002-2006 Platon Group
Site powered by Metafox CMS
Go to Top