fun_ver (em vários formatos) neste diretório. Este programa simula este jogo entre
dois jogadores (o programa usa o módulo gb_flip para simular os lances da moeda).
fun_ver_modif.c, gb_flip.c e gb_flip.h e gere um executável
fun_ver_modif. Veja aqui
como você pode fazer isto. Em particular, você pode usar este Makefile.
fun_ver_modif.c automaticamente, após ter
escrito o programa fun_ver.w em CWEB.
Você deve estudar o programa fun_ver; use os arquivos fun_ver.dvi (que pode ser
visualizado com o programa xdvi no X), fun_ver.ps, ou fun_ver.pdf. Você pode obter o
CWEB na página acima, juntamente com o manual etc. Para ler
programas em CWEB, você não precisa saber nada sobre este
sistema, já que a apresentação é bastante intuitiva. De qualquer forma,
você pode consultar um capítulo de umas poucas páginas no livro sobre o Stanford
GraphBase (este é um livro de Knuth de programas
escritos em CWEB).
fun_ver estão além do escopo
desta disciplina, mas você deve ser capaz de entender como executá-lo (veja
compila.txt). Só para mencionar, neste
programa usamos um algoritmo famoso de Knuth, Morris e Pratt para
busca de padrões. Se você estiver curioso sobre este problema clássico de
busca de padrões, você pode consultar http://www.dir.univ-rouen.fr/~charras/string/string.html.
fun_ver para fazer uma
série de experimentos com o jogo Penney-Ante. Observação. Você
não deve se basear muito no programa fun_ver_modif.c!
Este programa está sendo fornecido apenas como algo com que você pode
experimentar. Os seus programas devem ser escritos `a partir do zero'. Em
princípio, eu poderia ter fornecido apenas executáveis de
fun_ver.
fun_ver. Para tanto, você deve observar em
fun_ver que (a) o gerador de números aleatórios deve ser
inicializado com gb_init_rand(seed), onde seed é a
semente dada, e (b) para gerar 0 ou 1 com
probabilidade 1/2 cada, você deve executar a chamada
gb_unif_rand(2). Em fun_ver, 0 é
identificado com `cara' (H) e 1 com
`coroa' (T).
gb_flip se comporte de forma idêntica em todas as situações.
Para ver se a máquina/ambiente/compilador que você está usando é compatível
com o gb_flip, você pode executar um pequeno teste, compilando
e rodando o programa test_flip.c. Veja aqui
o teste que executei na rede Pró-aLinux do IME. (O Makefile deste
diretório é o mesmo que o Makefile usado para gerar o
fun_ver_modif.)
HTHH, um inteiro positivo n
e uma semente seed (para o gerador de números aleatórios).
No caso n = 1, o seu programa ep3a deve simular uma
seqüência de lances de uma moeda honesta (i.e., com probabilidade
1/2 de dar tanto cara como coroa) até que o padrão dado ocorra.
O seu programa deve imprimir o comprimento da seqüência de caras e coroas
gerada, isto é, o número de vezes que a moeda foi lançada, até o padrão dado
ocorrer. Veja aqui como o
fun_ver_modif pode ser usado.
Quando n > 1, o seu programa ep3a deve executar
n experimentos e registrar o resultado (i.e., o número de lances
da moeda) em cada caso. Ele deve imprimir a média destes valores. Por
exemplo, para a entrada HTHH, seed = 31415 e n
= 10, o resultado deve ser 32.4 (os resultados dos
10 experimentos são, respectivamente, 48 61 9 46 13 24 66
15 23 19. Veja aqui). Para a
entrada HTHH, seed = 31415 e n =
100000, o resultado deve ser 17.9264.
p1 e p2, uma semente
seed, e um inteiro positivo n. O seu
programa ep3b deve simular o jogo Penney-Ante com os dois
padrões dados, usando seed para inicializar o gerador de
números aleatórios gb_flip. O programa deve, na verdade,
simular n jogos com estes padrões (com
gb_flip inicializado uma única vez, naturalmente).
Ao término destas n simulações, o programa deve dizer quantas
vezes cada um dos padrões venceu. O programa também deve imprimir a razão
entre o número de vitórias do padrão p1 e n. Note
que esta razão é uma estimativa para a probabilidade do padrão
p1 ser `melhor' que o padrão p2 neste jogo
(isto é, para a probabilidade de p1 ocorrer antes de
p2 em uma seqüência aleatória).
Escrevamos P(p1, p2) para a probabilidade do parágrafo anterior.
Existe uma fórmula para esta probabilidade; você pode ver, por exemplo, o
programa fun_ver. Esta fórmula, devida a J.H. Conway, está além
do escopo desta disciplina, e portanto nós nos contentaremos com as
estimativas que obteremos usando o ep3b para valores grandes de
n.
O programa fun_ver_modif pode ser usado para ver como tais
estimativas se comparam com o resultado teórico. Veja nestes arquivos como
usar este programa: exemplo3b1.txt, exemplo3b2.txt.
O seu programa ep3b deve ser capaz de obter boas
estimativas experimentais para os valores de P(p1, p2)
para padrões p1 e p2 de comprimento
razoável. Note que, para tanto, o seu programa deve ser o mais
eficiente possível, já que suas estimativas vão ser melhores para
n maiores.
Executando seu ep3b para várias entradas, você poderá
classificar padrões de acordo com a sua `eficácia' neste jogo. De
fato, o padrão p1 é `melhor' que o padrão p2
se
P(p1, p2) > 1/2.
Por comodidade, se este for o caso, vamos escrever p1 > p2.
ep3c deve receber como entrada inteiros
positivos n e L. Aqui, L será
o comprimento dos padrões que consideraremos. O comprimento de um
padrão é, naturalmente, o número total de Hs e
Ts no padrão; por exemplo, HTHH tem
comprimento 4. O inteiro n é o número de vezes que você
deve simular o jogo entre dois padrões para estimar a probabilidade de
vitória de um deles sobre o outro.
A saída de ep3c deve ser uma lista de triplas (p1,
p2, p3) de padrões de comprimento L. Estas
triplas devem satisfazer a seguinte propriedade:
p1 > p2 > p3 > p1
(Veja a definição de > acima.) O seu programa
ep3c deve encontrar o maior número possível de tais triplas.
Pode ser útil para o usuário de ep3c a possibilidade de
pedir apenas o número de tais triplas que ele encontrou, ao invés de
imprimir todas as triplas encontras. Implemente esta opção em seu
ep3c.
Note que, em particular, uma hipótese subjacente a este enunciado para
ep3c é que, um tanto surpreendentemente, a relação
> não é transitiva (se fosse, triplas como
acima não existiriam).
Observação. Para verificar sua saída, veja o arquivo saidaEP3c.txt. O programa que usei para gerar esta
saída é baseado na fórmula de Conway (veja o programa fun_ver).
ep3d que procura seqüências longas de
padrões p1, p2, p3,... satisfazendo
p1 > p2 > p3 > ... > p1.
Tais seqüências de comprimento L existem, com padrões de
comprimento L. Será que existem tais seqüências com
muito mais do que L elementos? Note que o número de
padrões de comprimento L é 2^L, que é muito
maior que L (para valores grandes de L).
/*********************************************************************** * * Nome do Aluno ... Numero USP ... * * Curso ... Data ... * * Nome do Professor ... * * Exercicio Programa Numero ... * * Compilador usado ... * **********************************************************************/
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Tue Jun 22 14:29:34 EST 1999