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

\begin{center}Bevezetés a programozáshoz 1., 2. zárthelyi dolgozat (megoldás)\\2005. december\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}\\Igaz-e, ha $S\subseteq B\times B^{**}$, $A$ altere $B$-nek, akkor
\begin{itemize}
\item $\D_{pr_A(p(S))} = pr_A(D_{p(S)})?$ (8 pont)
\item $S$ $A$-ra történő projekciójának kiterjesztése $B$-re azonos $S$-sel? (8 pont)
\end{itemize}
\emph{Megoldás:}
\begin{itemize}
\item igaz, mert $ a\in\D_{pr_A(p(S))}\kov \exists b\in A: (a,b)\in
  pr_A(p(S)) \kov \exists a',b'\in B: a=pr_A(a') \es b=pr_A(b') \es
  (a',b')\in p(S) \kov a'\in \D_{p(S)} \kov a=pr_A(a')\in
  pr_A(\D_{p(S)})$, valamint $a\in pr_A(\D_{p(S)}) \kov \exists x'\in
  B: pr_A(x')=a \es x'\in \D_{p(S)} \kov \exists y'\in B: (x',y')\in
  p(S) \kov (pr_A(x'),pr_A(y'))\in pr_A(p(S)) \kov a=pr_A(x')\in
  \D_{pr_A(p(S))}$.
\item nem igaz, ellenpélda:\\
$B=\{1,2\}\times\{1,2\}$\\
$B=\{1,2\}$\\
$S=\{((1,1),<(1,1),(1,2)>), ((1,2),<(1,2)>), ((2,1),<(2,1)>), ((2,2),<(2,2)>)\}$\\
ugyanis, ekkor\\
$pr_A(S)=\{(1,<1,1>),(1,<1>),(2,<2>)\}$\\
$(pr_A(S))'=\{((1,1),<(1,1),(1,1)>), ((1,2), <(1,2),(1,2)>), ((1,1), <(1,1)>), ((1,2), <(1,2)>), ((2,1), <(2,1)>), ((2,2),<(2,2)>)\} \ne S$
\end{itemize}
\emph{2. Feladat}\\Van-e olyan program, ami felírható szekvenciaként is, elágazásként is, és felírható ciklusként is? (8 pont)

\emph{Megoldás:}\\
Van, pl. a SKIP, ui.: $SKIP=(SKIP;SKIP)$, $SKIP=IF(\text{igaz}:SKIP)$, $SKIP=DO(\text{hamis}:SKIP)$.

\emph{3. Feladat}\\$A=\alatt{\N}{x} \times \alatt{\N}{k} \times \alatt{\L}{l}$\\
$S=((DO(x>k, x:=x-k);IF(x=k:l:=\text{igaz}, x\ne k:l:=\text{hamis}))$

\begin{itemize}
\item Rajzold fel a program stuktogramját! (5 pont)
\item Milyen pontokat rendel a program a $(5,3,\text{igaz})$ és $(6,2,\text{hamis})$ pontokhoz? (10 pont)
\end{itemize}
\emph{Megoldás:}
\begin{stuki}[5cm]
  \begin{WHILE}{1}{\stm{x>k}}
    \stm{x:=x-k}
  \end{WHILE}
  \begin{CASE}{1}{2}
    \WHEN{\stm{x=k}}
    \stm{l:=\text{igaz}}
    \WHEN{\stm{x\ne k}}
    \stm{l:=\text{hamis}}
  \end{CASE}
\end{stuki}
$S(5,3,\text{igaz})=\{<(5,3,\text{igaz}),(2,3,\text{igaz}),(2,3,\text{hamis})>\}$,\\
$S(6,2,\text{hamis})=\{<(6,2,\text{hamis}),(4,2,\text{hamis}),(2,2,\text{hamis}),(2,2,\text{igaz})>\}$.
\newpage
\emph{4. Feladat}\\
\begin{stuki}[3cm]
  \stm{x:=x+y}
  \stm{y:=x-y}
  \stm{x:=x-y}
\end{stuki}

\begin{itemize}
\item Add meg a program egy lehetséges állapotterét és a program felírását a 3. feladatban használt jelölésekkel! (3 pont)
\item Ha az állapottér két komponensű, akkor milyen pontokat rendel a program a $(4,9)$ és $(9,10)$ pontokhoz? (3 pont)
\end{itemize}
\emph{Megoldás:}\\
$S=(((x:=x+y;y:=x-y);x:=x-y))$.\\
$S(4,9)=\{<(4,9),(13,9),(13,4),(9,4)>\}$,\\
$S(9,10)=\{<(9,10),(19,10),(19,9),(10,9)>\}$.

\emph{5. Feladat}\\Specifikáld azt a típust, amelynek értékei a
komplex számok, ahol a műveletek két komplex szám összeadása és egy
komplex szám képzetes részének meghatározása.  Csupán olyan komplexet
akarunk ábrázolni, aminek valós és képzetes része is egész értékű.
(Az elemi típus az egész típus.) (15 pont)\\
A típus megvalósítása során a programoknak elég a neveiket felírni, a
konkrét programok valamilyen formában való megadása csupán plusz pont
elérését teszi lehetővé.

\emph{Megoldás:}\\
Típusspecifikáció:\\
$\T_s=(H, I_s, \mathbb{F})$, ahol $H=\mathbb{C}$ és $I_s: \mathbb{C}\nyil \mathbb{L}, \forall c\in \mathbb{C}: I_s(c)=(Re(c)\in \mathbb{Z} \es Im(c)\in\mathbb{Z})$,\\
vagy $H=\{\text{``egész értékű'' komplexek}\}$ és $I_s=\text{igaz}$.\\
$\mathbb{F}=\{F_+, F_i\}$.

$F_+$:\\
$F_+\subseteq A_+\times A_+$.\\
$A_+=\alatt{\mathbb{C}}{x}\times\alatt{\mathbb{C}}{y}\times\alatt{\mathbb{C}}{z}$\\
$B_+=\alatt{\mathbb{C}}{x'}\times\alatt{\mathbb{C}}{y'}$\\
$Q_+=(x=x'\es y=y')$\\
$R_+=(Q \es z=x+^*y)$  (a $+^*$ a szokásos komplex összeadást jelöli)

$F_i$:\\
$F_i\subseteq A_i\times A_i$.\\
$A_i=\alatt{\mathbb{C}}{x}\times\alatt{\mathbb{Z}}{i}$\\
$B_i=\alatt{\mathbb{C}}{x'}$\\
$Q_i=(x=x')$\\
$R_i=(Q \es i=Im(x))$

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

$E=\mathbb{Z}, \T=(\rho,I,\mathbb{S}), \rho\subseteq E^*\times\mathbb{C}, T=\mathbb{C}, \mathbb{S}=\{S_+, S_i\}, \forall \alpha\in E^*: I(\alpha)=(|\alpha|=2), \forall \alpha\in E^*\es I(\alpha):\rho(\alpha)=\{\alpha_1+\alpha_2i\}$.
\end{document}