\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{Alapvető programozási tételek}
\begin{document}
\noindent
\emph{Összegzés}

$f:\Z\nyil\Z$, $[m..n]\subset\Z$

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{s}( \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 s=\sum\limits_{i=m}^n f(i))$

\begin{stuki}
  \stm{k,s:=m-1,0}
  \begin{WHILE}{2}{\stm{k \ne n}}
    \stm{s:=s+f(k+1)}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\clearpage

\emph{Számlálás}

$\beta : \Z \nyil \L$, $[m..n]\subset\Z$

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\N_0}{d}( \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 d=\sum\limits_{i=m}^n \chi(\beta(i)))$

\begin{stuki}
  \stm{k,d:=m-1,0}
  \begin{WHILE}{3}{\stm{k \ne n}}
    \begin{IF}{1}{\stm{\beta(k+1)}}
      \stm{d:=d+1}
      \ELSE
      \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

\clearpage

\emph{Maximumkeresés}

$\mathcal{H}$ rendezett halmaz és $f : \Z \nyil \mathcal{H}$, $[m..n]\subset\Z$

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{i} \times \alatt{\mathcal{H}}{\max}( \times \alatt{\Z}{k})$\\
$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=f(i)\es \forall j\in [m..n]: f(j)\le f(i))$

\begin{stuki}
  \stm{i,k,\max:=m,m,f(m)}
  \begin{WHILE}{3}{\stm{k \ne n}}
    \begin{CASE}{1}{2}
      \WHEN{\stm{f(k+1)\ge \max}}
      \stm{i,\max:=k+1,f(k+1)}
      \WHEN{\stm{f(k+1)\le \max}}
      \SKIP
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Alteres általánosításainak esetei:
\begin{itemize}
  \item Ha a $\max$ nincs a feladat állapotterében:\\
    $\begin{array}{rcl}
      R_{\text{tétel}} & = & ( Q \es i\in [m..n] \es \max=f(i)\es \forall j\in [m..n]: f(j)\le f(i)) \\
      \Downarrow \\
      R  & = & ( Q \es i\in [m..n] \es \forall j\in [m..n]: f(j)\le f(i))
    \end{array}$
  \item Ha az $i$ nincs a feladat állapotterében:\\
    $\begin{array}{rcl}
      R_{\text{tétel}} & = & ( Q \es i\in [m..n] \es \max=f(i)\es \forall j\in [m..n]: f(j)\le f(i)) \\
      \Downarrow \\
      R  & = & ( Q \es \exists i\in [m..n]: (\max=f(i) \es \forall j\in [m..n]: f(j)\le f(i))) \\
    \end{array}$

\end{itemize}

\clearpage

\emph{Feltételes maximumkeresés}

$\mathcal{H}$ rendezett halmaz és $f : \Z \nyil \mathcal{H}$, $\beta: \Z\nyil\L$, $[m..n]\subset\Z$

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{i} \times \alatt{\mathcal{H}}{\max} \times \alatt{\L}{l}( \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 l=(\exists i\in [m..n]:\beta(i)) \es l\nyil(i\in[m..n]\es\beta(i)\es \max=f(i)\es \forall j\in [m..n]: \beta(j)\nyil (f(j)\le f(i))))$

\begin{stuki}[16cm]
  \stm{k,l:=m-1,\hamis}
  \begin{WHILE}{4}{\stm{k \ne n}}
    \begin{CASE}{2}{9}
      \WHEN[1]{\stm{\nem\beta(k+1)}}
      \SKIP
      \WHEN[3]{\stm{\beta(k+1)\es\nem l}}
      \stm{l,i,\max:=\igaz,k+1,f(k+1)}
      \WHEN[5]{\stm{\beta(k+1) \es l}}
      \begin{CASE}{1}{2}
        \WHEN{\stm{f(k+1)\ge \max}}
        \stm{i,\max:=k+1,f(k+1)}
        \WHEN{\stm{f(k+1)\le \max}}
        \SKIP
      \end{CASE}
    \end{CASE}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Alteres általánosításainak esetei:
\begin{itemize}
  \item Ha a $\max$ nincs a feladat állapotterében:\\
    $\begin{array}{rcl}
      R_{\text{tétel}} & = & ( Q \es l=(\exists i\in [m..n]:\beta(i)) \es l\nyil(i\in[m..n]\es\beta(i)\es \max=f(i)\es \forall j\in [m..n]: \beta(j)\nyil (f(j)\le f(i)))) \\
      \Downarrow \\
      R & = & ( Q \es l=(\exists i\in [m..n]:\beta(i)) \es l\nyil(i\in[m..n]\es\beta(i)\es \forall j\in [m..n]: \beta(j)\nyil (f(j)\le f(i)))) \\
    \end{array}$
  \item Ha az $i$ nincs a feladat állapotterében:\\
    $\begin{array}{rcl}
      R_{\text{tétel}} & = & ( Q \es l=(\exists i\in [m..n]:\beta(i)) \es l\nyil(i\in[m..n]\es\beta(i)\es \max=f(i)\es \forall j\in [m..n]: \beta(j)\nyil (f(j)\le f(i)))) \\
      \Downarrow \\
      R  & = & ( Q \es l=(\exists i\in [m..n]:\beta(i)) \es l\nyil(\exists i\in[m..n]:(\beta(i)\es \max=f(i)\es \forall j\in [m..n]: \beta(j)\nyil (f(j)\le f(i)))))
    \end{array}$
\end{itemize}

\clearpage

\emph{Lineáris keresés 1.0}\\
$\beta:\Z\nyil\L$\\
$A = \alatt{\Z}{m}  \times \alatt{\Z}{i}$\\
$B = \alatt{\Z}{m'}$\\
$Q = ( m=m' \es \exists j\ge m:\beta(j) )$\\
$R = ( Q \es i\ge m \es \beta(i) \es \forall j\in[m..i-1]:\nem\beta(j))$
\begin{stuki}
  \stm{i:=m}
  \begin{WHILE}{1}{\stm{\nem\beta(i)}}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

\emph{Lineáris keresés 2.0}\\
$A = \alatt{\Z}{m}  \times \alatt{\Z}{i}( \times \alatt{\L}{l})$
\begin{stuki}
  \stm{i,l:=m-1,\hamis}
  \begin{WHILE}{2}{\stm{\nem l}}
    \stm{l:=\beta(i+1)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

\emph{Lineáris keresés 3.0}: $\beta = \gamma \vagy \delta$\\
$A = \alatt{\Z}{m}  \times \alatt{\Z}{i} \times \alatt{\L}{u}( \times \alatt{\L}{v})$\\
$Q = ( m=m' \es \exists j\ge m:\beta(j) )$\\
$R = ( Q \es u=(\exists j\ge m: \gamma(j)\es\forall k\in[m..j-1]:\nem\delta(k)) \es
u\nyil(i\ge m \es \gamma(i)\es \forall j\in[m..i-1]:\nem\beta(j)))$

\begin{stuki}
  \stm{i,u,v:=m-1,\hamis,\hamis}
  \begin{WHILE}{2}{\stm{\nem u \es \nem v}}
    \stm{u,v:=\gamma(i+1),\delta(i+1)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

\clearpage

\emph{Lineáris keresés 2.8}: Lin. ker. 3.0, de $\delta = $ nem értük el $n$-et\\
$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\Z}{i} \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=(\exists j\in [m..n]: \beta(j))  \es
l\nyil(i\in [m..n] \es \beta(i)\es \forall j\in[m..i-1]:\nem\beta(j)))$

\begin{stuki}
  \stm{i,l:=m-1,\hamis}
  \begin{WHILE}{2}{\stm{\nem l \es i \ne n}}
    \stm{l:=\beta(i+1)}
    \stm{i:=i+1}
  \end{WHILE}
\end{stuki}

Általánosításának tipikus esetei:
\begin{itemize}
  \item Ha az $i$ nincs a feladat állapotterében (alteres):\\
    $\begin{array}{rcl}
      R_{\text{tétel}} & = & ( Q \es l=(\exists j\in [m..n]: \beta(j)) \es l\nyil(i\in [m..n] \es \beta(i)\es \forall j\in[m..i-1]:\nem\beta(j))) \\
      \Downarrow \\
      R & = & ( Q \es l=(\exists j\in [m..n]: \beta(j)) \es l\nyil(\exists i\in [m..n]: \beta(i)\es \forall j\in[m..i-1]:\nem\beta(j))) \\
        & = & ( Q \es l=(\exists j\in [m..n]: \beta(j)))
    \end{array}$
  \item Ha nem követeljük meg, hogy az első megfelelő értéket találjuk meg:\\
    $\begin{array}{rcl}
      R_{\text{tétel}} & = & ( Q \es l=(\exists j\in [m..n]: \beta(j)) \es l\nyil(i\in [m..n] \es \beta(i)\es \forall j\in[m..i-1]:\nem\beta(j))) \\
      \Downarrow \\
      R & = & ( Q \es l=(\exists j\in [m..n]: \beta(j)) \es l\nyil(i\in [m..n] \es \beta(i)))
    \end{array}$
\end{itemize}

\clearpage

\emph{Logaritmikus keresés}: 
$\mathcal{H}$ halmazon van egy rendezési reláció és $f:\Z\nyil\mathcal{H}$ monoton növekedő., 
$[m..n]\subset\Z$.

$A = \alatt{\Z}{m} \times \alatt{\Z}{n} \times \alatt{\mathcal{H}}{h} \times \alatt{\Z}{i} \times \alatt{\L}{l}( \times \alatt{\Z}{u} \times \alatt{\Z}{v})$\\
$B = \alatt{\Z}{m'} \times \alatt{\Z}{n'} \times \alatt{\mathcal{H}}{h'}$\\
$Q = ( m=m' \es n=n' \es h=h')$\\
$R = ( Q \es l=(\exists j\in [m..n]: f(j)=h)  \es
l\nyil(i\in [m..n] \es f(i)=h))$

\begin{stuki}
  \stm{u,v,l:=m,n,\hamis}
  \begin{WHILE}{3}{\stm{\nem l \es u \le v}}
    \stm{i:=\lceil(u+v)/2\rceil}
    \begin{CASE}{1}{3}
      \WHEN{\stm{f(i)<h}}
      \stm{u:=i+1}
      \WHEN{\stm{f(i)=h}}
      \stm{l:=\igaz}
      \WHEN{\stm{f(i)>h}}
      \stm{v:=i-1}
    \end{CASE}
  \end{WHILE}
\end{stuki}
\end{document}