\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, felt. max. ker. \nyil max. ker.}
\begin{document}
\noindent
\emph{Feladat:} Adott az $[m,n]$ intervallumon �rtelmezett $\beta$ logikai �rt�k� �s $f$ eg�sz �rt�k� f�ggv�ny.
\[
g:\Z\nyil\L\times\Z, \quad\forall i\in[m,n]:g(i):=(\beta(i), f(i))
\]

A $\L\times\Z$ halmaz elemei �sszehasonl�that�ak: akkor �s
csak akkor legyen egy $a=(a_1, a_2)$ elem nagyobb vagy egyenl� egy
$b=(b_1, b_2)$ elemn�l, ha $a_1$ igaz �s $b_1$ hamis vagy $a_1$
�s $b_1$ is igaz, de $a_2\ge b_2$.

Keress�k meg a $g$ legnagyobb �rt�k�t �s a hozz� tartoz� argumentumot
az $[m,n]$ intervallumon!


\emph{Specifik�ci�:}\\
$\mathbb D=(\L:l, \Z:z)$ rekord, �gy $g$ felfoghat�, mint $g:\Z\nyil\mathbb D$ f�ggv�ny.\\
$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\mathbb D}{\max} \times \alatt{\Z}{i}$ \\
$B = \alatt{\Z}{m'} \times \alatt{\Z}{n'}$ \\
$Q = ( m=m' \es n=n' \es m\le n)$ \\
$R = ( Q \es i\in [m,n] \es \max=g(i) \es \forall j\in[m,n]: g(j)\le \max)$

\begin{tabular}{cccl}
  feladat &  & max. ker. & \\
  \hline
  $g(i)$ & \knyil & $f(i)$
\end{tabular}

A visszavezet�s term�szetes.

\begin{stuki}
  \stm{k,i,\max := m,m,(\beta(m),f(m))}
  \begin{WHILE}{3}{\stm{k\ne n}}
    \begin{IF}[70]{1}{\stm{\beta(k+1) \es \nem \max.l \vagy \beta(k+1) \es \max.l \es f(k+1)\ge \max.z}}
      \stm{i,\max:=k+1, (\beta(k+1),f(k+1))}
      \ELSE
      \SKIP
    \end{IF}
    \stm{j:=j+1}
  \end{WHILE}
\end{stuki}

Helyettes�ts�k a max rekordkomponenst k�t v�ltoz�val $l$-lel �s
max-szal, valamint vegy�k �szre, hogy az el�gaz�s igaz �g�ban
$\beta(k+1)$ sz�s�gszer�en igaz!  Alak�tsunk egy kicsit a felt�telen
is, emelj�nk ki $\beta(k+1)$-et!

\begin{stuki}
  \stm{k,i,l,\max := m,m,\beta(m),f(m)}
  \begin{WHILE}{3}{\stm{k\ne n}}
    \begin{IF}[70]{1}{\stm{\beta(k+1) \es (\nem l \vagy l \es f(k+1)\ge \max)}}
      \stm{i,l,\max:=k+1, \igaz,f(k+1)}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Vigy�zat, a $\nem l \vagy l$ nem hagyhat� el a precedencia sorrend
miatt, az ``�s'' er�sebben k�t!

A kit�z�tt feladat l�nyeg�ben a felt�teles maximumkeres�s �s a kapott
program is nagyon hasonl�t hozz�.  K�l�nbs�g, hogy mivel
maximumkeres�sre vezett�nk vissza, a program �res intervallumon nem
m�k�dik, az el�felt�tel meg is k�veteli, hogy legal�bb egy eleme
legyen az intervallumnak.  Ez persze nem l�nyeges megszor�t�s, �gy
�rdekes eredm�ny, hogy a maximumkeres�s tekinthet� olyan �ltal�nosnak,
mint a felt�teles v�ltozata.  Trivalit�s, hogy a m�sik ir�ny is
teljes�l (konstans igaz $\beta$ f�ggv�nnyel), �gy a k�t feladat
ekvivalens, ami az egyikre visszavezethet�, biztos, hogy a m�sikra is
(esetleg kev�sb� praktikusan).

\end{document}
