
\documentclass[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{LastRevised=Sat Jan 18 16:35:44 2003}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{CSTFile=article.cst}
%TCIDATA{MapleDefs=
%$T\left( n\right) =$
%}


\include{lecture}

%\input{tcilatex}

\begin{document}


\lecture{9}{20/01/03}{M\'{e}todo da \'{A}rvore de Recurs\~{a}o}{Rodrigo Pessoa}
\draft % put this here only if you want to indicate this is a draft

\section{M\'{e}todo da \'{A}rvore de Recurs\~{a}o}

Este m\'{e}todo \'{e} uma forma conveniente de vizualizar o que ocorre
quando a recurs\~{a}o \'{e} iterada. Desta forma este m\'{e}todo ajuda a
organizar a estrutura alg\'{e}brica necess\'{a}ria para resolver uma recorr%
\^{e}ncia. Adicionalmente este m\'{e}todo ajuda na determina\c{c}\~{a}o de
uma boa adivinha\c{c}\~{a}o para o m\'{e}todo da substitui\c{c}\~{a}o.

\begin{example}Considere a rela\c{c}\~{a}o de recorr\^{e}ncia,
\begin{equation}
T\left(  n\right) =\left\{
\begin{array}
[c]{l}%
T\left( n\right) =2T\left( \frac{n}{2}\right) +n^{2}\qquad se\
n>1,\ \\
1\qquad \qquad \quad\quad\quad\quad\quad \quad se\ n=1.\
\end{array}
\right\}
\end{equation}


N\'{o}s agora desenhamos o come\c{c}o da \'{a}rvore de recurs\~{a}o para a
recorr\^{e}ncia acima. Por agora, assuma que n \'{e} uma pot\^{e}ncia de 2.
Um diagrama \'{a}rvore de recurs\~{a}o tem tr\^{e}s partes. Do lado
esquerdo, n\'{o}s mantemos a trilha do tamanho do problema, no meio n\'{o}s
desenhamos a \'{a}rvore, e do lado direito, n\'{o}s montamos a trilha do
trabalho j\'{a} feito. Dessa forma no come\c{c}o da \'{a}rvore de recurs\~{a}%
o deste exemplo n\'{o}s tomamos um problema de tamanho n, dividimos este em
2 problemas de tamanho $\frac{n}{2}$ e anotamos do lado direito que n\'{o}s
tivemos o custo de $n^{2}$ para fazer o trabalho neste n\'{i}vel da \'{a}%
rvore. O fato que n\'{o}s quebramos o problema em dois problemas \'{e}
representado desenhando-se dois filhos do no raiz (n\'{i}vel 0). Isto
resulta na seguinte figura:

\begin{figure}
[tbh]
\begin{center}
\includegraphics[
height=1.4745in,
width=2.8349in
]%
{Figura1_niv3.eps}%
\caption{}%
\label{figura1}%
\end{center}
\end{figure}

N\'{o}s continuamos a desenhar a \'{a}rvore desta maneira, at\'{e} atingir a
condi\c{c}\~{a}o de fronteira, ou seja o caso base da recurs\~{a}o.

Dessa forma para desenhar uma \'{a}rvore de recurs\~{a}o n\'{o}s
necessitamos determinar:

\begin{itemize}
\item  o n\'{u}mero de subproblemas;

\item  o tamanho de cada subproblema;

\item  o trabalho feito em cada n\'{i}vel da \'{a}rvore;

\item  e a altura da \'{a}rvore de recurs\~{a}o.
\end{itemize}

\begin{figure}
[tbh]
\begin{center}
\includegraphics[
height=1.9078in,
width=6.5276in
]%
{Figura2_niv3.eps}%
\caption{}%
\label{figura1}%
\end{center}
\end{figure}


N\'{o}s podemos ver que para este problema, no n\'{i}vel 2, n\'{o}s temos $%
2^{i}$\ subproblemas de tamanho $\frac{n}{2^{i}}$. dAdicionalmente, uma vez
que um problema de tamanho $\frac{n}{2^{i}}$\ requer $\left( \frac{n}{2^{i}}%
\right) ^{2}$ unidades de trabalho para ser executado, h\'{a} $\left(
2^{i}\right) \left( \frac{n}{2^{i}}\right) ^{2}=\frac{n^{2}}{2^{i}}$
unidades de trabalho adicional por n\'{i}vel . De modo a determinar quantos n%
\'{i}veis existem na \'{a}rvore, n\'{o}s observamos que em cada n\'{i}vel o
problema \'{e} reduzido pela metade, e a \'{a}rvore para quando o tamanho do
problema \'{e} 1. Portanto existem $\lg n+1$\ n\'{i}veis na \'{a}rvore. E a
altura da \'{a}rvore \'{e} $\lg n$. Em cada n\'{i}vel da \'{a}rvore, a exce%
\c{c}\~{a}o do \'{u}ltimo n\'{i}vel, n\'{o}s temos que o montante de
trabalho feito neste n\'{i}vel \'{e} igual a $\frac{n^{2}}{2^{i}}>0\leq
i\leq $ $\lg n-1$.

O \'{u}ltimo n\'{i}vel \'{e} diferente dos demais n\'{i}veis. Nos outros n%
\'{i}veis, o custo \'{e} descrito pela parte recursiva da recorr\^{e}ncia,
neste caso $T\left( n\right) =2T\left( \frac{n}{2}\right) +n^{2}$. No \'{u}%
ltimo n\'{i}vel, a carga de trabalho vem do caso base. Dessa forma n\'{o}s
devemos computar o n\'{u}mero de problemas de tamanho 1, e ent\~{a}o
multiplicar este valor por $T\left( 1\right) $.

A coisa importante \'{e} que n\'{o}s sabemos exatamente quantos n\'{i}veis
existem, e a quantidade de trabalho feita em cada n\'{i}vel. Uma vez que n%
\'{o}s conhecemos estes fatos, n\'{o}s podemos somar a quantidade de
trabalho feita em cada n\'{i}vel. Neste exemplo a quantidade de trabalho
feita \'{e}:

\begin{equation}
\ T\left( n\right) =nT\left( 1\right) +\sum\limits_{i=0}^{\lg n-1}\frac{n^{2}%
}{2^{i}},=\Theta (n^{2})
\end{equation}


O trabalho total feito pela \'{a}rvore de recurs\~{a}o \'{e} a solu\c{c}\~{a}%
o para nossa recorr\^{e}ncia, porque a \'{a}rvore simplesmente modela o
processo de itera\c{c}\~{a}o da recorr\^{e}ncia. O m\'{e}todo da \'{a}rvore
de recorr\^{e}ncia pode ser utilizado para dar uma boa indica\c{c}\~{a}o da
aproxima\c{c}\~{a}o que ser\'{a} utilizada no m\'{e}todo da substitui\c{c}%
\~{a}o.

Uma outra forma de observar que a recorr\^{e}ncia (1) tem solu\c{c}\~{a}o $%
\Theta (n^{2})$ \'{e} observar que o primeiro n\'{i}vel tem um custo de $%
n^{2}$, o segundo n\'{i}vel tem um custo de $\left( \frac{n}{2}\right)
^{2}+\left( \frac{n}{2}\right) ^{2}=\frac{n^{2}}{2}$ o terceiro n\'{i}vel
tem custo $\left( \frac{n}{4}\right) ^{2}+\left( \frac{n}{4}\right)
^{2}+\left( \frac{n}{4}\right) ^{2}+\left( \frac{n}{4}\right) ^{2}=\frac{%
n^{2}}{4}$, e assum sucessivamente. Desa forma os custos decrescem
geometricamente, portanto o custo total \'{e} no m\'{a}ximo um fator
constante maior que o primeiro termo, e assim a solu\c{c}\~{a}o \'{e} $%
\Theta (n^{2})$.
\end{example}
Considere agora mais uma recorr\^{e}ncia:
\begin{equation}
T\left(  n\right) =\left\{
\begin{array}
[c]{l}%
T\left( \frac{n}{2}\right) +n\qquad se\
n>1,\ \\
1\qquad \qquad \quad \quad se\ n=1.\
\end{array}
\right\}
\end{equation}

Novamente, vamos assumir que n \'{e} uma pot\^{e}ncia de dois. N\'{o}s
podemos interpretar esta recorr\^{e}ncia da seguinte forma: para resolver um
problema de tamanho n, n\'{o}s devemos resolver um problema de tamanho $%
\frac{n}{2}$\ e n\'{o}s fazemos n unidades de trabalho adicional.

Vamos desenhar a \'{a}rvore de recurs\~{a}o para este problema:
\begin{figure}
[tbh]
\begin{center}
\includegraphics[
height=2.9542in,
width=1.1882in
]%
{Figura3_niv3.eps}%
\caption{}%
\label{figura1}%
\end{center}
\end{figure}

N\'{o}s vemos neste exemplo que o tamanho dos problemas permanece o mesmo
como na \'{a}rvore anterior. Contudo, todo o resto \'{e} diferente. O n\'{u}%
mero de subproblemas n\~{a}o duplica, este permanece o mesmo em cada n\'{i}%
vel. Consequentemente a quantidade de trabalho fica reduzida a metade em
todo n\'{i}vel. Note que existe ainda $\ln n+1$ n\'{i}veis. Dessa forma no n%
\'{i}vel i, n\'{o}s temos 1 problema de tamanho $\frac{n}{2^{i}}$, e um
montante de trabalho de $\frac{n}{2^{i}}$.

N\'{o}s agora desejamos calcular a quantidade total de trabalho feita, temos
que o trabalho total \'{e}:

\begin{eqnarray}
T(n) &=& n+\frac{n}{2}+\frac{n}{4}+...+2+1\\
&=&\sum\limits_{i=0}^{\lg n}\frac{n}{2^{i}}\nonumber\\%
&=&n\sum\limits_{i=0}^{\lg n}(\frac{1}{2})^{i}\leq n\sum\limits_{i=0}^{\infty
}(\frac{1}{2})^{i}=n\nonumber\\
T(n)&=&O(n).\nonumber
\end{eqnarray}
\bigskip Mas $T(n)=\Omega (n)$, portanto, $T(n)=\Theta (n)$.

O que \'{e} importante para n\'{o}s n\~{a}o \'{e} a forma ''exata'' da solu%
\c{c}\~{a}o, mas um limite big O, ou melhor, um limite big $\Theta $ sob a
solu\c{c}\~{a}o.

Considere agora a seguinte recorr\^{e}ncia:
\begin{equation}
T\left(  n\right) =\left\{
\begin{array}
[c]{l}%
T\left( \frac{n}{3}\right)+T\left( \frac{2n}{3}\right) +n\qquad se\
n>1,\ \\
1\qquad \qquad \quad \quad se\ n=1.\
\end{array}
\right\}
\end{equation}

A \'{a}rvore de recurs\~{a}o desta recorr\^{e}ncia \'{e} mostrada
abaixo:
\begin{figure}
[tbh]
\begin{center}
\includegraphics[
height=2.0211in,
width=3.2526in
]%
{Figura4_niv3.eps}%
\caption{}%
\label{figura1}%
\end{center}
\end{figure}

Quando n\'{o}s adicionamos os valores de cada n\'{i}vel, n\'{o}s obtemos um
valor de n. Mas ser\'{a} que o custo de cada n\'{i}vel \'{e} sempre n? O
caminho mais longo da raiz para uma folha \'{e} $n\rightarrow (2/3)n\rightarrow (2/3)^{2}n\rightarrow ...\rightarrow 1$. Uma
vez que $(2/3)^{k}n=1$ quando $k=\log _{(3/2)}n$, a altura
da \'{a}rvore \'{e} $\log _{\frac{3}{2}}n$. Assim a solu\c{c}\~{a}o da recorr%
\^{e}ncia \'{e} no m\'{a}ximo $n\log _{\frac{3}{2}}n$ $=O(n\lg n)$.

Ser\'{a} que n\'{o}s podemos fazer melhor que isto?

\end{document}
