%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% D3 de MAC323 Estruturas de Dados                                   %
% BCC, 1o. semestre de 2001                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 06 Apr 2001 04:13:50pm BRST yoshi@rebutosa>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

\let\:=\colon
\def\dist{\mathop{\rm dist}\nolimits}
\def\RR{\mathbb R}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\renewcommand{\datename}{\textit{Data}:}

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}

\begin{document}

\title[MAC323, 3o.~Desafio, Árvores Binárias]%
{{\footnotesize MAC323/BCC Terceiro Desafio}\\
\vspace{6\jot}
\textsl{Estatísticas de Árvores Binárias}}
\author{Y.\ Kohayakawa}
\date{Versão de \today}
\maketitle
\thispagestyle{empty}

Neste desafio, você verificará empiricamente as afirmações que vimos em aula
sobre a profundidade média dos nós em uma (\textit{i})~árvore de busca binária
gerada a partir de uma permutação aleatória de~$N$ chaves distintas e em uma
(\textit{ii})~árvore binária escolhida uniformemente ao acaso, dentre todas as
árvores com~$N$ nós internos.

\subsection*{Árvores de busca binária aleatórias} Escreva um programa que,
dado~$N\geq1$, gera uma permutação aleatória dos inteiros~$1,\dots,N$, digamos
$\rho\colon[N]\to[N]$, e que contrói uma ABB com estas chaves, inserindo-as na
ordem 
$$
\rho(1),\rho(2),\dots,\rho(N). 
$$
\begin{itemize}
\item Execute seu programa para valores grandes de~$N$, várias vezes, e
  compile estatísticas sobre as árvores geradas (possivelmente também fazendo
  alguns histogramas para ilustrar seus dados de forma intuitiva).  Você pode
  calcular a altura média e os comprimentos interno e externo médios.
\item Uma estatística um pouco diferente refere-se à eficiência de se contruir
  tais árvores: você pode verificar qual é o número médio de comparações que
  se faz para construir estas árvores com~$N$ nós.  
\end{itemize}
Lembre que o resultado fundamental visto em aula (mas não demonstrado) é que
tais árvores tem comprimento interno basicamente igual a~$2N\log N$.

\subsection*{Árvores de busca binária uniformes} Escreva um programa que,
dado~$N\geq1$, gera uma árvore binária com~$N$ nós internos, com todas estas
árvores equiprováveis.  \textit{Você vai ter de pensar um pouco como fazer
  isto.}  Você pode usar o fato mencionado em sala que diz que o número de
tais árvores é 
$$
t(N)={1\over N+1}{2N\choose N}.
$$
\begin{itemize}
\item Execute seu programa para valores grandes de~$N$, várias vezes, e
  compile estatísticas sobre as árvores geradas (possivelmente também fazendo
  alguns histogramas).  Você pode calcular a altura média e os comprimentos
  interno e externo médios.  
\end{itemize}
Lembre que o resultado fundamental visto em aula (mas não demonstrado) é que
tais árvores tem comprimento interno basicamente igual a~$N\sqrt{\pi N}$.


\subsection*{Observações}  Você pode achar interessante consultar a página
$$
\href{http://cgm.cs.mcgill.ca/~luc/trees.html}%
{\texttt{http://cgm.cs.mcgill.ca/\~\null luc/trees.html}}
$$
escrita por \href{http://cgm.cs.mcgill.ca/~luc/}{Luc Devroye}, do
Departamento de Ciência da Computação da Universidade de McGill.

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
