\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\equiv 1\text{ mod }(4)\} \\ & \cup & \{(b,),(b,)|b\equiv 2\text{ mod }(4)\} \\ & \cup & \{(c,)|c\equiv 3\text{ mod }(4)\} \\ & \cup & \{(d,)|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}