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

\begin{center}Bevezetés a programozáshoz 1., 1. zárthelyi dolgozat (megoldás)\\2005. október 28.\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}\\Írjuk fel az $A\times B, A\times C, (C\times B)\times A$ és $B\times C\times A$ halmazok elemeit, ha $A=\{\alpha, \varphi\}, B=\{1,2,3\}, C=\{x,y\}$. (5 pont)

\emph{Megoldás:}\\
$A\times B = \{ (\alpha, 1), (\alpha, 2), (\alpha, 3),(\varphi, 1),(\varphi, 2),(\varphi, 3)\}$\\
$A\times C = \{ (\alpha, x),(\alpha, y),(\varphi, x),(\varphi, y)\}$\\
$(C\times B)\times A = \{ ((x,1), \alpha),((x,1), \varphi),
((x,2), \alpha),((x,2), \varphi),
((x,3), \alpha),((x,3), \varphi),
((y,1), \alpha),((y,1), \varphi),
((y,2), \alpha),((y,2), \varphi),$\\
$((y,3), \alpha),((y,3), \varphi) \}$\\
$B\times C\times A = \{
(1,x,\alpha),
(2,x,\alpha),
(3,x,\alpha),
(1,y,\alpha),
(2,y,\alpha),
(3,y,\alpha),
(1,x,\varphi),
(2,x,\varphi),
(3,x,\varphi),
(1,y,\varphi),
(2,y,\varphi),
(3,y,\varphi)\}$

\emph{2. Feladat}\\$R\subseteq A\times A$.  Igaz-e, hogy $\forall H\subseteq A: R^{-1}(R^{-1}(H)) = (R^2)^{-1}(H)$? (10 pont)

\emph{Megoldás:} Az állítás hamis, ellenpélda: $A=\{1,2,3,4\}, R=\{(1,2), (1,4), (2,3)\}$\\
$R^2=\{(1,3)\}, (R^2)^{-1}(\{3\}) = \{1\}.$\\
$R^{-1}(\{3\})=\{2\}, R^{-1}(R^{-1}(\{3\})) = \emptyset.$

Érdekesség: az egyik irányú tartalmazás igaz...

$\subseteq$:

$a\in R^{-1}(R^{-1}(H)) \kov a\in D_R \es R(a)\subseteq R^{-1}(H) \kov a\in D_R \es \forall b\in R(a): b\in D_R \es R(R(a))\subseteq H \kov a\in D_{R^2} \es R^2(a)\subseteq H \kov a\in (R^2)^{-1}(H)$

%\emph{3. Feladat}\\$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? (10 pont)

\emph{3. Feladat}\\$R\subseteq \N_0\times\N_0$.
\begin{displaymath}
R(a)=\left\{
\begin{array}{ll}
\{a-3\}, & \text{ha } a>2 \\
\{3*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? (10 pont)

\emph{Megoldás:}  Először adjuk meg a lezárt értelmezési tartományát!

Azok az $N_0$-beliek, amik nincsenek benne a reláció értelmezési
tartományában (a 0 és a 2), biztos benne vannak a lezárt értelmezési
tartományában is.  A hárommal osztva 0 vagy 2 maradékot adó számok is
benne vannak, hiszen előbb-utóbb a szükséges végetelen sorozatnak
olyan eleme kellene hogy legyen, ami $R(0)$-nak vagy $R(2)$-nek eleme,
de ilyen nem létezik.  Az egy maradékot adó számok viszont nulla
maradékot adóra ``vezetnek'', hiszen minden $3*k$ szám osztható
hárommal.  Továbbá minden a lezárt által értelmezett pontban a lezárt
értéke a $\{0, 2\}$ halmaz részhalmaza, hiszen ezek az  $R$ által nem
értelmezett számok.

$\D_{\overset{-}R} = N_0 \es \forall a\in N_0\setminus\{x|(x \mod 3 ) = 2 \}: \overset{-}R(a)=\{0\} \es \forall x \in N_0: (x \mod 3) = 2 : \overset{-}R(x)=\{2\}.$

A korlátos lezárt értelmezési tartományából az egy maradékot adó
számok kiesnek, mivel nem lehet előre megmondani egy olyan lépésszám
korlátot ami mellett hármasával csökkentve egy $3*k$ alakó értékét
eljutunk a nullához azon korláton belül.  (Hiszen vannak tetszőlegesen
nagy $k$ értékek is.)

$\D_{\overset{=}R} = N_0 \setminus \{x\in N|(x\mod 3 ) = 1 \} \es \forall x\in D_{\overset{=}R}: \overset{=}R(x)=\overset{-}R(x).$

%\emph{5. Feladat}\\$A=\N\times\N\times\N. S\subseteq A\times A^{**}.$
%$S$ az $(1,1,2)$ pontból kiindulva előállítja a 10. Fibonacci számot
%az $u(n)=u(n-1)+u(n-2)$ rekurzív összefüggés alapján.  A koordináták
%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? (7 pont)

\newcommand{\Legendre}{\text{Legendre}}
\emph{4. Feladat}\\Számítsuk ki egy szám természetes kitevőjű hatványát!\\
$A=\Z\times\N_0\times\Z, F\subseteq A\times A. F=\{((x,n,k),(y,z,x^n))|k=1\}$.\\
$S_1, S_2\subseteq A\times A^{**}$
\begin{eqnarray*}
S_1((x,n,h)) & = & \{<(x,n,h),(x,n-1,h*x), ..., (x,0,h*x^n)>\} \\
S_2((x,n,h)) & = & \{<(a_1), ..., (a_m)> | (a_1) = (x,n,h) \es \Legendre(a_m) = \emptyset \es \\
 &  & \forall i\in [2,m]: (\Legendre(a_{i-1})\ne\emptyset \es (a_i)\in \Legendre(a_{i-1}))\}
\end{eqnarray*}
ahol $\Legendre\subseteq A\times A$ \\
\begin{displaymath}
\Legendre(x,n,h)=\left\{
\begin{array}{ll}
  (x^2, n/2, h), & \text{ha } 2|n \es n\ne 0 \\
  (x, n-1, x*h), & \text{ha } \nem(2|n) \es n\ne 0 \\
\end{array}
\right.
\end{displaymath}
\begin{itemize}
\item $S_1$ és $S_2$ programok? (5 pont)
\item Írjuk fel $S_1$ és $S_2$ lefutását is a $3^5 (243)$ kiszámításakor! (4 pont)
\item Milyen pontokat rendel a feladat a $(3,5,1)$ hármashoz? (3 pont)
\item Megoldja-e $S_1$ illetve $S_2$ az F feladatot? (10 pont)
\item Ekvivalensek-e a programok az állapottéren vagy valamely alterén? (3 pont)
\end{itemize}

\emph{Megoldás:}
\begin{itemize}
\item
  $S_1$ program, mivel mindenhol értelmezett, redukált és az általa pontokhoz rendelt sorozatok első elemei a pontok.
  $S_2$-ről a mindenhol értelmezettség és a redukáltság nem látszik elsőre, ezeket ellenőrízzük:
  \begin{itemize}
  \item $S_2$ mindenhol értelmezett, ha a definíciója értelmes és nem
    ütköznek a kikötések.  Ha $a_m$-et úgy választjuk, hogy a második
    eleme 0 legyen, akkor ez teljesül.
  \item A redukáltság a rendezett hármasok második elemének folyamatos
    csökkenése miatt teljesül.
  \end{itemize}
\item
  $S_1(3,5,1)=\{<(3,5,1),(3,4,3),(3,3,9),(3,2,27),(3,1,81),(3,0,243)>\}$\\
  $S_2(3,5,1)=\{<(3,5,1),(3,4,3),(9,2,3),(81,1,3),(81,0,243)>\}$
\item A feladat a $(3,5,1)$ hármashoz bármilyen olyan rendezett
  hármast hozzárendel, aminek utolsó tagja a $243$.
\item $S_1$ triviálisan megoldja a feladatot.  $S_2$ a futása végére
  azért jut mindig a harmadik komponenesben pont a hatvány értékére,
  mert az általa bejárt sorozat minden $(x,n,h)$ pontjában igaz, hogy
  a sorozat hátra lévő része azt éri el, hogy a harmadik komponensben
  megjelenjen a $x^n*h$ érték.  Ha $n$ páratlan, akkor ezzel a
  célkitűzéssel ekvivalens $x^{n-1}*(h*x)$ kiszámításának célkitűzése,
  ha páros, akkor azonban ${x^2}^{n/2}*h$ is azonos érték.  A legendre
  függvény ezt írja le formalizálva.  Amikor a kitevőben, azaz az $n$
  komponensben megjelenik a 0, akkor a $h$-ban így pont az $x^n*h$
  érték (az eredeti $x$, $h$ és $n$ vonatkozásában) kell, hogy
  szerepeljen, de tudjuk, hogy a feladat csak $h=1$ értékkel kezdődő
  futtatásra követel meg helyes eredményt.
\item A $3^5$ példából is látszik, hogy a programok az állapottéren
  biztos nem, esetleg annak egy alterén lehetnek ekvivalensek.  Ez az
  altér az $n$ és $h$ komponens által kifeszített altér, mivel a
  programok lefutása végén $n$ mindig a 0, míg $h$ a hatvány értéke az
  eredeti $h$-val felszorozva.
\end{itemize}
%\emph{6. Feladat}\\$\lceil H_1\rceil, \lceil H_2\rceil \subseteq A$.
%Igaz-e, hogy ha minden $S\subseteq A\times A^{**}$ programra
%$\lceil\lf(S, H_1)\rceil = \lceil\lf(S, H_2)\rceil$, akkor $\lceil H_1
%\rceil = \lceil H_2 \rceil$? (10 pont)

\emph{5. Feladat}\\Egy program programfüggvénye $p(S)=\{(2,1),(2,4),(4,5),(4,1),(4,2),(5,4)\}$.
$\lceil R\rceil=\{1,2,4\}$.  Írd fel az $\lceil \lf(S,R)\rceil$ halmazt! (5 pont)

\emph{Megoldás:} definíció szerint: $\lceil\lf(S,R)\rceil=\{2,5\}$

\emph{6. Feladat}\\Állapítsuk meg, hogy mennyi valódi osztója van egy
természetes számnak.  Specifikáld a feladatot! (Felhasználható a
$\chi:\L\nyil\{0,1\}$ függvény, ami az igaz helyeken 1.)  (5 pont)

\emph{Megoldás:}\\
$A=\alatt{N}{x} \times \alatt{N_0}{d}$\\
$B=\alatt{N}{x'}$\\
$Q=(x=x')$\\
$R=(Q \es d=\sum\limits_{i=2}^{x-1}\chi(i|x))$
\end{document}