\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{1. zárthelyi dolgozat, 2006. október 24.}
\pagestyle{empty}
\begin{document}
\noindent

``Computer Science is no more about computers than astronomy is about telescopes.''\\
--- Edsger Dijkstra



\begin{center}Bevezetés a programozáshoz 1., 1. zárthelyi dolgozat, megoldások\\2006. október 24.\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$,
$(A\times B)\times C$, és $A\times B\times C$ halmazok elemeit, ha $A
=\{0,1\}$, $B=\{1,2,3\}$, $C=\{p,q\}$!\\(5 pont)\\
\emph{Megoldás: (direktszorzatonként 1 pontért)}\\
$A\times B=\{(0,1), (0,2), (0,3), (1,1), (1,2), (1,3)\}$\\
$A\times C=\{(0,p), (0,q), (1,p), (1,q)\}$\\
$C\times B=\{(p,1), (p,2), (p,3), (q,1), (q,2), (q,3)\}$\\
$(A\times B)\times C=$\\$\{((0,1),p), ((0,2),p), ((0,3),p), ((1,1),p), ((1,2),p), ((1,3),p), ((0,1),q), ((0,2),q), ((0,3),q), ((1,1),q), ((1,2),q), ((1,3),q)\}$\\
$A\times B\times C=\{(0,1,p), (0,2,p), (0,3,p), (1,1,p), (1,2,p), (1,3,p), (0,1,q), (0,2,q), (0,3,q), (1,1,q), (1,2,q), (1,3,q)\}$


\emph{2. Feladat}\\$R\subseteq A\times A$.  Tegyük fel, hogy az $R$
értelmezési tartománya egyenlõ az $R$ értelmezési tartományának $R$-re
vonatkozó õsképével.  Mit mondhatunk $R$ lezártjáról? (13 pont)\\
\emph{Megoldás:}\\
Tudjuk, hogy $\forall a\not\in\D_R: (a,a)\in\D_{\overset{-}R}$ (4 pont)\\
Valamint: $\D_R = R^{-1}(\D_R)$, azaz $\{a\in\D_R\}=\{a\in\D_R|R(a)\subseteq\D_R\}$,
ami úgy lehetséges, hogy $\forall a\in\D_R:\emptyset\ne R(a)\subseteq\D_R$.
Ekkor viszont minden $a\in\D_R$ elemre biztos van olyan sorozat, ami ``végigköveti''
a relációt, azaz egyik ilyen elem sem lehet benne a lezárt értelmezési tartományában. (8 pont)\\
Így a lezárt: $\overset{-}R=\{(a,a)\in A\times A|a\not\in\D_R\}$. (1 pont)

\emph{3. Feladat}\\$S_1 \subseteq S_2$ ($S_1$ és $S_2$ programok). $S_2$
megoldja az $F$ feladatot.  Igaz-e, hogy $S_1$ megoldja $F$-et? (10 pont)\\
\emph{Megoldás:}\\
Írjuk fel, hogy mit jelent az, hogy $S_2$ megoldja $F$-et:\\
$\D_F\subseteq\D_{p(S_2)}$ (2 pont) és $\forall a\in\D_F: p(S_2)(a)\subseteq F(a)$ (2 pont), \\
ugyanakkor az, hogy $S_1\subseteq S_2$, mivel $S_1$ is program kell, hogy maradjon,
(azaz mindenhonnan elindítható) azt jelenti, hogy:\\
$\D_{p(S_2)} \subseteq \D_{p(S_1)}$ (2 pont) és $\forall a\in \D_{p(S_2)}:p(S_1)(a)\subseteq p(S_2)(a)$ (2 pont), az elmondottakat együttvéve viszont:\\
$\D_F\subseteq\D_{p(S_2)}\subseteq \D_{p(S_1)}$ és $\forall a\in\D_F:  p(S_1)(a)\subseteq p(S_2)(a)\subseteq F(a)$, így $S_1$ is megoldja $F$-et (2 pont).

\emph{4. Feladat}\\Keressük meg egy természetes szám egy osztóját!\\
$A=\N, F=\{(u, v)\in \N\times \N | v \text{ osztója } u \text{-nak}\}$.\\
$S_1=\{(a, <a, 1>)\in A\times A^*| a>1\} \cup \{(1,<1>)\}$,\\
$S_2=\{(1,<1>), (2,<2,1,2>)\} \cup\{(a, \alpha)\in A\times A^*|\alpha_1=a\es \tau(\alpha)=(a\text{ legkisebb 1-nél nagyobb osztója})\}$.
\begin{itemize}
  \item $S_1$ felírásában miért van szükség az unióra (azaz miért nem írhatunk egyszerûen az elsõ részhalmazba $a\ge 1$-et megkötésként)? (3 pont)
    \\\emph{Megoldás:} Azért, mert akkor igaz lenne $(1, <1,1>)\in S_1$ és így $S_1$ nem teljesítené a program azon feltételét, ami önmaga értékkészletének redukáltságára vonatkozik.
  \item Írjuk fel $p(S_1)$-et és $p(S_2)$-t! (5 pont)
    \\\emph{Megoldás:} \\$p(S_1)(1)=p(S_2)(1)=\{1\}$\\ $\forall a\in \N\setminus\{1\}: p(S_1)(a)=\{1\}, p(S_2)(a)=\{\text{$a$ legkisebb, de 1-nél nagyobb osztója}\}$
  \item Megoldja-e $S_1$ ill. $S_2$ a feladatot? (5 pont)
    \\\emph{Megoldás:} A fenti programfüggvények mindenhol értelmezhetõk, így a megoldás definíció elsõ pontja mindkét esetben teljesül.  A második pont pedig azért igaz mindkét esetben, mert minden számhoz egy konkrét osztót rendelnek, míg a feladat bármely osztót megengedné.  Azaz igaz a tartalmazás, amit a második pont követel.  Mindkét program megoldja a feladatot.
\end{itemize}

\emph{5. Feladat}\\
\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! (12 pont)\\
\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{6. Feladat}\\
Keressük meg egy természetes szám összes valódi osztóját.  Specifikáld a feladatot! (7 pont)\\
\emph{Megoldás:}\\
$A = \alatt{\N}{x} \times \alatt{\mathcal{F}(\N)}{r}$ (2 pont)\\
$B = \alatt{\N}{x'}$ (1 pont)\\
$Q = ( x=x' )$ (1 pont)\\
$R = ( Q \es (a\in r)\knyil(a|x \es a\ne1 \es a\ne x)$ (3 pont)

Megjegyzés: az $\mathcal{F}(\N)$ a természetes számok
összes lehetséges véges részhalmazát jelenti.
\end{document}
