% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 54. feladat}
\begin{document}
\noindent
\emph{Feladat:} Adottak az $f$ és $g$ monoton növő függvények,
valamint a $k$ szám.  Álapítsuk meg, található-e olyan $i$ és $j$
argumentum, amire $f(i)+g(j)=k$!

A megoldás az lesz, hogy a egy lin. ker. 2.8-cal megállapítjuk, hogy
van-e olyan $f(i)$, amihez található jó $g(j)$.  A jó $g(j)$
megtalálása adott $f(i)$-hez pedig lin. ker. 3-ra vezethető vissza,
ugyanis nem kell elmenni $g$ értelmezési tartományának a végéig, hanem
ha $f(i)+g(j)>k$, akkor már megállhatunk hamis eredménnyel.  Ugyanez a
trükk az $f$ esetében nem süthető el, hiába monoton nő, hiszen lehet,
hogy $g$ negatív értékeket is tartalmaz.

Sepcifiáljuk először a $g$-ben való keresésre vonatkozó feladatot: a
$j$ értéket keressük, úgy, hogy $f(i+1)+g(j)=k$ igaz legyen rögzített
$k$-ra és $i$-re.

\emph{Specifikáció:}\\
$f\colon[m,n]\to\Z, g\colon[o,p]\to\Z$ \\
$A = \alatt{\Z}{o} \times \alatt{\Z}{p} \times \alatt{\Z}{i} \times \alatt{\Z}{k} \times \alatt{\L}{l}$\\
$B = \alatt{\Z}{o'} \times \alatt{\Z}{p'} \times \alatt{\Z}{i'} \times \alatt{\Z}{k'}$\\
$Q = ( o=o' \es p=p' \es o\le p+1 \es \forall j\in[o,p-1]: g(j+1)\ge g(j) \es \exists j\ge o: \beta(j))$\\
$R = ( Q \es l=(\exists j\ge o: \gamma(j) \es \forall x\in[m..j-1]: \nem \delta(x)))$, ahol
\begin{align*}
  \gamma(j)&:=(f(i+1)+g(j)=k) \\
  \delta(j)&:=(j>p \vagy f(i+1)+g(j)>k) \\
  \beta(j)&:=\gamma(j) \vagy \delta(j)
\end{align*}

Visszavezetés a lin. ker. 3-ra, alteres általánosított (a tétel $i$
értékére nem vagyunk kiváncsiak).  Paraméteres $p$, $i$ és $k$
szerint.  Valamint általánosított is, ugyanis a lin. ker. 3. tételben
nem szerepel az előfeltételben egy függvényről az a kikötés, hogy monoton nő.

\begin{tabular}{rcl}
  \parbox{4cm}{
    \begin{tabular}{ccc}
      feladat &  & lin. ker. 3 \\
      \hline
      $-\quad (j)$ & \knyil & $i$ \\
      $o$ & \knyil & $m$ \\
      $l$ & \knyil & $u$
    \end{tabular}
  } & \parbox{7cm}{
  \begin{stukibox*}[7cm]{$l$:=vanjó$g(i+1)$}
    \stm{j,l,v:=o-1, \hamis, \hamis}
    \begin{WHILE}{4}{\stm{\nem l\es \nem v}}
      \stm[3]{\quad l,v:= \hfill \\
        f(i+1)+g(j+1)=k, \\
        j+1>p \vagy f(i+1)+g(j+1)>k}
      \stm{j:=j+1}
    \end{WHILE}
  \end{stukibox*}} & \parbox[c]{5cm}{A tételben szereplő $i$-t át
  kellett nevezni $j$-re, ugyanis $i$ a feladat paramétere.}
\end{tabular}

Ezzel a részprogrammal már könnyű:

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{k} \times \alatt{\L}{l}$\\
$B = \alatt{\Z}{m'} \times \alatt{\Z}{n'} \times \alatt{\Z}{k'}$\\
$Q = ( m=m' \es n=n' \es m\le n+1 \es k=k' \es \forall i\in [m,n-1]: f(i+1)\ge f(i))$\\
$R = ( Q \es l=(\exists i\in[m,n]: \text{vanjó}g(i)))$

\begin{tabular}{ccc}
  feladat &  & lin. ker. 2.8 \\
  \hline
  vanjó$g(i)$ & \knyil & $\beta(i)$ \\
\end{tabular}

A visszavezetés paraméteres $k$ szerint, valamint alteres
általánosított $i$ szerint és általánosított az $f$ függvény monoton
növekedése miatt.

\begin{stuki}[5cm]
  \stm{i,l:=m-1,\hamis}
  \begin{WHILE}{2}{\stm{\nem l \es t\ne n}}
    \stm{l:=\text{vanjó}g(i+1)}
    \stm{j:=j+1}
  \end{WHILE}
\end{stuki}

\end{document}