%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC323 Estruturas de Dados                           %
% 1o. semestre de 2008                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 23 Apr 2008 09:10:50pm BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim
\def\|{|\!|}

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}\nolimits}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bff{\textbf{f}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

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

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC323 Estruturas de Dados]{%
  {\sl Exercícios}\\\medskip
  Estruturas de Dados\\\medskip
  1{\tiny o.} semestre de 2008}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\begin{enumerate}
  
\item\label{Q:1}[Desafio] Sejam~$x_1,\dots,x_n$ pontos no quadrado
  unitário~$[0,1]\times[0,1]$.  Seja~$\mu=\mu(x_1,\dots,x_n)$ a distância
  mínima entre esses pontos:
  \begin{equation}
    \label{eq:1}
    \mu=\min\{\|x_i-x_j\|\:i\neq j\}.
  \end{equation}
  Estamos interessados em estudar~$\mu$, quando os~$x_i$ são gerados
  aleatoriamente, de forma independente e uniforme.
  \begin{enumerate}
  \item[(\textit{i})]Escreva um programa que recebe~$n$ como entrada, 
    gera~$x_1,\dots,x_n$ como acima, e determina~$\mu=\mu(x_1,\dots,x_n)$.
    Seu programa também deve receber como entrada um natural~$N$: se~$N>1$,
    então seu programa deve repetir o experimento acima~$N$ vezes, e deve
    calcular a média e desvio padrão dos~$N$ valores de~$\mu$ obtidos.  
    
  \item[(\textit{ii})]Não é difícil ver que ver que~$\mu=O(1/n)$.  Através de
    experimentos computacionais, tente descobrir mais sobre~$\mu$.  Por
    exemplo, o valor de~$n\mu$ ``tende'' para alguma constante positiva
    quando~$n\to\infty$?
  \end{enumerate}
  Note que, para ser bem sucedido neste desafio, você precisará escrever um
  programa eficiente para~(\textit{i}) acima.



\end{enumerate}  
 
\end{document}

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

