\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}
