MAC338 Análise de Algoritmos

BCC - 1o. Semestre de 2000

Um Truque de Baralho

Inicialmente, leia a descrição de um truque de baralho no EP1 da Poli deste semestre.

Há várias investigações interessantes que podemos fazer em torno deste truque. Gostaria de desafiar os interessados a estudar este truque de vários pontos de vista. Abaixo, sugiro alguns enfoques que eu acredito serem interessantes.

Simulação do Truque

Na página do EP1 acima, há disponível um executável para Winbugs que serve para simular este truque. Aqui você tem uma versão para a rede GNU/Linux do IME: baralho. Confesso que fiquei um tanto surpreso com a forma mais eficiente que tenho para implementar este simulador. Acredito que o interessante é o processo de geração de uma permutação aleatória dos inteiros 1,...,n (o resto da simulação deste truque é muito simples!). Como podemos gerar, eficientemente, uma tal permutação? O programa que forneço acima parece ser bom para valores de n por volta de 1000.

Na verdade, não tenho tanta certeza que o programa que tenho é tão bom assim. Um teste que me parece interessante é verificar o tempo de execução da chamada

[jacuzzi:~/sink]$ baralho -s999 -n1000 -m50 -c50 -R -r100000

A execução de baralho acima gera 100000 permutações dos inteiros 1,...,1000 e simula o resultado do truque com os parâmetros dados (execute baralho sem parâmetros para ver o significado das opções).

Nós poderíamos, na verdade, ir direto ao ponto e considerar o seguinte problema: escreva um programa eficiente que gera M permutações dos inteiros 1,...,n. O seu programa deve ter complexidade O(nM).

Versão Simplificada

No EP1 da Poli, pede-se que se escreva uma simulação de um truque mais simples; a saber, simplificamos o truque assumindo que não mais temos um baralho para gerar os números, mas que usamos um gerador de números aleatórios que gera números no intervalo 1,...,n_max. Isto é de fato mais simples porque não precisamos saber quais números já foram gerados; a cada instante simplesmente geramos um novo número, independetemente do que ocorreu antes. Ademais, assumimos que iniciamos as contagens a partir da primeira e da segunda cartas (e prosseguimos até a ocorrência de coincidência; veja o enunciado do EP).

Seja N(n_max) o número esperado de números que geramos até a ocorrência de coincidência. Prove que N(n_max) = O(n_max^2).

Um resultado um pouco mais difícil de provar é que N(n_max) = Omega(n_max^2/log n_max). Tente provar isto! (A "notação Ômega" será explicada em aula.)

Finalmente, com toda certeza vale que N(n_max) é assintótico a c n_max^2 para alguma constante c. Determine uma aproximação para esta constante escrevendo um pequeno programa para simular esta versão simplificada deste truque.

O desafio principal nesta linha é provar que, de fato, N(n_max) é assintótico a c n_max^2 para alguma constante c.

Análise Teórica do Truque do Original

Eis um desafio para aqueles que acharam processos estocásticos interessante: analise o truque do baralho teoricamente. Você consegue estimar a probabilidade do truque descrito no EP1 da Poli dar certo? No enunciado daquele EP, está dito que esta probabilidade é de algo como 75%.

Para este desafio, você pode precisar usar pacotes de manipulação numérica ou algébrica (como MATLAB ou Maple).

[Página principal dos desafios de MAC338 | Página principal de MAC338 (BCC - 1o. Semestre de 2000)]

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Tue Mar 14 04:08:38 BRT 2000