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

``Simplicity is prerequisite for reliability.''\\
--- Edsger Dijkstra

\begin{center}Bevezetés a programozáshoz 1., 3. zárthelyi dolgozat\\2007. december 12.\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 (20 pont)}\\Legyen $R\subseteq\{1,2,3,4,5\}\times\{1,2,3,4,5\}$.\\
$R=\{(1,2), (1, 4), (2, 1), (3, 4), (3, 3), (3, 5), (4, 5)\}$.
\begin{itemize}
\item Mi a reláció értelmezési tartománya és értékkészlete? (2 pont)
\item Determinisztikus-e, illetve függvény-e a reláció? (4 pont)
\item Mi R 0., 2. hatványa, mi R inverze? (5 pont)
\item Mi a \{4, 5\} halmaz inverz képe, illetve õsképe? (5 pont)
\item Hány eleme van R értékkészlete hatványhalmazának? ($|\mathcal{P}(\mathcal{R}_R)|=?$) (4 pont)
\end{itemize}

\emph{Megoldás:}
\begin{itemize}
\item $\mathcal{D}_R=\{1,2,3,4\}, \mathcal{R}_R=\{1,2,3,4,5\}$
\item Nem determinisztikus, mivel az $1$-hez két értéket is
  hozzárendel.  Függvény sem lehet, mivel nem determinisztikus.
\item $R^0=\{(1,1), (2,2), (3,3), (4,4), (5,5)\}, \\ R^2=\{(1,1), (1,5), (2,2), (2,4), (3,5), (3,3), (3,4)\}, \\ R^{(-1)}=\{(2,1), (4,1), (1,2), (4, 3), (3,3), (5,3), (5,4)\}.$
\item $|\mathcal{R}_R| = 5 \kov |\mathcal{P}(\mathcal{R}_R))| = 2^5 = 32$
\end{itemize}

\emph{2. Feladat (10 pont)}\\$R\subseteq \N_0\times\N_0$.
\begin{displaymath}
R(a)=\left\{
\begin{array}{ll}
\{a-2\}, & \text{ha } a>1 \\
\{2^k|k\in\N\}, & \text{ha } a=1 \\
\end{array}
\right.
\end{displaymath}
Mi az $R$ reláció lezártja és korlátos lezártja?

\emph{Megoldás:}\\
$\forall x\in\N_0: x\in \mathcal{D}_{\overline{R}}$, hiszen ha páros
számról van szó, akkor véges lépésben 2-t mindig kivonva a számból
elérjük az értelmezési tartományon kívûl lévõ $0$-át.  Páratlan számok
esetén pedig az $1$-et, ahonnan viszont biztosan páros számba jutunk,
hiszen $2$ minden természetes kitevõjû hatványa páros.  Tehát a
relációt ``végigkövetõ'' sorozatok mindig 0-ra végzõdnek, így:
$\forall x \in\N_0: \overline{R}(x)=\{0\}$.

A sorozatok hossza azonban csak akkor becsülhetõ felülrõl, ha a
kiinduló érték páros, ugyanis páratlan esetben elérve az $1$-et,
bármekkora kettõhatványra ``ugorhatunk''.  Így a korlátos lezárt
értelmezési tartományában a páratlan számok nincsenek benne.

\emph{3. Feladat (12 pont)}\\
\begin{eqnarray*}
A & = & \N\\
\N\times\N^{**}\supseteq S & = &\{(a,<a\cdots>)|a\equiv 1\text{ mod }(4)\} \\
& \cup & \{(b,<b>),(b,<b,\frac{b}{2}>)|b\equiv 2\text{ mod }(4)\} \\
& \cup & \{(c,<c,2*c>)|c\equiv 3\text{ mod }(4)\} \\
& \cup & \{(d,<d,\frac{d}{2}>)|d\equiv 0\text{ mod }(4)\} \\
H(x) & = & (x\text{ páros szám})
\end{eqnarray*}
Add meg az $\lceil\lf(S,H)\rceil$ halmazt!  (Az $x\equiv 2\bmod(4)$ jelölés azt jelenti, hogy ``$x$ $4$-el osztva $2$ maradékot ad''.)

\emph{Megoldás:} A megértés kedvéért írjunk fel a programhalmazt valameddig konkrét számokkal:\\
$S=\{(1, <1, \dots>), (2, <2>), (2, <2,1>), (3, <3, 6>), (4, <4, 2>),$ \\ $(5, <5, \dots>), (6, <6>), (6, <6, 3>), (7, <7, 14>), (8, <8, 4>), \dots\}$\\
Számoljuk ki $p(S)$-t, mert tudjuk, hogy az $\lceil\lf(S, H)\rceil (=p(S)^{-1}(\lceil H\rceil))$ annak segítségével könnyen számolható.\\
$p(S)=\{(2,2), (2,1), (3,6), (4,2), (6,6), (6,3), (7,14), (8,4), \dots\}$, innen már látható, hogy a páros számok programfüggvényre vonatkozó õsképe
a 4-el osztható, illetve 3 maradékot adó számok lesznek, azaz \\$\lceil\lf(S,H)\rceil=\{3,4,7,8,11,12,15,16,\dots\}$.

\emph{4. Feladat (12 pont)}\\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)})?$ (6 pont)
\item $S$ $A$-ra történõ projekciójának programként való kiterjesztése $B$-re azonos $S$-sel? (6 pont)
\end{itemize}

\emph{Megoldás:}
\begin{itemize}
\item Ez minden relációra igaz, két irányú tartalmazással bizonyítható.
\item Nem igaz, ellenpélda pl. úgy kapható, ha az $S$ egyik
  sorozatának két egymás melletti tagja csak a kiegészítõ altérben tér
  el.  Ugyanis a projekció és kiterjesztés után ez az eltérés meg fog
  szûnni, így a két egymás melletti tag azonos lesz, a sorozat nem
  lesz redukált és így a program már nem is program.  Egy olyan
  reláció, ami program, illetve a most kapott nem program reláció
  pedig biztosan nem egyezhet.
\end{itemize}

\emph{5. Feladat (6 pont)}\\$A=\N\times\N\times\N. S\subseteq A\times A^{**}.$
$S$ az $(1,1,2)$ pontból indítva mindig elõállítja a 10. Fibonacci
számot az $u(n)=u(n-1)+u(n-2)$ rekurzív összefüggés alapján.  Az
állapottér koordinátái rendre $u(n-2)$-nek, $u(n-1)$-nek és $u(n)$-nek
felelnek meg.  Írd fel azt a sorozatot, amelyet $S$ az $(1,1,2)$
ponthoz rendel!  Mit rendel $p(S)$ az $(1,1,2)$ ponthoz?

\emph{Megoldás:}\\
$S(1,1,2)=\{<(1,1,2),(1,2,3),(2,3,5),(3,5,8),(5,8,13),(8,13,21),(13,21,34),(21,34,55)>\}$, tehát \\
$p(S)(1,1,2)=\{(21,34,55)\}$.
\end{document}
