EXERCÍCIOS

ESTRUTURAS DE DADOS

1O. SEMESTRE DE 2008

1. [Desafio] Sejam x_{1}, …, x_{n} pontos no quadrado unitário [0, 1] × [0, 1]. Seja μ = μ(x_{1}, …, x_{n}) a distância mínima entre esses pontos:

μ = min{||x_{i} − x_{j}||: i ≠ j}.  (1)

Estamos interessados em estudar μ, quando os x_{i} são gerados aleatoriamente, de forma independente e uniforme.

(i) Escreva um programa que recebe n como entrada, gera x_{1}, …, x_{n} como acima, e determina μ = μ(x_{1}, …, 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 μ obtidos.

(ii) Não é difícil ver que ver que μ = O(1/n). Através de experimentos computacionais, tente descobrir mais sobre μ. Por exemplo, o valor de nμ “tende” para alguma constante positiva quando n → ∞?

Note que, para ser bem sucedido neste desafio, você precisará escrever um programa eficiente para (i) acima.

Date: Versão de 5 de março de 2008.