% Ondrej Jombik <nepto@pobox.sk>
% [7/3/2001] - vytvorenie dokumentu

\documentclass[a4paper]{article}
\usepackage{a4wide}

\def\tm{t\kern-0.035cm\char39\kern-0.03cm} % 't' s makcenom
\def\lm{l\kern-0.035cm\char39\kern-0.03cm} % 'l' s makcenom
\def\dm{d\kern-0.035cm\char39\kern-0.03cm} % 'd' s makcenom
\def\id{\'{\i}} % dlhe 'i'
\def\ud{\'u}	% dlhe 'u'
\def\ad{\'a}	% dlhe 'a'
\def\od{\'o}	% dlhe 'o'
\def\ed{\'e}	% dlhe 'e'
\def\yd{\'y}	% dlhe 'y'
\def\ld{\'l}	% dlhe 'l'
\def\Ud{\'U}	% dlhe 'U'
\def\zm{\v{z}}	% 'z' s makcenom
\def\cm{\v{c}}	% 'c' s makcenom
\def\sm{\v{s}}	% 's' s makcenom
\def\nm{\v{n}}	% 'n' s makcenom
\def\Dm{\v{D}}	% 'D' s makcenom
\title{Z{\ad}klady te{\od}rie programovania}
\author{Copyright \copyright{} 2001 Ondrej Jomb{\id}k <<nepto@pobox.sk>>} 

\begin{document}
\maketitle

\section{Zadanie}

\par
Majme dan{\ud} Janovu sch{\ed}mu $S$:
\\
\\
{
\tt
\hsize = 4 in
\parindent = 0 pt
\leftskip = 2 in
begin [y]:=[x]           \\
1:    [y]:=[f(y)]        \\
2:    if p(y) then goto 6\\
3:    [y]:=[f(y)]        \\
4:    if p(y) then goto 6\\
5:    goto 2             \\
6:    if q(y) then goto 8\\
7:    goto 4             \\
8:    [y]:=[f(y)]        \\
end   [z]:=[y]           \\
}

\par
N{\ad}jdite ku sch{\ed}me $S$ ekvivalentn{\ud} vo{\lm}n{\ud} Janovu sch{\ed}mu 
$S_1$. Sch{\ed}mu $S_1$ nap{\id}{\sm}te a nakreslite aj jej grafick{\ud}
reprezent{\ad}ciu (v{\yd}vojov{\yd} diagram). Stru{\cm}ne zd\^ovodnite,
pre{\cm}o je sch{\ed}ma $S_1$ vo{\lm}n{\ad} a ekvivalentn{\ad} so sch{\ed}mou
$S$.

\section{Rie{\sm}enie}

\par
Rie{\sm}en{\id}m je sch{\ed}ma $S_1$:
\\
\\
{
\tt
\hsize = 4 in
\parindent = 0 pt
\leftskip = 2 in
begin  [y]:=[x]\\
1:     [y]:=[f(y)]\\
2:     if p(y) then goto 4\\
3:     goto 1\\
4:     if q(y) then goto 6\\
5:     goto 5\\
6:     [y]:=[f(y)]\\
end    [z]:=[y]\\
}

\section{D\^okaz}
\underline{Vo{\lm}nos{\tm}:} 
\\
\par
Ak predik{\ad}t $p(y)$ plat{\id}, tak sa u{\zm} {\dm}alej netestuje. Ak
neplat{\id}, tak pred {\dm}al{\sm}{\id}m testom toho ist{\ed}ho predik{\ad}tu
sa zmen{\id} premenn{\ad} $y$. 
\\
\par
Predik{\ad}t $q(y)$ sa testuje len raz.
\\
\par
Pre ka{\zm}d{\ud} cestu existuje interpret{\ad}cia a valu{\ad}cia, {\zm}e
v{\yd}po{\cm}et $(S_1, I, v)$ sleduje t{\ud}to cestu.
\\
\\
\underline{Ekvivalencia:} 
\\
\par
Oproti p\^ovodnej sch{\ed}me sme zmenili pr{\id}kaz $7\:goto\:4$ na nov{\yd} 
pr{\id}kaz $6\:goto\:6$. V p\^ovodnej sch{\ed}me bol tento pr{\id}kaz
dosiahnute{\lm}n{\yd} iba ak na riadku $4$ platilo $p(y)$ a na riadku $6$
neplatilo $q(y)$, {\cm}oho d\^osledkom bol op\"a{\tm} skor na riadok $4$ a
rovnk{\ed} testy s rovnak{\yd}mi hodnotami, {\cm}i{\zm}e ve{\cm}n{\yd} cyklus.
\\
\par
Cyklusom $6\:goto\:6$ sme teda dosiahli ekvivalentn{\ud} sch{\ed}mu.
\\
\par
Taktie{\zm} sme vynechali podmienku na riadku $4$, preto{\zm}e m\^o{\zm}e
by{\tm} nahraden{\ad} ekvivalentnou podmienkou na riadku $2$ p\^ovodnej
sch{\ed}my.
\\
\par
Nakoniec sme zredukovali pr{\id}kazy na riadkoch $1$ a $3$ p\^ovodnej
sch{\ed}my, preto{\zm}e sa po mal{\yd}ch {\ud}prav{\ad}ch novej sch{\ed}my 
daj{\ud} nahradi{\tm} jedn{\yd}m pr{\id}kazom.

\section{Z{\ad}ver}

\par
{\Ud}lohu sa mi podarilo {\ud}spe{\sm}ne vyrie{\sm}i{\tm} a dok{\ad}za{\tm}.

\end{document}