% Time-stamp: <Fri Aug 15 09:43:22 2003  nho@giga.simon>   

\documentclass[25pt,landscape]{foils}
%\documentclass[30pt,landscape]{foils}

%\documentclass[25pt,reportclass,landscape]{powersem}

%% \documentclass[25pt,landscape]{report} 
%\documentclass[semcolor,portrait]{seminar} 
\input{frente-apresentacao}
%\listfiles{}

\newcommand{\ppause}{}

\begin{document}

\title{\color{red}MAC e MVC em tempo $\langle O(n),O(1) \rangle$}
\author{\color{in}Alair Pereira do Lago \and \color{in} Imre Simon}
\date{\color{out}Julho de 2003\\Colóquio Brasiliero de Matemática}

\maketitle
\thispagestyle{empty}
\LogoOff

\begin{list1}

%\bfseries
\section{Apresentação}
\label{cha:prefacio}

\item A combinatória das palavras é área bastante rica e diversas
aplicações têm se desenvolvido ao longo dos anos auxiliando áreas da Matemática como 

\begin{list2}
\item teoria dos grupos, dos semigrupos,
\item autômatos e linguagens formais
\item desenvolvimento de algoritmos \ppause
que possibilitem a \IN{análise}, \IN{processamento} e \IN{extração de informações} em \IN{seqüências cada vez mais compridas},\ppause
  \begin{list3}
    \item textos disponíveis na internet\ppause
    \item bibliotecas digitais\ppause
    \item seqüências genômicas
  \end{list3}
\end{list2}

\item \emph{algoritmos eficientes} têm sido cada vez mais
requisitados.  

\section{O problema do Menor Ancestral Comum em Árvores}
\label{cha:MenorAncestralComum}


\item 
Dado um vértice $u$ de uma árvore existe um único caminho da raiz até
$u$. 
\ppause\item Qualquer vértice neste caminho é dito um {\em ancestral} de $u$.

\ppause\item Dados dois vértices, $u$ e $v$ numa árvore, eles sempre tem ancestrais
comuns dado que a raiz é um exemplo de um ancestral comum.

\ppause\item \emph{Denominamos de {\em menor
ancestral comum} de $u$ e $v$ o ancestral comum de $u$ e de $v$ que seja
a mais distante da raiz}. 
\begin{list2}
  
\ppause\item 
(O adjetivo menor refere-se ao ancestral comum ``menos antigo'' de $u$ e de $v$).

\ppause\item  Denotaremos por $\MAC{u}{v}$ o menor ancestral comum
de $u$ e $v$. 

\end{list2}


\section{Exemplos de \MACsym s}
\label{sec:Exemplos de MACs}
\begin{figure}[htbp]
  \centering
  \includegraphics[scale=1.5]{figs/fig-101}
%  \caption{Árvore $\grafo T$ para ilustrar o problema do menor ancestral comum}
  \label{fig:ExemploParaMAC}
\end{figure}

\item Por exemplo, na Figura~\ref{fig:ExemploParaMAC}:
\[\MAC{w}{y}=u,\quad\MAC{s}{z}=p,\quad\MAC{o}{z}=m.\]


\section{Notação de complexidade com pré-processamento}
\label{sec:notacao de complexidade com pre-processamento}



\item Os algoritmos do nosso interesse terão
sempre duas partes bem distintas e sua complexidade será expressa em
termos de um \emph{par ordenado de complexidades}, como por exemplo em $\langle O(n),O(1) \rangle$.


\ppause\item A \emph{primeira} complexidade, $O(n)$ no caso, refere-se ao tempo usado por 
um algoritmo de \emph{pré-processamento}.


\ppause\item A \emph{segunda} componente, $O(1)$ no caso,
refere-se ao tempo usado para \emph{responder uma instância do problema}, dado que o
pré-processamento foi feito (e suas estruturas de dados estão
disponíveis).

\ppause\item 
Desta forma, uma solução $\langle O(n),O(1) \rangle$ do problema de MAC
implica que a árvore de $n$ vértices sofre um pré-processamento linear. A
partir deste pré-processamento qualquer instância do problema pode ser
resolvida em tempo constante ($O(1)$), independente do tamanho da árvore.


\section{Reflexão sobre solução  $\langle O(n),O(1) \rangle$}
\label{sec:Replexao sobre solucao <O(n),O(1)>}


\item Daremos as idéias principais que embasam uma solução  
$\langle O(n),O(1) \rangle$ do problema do Menor ancestral comum.

\item Vale a pena refletir sobre este resultado...

\ppause\item Pré-processamento que demora um \emph{tempo constante em cada vértice} da árvore
dada. 
\ppause\item Faz-se anotações que poderão ser
consultadas mais adiante. Tabelas de tamanho
$O(n)$. 
\ppause\item Feito o pré-processamento, qualquer instância do
problema pode ser respondida em tempo constante, qualquer que tenha sido o
tamanho da árvore envolvida.

\section{Busca em profundidade de árvores}
\label{sec:Percurso}


\item Dada uma árvore $\grafo T$ com $n$ vértices, calculamos  um vetor
com $m=2n-1$ vértices, que descreve, passo a passo, a busca em profundidade de
$\grafo T$. 
\ppause\item Chamaremos este vetor de $\Buscasym$, estando o grafo $\gT$
subentendido.
\ppause\item
O índice dos
elementos serve também como um parâmetro de ``cronometragem'' do algoritmo da
busca em profundidade: se $\lB{i}=u$ então dizemos que a busca visitou o
vértice $u$ no instante $i$.

\ppause\item  Calcularemos, também, o vetor $\Profsym$, indexado de $1$ a $m$, cujos elementos serão,
respectivamente, as profundidades dos vértices em $\Buscasym$.


\ppause\item   Registraremos em $\lD{u}$ o instante da primeira
visita ao vértice $u$ e em $\lA{u}$ o instante da última visita a $u$. Estes
instantes são, respectivamente, a {\em descoberta} e o {\em abandono} de $u$.

%% \ppause\item Estes cálculos serão feitos no Algoritmo~\ref{alg:Busca} em tempo e espaço
%% $O(n)$. Eles permitirão reduzir, na seção seguinte, o problema do Menor
%% Ancestral Comum a um outro problema, aparentemente mais simples: o problema do
%% Mínimo de um Vetor Contínuo, a ser abordado na próxima seção.

%% \newpage{}

%% \begin{algorithm}[htbp]
%%   \caption{Busca em profundidade da árvore $\gT$}
%%   \label{alg:Busca}
%%   \begin{algo}{\BuscaEmProfundidadesym}{\grafo T}
%%     \COM{$\Descsym$, $\Abansym$ e $A$ são vetores indexados pelos vértices de
%%     ${\gT}$} 
%%     \COM{$\Buscasym$ e $\Profsym$ são indexados pela ``cronometragem'' do
%%     algoritmo} 
%%     \DOFOR{u\in V} \label{busca:ini-a}
%%       \SET {A[u]} {\Primog u }
%%       \RCOM{5}{$A[u]$: filho não descoberto de $u$}
%%     \OD
%%     \SET v {\Raiz {\grafo T}}
%%     \SET i 1
%%     \SET {\lB{i}} v
%%     \SET {\lP{i}} 0
%%     \SET {\lD{v}} 1
%%     \DOWHILE{ \PaiA v \neq \Nil \Or A[v] \neq \Nil }
%%       \SET i {i+1}
%%       \IF{ A[v] \neq \Nil}
%%         \SET w {A[v]}
%%         \RCOM{5}{Descemos}
%%         \SET {\lP{i}} {\lP{i-1}+1}
%%         \SET {\lD{w}} i
%%         \RCOM{5}{Registramos a descoberta de $w$}
%%         \SET {A[v]} {\IrmaoA {A[v]} }
%%         \RCOM{5}{Novo filho não descoberto de $v$}
%%       \ELSE {}
%%         \SET w {\PaiA v }
%%         \RCOM{5}{Subimos}
%%         \SET {\lP{i}} {\lP{i-1}-1}
%%         \SET {\lA{v}} {i-1}
%%         \RCOM{5}{Registramos o abandono de $v$}
%%       \FI
%%       \SET v w
%%       \SET {\lB{i}} v
%%     \OD
%%     \SET {\lm} i
%%     \SET {\lA{v}} {\lm}
%%     \RETURN{(\lm,\Buscasym,\Profsym,\Descsym,\Abansym)}
%%   \end{algo}
%% \end{algorithm}



%% A Busca em Profundidade de um grafo é um algoritmo clássico nas Teorias dos
%% Grafos e da Computação. O seu estudo detalhado está fora do escopo deste livro;
%% suporemos que o leitor está familiarizado com os conceitos envolvidos. Uma
%% excelente referência é o Capítulo~23, ``Elementary Graph Algorithms'' do livro
%% de Cormen, Leiserson e Rivest~\cite{MR91i:68001}.

%% %CormenLR90 = MR91i:68001

%% A nossa busca em profundidade inicia-se no instante $1$ na raiz da árvore
%% $\gT$. Em cada instante a busca está visitando um vértice; se no instante $i$
%% o vértice visitado é $v$ então teremos
%% \[ \lB{i}=v. \]
%% Escolhe-se o próximo vértice a ser visitado de acordo com os critérios abaixo:
%% \begin{enumerate}
%%   \item Se $v$ tiver algum filho, $u$, ainda não visitado então visita-se $u$
%%     a seguir; isto corresponde a percorrer a aresta $\num{u,v}$ na direção de
%%     afastar-se da raiz, i.e. descemos a aresta $\num{u,v}$.

%%   \item Se todos os filhos de $v$ já foram visitados e $v$ não é a raiz da
%%     árvore então (re)visita-se a seguir $\PaiA{v}=u$; isto corresponde a
%%     percorrer a aresta  $\num{u,v}$ na direção de aproximar-se da raiz,
%%     i.e. subimos a aresta $\num{u,v}$.

%%   \item Se todos os filhos de $v$ já foram visitados e $v$ é a raiz de $\gT$,
%%     isto é,  $\PaiA{v}=\Nil$,  então a busca terminou. Guardamos o
%%     instante do término em $m$.
%% \end{enumerate}
%% Não é difícil ver que a busca em profundidade da árvore $\gT$ percorrerá cada
%% aresta da árvore duas vezes, uma vez em cada direção: afastando-se e
%% a\-pro\-xi\-man\-do-se da raiz. Como a árvore tem $n-1$ arestas, a busca
%% termina no instante $m=2n-1$, na raiz de $\gT$.
%% Esta observação garante que a complexidade do Algoritmo~\ref{alg:Busca},
%% $\BuscaEmProfundidadesym$, é $O(n)=O(m)$.

%% Os vetores $\Descsym$ e $\Abansym$ são indexados pelos vértices de $\gT$. O
%% valor de $\lD{u}$ é o instante da primeira visita a $u$. O de $\lA{u}$ é o
%% instante da última visita a $u$. Veremos adiante que os
%% intervalos\footnote{Todos os intervalos que consideraremos neste capítulo
%%   serão fechados e como de costume serão denotados por $[a\Rng b]$}
%% $[\lD{u}\Rng\lA{u}]$ impõem uma estrutura de parênteses no histórico da busca em
%% profundidade.

%% Acompanhando o cálculo de $\lB{i}$ registramos também, em $\lP{i}$ a
%% profundidade do vértice visitado no instante $i$. Note que valores
%% consecutivos deste vetor variam de $\pm1$, já que em cada instante da busca ou
%% subimos ou descemos uma aresta. Esta propriedade será fortemente explorada a
%% seguir. Note, também, que as computações podem ser usadas para determinar, em
%% tempo $O(1)$, a profundidade dos vértices. De fato, a profundidade do vértice
%% $u$ é dada por
%% \[ \lP{\lD{u}} \mbox{\quad ou\quad } \lP{\lA{u}}. \]

%% Exemplificamos os conceitos e procedimentos acima com a árvore da
%% Figura~\ref{fig:ExemploParaMAC}.
%% Numa busca em profundidade, usando a representação da
%% Tabela~\ref{tab:arvore}, os vértices de $\gT$ são descobertos na ordem
%% abaixo, que (não por acaso) é a lista dos nomes dos vértices em ordem
%% alfabética: 

%% \[ m,n,o,p,q,r,s,t,u,v,w,x,y,z. \]

\section{Exemplo de busca em profundidade}
\label{sec:Exemplo de busca em profundidade}

\item 
\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{|c|cccc|cccc|} \hline
$i$ &
$1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\ \hline
$\lB{i}$ &
$m$ & $n$ & $o$ & $n$ & $m$ & $p$ & $q$ & $r$ \\
$\lP{i}$ &
$0$ & $1$ & $2$ & $1$ & $0$ & $1$ & $2$ & $3$ \\ \hline
    \end{tabular}
{}\\[1ex]    
    \begin{tabular}{|c|cccc|cccc|} \hline
$i$ &
$9$ & $10$ & $11$ & $12$ & $13$ & $14$ & $15$ & $16$ \\ \hline
$\lB{i}$ &
$q$ & $s$  & $q$  & $p$ & $t$  & $p$  & $u$  & $v$ \\
$\lP{i}$ &
$2$ & $3$  & $2$  & $1$ & $2$  & $1$  & $2$  & $3$ \\ \hline
    \end{tabular}
{}\\[1ex]    
    \begin{tabular}{|c|cccc|cccc|ccc|} \hline
$i$ &
$17$ & $18$ & $19$ & $20$ & $21$ & $22$ & $23$ & $24$ & $25$ & $26$ & $27$ \\ \hline
$\lB{i}$ &
$u$  & $w$  & $u$  & $x$  & $y$  & $x$  & $z$  & $x$  & $u$  & $p$  & $m$ \\
$\lP{i}$ &
$2$  & $3$  & $2$  & $3$  & $4$  & $3$  & $4$  & $3$  & $2$  & $1$  & $0$ \\ \hline
    \end{tabular}
{}\\[3ex]
    \begin{tabular}{|c|cc|cc|cc|cc|cc|cc|cc|} \hline
$\bf{v}$ &
$m$ & $n$ & $o$ & $p$ & $q$ & $r$ & $s$ & $t$ & $u$ & $v$ & $w$ & $x$ & $y$ & $z$ \\ \hline
$\lD{\bf{v}}$ &
$1$ & $2$ & $3$ & $6$ & $7$ & $8$ & $10$ & $13$ & $15$ & $16$ & $18$ & $20$ &
$21$ & $23$ \\ %\hline
$\lA{\bf{v}}$ &
$27$ & $4$ & $3$ & $26$ & $11$ & $8$ & $10$ & $13$ & $25$ & $16$ & $18$ & $24$ &
$21$ & $23$ \\ \hline
    \end{tabular}
  \end{center}
%  \caption{\label{tab:busca}
%           Histórico e profundidades dos vértices visitados na busca em
%           profundidade da árvore $\gT$.}
\end{table}


%% Uma propriedade fundamental da busca em profundidade é dada pelo Teorema dos
%% Parênteses~\cite[página 480]{MR91i:68001} que no nosso contexto, já
%% especializado para a busca em profundidade de árvores, exploradas a partir da
%% sua raiz, pode ser assim enunciado:



\section{Um novo problema}
\label{sec:NovoProblema}

%% Apresentamos um problema, relacionado ao cálculo de
%% $\MAC{u}{v}$ através da redução acima, e cuja solução eficiente vai levar à
%% solução procurada para o problema original.


\item Seja $V[1\Rng m]$ um vetor de $m$ números inteiros. Dizemos que o vetor $V$ é
{\em contínuo} se a diferença entre elementos consecutivos do vetor é $\pm1$,
isto é, para cada $i$, $1<i\le m$, $|V[i]-V[i-1]|=1$.

%% Vetores contínuos de $m$ elementos estão em correspondência biunívoca com
%% fatores de comprimento $m-1$ de palavras balanceadas de parênteses, isto segue
%% das propriedades da linguagem de Dyck, estudadas na Teoria de Linguagens
%% Livres de Contexto, ou das propriedades dos números de Catalan, estudadas em
%% Combinatória. Estas ligações são irrelevantes para o nosso problema (são mesmo?),
%% por isto não entraremos mais a fundo nestas questões.


\ppause\item Dado um \emph{vetor contínuo $V[1\Rng m]$},
pré-processamos $V$ para responder, em tempo
constante, a pergunta: \emph{dados índices $i$ e $j$, $1\le i\le j\le m$, qual é a
posição do elemento mínimo do intervalo $V[i\Rng j]$?}

\ppause\item  Denotamos por
$\MVC{i}{j}$ uma posição do mínimo procurado.
$\MVCsym$ satisfaz
\begin{quote}
$i \le \MVC{i}{j}\le j$,\\
$ \lV{\MVC{i}{j}} =  \min\num{\lV{i},\lV{i+1},\ldots,\lV{j}}$.
\end{quote}


\section{Exemplo para \MVCsym}
\label{sec:Exemplo para MVC}


\item O vetor de profundidades $\lP{i}$ da Tabela~\ref{tab:busca} é um exemplo de um
vetor contínuo.  Usaremos ele para exemplificar o novo problema: notamos que
\[\MVC{18}{21}=19,\quad\MVC{10}{23}=12,\quad\MVC{3}{23}=5.\]

\ppause\item Os exemplos foram escolhidos para 
poder calcular
\[\MAC{w}{y}=u,\quad\MAC{s}{z}=p,\quad\MAC{o}{z}=m.\]


%% Mostraremos, a seguir, que existe um par de algoritmos de complexidade $\langle O(n),O(1)
%% \rangle$ para resolver o Problema do Mínimo de um Vetor
%% Contínuo. Este algoritmo, por sua vez, será usado na obtenção do resultado
%% principal do Capítulo.



%% \ppause\item Os algoritmos desta seção serão chamados de {\em intermediários} já que eles
%% situam-se entre os algoritmos ótimos, nosso objetivo, e os algoritmos
%% ingênuos.


\section{Propriedade Fundamental}
\label{sec:Propriedade Fundamental}



\item  
Sejam $[i\Rng j]$ e $[i'\Rng j']$ dois intervalos cuja união é o intervalo
$[i\Rng j']$.
  
\[( i<i'\le j<j'\mbox{\quad ou \quad} i\le j<j+1=i'\le j'.)\]

Os dois intervalos se sobrepõem ou são 
disjuntos.

\ppause\item Para todo vetor $V$ de números reais (pode não ser um vetor contínuo) 

\begin{equation}
  \min V[i\Rng j']=\min{\num{\min V[i\Rng j],\min V[i'\Rng j']}}.
  \label{eq:min} 
\end{equation}


\section{Mínimos de intervalos de comprimento $2^k$}
\label{sec:Minimos de Intervalos de comprimento 2^k}

\item Para usar a Propriedade~\ref{eq:min} pré-calcularemos a posição dos mínimos
em intervalos de $V$ cujo número de elementos são potências de
dois, ou seja, intervalos com 1, 2, 4, 8 ... elementos. 
\begin{list2}
  \ppause\item Para $i,j$ e
$k$ %\footnote{Note que os três parâmetros $i,j$ e $k$ são  dependentes. Quaisquer dois deles determina o terceiro.}
tais que $1\le i\le i+2^k-1=j\le m$ computaremos $\PosMin{i}{k} = t \in [i\Rng j] $ tal que $V[t]=\min V[i\Rng j]$.
Ou seja, teremos a identidade:
\[ \lV{\PosMin{i}{k}}=\min V[i\Rng j]. \]
\end{list2}


\ppause\item Computamos $\MVC{i}{j}$ (sejam $k=\Log{j-i+1}$ e $i'=j-2^k+1$) então 
\[ \MVC{i}{j}=\left\{
           \begin{array}{ll}
             \PosMin{i}{k}   &
             \mbox{se $\lV{\PosMin{i}{k}}\le\lV{\PosMin{i'}{k}}$}, \\
             \PosMin{i'}{k}  &   \mbox{caso contrário}.
           \end{array}
           \right.
\]


%\section{Cálculo de \PosMinsym\ }
%\label{sec:Calculo de PosMin}

\newpage{}

\item Computamos \PosMinsym\ pela recorrência (seja $i'=i+2^{k-1}$)
\[ \PosMin{i}{k}=\left\{
           \begin{array}{ll}
             i & \mbox{se $k=0$,} \\
             \PosMin{i}{k-1}   &
             \mbox{se $k>1$ e $\lV{\PosMin{i}{k}}\le\lV{\PosMin{i'}{k}}$}, \\
             \PosMin{i'}{k-1}  &   \mbox{se $k>1$ e $\lV{\PosMin{i}{k}}>\lV{\PosMin{i'}{k}}$}.
           \end{array}
           \right.
\]
%\ppause\item Exemplificamos a matriz $\PosMinsym$ com a Tabela~\ref{tab:tabelona} que
%corresponde ao nosso exemplo.
%Os números entre parênteses na Tabela são o extremo superior, $j$, dos
%respectivos intervalos envolvidos no cálculo de $\PosMin{i}{k}$.



% Tabelona de PosMin
% 
% i 1 2 3 4 5 6
% k=0 (1) 1 (2) 2 (3) 3 (4) 4 (5) 5 (6) 6
% k=1 (2) 1 (3) 2 (4) 4 (5) 5 (6) 5 (7) 6
% k=2 (4) 1 (5) 5 (6) 5 (7) 5 (8) 5 (9) 6
% k=3 (8) 1 (9) 5 (10) 5 (11) 5 (12) 5 (13) 6
% k=4 (16) 1 (17) 5 (18) 5 (19) 5 (20) 5 (21) 6
% 
% i 7 8 9 10 11 12
% k=0 (7) 7 (8) 8 (9) 9 (10) 10 (11) 11 (12) 12
% k=1 (8) 7 (9) 9 (10 9 (11) 11 (12) 12 (13) 12
% k=2 (10) 7 (11) 9 (12) 12 (13) 12 (14) 12 (15) 12
% k=3 (14) 12 (15) 12 (16) 12 (17) 12 (18) 12 (19) 12
% k=4 (22) 12 (23) 12 (24) 12 (25) 12 (26) 12 (27) 27
% 
% 1 13 14 15 16
% k=0 (13) 13 (14) 14 (15) 15 (16) 16
% k=1 (14) 14 (15) 14 (16) 15 (17) 17
% k=2 (16) 14 (17) 14 (18) 15 (19) 17
% k=3 (20) 14 (21) 14 (22) 15 (23) 17
% 
% 1 17 18 19 20
% k=0 (17) 17 (18) 18 (19) 19 (20) 20
% k=1 (18) 17 (19) 19 (20) 19 (21) 20
% k=2 (20) 17 (21) 19 (22) 19 (23) 20
% k=3 (24) 17 (25) 19 (26) 26 (27) 27
% 
% 1 21 22 23 24
% k=0 (21) 21 (22) 22 (23) 23 (24) 24
% k=1 (22) 22 (23) 22 (24) 19 (25) 20
% k=2 (24) 22 (25) 25 (26) 26 (27) 27
% 
% 1 25 26 27
% k=0 (25) 25 (26) 26 (27) 27
% k=1 (26) 26 (27) 27

%% \begin{table}[htbp]
%% \footnotesize
%%   \begin{center}
%%     \begin{tabular}{|c|cc|cc|cc|cc|cc|cc|} \hline
%% $i$ & \multicolumn{2}{c|}{1} & \multicolumn{2}{c|}{2} & \multicolumn{2}{c|}{3} & \multicolumn{2}{c|}{4} & \multicolumn{2}{c|}{5} & \multicolumn{2}{c|}{6} \\ \hline
%% $k=0$ & (1) & 1 & (2) & 2 & (3) & 3 & (4) & 4 & (5) & 5 & (6) & 6 \\ \hline
%% $k=1$ & (2) & 1 & (3) & 2 & (4) & 4 & (5) & 5 & (6) & 5 & (7) & 6 \\ \hline
%% $k=2$ & (4) & 1 & (5) & 5 & (6) & 5 & (7) & 5 & (8) & 5 & (9) & 6 \\ \hline
%% $k=3$ & (8) & 1 & (9) & 5 & (10) & 5 & (11) & 5 & (12) & 5 & (13) & 6 \\ \hline
%% $k=4$ & (16) & 1 & (17) & 5 & (18) & 5 & (19) & 5 & (20) & 5 & (21) & 6 \\ \hline
%%     \end{tabular}
%% {}\\[3ex]
%%     \begin{tabular}{|c|cc|cc|cc|cc|cc|cc|} \hline
%% $i$ & \multicolumn{2}{c|}{7} & \multicolumn{2}{c|}{8} & \multicolumn{2}{c|}{9} & \multicolumn{2}{c|}{10} & \multicolumn{2}{c|}{11} & \multicolumn{2}{c|}{12} \\ \hline
%% $k=0$ & (7) & 7 & (8) & 8 & (9) & 9 & (10) & 10 & (11) & 11 & (12) & 12 \\ \hline
%% $k=1$ & (8) & 7 & (9) & 9 & (10) & 9 & (11) & 11 & (12) & 12 & (13) & 12 \\ \hline
%% $k=2$ & (10) & 7 & (11) & 9 & (12) & 12 & (13) & 12 & (14) & 12 & (15) & 12 \\ \hline
%% $k=3$ & (14) & 12 & (15) & 12 & (16) & 12 & (17) & 12 & (18) & 12 & (19) & 12 \\ \hline
%% $k=4$ & (22) & 12 & (23) & 12 & (24) & 12 & (25) & 12 & (26) & 12 & (27) & 27 \\ \hline
%%     \end{tabular}
%% {}\\[3ex]
%%     \begin{tabular}{|c|cc|cc|cc|cc|} \hline
%% $i$ & \multicolumn{2}{c|}{13} & \multicolumn{2}{c|}{14} & \multicolumn{2}{c|}{15} & \multicolumn{2}{c|}{16} \\ \hline
%% $k=0$ & (13) & 13 & (14) & 14 & (15) & 15 & (16) & 16 \\ \hline
%% $k=1$ & (14) & 14 & (15) & 14 & (16) & 15 & (17) & 17 \\ \hline
%% $k=2$ & (16) & 14 & (17) & 14 & (18) & 15 & (19) & 17 \\ \hline
%% $k=3$ & (20) & 14 & (21) & 14 & (22) & 15 & (23) & 17 \\ \hline
%%     \end{tabular}
%% {}\\[3ex]
%%     \begin{tabular}{|c|cc|cc|cc|cc|} \hline
%% $i$ & \multicolumn{2}{c|}{17} & \multicolumn{2}{c|}{18} & \multicolumn{2}{c|}{19} & \multicolumn{2}{c|}{20} \\ \hline
%% $k=0$ & (17) & 17 & (18) & 18 & (19) & 19 & (20) & 20 \\ \hline
%% $k=1$ & (18) & 17 & (19) & 19 & (20) & 19 & (21) & 20 \\ \hline
%% $k=2$ & (20) & 17 & (21) & 19 & (22) & 19 & (23) & 20 \\ \hline
%% $k=3$ & (24) & 17 & (25) & 19 & (26) & 26 & (27) & 27 \\ \hline
%%     \end{tabular}
%% {}\\[3ex]
%%     \begin{tabular}{|c|cc|cc|cc|cc|} \hline
%% $i$ & \multicolumn{2}{c|}{21} & \multicolumn{2}{c|}{22} & \multicolumn{2}{c|}{23} & \multicolumn{2}{c|}{24} \\ \hline
%% $k=0$ & (21) & 21 & (22) & 22 & (23) & 23 & (24) & 24 \\ \hline
%% $k=1$ & (22) & 22 & (23) & 22 & (24) & 24 & (25) & 25 \\ \hline
%% $k=2$ & (24) & 22 & (25) & 25 & (26) & 26 & (27) & 27 \\ \hline
%%     \end{tabular}
%% {}\\[3ex]
%%     \begin{tabular}{|c|cc|cc|cc|} \hline
%% $i$ & \multicolumn{2}{c|}{25} & \multicolumn{2}{c|}{26} & \multicolumn{2}{c|}{27} \\ \hline
%% $k=0$ & (25) & 25 & (26) & 26 & (27) & 27 \\ \hline
%% $k=1$ & (26) & 26 & (27) & 27 & \multicolumn{2}{c}{} \\ \cline{1-5}
%%     \end{tabular}
%%   \end{center}
%%   \caption{\label{tab:tabelona}
%%            A matriz $\PosMinsym$ para o pré-processamento $O(m\log m)$}
%% \end{table}

\begin{table}[htbp]
\footnotesize
  \begin{center}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
$i$ & {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} & {10} & {11} & {12}& {13} & {14} \\ \hline
$k=0$ &  1 &  2 &  3 &  4 &  5 &  6     &  7 &  8 &  9 &  10 &  11 &       12  &  13 &  14 \\ \hline      
$k=1$ &  1 &  2 &  4 &  5 &  5 &  6     &  7 &  9 &  9 &  11 &  12 &       12  &  14 &  14 \\ \hline      
$k=2$ &  1 &  5 &  5 &  5 &  5 &  6     &  7 &  9 &  12 &  12 &  12 &      12  &  14 &  14 \\ \hline     
$k=3$ &  1 &  5 &  5 &  5 &  5 &  6     &  12 &  12 &  12 &  12 &  12 &    12  &  14 &  14 \\ \hline   
$k=4$ &  1 &  5 &  5 &  5 &  5 &  6     &  12 &  12 &  12 &  12 &  12 &    27 \\ \cline{1-13}
    \end{tabular}
{}\\[2ex]
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
$i$   & {15} & {16} &  {17} & {18} & {19} & {20} & {21} & {22} & {23} & {24} & {25} & {26} & {27}               \\ \hline   
$k=0$&  15 &  16 &     17 &  18 &  19 &  20 &      21 &  22 &  23 &  24   & 25 &  26 &  27                   \\ \hline      
$k=1$&  15 &  17 &     17 &  19 &  19 &  20 &      22 &  22 &  24 &  25   & 26 &  27 &  \multicolumn{1}{c}{} \\ \cline{1-13} 
$k=2$&  15 &  17 &     17 &  19 &  19 &  20 &      22 &  25 &  26 &  27   &  \multicolumn{3}{c}{}                       \\  \cline{1-11} 
$k=3$&  15 &  17 &     17 &  19 &  26 &  27 & \multicolumn{7}{c}{} \\      \cline{1-7}                                                              
    \end{tabular} 
  \end{center}
%  \caption{\label{tab:tabelona}
%           A matriz $\PosMinsym$ para o pré-processamento $O(m\log m)$}
\end{table}



\section{Logaritmos e Potências}
\label{sec:Logaritmos e Potencias}

\item Os vetores $\Logsym$ e $\Expsym$ tais que 
$\Log{i}=\lfloor \log_2 i\rfloor$, para $1\le i\le m$, e
$ \Exp{k}=2^k$, para $0\le k\le\Log{m}$,
são calculados no 
Algoritmo~\ref{alg:LogPot} em tempo $O(m)$.


\ppause\item 
\begin{algorithm}[htbp]
%  \caption{Cálculo de Logaritmos e de Potências}
  \label{alg:LogPot}
  \begin{algo}{\LogaritmosEPotenciassym}{\lm}
    \SET k 0
    \SET {\Exp{k}} 1
    \DOFORI i 1 \lm
      \IF{ i \ge \Exp{k} }
        \INCR k
        \SET {\Exp{k}} {2*\Exp{k-1}}
      \FI
      \SET {\Log{i}} {k-1}
    \OD
    \RETURN {(\Logsym,\Expsym)}
   \end{algo}
\end{algorithm}


\section{\MVCsym\ em tempo $\langle O(m\log m),O(1) \rangle$} 
\label{sec:mlogm}


%\item O par de algoritmos 
%\PreProcessamentoIntermediariosym\ e \MVCIntermediariosym (Algoritmo~\ref{alg:MvcIntermediario}) resolve o
%Problema do Mínimo de um Vetor Contínuo em tempo $\langle
% O(m\log m),O(1) \rangle$.



\begin{algorithm}[htbp]
%  \caption{\MVCsym\ em tempo $\langle O(m\log m),O(1) \rangle$}
  \label{alg:MvcIntermediario}
  \begin{algo}{\PreProcessamentoIntermediariosym}{V}
      \SET {(\Logsym,\Expsym)} {\LogaritmosEPotenciassym(m)}
      \DOFORI i 1 m
        \SET {\PosMin{i}{0}} i
      \OD
      \DOFORI k 1 {\Log{m}}
        \DOFORI i 1 {m-\Exp{k}}
          \SET {\PosMin{i}{k}} {\PapaLeguas{i}{i+\Exp{k}-1}}
        \OD
      \OD
      \RETURN {\PosMinsym}
      \RCOM 5 {Tabela $m \times \Log{m}$}
    \end{algo}
{}\\[6ex]
  \begin{algo}{\MVCIntermediariosym}{i,j}
      \RETURN {\PapaLeguas{i}{j}}
    \end{algo}
\end{algorithm}

\section{\MVCsym\ em tempo $\langle O(m),O(1) \rangle$} 
\label{sec:m}

A idéia básica é esta: temos que diminuir o espaço ocupado pela tabela
$\PosMinsym$ que usa $O(m\log m)$ posições.  Uma forma de obter isto é
particionar o vetor $\Vetorsym$ em blocos de $b$ elementos,
com $b$ proporcional a $\log m$, e construir a matriz $\PosMinsym$ apenas para
auxiliar em consultas que começam e terminam em fronteiras entre blocos
vizinhos, isto é, consultas que envolvem uniões de blocos inteiros.
Naturalmente, com este $\PosMinsym$ restrito não poderemos responder muitas
das consultas possíveis.  Felizmente, estas respostas podem ser recuperadas
através de uma técnica chamada dos ``quatro russos''.
%\footnote{Veja uma
%  explicação geral sobre a técnica dos ``quatro russos'' na seção 12.7 do
%  livro de Gusfield~\cite{MR99b:68095}.}.
Esta técnica pode ser usada para
levar em conta o que ocorre dentro dos blocos extremos envolvidos numa
consulta.

\section{A técnica dos quatro russos}

A técnica dos ``quatro russos'' consiste, no caso, em pré-computar e
estocar todos os $\MVCsym$'s internos aos blocos. Veremos que isto pode ser
feito em tempo e espaço $O(m)$ para blocos de $\log m$ elementos. Usaremos
fortemente a condição da continuidade do vetor dado para obter a complexidade
linear.

\section{Cálculo do \MVCsym\ }

Tendo o pré-processamento dos resultados internos aos blocos, qualquer
consulta pode ser respondida encontrando, em geral, o mínimo de três mínimos
parciais:
\begin{itemize}
  \item o mínimo interno a um bloco inicial,
  \item o mínimo de uniões de blocos inteiros e
  \item o mínimo interno a um bloco final.
\end{itemize}
O caso que sobra é quando a consulta está inteiramente contida num só bloco: o
pré-processamento fornece a resposta. Em qualquer caso, a consulta é
respondida em tempo constante! Vejamos, agora, os detalhes.

%% No que segue, escolhemos um natural $b>1$ que será o tamanho dos blocos.
%% O valor de $b$ será fixado no
%% final da sub-seção em $\Log{m}$ mas preferimos manter a discussão independente deste valor.
%% No nosso exemplo usaremos $b=4$. A primeira providência é subdividir o
%% vetor $\Vetorsym$ em blocos de $b$ elementos. Os intervalos
%% de índices correspondentes aos primeiros $g$ blocos serão, respectivamente,
%% \[ [1\Rng b], [b+1\Rng 2b], \ldots, [(g-1)b+1\Rng gb]. \]
%% O último bloco de $\Vetorsym$
%% poderá ser incompleto, dependendo dos valores de $m$ e $b$. O número de blocos
%% completos que teremos será $\lfloor m/b\rfloor$ enquanto o número total de
%% blocos será $g_m=\lceil m/b\rceil$.

%% O posicionamento de um índice $i$ do vetor $\Vetorsym$ agora será expressa por duas coordenadas:
%% diremos que $i$ está no $g_i$-ésimo bloco, com $1\le g_i \le g_m$ e que dentro
%% deste bloco $i$ ocupa a posição $p_i$, $1\le p_i\le b$. Evidentemente, existe
%% uma bijeção entre os índices $i$ e os pares $(g_i,p_i)$. O valor do par
%% $(g_i,p_i)$ correspondente a $i$ é dado pelo procedimento $\Agrupa{i}$,
%% apresentado no Algoritmo~\ref{alg:Agrupa}. A função inversa, que não será
%% utilizada, seria, para $g\ge 1$ e $1\le p\le b$,
%% \[ \Dispersasym(g,p)=(g-1)*b+p. \]
%% Nitidamente, o procedimento $\Agrupasym$ tem complexidade $O(1)$. Ele usa um
%% operador, que denominamos de {\em divisão inteira}, denotada por $x \DIV d$,
%% que associa a inteiros positivos $x$ e $d$, $d\neq0$,  o par $(q,r)$ de inteiros, onde $q$
%% é o quociente da divisão inteira de $x$ por $d$ e $r$ é o resto desta
%% divisão. Temos: $q=\lfloor x/d\rfloor$, $0\le r<d$ e $x=qd+r$.
%% No nosso exemplo o vetor $\Vetorsym$ é o $\Profsym$ e a sua partição em blocos
%% de $b=4$ elementos está feita na tabela~\ref{tab:busca}.

%% \begin{algorithm}[htbp]
%%   \caption{Cálculo do grupo e da posição do índice $i$}
%%   \label{alg:Agrupa}
%% % Agrupa(i) -> (g,p) com (grupo) g em 1..teto(m/b) e (posição) p em 1..b 
%%   \begin{algo}{\Agrupasym}{i}
%%       \SET {(q,r)} {i \DIV \lb}
%%       \IF {r=0}
%%         \RETURN{(q,\lb)}
%%       \ELSE
%%         \RETURN{(q+1,r)}
%%       \FI
%%     \end{algo}
%% \end{algorithm}

%% A próxima observação é essencial para a obtenção da complexidade do nosso
%% algoritmo. A posição do mínimo de um vetor contínuo não é alterada por uma
%% translação do vetor. Ou seja, se $V[1\Rng n]$ for um vetor contínuo então
%% $V'[1\Rng n]$, onde $V'[i]=V[i]+t$, para algum inteiro $t$, é contínuo
%% também e, os mínimos de $V$ e de $V'$ ocorrem exatamente nas mesmas
%% posições. Isto permite trabalharmos apenas com vetores ``normais'' onde
%% diremos que um vetor contínuo é {\em normal}, se o seu primeiro elemento for
%% $0$.

%% Podemos representar, biunivocamente, um vetor contínuo normalizado
%% de $n$ elementos pela seqüência das $n-1$ diferenças entre elementos
%% sucessivos do vetor.
%% Tais seqüências de diferenças serão denotadas por palavras de comprimento $n-1$ sobre o
%% alfabeto $A=\num{\ld,\ls}$ de duas letras.
%% Seja $N[1\Rng n]$ um vetor contínuo normalizado.
%% As correspondências entre as letras e
%% as diferenças que usaremos são:
%% \[ \ld \mbox{ representa } N[i\Rng i+1] \mbox{ se } N[i+1]-N[i]=-1 \mbox{ e } \]
%% \[ \ls \mbox{ representa } N[i\Rng i+1] \mbox{ se } N[i+1]-N[i]=1. \]
%% Necessitaremos de um vetor de duas posições para expressar esta
%% correspondência, por isto, definimos:
%% \[ \Variacao{\ld}=-1 \mbox{\quad e \quad} \Variacao{\ls}=1. \]
%% A idéia por trás desta notação é que a letra $\ld$ representa uma diminuição
%% em $N$.  Analogamente, a letra
%% $\ls$ representa um acréscimo em $N$.

%% Por exemplo, o vetor contínuo normalizado $N$ de 6
%% elementos 
%% \begin{equation}
%%   N[1\Rng 6]=(0,1,0,-1,-2,-1)
%%   \label{eq:vetor6} 
%% \end{equation}
%% será representado pela palavra $v$ de comprimento 5
%% \begin{equation}
%%   v=\ls\ld\ld\ld\ls.
%%   \label{eq:palavra5} 
%% \end{equation}

%% A seguir, definimos uma bijeção
%% \[ \fun{\gamma}{A^*}{\N _+} \]
%% entre as palavras sobre o alfabeto $A=\num{\ld,\ls}$ e os números naturais não
%% nulos. Postulamos que $\ld<\ls$ e associamos o natural $n>0$ à
%% $n$-ésima palavra de $A^*$ na ordem militar, isto é, na ordem
%% \[ \lambda, \ld, \ls, \ld\ld, \ld\ls, \ls\ld, \ls\ls, \ld\ld\ld,
%% \ld\ld\ls,\ldots .\]
%% A bijeção $\gamma$ é uma enumeração das palavras de $A^*$ e é amplamente
%% utilizada na Teoria da Computação. A partir da representação binária dos
%% números naturais não nulos é fácil visualizar a bijeção $\gamma$.
%% De fato, se $\gamma(v)=x$ e $v=v_1v-2\cdots v_n$, com os $v_i$ sendo letras em
%% $A$, e a representação binária de $x$ é $1x_1x_2\cdots x_m$, com os $x_i$
%% dígitos binários em $\num{0,1}$, então temos $n=m$ e $v_i=\ld$ sse $x_i=0$ e
%% $v_i=\ls$ sse $x_i=1$. De fato, veja a representação binária de 1 a 9 e
%% compare com as primeiras palavras de $A^*$ na ordem militar:
%% \[ 1,10,11,100,101,110,111,1000,1001,\ldots . \]
%% Esta propriedade pode ser vista como uma extensão das
%% correspondências abaixo, que serão usadas nos algoritmos a seguir:
%% \[ \Digito{\ld}=0 \mbox{\quad e \quad} \Digito{\ls}=1, \]
%% \[ \Letra{0}=\ld \mbox{\quad e \quad} \Letra{1}=\ls. \]

%% Utilizamos a construção acima através do conceito do ``crachá'' de um vetor
%% contínuo normalizado que definimos a
%% seguir.  Seja $N[1\Rng n]$ um vetor contínuo e seja $v$ a palavra de
%% comprimento $n-1$ que representa as diferenças sucessivas de elementos de
%% $N$.  O {\em crachá} de $N$ é o natural $x=\gamma(v)$.
%% Por exemplo, dado o vetor normalizado em~\ref{eq:vetor6}, temos $n=6$ e a palavra
%% associada é $v$, de comprimento 5, dado em~\ref{eq:palavra5}. Substituindo $\ld$ por
%% 0 e $\ls$ por 1 e acrescentando um dígito mais significativo 1 obtemos 110001,
%% que representa em binário o número 32+16+1=49. O crachá de $N$ é
%% 49.

%% Inversamente, seja $x$ um natural não nulo e seja $v=\gamma^{-1}(x)$. Seja
%% $n=1+|v|$, onde $|v|$ denota o comprimento da palavra $v$.  Associamos a $x$ o
%% vetor contínuo normalizado $N[1\Rng n]$ de $n$ elementos, que começa com 0 e
%% cujas diferenças sucessivas são exatamente as correspondentes às letras de
%% $v$. Segue da construção que $n$ e $x$ satisfazem as relações
%% \[ n=1+\Log{x} \mbox{ \quad e \quad} 2^{n-1}\le x<2^n. \]

%% Exemplificamos estas definições com a Tabela~\ref{tab:crachas} que apresenta
%% os crachás dos vetores normalizados dos 7 blocos do nosso exemplo. O crachá do
%% vetor normalizado do $g$-ésimo bloco será guardado em $\Cracha{g}$.

\section{Os crachás dos 7 blocos do exemplo}

%% % Vetor de crachás:
%% % 
%% % g           1 2 3 4 5 6 7
%% % sd's        ssd sss sdd dss sds dsd dd
%% % Crachá[g]   14  15  12  11  13  10  4

\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{|c|cc|cc|cc|c|} \hline
$g$          &  $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ \\ \hline
$\ls\ld$'s     &  $\ls\ls\ld$ & $\ls\ls\ls$ & $\ls\ld\ld$ & $\ld\ls\ls$ & $\ls\ld\ls$ &
$\ld\ls\ld$ & $\ld\ld$ \\ \hline
$\Cracha{g}$ &  $14$ & $15$ & $12$ & $11$ & $13$ & $10$ & $4$ \\ \hline
    \end{tabular}
  \end{center}
%  \caption{\label{tab:crachas}
%           Os crachás dos 7 blocos do exemplo}
\end{table}


%%\section{Vetor de Crachás}
%%\label{sec:Vetor de crachas}


%\ppause\item O Algoritmo~\ref{alg:FazCrachas}, $\FazCrachassym$, calcula o vetor
%$\Crachasym$ a partir do vetor $\Vetorsym$.  

%% \begin{algorithm}[htbp]
%%   \caption{Cálculo dos crachás dos blocos de $\Vetorsym$}
%%   \label{alg:FazCrachas}
%%   \begin{algo}{\FazCrachassym}{\Vetorsym,\lb}
%%       \SET x 0
%%       \DOFORI i 2 \lm
%%         \SET {(q,r)} {(i-1) \DIV \lb}
%%         \IF { r = 0 }
%%         \RCOM{5}{bloco completo, começar outro}
%%           \SET {\Cracha{q}} {x+\Exp{\lb-1}}
%%           \SET x 0
%%         \ELSEIF { \lV{i}=\lV{i-1}+1 }
%%         \RCOM{7}{letra $\ls$, dígito 1}
%%           \SET x {2*x+1}
%%         \ELSE
%%           \SET x {2*x}
%%           \RCOM{7}{letra $\ld$, dígito 0}
%%         \FI
%%       \OD
%%       \SET {(g_{\lm},p_{\lm})} {\Agrupa{\lm}}
%%       \SET {\Cracha{g_{\lm}}} {x+\Exp{p_{\lm}-1}}
%%       \RETURN {\Crachasym}
%%     \end{algo}
%% \end{algorithm}

%% Precisaremos, no decorrer dos algoritmos, decompor vetores contínuos
%% normalizados representados por seus crachás. Isto é feito no
%% Algoritmo~\ref{alg:Quebra} que implementa o procedimento $\Quebra{x}{c_1}$.
%% Seja $x$ um crachá que representa o vetor normalizado $N[1\Rng n]$, com
%% $n\ge2$, e seja $c_1$ um inteiro $0\le c_1<n-1$.
%% O vetor $N$ pode ser decomposto em dois vetores não vazios:
%% \[ N[1\Rng n]=N[1\Rng c_1+1]\cdot N[c_1+2\Rng n], \]
%% com $c_1+1$ e $n-c_1-1$ elementos, respectivamente.
%% Note que o segundo vetor é contínuo, mas pode não ser normalizado. Seja,
%% portanto, $N'[c_1+2\Rng n]$ o vetor normalizado de $N[c_1+2\Rng n]$.  Sejam
%% $x_1$ e $x_2$ os crachás de $N_1=N[1\Rng c_1+1]$ e $N_2=N'[c_1+2\Rng n]$,
%% respectivamente.  Então, os comprimentos das palavras correspondentes a $N_1$
%% e $N_2$ são, respectivamente, $c_1$ e $n-c_1-2$. Note que na fronteira
%% $N[c_1+1\Rng c_1+2]$ temos uma letra em $A=\num{\ls,\ld}$, correspondente à
%% diferença $N[c_1+2]-N[c_1+1]$ que não influi nem em $x_1$ nem em $x_2$.  O
%% procedimento $\Quebra{x}{c_1}$ devolve uma tripla $(x_1,\letra,x_2)$, onde
%% $x_1$ e $x_2$ são os crachás de $N_1$ e $N_2$, respectivamente, e $\letra$
%% representa a diferença $N[c_1+2]-N[c_1+1]$ que ocorre na fronteira.
%% é a letra na fronteira $N[c_1+1\Rng c_1+2]$.  As operações em que o
%% procedimento se apóia são o quociente e o resto da divisão inteira por
%% potências de $2$. Nitidamente, a complexidade de $\Quebrasym$ é $O(1)$.

%% Exemplificando esta decomposição, consideremos o vetor normalizado $N$
%% de~\ref{eq:vetor6} 
%% de crachá 49. 
%% Para $c_1=3$, a decomposição de $N$ é dada por $N=(0,1,0,-1)\cdot(-2,-1)$. O
%% vetor normalizado da segunda parte é $N_2=(0,1)$. A
%% letra na fronteira $(-1,-2)$ é $\ld$. Os crachás dos pedaços correspondem às
%% palavras $\ls\ld\ld$ e $\ls$  valem, respectivamente, 1100 e 11 em binário, ou
%% seja, 12 e 3. Assim, $\Quebra{49}{3}=(12,\ld,3)$. É uma aritmética peculiar,
%% mas simples e, principalmente, eficiente. Obtemos todas as informações sobre a
%% decomposição de $x$ em tempo constante.

\section{A decomposição de crachás}

\begin{algorithm}[htbp]
%  \caption{Decomposição de crachás}
  \label{alg:Quebra}
  \begin{algo}{\Quebrasym}{x,c_1}
      \SET {c_2} {\Log{x}-c_1-1}
      \SET {(y_1,y_2)} {x \DIV \Exp{c_2}}
      \SET {x_2} {y_2+\Exp{c_2}}
      \SET {(x_1,z)} {y_1 \DIV 2}
      \RETURN {(x_1,\Letra{z},x_2)}
    \end{algo}
\end{algorithm}

%A técnica dos quatro russos está implementada no procedimento
%\Russificasym, dado no Algoritmo~\ref{alg:Russifica}. Este procedimento
%calcula um vetor $\lR{1\Rng 2^b-1}$, com $2^b-1$ posições, indexadas pelos
%crachás de vetores contínuos normalizados com até $b$ elementos.
%O valor de $\lR{x}$ é a posição do mínimo no vetor contínuo normalizado
%de crachá $x$.


%% O vetor $\Russosym$ é calculado usando-se um vetor auxiliar, $r[1\Rng
%% 2^b-1]$. Para um crachá $x$, seja $N[1\Rng n]$ o vetor contínuo normalizado de
%% crachá $x$. Lembre que $n=1+\Log{x}$. O elemento $r[x]$ é uma tripla
%% \[ r[x]=(pm,vm,d), \]
%% onde $pm$ é a posição do mínimo no vetor $N$, $vm$ é o valor deste mínimo e
%% $d$ é a variação total do vetor $N$, isto é $d=N[n]-N[1]=N[n]$.
%% Por exemplo, de~\ref{eq:vetor6} obtemos que $r[49]=(5,-2,-1)$.

%% Os cálculos são feitos na ordem de crachás crescentes, assim, o cálculo de
%% $r[x]$ pode usar (e usa!) os resultados de vetores mais curtos.
%% Os crachás dos vetores mais curtos são obtidos pelo uso de $\Quebrasym$.
%% Nitidamente, a complexidade de $\Russifica{b}$ é $O(2^b)$: temos um número
%% constante de operações para cada crachá. Note, para uso futuro, que os
%% coeficientes 
%% ``escondidos'' pela notação $O()$ são pequenos no caso.

%% \begin{algorithm}[htbp]
%%   \caption{Cálculo dos Russos de comprimento pequeno}
%%   \label{alg:Russifica}
%%   \begin{algo}{\Russificasym}{\lb}
%%       \SET {r[1]} {(1,0,0)}
%%       \SET {\lR{1}} 1
%%       \DOFORI x 2 {\Exp{\lb}-1}
%%         \SET c {\Log{x}}
%%         \RCOM{3}{$c$ é o comprimento da palavra em $\num{\ls,\ld}^*$}
%%         \SET {(x_1,\letra,x_2)} {\Quebra{x}{c-1}}
%%         \RCOM{6}{volta: $x_2=1$}
%%         \SET {(pm,vm,d)} {r[x_1]}
%%         \SET {d'} {d+\Variacao{\letra}}
%%         \IF { vm \le d' }
%%           \SET {r[x]} {(pm,vm,d')}
%%         \ELSE
%%           \SET {r[x]} {(c+1,d',d')}
%%         \FI
%%         \SET {\lR{x}} {r[x][1]}
%%         \RCOM{4}{primeira componente de $r[x]$}
%%       \OD
%%       \RETURN {\Russosym}
%%     \end{algo}
%% \end{algorithm}

%% Para exemplificarmos o Algoritmo~\ref{alg:Russifica}, a
%% Tabela~\ref{tab:russos} apresenta os resultados finais de $\Russifica{4}$
%% enquanto a Tabela~\ref{tab:crachas-aux} apresenta os resultados
%% intermediários, guardados no vetor $r[x]$.

%% Note que o procedimento $\Russifica{b}$ independe do vetor de dados
%% $\Vetorsym$. O vetor $\Russosym$ é uma ``constante universal'', ele poderia
%% ser armazenada na Internet, por exemplo, e consultado em tempo constante por
%% quem quer que seja. Esta economia de pré-processamento, no entanto, não iria
%% diminuir a complexidade dos nossos algoritmos finais.

%% % Vetor de russos
%% % 
%% % c      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
%% % sd's   1 d s dd ds sd ss ddd dds dsd dss sdd sds ssd sss
%% % \lR{c}   1 2 1 3 2 1 1 4 3 2  2  4  1  1  1
%% % 
%% % Vetor auxiliar para russos
%% % 
%% % c      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
%% % r[c]   (1,0,0) (2,-1,-1) (1,0,1) (3,-2,-2) (2,-1,0) (1,0,0) (1,0,2) (4,-3,-3)
%% %        (3,-2,-1) (2,-1,-1) (2,-1,1) (4,-1,-1) (1,0,1) (1,0,1) (1,0,3)

%% % sd's        ssddsssdsddsdssdsdssdsdddd
%% % ()'s        (())((()())()(()()(()())))

\section{Os russos dos 15 crachás de comprimento até 3}

\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{|c|c|cc|cccc|} \hline
$x$ &      $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ \\ \hline
$\ls\ld$'s &  $\lambda$ & $\ld$ & $\ls$ & $\ld\ld$ & $\ld\ls$ & $\ls\ld$ & $\ls\ls$
\\ \hline 
$\lR{x}$ &    $1$ & $2$ & $1$ & $3$ & $2$ & $1$ & $1$ \\ \hline
    \end{tabular}
{}\\[4ex]
    \begin{tabular}{|c|cccccccc|} \hline
$x$ &      $8$ & $9$ & $10$ & $11$ & $12$ & $13$ & $14$ & $15$ \\ \hline
$\ls\ld$'s &  $\ld\ld\ld$ & $\ld\ld\ls$ & $\ld\ls\ld$ & $\ld\ls\ls$ & $\ls\ld\ld$ & $\ls\ld\ls$ & $\ls\ls\ld$ & $\ls\ls\ls$ \\ \hline
$\lR{x}$ &    $4$ & $3$ & $2$ & $2$ & $4$ & $1$ & $1$ & $1$ \\ \hline
    \end{tabular}
  \end{center}
%  \caption{\label{tab:russos}
%           Os russos dos 15 crachás de comprimento até 3}
\end{table}

%% \begin{table}[htbp]
%%   \begin{center}
%%     \begin{tabular}{|c|c|cc|} \hline
%% $x$ &      $1$ & $2$ & $3$ \\ \hline
%% $r[x]$ &   $(1,0,0)$ & $(2,-1,-1)$ & $(1,0,1)$ \\ \hline
%%     \end{tabular}
%% {}\\[4ex]
%%     \begin{tabular}{|c|cccc|} \hline
%% $x$ &      $4$ & $5$ & $6$ & $7$ \\ \hline
%% $r[x]$ &   $(3,-2,-2)$ & $(2,-1,0)$ & $(1,0,0)$ & $(1,0,2)$ \\ \hline
%%     \end{tabular}
%% {}\\[4ex]
%%     \begin{tabular}{|c|cccc|} \hline
%% $x$ &      $8$ & $9$ & $10$ & $11$ \\ \hline
%% $r[x]$ &   $(4,-3,-3)$ & $(3,-2,-1)$ & $(2,-1,-1)$ & $(2,-1,1)$ \\ \hline
%%   \end{tabular}
%% {}\\[4ex]
%%     \begin{tabular}{|c|cccc|} \hline
%% $x$ &      $12$ & $13$ & $14$ & $15$ \\ \hline
%% $r[x]$ &   $(4,-1,-1)$ & $(1,0,1)$ & $(1,0,1)$ & $(1,0,3)$   \\ \hline
%%   \end{tabular}
%%   \end{center}
%%   \caption{\label{tab:crachas-aux}
%%            Vetor de valores auxiliares no cálculo dos russos}
%% \end{table}

%% O Algoritmo~\ref{alg:MvcMonoBloco}, \MvcMonoBlocosym, tem complexidade
%% $O(1)$. Ele calcula $\MVC{i}{j}$ quando $i$ e $j$ caem no mesmo bloco, caso
%% contrário ele devolve 0.  Note que 0 é um índice inválido no vetor $\Vetorsym$
%% e assim este valor é usado para sinalizar que $i$ e $j$ caem em blocos
%% distintos. Este é um expediente que simplifica (um pouco) os programas
%% seguintes.

%% \begin{algorithm}[htbp]
%%   \caption{Cálculo do \MVCsym\ interno a um bloco}
%%   \label{alg:MvcMonoBloco}
%%   \begin{algo}{\MvcMonoBlocosym}{i,j}
%%     \COM{$i$ e $j$ são índices de elementos no vetor de dados $\Vetorsym$}
%%     \COM{devolvemos 0 se $i$ e $j$ estiverem em blocos distintos}
%%     \COM{devolvemos $\MVC{i}{j}$, caso contrário}
%%     \SET {(g_i,p_i)} {\Agrupa{i}}
%%     \SET {(g_j,p_j)} {\Agrupa{j}}
%%     \IF { g_i \neq g_j \Or i > j }
%%       \RETURN 0
%%     \FI
%%     \SET {(x_1,\letra,x_2)} {\Quebra{\Cracha{g_i}}{p_i-1}}
%%     \SET {(x_3,\letra,x_4)} {\Quebra{x_2}{j-i}}
%%     \RETURN {i-1+\lR{x_3}}
%%     \end{algo}
%% \end{algorithm}

%%% O Algoritmo~\ref{alg:Tabelona}, $\Tabelona{\Vetorsym}{b}$, calcula a tabela
%%% $\PosMinsym$, versão compacta da (ex) tabelona $\PosMinsym$. Ele usa
%%% $\MvcMonoBlocosym$ para calcular as posições dos mínimos de blocos individuais,
%%% quanto ao resto, ele é similar ao pré-processamento da seção
%%% anterior~\ref{sec:mlogm}, Algoritmo~\ref{alg:PreIntermediario}. A complexidade
%%% de $\Tabelona{\Vetorsym}{b}$ é $O(m'\log m')$, onde $m'=\lfloor m/b\rfloor$. A
%%% nova matriz $\PosMinsym$, referente ao nosso exemplo está dada na
%%% Tabela~\ref{tab:tabelinha}.
%%% 
%%% \begin{algorithm}[htbp]
%%%   \caption{Cálculo das respostas para uniões de blocos}
%%%   \label{alg:Tabelona}
%%%   \begin{algo}{\Tabelonasym}{\Vetorsym,\lb}
%%%       \SET {m'} {\lfloor \lm/\lb \rfloor}
%%%       \RCOM{4}{Número de blocos inteiros}
%%%       \DOFORI i 1 {m'} 
%%%         \SET {\PosMin{i}{0}} {\MvcMonoBloco{(i-1)*\lb+1}{i*\lb}}
%%%       \OD
%%%       \DOFORI k 1 {\Log{m'}}
%%%         \DOFORI i 1 {m'-\Exp{k}}
%%%           \SET {\PosMin{i}{k}} {\PapaLeguas{i}{i+\Exp{k}-1}}
%%%         \OD
%%%       \OD
%%%       \RETURN {\PosMinsym}
%%%   \end{algo}
%%% \end{algorithm}
%%% 
%%% % Tabela de PosMin, versão linear

% i 1 2 3 4 5 6
% k=0 (1) 1 (2) 5 (3) 12 (4) 14 (5) 17 (6) 22 
% k=1 (2) 1 (3) 5 (4) 12 (5) 14 (6) 17 
% k=2 (4) 1 (5) 5 (6) 12 

\section{A nova matriz \PosMinsym\ }

\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{|c|cc|cc|cc|cc|cc|cc|} \hline
$i$ & \multicolumn{2}{c|}{1} & \multicolumn{2}{c|}{2} & \multicolumn{2}{c|}{3} &
\multicolumn{2}{c|}{4} & \multicolumn{2}{c|}{5} & \multicolumn{2}{c|}{6} \\ \hline
$k=0$ & (1) & 1 & (2) & 5 & (3) & 12 & (4) & 14 & (5) & 17 & (6) & 22 \\ \hline
$k=1$ & (2) & 1 & (3) & 5 & (4) & 12 & (5) & 14 & (6) & 17 &
\multicolumn{2}{c}{} \\ \cline{1-11}
$k=2$ & (4) & 1 & (5) & 5 & (6) & 12 & \multicolumn{6}{c}{} \\ \cline{1-7}
    \end{tabular}
  \end{center}
%  \caption{\label{tab:tabelinha}
%           A matriz $\PosMinsym$ para o pré-processamento linear}
\end{table}

%% O Algoritmo~\ref{alg:PreMvc}, $\PreMvc{\Vetorsym}$, implementa o
%% pré-processamento da solução linear. Ele calcula logaritmos e potências em
%% tempo $O(m)$. Fixa o valor de $b$ em $\Log{m}=\lfloor \log_2 m\rfloor$.
%% Calcula o vetor $\Russosym$ em tempo $O(2^b)=O(m)$.
%% Calcula, a seguir, $\Crachasym$ em tempo $O(m)$. Finalmente, calcula a matriz
%% $\PosMinsym$ em tempo $O(m'\log m')=O(m)$, já que
%% \[ m'=\lfloor m/b\rfloor=\lfloor m/\lfloor\log m\rfloor\rfloor. \]

%% Queremos realçar que as constantes ``escondidas'' pela notação $O()$ são todas
%% ``pequenas'' no caso deste algoritmo. Trata-se de um procedimento rebuscado,
%% mas natural em todos os seus passos.
%% Neste ponto a versão de $\MVCsym$ que apresentamos difere de todas as outras
%% que conhecemos, já que elas recorrem a artifícios que comprometem a
%% naturalidade do procedimento sem comprometer a sua complexidade. Isto, porém,
%% aumenta, em geral, as constantes ``escondidas'' pela notação $O()$.

\section{Pré-processamento linear para \MVCsym\ }

\begin{algorithm}[htbp]
%  \caption{Pré-processamento linear para $\MVCsym$}
  \label{alg:PreMvc}
  \begin{algo}{\PreProcessamentoLinearsym}{\Vetorsym}
      \SET {(\Logsym,\Expsym)} {\LogaritmosEPotenciassym(\lm)}
      \SET {\lb} {\Log{\lm}}
      \SET {\Russosym} {\Russifica{\lb}}
      \SET {\Crachasym} {\FazCrachas{\Vetorsym}{\lb}}
      \SET {\PosMinsym} {\Tabelona{\Vetorsym}{\lb}}
  \end{algo}
\end{algorithm}

%% Finalmente, o procedimento de consulta $\MVC{i}{j}$, em tempo constante, é
%% dado no Algoritmo~\ref{alg:Mvc}.  Ele é comprido, mas é simples. Inicialmente,
%% define-se $\lV{0}$ como $\infty$, para facilitar as contas de mínimos em casos
%% particulares; note que $\infty$ é o elemento neutro da operação $\min$.
%% Deixamos o comando~\ref{lin:infty} no Algoritmo~\ref{alg:Mvc} como um
%% lembrete, nitidamente este comando poderia ser transferido para o
%% pré-processamento.  A seguir, ``tentamos a sorte'' chamando
%% $\MvcMonoBloco{i}{j}$.  Se $i$ e $j$ estão em blocos distintos então
%% decompomos a consulta em 3 sub-consultas, respondidas por $r_1$, $r_2$ e
%% $r_3$, uma ou duas das quais podem se referir a mínimos de conjuntos vazios,
%% caso em que o seu resultado será a posição 0. Temos:
%% \begin{itemize}
%%   \item $r_1$ é a posição do mínimo num intervalo próprio de um eventual bloco
%%     inicial, este intervalo é sempre da forma $[i\Rng b]$;
%%   \item $r_2$ é a posição do mínimo referente à união de blocos inteiros, ele
%%     é calculado de forma inteiramente análoga à consulta feita no
%%     Algoritmo~\ref{alg:MvcIntermediario}, $\MVCIntermediario{i}{j}$; o cálculo
%%     de $r_3$ chama $\PapaLeguassym$, dado no Algoritmo~\ref{alg:Auxiliar};
%%   \item $r_3$ é a posição do mínimo num intervalo próprio de um eventual bloco
%%     final, este intervalo é sempre da forma $[1,j]$.
%% \end{itemize}
%% As últimas linhas do Algoritmo~\ref{alg:Mvc} calculam a posição do mínimo de
%% $\lV{r_1}$, $\lV{r_2}$ e $\lV{r_3}$. Esta será a resposta à consulta feita.
%% Nitidamente o Algoritmo~\ref{alg:Mvc} tem complexidade $O(1)$, observação que
%% encerra esta seção.

\item O algoritmo de cálculo de $\MVC{i}{j}$ fica simples mas não cabe numa só
  transparência. Tem umas 22 linhas (com comentários).
  
\newpage{}

\begin{algorithm}[htbp]
%  \caption{Consulta $\MVCsym$ em tempo constante}
  \label{alg:Mvc}
  \begin{algo}{\MVCsym}{i,j}
    \SET {\lV{0}} {\infty} \label{lin:infty}
    \RCOM{4}{Anteparo para o cálculo dos mínimos}
    \SET r {\MvcMonoBloco{i}{j}}
    \RCOM{4}{$i$ e $j$ no mesmo grupo?}
    \IF { r \neq 0}
      \RETURN r
    \FI
    \COM{Calculamos $i'$ e $j'$ satisfazendo $i\le i'$ e $j'\le j$}
    \SET {i'} {\lceil (i-1)/\lb \rceil *\lb+1}
    \RCOM{4}{$i'$ inicia o primeiro bloco depois de $i$}
    \SET {r_1} {\MvcMonoBloco{i}{i'-1}}
    \SET {j'} {\lfloor j/\lb \rfloor *\lb}
    \RCOM{4}{$j'$ termina o último bloco antes de $j$}
    \SET {r_3} {\MvcMonoBloco{j'+1}{j}}
    \COM{$g_{i'}$ e $g_{j'}$ são os blocos contendo $i'$ e $j'$,
    respectivamente} 
    \SET {g_{i'}} {1+(i'-1)/\lb}
    \SET {g_{j'}} {j'/\lb}
    \IF { g_{i'}\le g_{j'} }
      \SET {r_2} {\PapaLeguas{g_{i'}}{g_{j'}}}
    \ELSE
      \SET {r_2} 0
    \FI
%\newpage{} não funciona :-(
    \COM{Calculamos, a seguir, a posição do mínimo de $\lV{r_1}$, $\lV{r_2}$ e
    $\lV{r_3}$}
    \COM{Seis linhas de programa omitidos por falta de espaço}
%    \IF { \lV{r_1} \le \lV{r_2} }
%      \SET r {r_1}
%    \ELSE
%      \SET r {r_2}
%    \FI
%    \IF { \lV{r_3} < \lV{r} }
%      \SET r {r_3}
%    \FI
%    \RETURN r
%    \RCOM{3}{$r$ é a posição do menor elemento em $\lV{i\Rng j}$}
  \end{algo}
\end{algorithm}

\section{\MACsym\ em tempo $\langle O(n),O(1) \rangle$}
\label{sec:Solucao}

%% Dada uma árvore $\gT$, o seu pré-processamento consiste na execução da busca
%% em profundidade, para trabalharmos, em seguida, com o vetor $\Profsym$ das
%% profundidades dos vértices visitados. Como $m=2n-1$, a complexidade do
%% pré-processamento é $O(n)$, supondo que estamos usando o pré-processamento
%% linear para $\MVCsym$.

%% Suponhamos, agora, que vértices $u$ e $v$ de $\gT$ sejam tais que
%% $\lD{u}<\lD{v}$. Então,
%% \[ \MAC{u}{v}=\lB{\MVC{\lD{u}}{\lD{v}}} \]
%% A consulta $\MAC{u}{v}$ é feita em tempo constante.

%% Desta forma, os algoritmos principais de pré-processamento e de consulta do
%% capítulo são aqueles dados nos Algoritmos~\ref{alg:PreProcessamentoLinearMAC}
%% e~\ref{alg:ConsultaMAC}. A complexidade deste par de
%% algoritmos é $\langle O(n),O(1) \rangle$. A sua corretude segue do
%% Teorema~\ref{teo:Reducao}.

%% Aproveitamos para observar que os
%% Algoritmos~\ref{alg:PreProcessamentoLinearMAC} e~\ref{alg:ConsultaMAC}
%% podem ser usados com qualquer versão da solução para $\MVCsym$. Eles provam,
%% na verdade, que dado um par de algoritmos de complexidade
%% $\langle f(m), g(m) \rangle$ para a solução de $\MVCsym$, o Menor Ancestral
%% Comum em árvores pode ser encontrado com complexidade
%% $\langle O(n)+f(m), g(m) \rangle$.

\begin{algorithm}[htbp]
%  \caption{\MACsym\ em tempo $\langle O(n),O(1) \rangle$}
  \label{alg:ConsultaMAC}
  \begin{algo}{\PreProcessamentosym}{\gT}
      \SET {(\lm,\Buscasym,\Profsym,\Descsym,\Abansym)} {\BuscaEmProfundidadesym(\gT)}
      \SET {\Vetorsym} {\Profsym}
      \CALL {\PreProcessamentoLinearsym}{\Vetorsym}
  \end{algo}
{}\\[6ex]
  \begin{algo}{\MACsym}{u,v}
      \IF { \lD{u} \le \lD{v} }
        \RETURN {\lB{\MVC{\lD{u}}{\lD{v}}}}
      \ELSE
        \RETURN {\lB{\MVC{\lD{v}}{\lD{u}}}}
      \FI
    \end{algo}
\end{algorithm}


\section{Notas bibliográficas}
\label{sec:Historia}

O problema do Menor Ancestral Comum em Árvores tem uma longa história da
melhoras.  A primeira solução não trivial aparece em 1973 e é
publicada em~\cite{AhoHU76}.
A primeira solução de complexidade $\langle O(n),O(1) \rangle$ é de 1984 e aparece em
Harel e Tarjan~\cite{MR85f:68081}. %HarelT84
Estes algoritmos são muito complexos e foram
simplificados em 1988 por Schieber e Vishkin em~\cite{SchieberV88} e em 2000
por Bender e Farach-Colton em~\cite{BenderFC00}.
O problema do Mínimo de um Vetor aparece em 1984, num trabalho de Gabow,
Bentley e Tarjan em~\cite{Gabow:1984:SRT}. %GabowBT84
Existe uma descrição detalhada da variante de Shieber e Vishkin no livro de
Gusfield~\cite{MR99b:68095}, %Gusfield97
que é um dos raros casos em que o algoritmo é
descrito com alguns detalhes num livro. Existe uma ampla literatura sobre o
problema, seus usos e suas generalizações. Recomendamos a consulta aos
trabalhos~\cite{SODA01*845,SPAA02*258,MR1966146}. %BenderFCPSS01, AlstrupGKR02, BenderFC02


\end{list1}

\end{document}


%% Local Variables:
%% TeX-parse-self: t
%% mode: outline-minor
%% mode: iso-accents
%% make-backup-files: t
%% TeX-auto-save: t
%% End:
