\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. zárthelyi dolgozat, 2007. december 5.}
\pagestyle{empty}
\begin{document}
\noindent

``Elegance is not a dispensable luxury but a quality that decides between success and failure.''\\
--- Edsger Dijkstra



\begin{center}Bevezetés a programozáshoz 1., 2. zárthelyi dolgozat\\2007. december 5.\end{center}

Az alábbi feladatok megoldása során állításaidat indokold!  Az
indoklások triviális tényekre, a tanult definíciókra és a kimondott
tétetelekre hivatkozhatnak.  Az előadáson vagy gyakorlaton szerepelt
bármely állítás felhasználható, azonban az el nem hangzottakat
szintén indokolni kell!

\emph{1. Feladat (8 pont)}\\
$B=\{1,2,3\}, A=B\times\{1,2,3\}, F\subseteq B\times B, F=\{(1,2),
(1,3)\}$.  Mi az $F$ kiterjesztettje $A$-re?

\emph{Megoldás:} $F'_A=\{\\
((1,1), (2, 1)),
((1,1), (2, 2)),
((1,1), (2, 3)),\\
((1,2), (2, 1)),
((1,2), (2, 2)),
((1,2), (2, 3)),\\
((1,3), (2, 1)),
((1,3), (2, 2)),
((1,3), (2, 3)),\\
((1,1), (3, 1)),
((1,1), (3, 2)),
((1,1), (3, 3)),\\
((1,2), (3, 1)),
((1,2), (3, 2)),
((1,2), (3, 3)),\\
((1,3), (3, 1)),
((1,3), (3, 2)),
((1,3), (3, 3))
\}$

\emph{2. Feladat (8 pont)}\\
Legyen $A$ tetszőleges állapottér.  Melyek azok a feladatok az $A$-n,
amelyeknek a megoldása az ABORT program?

\emph{Megoldás:} Mivel a $p(\text{ABORT})=\emptyset$, ugyanis $\forall
a\in A: \text{ABORT}(a)={<a,a,\ldots>}$, csak az üreshalmaz (mint
feladat) jöhet szóba, mivel a feladatra teljesülnie kell a megoldás
első feltételének:
$\mathcal{D}_{F}\subseteq\mathcal{D}_{p(\text{ABORT})}$.

\emph{3. Feladat}\\Igaz-e, hogy minden program felírható
\begin{itemize}
\item szekvenciaként? (4 pont)
\item elágazásként? (4 pont)
\item ciklusként? (4 pont)
\end{itemize}

\emph{Megoldás:}
\begin{itemize}
\item Igaz, ui. $\forall S: S=(\text{SKIP}; S)$
\item Szintén igaz, ui. $\forall S: S=IF(\igaz: S)$
\item Nem igaz, ui. legyen az $A=\{1\}$ és az $S=\{(1, <1>), (1,
  <1,1,1,\ldots>)\}$!  Ez a program sehogy nem áll elő ezen az
  állapottéren ciklusként, hiszen ha a ciklusfeltétel igaz az $1$-ben,
  akkor az ABORT-ot, ha hamis, akkor a SKIP-et kapjuk.  A két program
  unióját (ami a mi kitűzésünk volt) sehogy nem kapjuk meg.
\end{itemize}

\emph{4. Feladat}\\Legyen $DO=(\pi, S_0)$!  Igaz-e, hogy
\begin{itemize}
\item $p(DO)\subseteq p(S_0)$? (4 pont)
\item $p(S_0)\subseteq p(DO)$? (4 pont)
\end{itemize}

\emph{Megoldás:}
\begin{itemize}
\item Nem igaz, ui. $\pi:=\hamis, S_0:=\text{ABORT}$, ekkor $p(DO)=A$, míg $p(S_0)=\emptyset$,
\item Nem igaz, ui. $\pi:=\igaz, S_0:=\text{SKIP}$, ekkor $p(DO)=\emptyset$, míg $p(S_0)=A$.
\end{itemize}
\emph{5. feladat (9 pont)}\\$A=\{1,2,3,4\}$.
\begin{stuki*}[6cm]{IF}
\begin{CASE}{1}{2}
  \WHEN{\stm{i=1}}
  \stm{i:=2i}
  \WHEN{\stm{i\le2}}
  \SKIP
  \end{CASE}
\end{stuki*}

Milyen sorozatokat rendel $S_1$, $S_2$, IF az állapottér egyes pontjaihoz?

\emph{Megoldás:}\\
$S_1(1)=\{<1,2>\}$\\
$S_1(2)=\{<2,4>\}$\\
$S_1(3)=\{<3,3,\ldots>\}$ (mivel az értékadás abortál, ha nem értelmezhető) \\
$S_1(4)=\{<4,4,\ldots>\}$ (mivel az értékadás abortál, ha nem értelmezhető) \\
$S_2(1)=\{<1>\}$\\
$S_2(2)=\{<2>\}$\\
$S_2(3)=\{<3>\}$\\
$S_2(4)=\{<4>\}$\\
$IF(1)=\{<1>, <1,2>\}$\\
$IF(2)=\{<2,4>\}$\\
$IF(3)=\{<3,3,\ldots>\}$ (mivel az elágazás abortál, ha egyik feltétel sem igaz)\\
$IF(4)=\{<3,3,\ldots>\}$ (mivel az elágazás abortál, ha egyik feltétel sem igaz)

\emph{6. Feladat (15 pont)}\\Adjunk típusspecifikációt, majd típust a
síkvektorokhoz ($\Z\times\Z$ rendezett párokhoz)!  Két műveletet
specifikáljunk: két vektor összeadását (koordinátánként), valamint
annak eldöntését, hogy egy vektor egy másik vektor (egész)
számszorosa-e!  A típusból csak a reprezentációs függvényt és a hozzá
tartozó invariánst kell megadni.  Az elemi típus az egész számok
halmaza.

\emph{Megoldás:}\\
Típusspecifikáció:\\
$\T_s=(H, I_s, \mathbb{F})$, ahol $H=\Z\times\Z$ és $I_s=\igaz, \mathbb{F}=\{F_+, F_\lambda\}$.  Legyen a típusunk neve mostantól $\Z^2$!

$F_+$:\\
$F_+\subseteq A_+\times A_+$.\\
$A_+=\Z^2\times\Z^2\times\Z^2$\\
$F_+=\{((x,y,z), (x', y', z'))\in A_+\times A_+ \mathop{\big|} x=x' \es y=y' \es z'=x\oplus y\}$ ($\oplus$ a szokásos vektorösszeadást jelöli)

$F_\lambda$:\\
$F_\lambda\subseteq A_\lambda\times A_\lambda$.\\
$A_\lambda=\Z^2\times\Z^2\times\L$\\
$F_\lambda=\{((x,y,l), (x', y', l'))\in A_\lambda\times A_\lambda \mathop{\big|} x=x' \es y=y' \es l'=(\exists z\in\Z: x=zy)\}$

A típus megvalósítása:

$E=\Z, \T=(\rho,I,\S), \rho\subseteq E^*\times\Z^2, \S=\{S_+, S_\lambda\}, \forall \alpha\in E^*: I(\alpha)=(|\alpha|=2), \forall \alpha\in E^*\es I(\alpha):\rho(\alpha)=\left\{\left[
\begin{array}{c}
\alpha_1\\
\alpha_2
\end{array}
\right]\right\}$.

\vspace{1cm}\hspace{15cm}Jó munkát!

\end{document}