
% 05/03/2006

\documentclass[11pt,portuges,brazil]{article}
\usepackage{babel}
\usepackage{html}
\usepackage{a4wide}

\begin{document}

\begin{flushleft}
UNIVERSIDADE FEDERAL DE MINAS GERAIS \\
DEPARTAMENTO DE CI\^{E}NCIA DA COMPUTA\c{C}\~{A}O\\
CURSO DE P\'OS-GRADUA\c{C}\~{A}O EM CI\^ENCIA DA COMPUTA\c{C}\~{A}O\\
PROJETO E AN\'ALISE DE ALGORITMOS

\smallskip
\noindent
\'Ultima altera\c{c}\~ao: \today

\medskip

Professor: \htmladdnormallink{Nivio Ziviani}{http://www.dcc.ufmg.br/\~\,nivio/} \\[0.2cm]
Monitor: \htmladdnormallink{Fabiano C. Botelho}{mailto:fbotelho@dcc.ufmg.br}
\\[0.2cm]
1$^{\underline{o}}$  Trabalho Pr\'{a}tico - 09/03/06 - 10 pontos\\[0.2cm]
Data de Entrega: 31/03/06 \\[0.2cm]
Penaliza\c{c}\~ao por Atrazo: 1 ponto at\'e 06/04/06 mais 1 ponto por dia \'util
a seguir\\[0.2cm]
Observa\c{c}\~ao: Toda a documenta\c{c}\~ao dever\'a ser apresentada como uma p\'agina
acess\'{\i}vel via Web (apresente o link para acesso \`a documenta\c{c}\~ao).\\[0.2cm]
\end{flushleft}

\noindent\rule{15.5cm}{0.2mm}

\newcounter{numquestao}
\newcounter{cont2}
\newcounter{cont3}

\begin{enumerate}
\item Avaliar as somas {\em (0,5 + 0.5 pontos)}:
\begin{enumerate}
\item \(\sum_{i=1}^n i2^{i-1}\)
\item \(\sum_{i=1}^n \frac{1}{i}\)
\end{enumerate}

\item {\em 2 pontos}

Sejam $a$, $b$ e $c$ constantes n\~ao negativas.
Prove que a solu\c{c}\~ao para

  $\left\{ \begin{array}{ll}
  T(1) = c & \ \ \ n = 1 \\
  T(n) = aT(n/b) + cn &     \ \ \ n > 1 
  \end{array}
  \right. $

para $n$ uma pot\^encia de $b$ \'e

\noindent
\begin{displaymath}
T(n) = \left\{ \begin{array}{ll}
 O(n), & \textrm{se} \ a < b, \\
 O(n \log n), & \textrm{se} \ a=b, \\
 O(n^{\log_b a}, & \textrm{se} \ a > b.
 \end{array} \right.
\end{displaymath}

\item Resolva as equa\c{c}\~oes de recorr\^encia {\em (2 pontos)}
\begin{enumerate}
\item \( \left\{ \begin{array}{lclr}
T(n) = 2T(n/4) + n \mbox{,\ \ para\ } n > 1 \\
T(1) = 27
\end{array} \right.\)

\item \( \left\{ \begin{array}{lclr}
T(n) = 7T(n/2) + n^2 \mbox{,\ \ para\ } n > 1 \\
T(1) = 0\\
\end{array} \right.\)
\item
  $\left\{ \begin{array}{ll}
  T(n) = T(\sqrt n) + \log n \mbox{,\ \ para\ } n \geq 1 \\
  T(1) = 1
  \end{array}
  \right. $

Dica: use mudan\c{c}a de vari\'aveis.

\item 

  $\left\{ \begin{array}{ll}
  T(n) = T(n/9) + T(8n/9) + n \mbox{, \ \ para\ } n \geq 1 \\
  \end{array}
  \right. $

Dica: Use uma \'arvore de recursividade para enxergar a solu\c{c}\~ao.
\end{enumerate}

\item Limite inferior
{\em (2 pontos)}

Apresente o limite inferior para intercalar dois conjuntos
de inteiros $A(1:m)$ e $B(1:n)$ onde os itens em $A$ e os itens em
$B$ est\~ao ordenados.
Assuma que todos os n\'umeros $m+n$ s\~ao distintos.

\item \'Arvore B
{\em (0,5 + 2 + 0,5 pontos)}

O objetivo deste trabalho \'e realizar um estudo
do algoritmo \'arvore B
(Ziviani, 2004).

\begin{enumerate}

\item Obtenha analiticamente o valor da altura $h$ de uma \'{a}rvore B de
ordem $m$ para o melhor caso e o pior caso.

\item Obtenha empiricamente os resultados a seguir. 
Utilize valores distintos de $m=1$, $m=50$ e $m=100$.
Utilize  arquivos de diferentes tamanhos com chaves geradas randomicamente
para cada valor de $m$.  
Use o programa {\em Permut.c} para obter uma
permuta\c{c}\~ao rand\^omica de $n$ valores (Ziviani, 2004, pag. 427).
Repita
cada experimento algumas vezes e obtenha a m\'{e}dia para cada medida
de complexidade.  

\begin{itemize}

\item A altura esperada $h$ de uma \'{a}rvore B de ordem $m$
rand\^{o}mica com $n$ chaves, para os valores de $m$ indicados acima.
Assuma que a altura esperada \'{e} aproximadamente $\log_x{n+1}$. Determine
empiricamento o valor de $x$.

\item A probabilidade de que a p\'{a}gina segura mais profunda esteja no primeiro
n\'{\i}vel da \'{a}rvore.

\item O valor da taxa de utiliza\c{c}\~{a}o de mem\'{o}ria.
\end{itemize}

\item
Procure trabalhos relacionados mais recentes na literatura
com resultados anal\'{\i}ticos e descreva suscintamente esses trabalhos.
Como os resultados experimentais que voc\^e obteve comparam com os resultados 
anal\'{\i}ticos de Ziviani (2004) e/ou encontrados na literatura?
\end{enumerate}

\end{enumerate}
\end{document}

