\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. zárthelyi dolgozat, 2006. december 5.}
\pagestyle{empty}
\begin{document}
\noindent

``Elegance is not a dispensable luxury but a quality that decides between success and failure.''\\
--- Edsger Dijkstra



\begin{center}Bevezetés a programozáshoz 1., 2. zárthelyi dolgozat megoldásai\\2006. december 5.\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}
\begin{itemize}
  \item $A=\{1,2,3\}, R=(x=3), p(S)=\{(1,1), (1,2), (2,2), (2, 3)\}$.
Vizsgáljuk meg ezen a konkrét példán, hogy milyen tartalmazási
kapcsolat állhat fenn $\lceil\nem \lf(S, R)\rceil$ és $\lceil\lf(S,
\nem R)\rceil$ között.  (5 pont)

\emph{Megoldás:}\\
$\lceil\lf(S, R)\rceil=\emptyset \kov \lceil\nem\lf(S, R)\rceil=\{1,2,3\}$,
$\lceil\lf(S, \nem R)\rceil=\{1\}$,
tehát $\lceil\lf(S, \nem R)\rceil\subseteq\lceil\nem \lf(S, R)\rceil$ lehetséges.
  \item Bizonyítsuk be a példa alapján kijött tartalmazást! (5 pont)

\emph{Megoldás:}\\
$a\in\lceil\lf(S, \nem R)\rceil \kov p(S)(a)\subseteq\lceil\nem R\rceil \kov
p(S)(a)\not\subseteq\lceil R\rceil \kov a\not\in\lceil\lf(S,R)\rceil\kov a\in\lceil\nem\lf(S,R)\rceil$
  \item Most vizsgáljuk meg, hogy milyen kapcsolat van $\lceil\lf(S,
  \igaz)\rceil$ és $\lceil\igaz\rceil$ között! (5 pont)

\emph{Megoldás:}\\
$\lceil\lf(S, \igaz)\rceil=D_{p(S)}, \lceil\igaz\rceil=A \kov \lceil\lf(S, \igaz)\rceil\subseteq\lceil\igaz\rceil$.
  \item Ez alapján rakjuk össze a kapcsolatot $\lf(S, \igaz\es(\nem
  R))$ valamint $(\igaz \es(\nem\lf(S, R)))$ állítások között! (5 pont)

\emph{Megoldás:}\\
$\lf(S, \igaz\es(\nem R)) = \lf(S, \igaz) \es\lf(S, \nem R)\kov\igaz \es \nem\lf(S,R)$
\end{itemize}

\emph{2. Feladat}\\$A$ altere $B$-nek.  $F'$ tetszõleges feladat
$B$-n, $F$ pedig $A$-n.
\begin{itemize}
\item Mutassuk meg, hogy $F=$pr$_A(F')$, nem biztosítja, hogy $F'$ az
$F$ feladat kiterjesztettje? (5 pont)

\emph{Megoldás:}\\
Legyen $A=\{1,2\}, B=\{1,2\}\times\{a,b\}, F=\{(1,2)\},
F'=\{((1,a),(2,a))\}$.  Ekkor $F=$pr$_A(F')$, de $F'$ mégsem $F$
kiterjesztettje, hiszen $F$ kiterjesztettje például tartalmazná az
$((1,b),(2,a))$ rendezett párt is!

\item Lássuk be, hogyha $F'$-t az $F$ feladat kiterjesztéseként
kaptuk, akkor $F'=$pr$_A^{(-1)}(F)$ ill. $F' = $pr$_A^{-1}(F)$
fennállnak! (10 pont)

\emph{Megoldás:}\\
A projekció függvény és függvény esetén az õskép és az inverzkép
megegyezik, így csak az egyik állítást szükséges bizonyítani.
Bizonyítsuk az inverzet!  Írjuk fel, hogy mit jelent $F$
kiterjesztése: \\
$F'=\{(a,b)\in B\times B | $pr$_A((a,b))\in F\}$, \\most
írjuk fel, hogy mit jelent a tetszõleges $H\subseteq B\times B$ mellett a
projekció $A$-ra: \\
pr$_A(H)=\{(a,b)\in A\times A|\exists (a',b')\in H: (a,b)=pr_A((a',b'))\}$,\\
ekkor már láthatjuk pr$_A^{(-1)}(F)$-et:\\
pr$_A^{(-1)}(F)=\{(a',b')\in B\times B|$pr$_A((a',b'))\in F\}$.  Ez viszont pont $F'$.
\end{itemize}

\emph{3. Feladat}\\Legyen $DO=(\pi, S)$! Hozzunk ellenpéldát mindkét
állításra:
\begin{itemize}
\item $p(DO)\subseteq p(S)$? (5 pont)
\item $p(S)\subseteq p(DO)$? (5 pont)
\end{itemize}

\emph{Megoldás:}\\
$A=\{1,2\}, \pi=\hamis, S=\{(1,<1,2>), (2,<2,1>)\}$.\\
Ekkor $p(S)=\{(1,2),(2,1)\}$, $p(DO)=\{(1,1),(2,2)\}$, tehát egyik tartalmazás sem igaz.

\emph{4. Feladat}\\$A=\alatt{\Z}{x} \times \alatt{\N}{n} \times \alatt{\Z}{r} \times \alatt{\Z}{b} \times \alatt{\Z}{k}$\\
$S=((k,b,r:=n,x,1;DO(k\ne 0,IF(2|k:k,b:=k/2,b*b, 2\not|k:k,r:=k-1,r*b))))$
\begin{itemize}
\item Rajzold fel a program stuktogramját! (5 pont)
\begin{stuki}
  \stm{k,b,r:=n,x,1}
  \begin{WHILE}{2}{\stm{k\ne 0}}
    \begin{IF}{1}{\stm{2|k}}
      \stm{k,b:=k/2,b*b}
      \ELSE
      \stm{k,r:=k-1,r*b}
    \end{IF}
  \end{WHILE}
\end{stuki}
\item Milyen pontokat rendel a program a $(3,5,0,0,0)$ és $(-2,6,-1,1,12)$ pontokhoz? (10 pont)

\emph{Megoldás:}\\
$S(3,5,0,0,0)=\{<(3,5,0,0,0), (3,5,1,3,5), (3,5,3,3,4), (3,5,3,9,2), (3,5,3,81,1), (3,5,243,81,0)>\}$, illetve \\
$S(-2,6,-1,1,12)=$\\
$\{<(-2,6,-1,1,12), (-2,6,1,-2,6), (-2,6,1,4,3), (-2,6,4,4,2), (-2,6,4,16,1), (-2,6,64,16,0)>\}$
\end{itemize}
\end{document}
