\documentclass[a4paper]{article}
\usepackage{progm}
\usepackage{verbatim}
\analpacks
\analoldal{}
\pagestyle{empty}
\begin{document}
\noindent

``Program testing can be used to show the presence of bugs, but never to show their absence!''\\
--- Edsger Dijkstra

\begin{center}Programozási alapismeretek 1., csoport ZH\\2007. december 13.\end{center}

\emph{1. Feladat  (15 pont)}\\Tekintsük a következõ specifikációt:\\
$A=\alatt{\N}{m}\times\alatt{\N}{n}\times\alatt{\N}{k}$\\
$B=\alatt{\N}{m}\times\alatt{\N}{n}$\\
$Q=(m=m' \es n=n' \es m\le n \es 2|(n-m))$\\
$R=(Q \es (\exists i\in [m,n]: k=f(i)) \es \sum\limits_{j=m}^n \chi(f(j)\le k) = \sum\limits_{l=m}^n \chi(f(l)\ge k))$

Legyen az $f$ függvény 5 és 11 között a következõ:
\begin{center}
  \vspace{-1cm}
  \begin{tabular}{c|c}
    $x$ & $f(x)$ \\
    \hline
    5 & 6 \\
    6 & 6 \\
    7 & 6 \\
    8 & 2 \\
    9 & 7 \\
    10 & 9 \\
    11 & 8
  \end{tabular}
\end{center}

Írd fel, hogy milyen pontokat rendel a feladat a $(5,9,100)$, illetve
a $(9, 11, 4)$ pontokhoz!  Fogalmazd meg érthetõen, szövegesen a
specifikált feladatot!

\emph{Megoldás: } Az utófeltétel egyrészt kiköti, hogy a $k$ értéke
megegyezik valamelyik függvényértékkel az $[m,n]$ intervallumból,
másrészt azt mondja, hogy az intervallumon belül lévõ függvényértékek
közül a $k$-nál kisebbek és nagyobbak legyenek ugyanannyian.  Tehát az
adott intervallumban a medián (középsõ) értéket keresi meg.

Azaz $F(5,9,100)=\{(5,9,6)\}$ és $F(9,11,4)=\{(9,11,8)\}$.

\emph{2. Feladat (10 pont)}\\Specifikáld a következõ feladatot:
állapítsuk meg, hogy az adott $[m,n]$ intervallumban az adott $f$
függvény szigorúan monoton növekvõ-e!  (Azaz minden függvényérték nagyobb-e az
elõzõ függvényértéknél az intervallumban.)

\emph{Megoldás:}\\
$A=\alatt{\Z}{m}\times\alatt\Z n\times\alatt\L l$\\
$B=\alatt\Z {m'}\times\alatt\Z {n'}$\\
$Q=(m=m' \es n=n' \es m\le n+1)$\\
$R=(Q\es l=(\forall i \in [m,n-1]: f(i)<f(i+1)))$

\emph{3. Feladat (10 pont)}\\Specifikáld a következõ feladatot:
állapítsuk meg, hogy az adott $[a,b]$ intervallumban van-e ikerprím
számpár! Ikerprím számpár az olyan két (a számegyenesen) egymás
melletti páratlan szám, hogy mindkettejük prím.  A feladat megoldása
során használhatod a $\text{prím}(i)$ jelölést, ami akkor és csak
akkor igaz értékû, ha $i$ prím.

$A=\alatt{\Z}{a}\times\alatt\Z b\times\alatt\L l$\\
$B=\alatt\Z {a'}\times\alatt\Z {b'}$\\
$Q=(a=a' \es b=b' \es a\le b+1)$\\
$R=(Q\es l=(\exists i \in [m,n-2]: prim(i) \es prim(i+2))$

\emph{4. Feladat  (10 pont)}\\Tekintsük az alábbi programot az $A=\alatt\N n \times\alatt \N i \times\alatt \L l$ állapottéren:
\begin{stuki}
\stm{i,l:=1,\igaz}
\begin{WHILE}{2}{\stm{l \es i \ne n-1}}
  \stm{l:=i+1\not\mathop{|}\hspace{0.3em}n}
  \stm{i:=i+1}
\end{WHILE}
\end{stuki}
Hogyan fut le a program az $n,i,l = 8,20,\igaz$, illetve az $n,i,l = 11,
3, \hamis$ pontokból?

$S((8,20,\igaz))=\{<(8,20,\igaz), (8,1,\igaz), (8,1,\hamis), (8,2,\hamis)\}$\\
$S((11,3,\hamis))=\begin{array}[t]{rl}
\{<
& \hspace{-0.9em} (11,3,\hamis), (11,1,\igaz), (11,2,\igaz), (11,3,\igaz), (11,4,\igaz), (11,5,\igaz), (11,6,\igaz),\\
& \hspace{-0.9em} (11,7,\igaz), (11,8,\igaz), (11,9,\igaz), (11,10,\igaz)>\}
\end{array}
$

\emph{5. Feladat  (15 pont)}\\Specifikáld a következõ feladatot: állapítsuk meg,
hogy az adott $[m,n]$ intervallumban mennyi prímszám van!  Vezesd is
vissza a feladatot, adj megoldóprogramot!  A feladat megoldása során
mind a specifikációban, mind a program tetszõleges részén használhatod
a $\text{prím}(i)$ jelölést, ami akkor és csak akkor igaz értékû, ha
$i$ prím.

\emph{Megoldás:}\\
$A=\alatt{\Z}{m}\times\alatt\Z n\times\alatt{\No} p (\times\alatt \Z k)$\\
$B=\alatt\Z {m'}\times\alatt\Z {n'}$\\
$Q=(m=m' \es n=n' \es m\le n+1)$\\
$R=(Q\es p=\sum\limits_{i=m}^n \text{prím}(i))$

\begin{center}
  \vspace{-1cm}
  \begin{tabular}{c|c}
    feladat & számlálás \\
    \hline
    $m$ & $m$ \\
    $n$ & $n$ \\
    $p$ & $d$ \\
    $k$ & $k$ \\
    prím$(j)$ & $\beta(j)$
  \end{tabular}
\end{center}


\begin{stuki}
\stm{k,p:=m-1,0}
\begin{WHILE}{3}{\stm{k \ne n}}
  \begin{IF}{1}{\stm{\text{prím}(k+1)}}
    \stm{p:=p+1}
    \ELSE
    \stm{SKIP}
  \end{IF}
  \stm{k:=k+1}
\end{WHILE}
\end{stuki}
\end{document}
