% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{2. feladatsor, 59. feladat}
\begin{document}
\noindent
\emph{Feladat:} Keressük meg a négyzetes $t$ mátrixnak azt az
oszlopát, amelyben a fődiagonális feletti elemek összege a legnagyobb!

\emph{Specifikáció:}\\
$\M = \vect([0..N-1], \vect([0..N-1], \Z))$ \\
$A = \alatt{\M}{t} \times \alatt{\N_0}{i}$\\
$B = \alatt{\M}{t'}$\\
$Q = ( t=t' )$\\
$R = ( Q \es i\in[0,N-1] \es \forall j\in[0,N-1]:\text{oszloposszeg}(j,t)\le\text{oszloposszeg}(i,t))$

Visszavezetés a maximum keresésre, alteres általánosított ($max$) és konstanssal helyettesítéses is ($m=0, n=N-1$).

\begin{tabular}{ccc}
  feladat &  & max. ker. \\
  \hline
  $0$ & \knyil & $m$ \\
  $N-1$ & \knyil & $n$ \\
  $\text{oszloposszeg}(i,t)$ & \knyil & $f(i)$
\end{tabular}

Megjegyzés: $\forall t\in\M: \text{oszloposszeg}(0,t)=0$.

\begin{stuki}[7cm]
  \stm{i,k,max:=0,0,0}
  \begin{WHILE}{4}{\stm{k\ne N-1}}
    \stm{z:=\text{oszloposszeg}(k+1,t)}
    \begin{IF}{1}{\stm{z > max}}
    \stm{i,max:=k+1,z}
    \ELSE
    \SKIP
    \end{IF}
    \stm{k:=k+1}
  \end{WHILE}
\end{stuki}

Most specifikáljuk és vezessük vissza összegzésre (konstanssal való
helyettesítésekkel) a $z:=\text{oszloposszeg}(k+1,t)$ nem megengedett
értékadást:

$A' = \alatt{\M}{t} \times \alatt{\N_0}{i} \times \alatt{\N_0}{k} \times \alatt{\Z}{z}$\\
$B' = \alatt{\M}{t'} \times \alatt{\N_0}{i'} \times \alatt{\N_0}{k'}$\\
$Q' = ( t=t' \es k=k' \es i=i' )$\\
$R' = ( Q \es z=\sum\limits_{i=0}^{k+1-1}m_{{i}_{k+1}})$

\begin{tabular}{ccc}
  feladat &  & összegzés \\
  \hline
  $0$ & \knyil & $m$ \\
  $k$ & \knyil & $n$ \\
  $m_{i_{k+1}}$ & \knyil & $f(i)$ \\
  $j$ & \knyil & $k$
\end{tabular}

\begin{stuki}[7cm]
  \stm{j,z:=-1,0}
  \begin{WHILE}{2}{\stm{j\ne k}}
    \stm{z:=z+m_{{j+1}_{k+1}}}
    \stm{j:=j+1}
  \end{WHILE}
\end{stuki}

\end{document}