aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por sandro vilela -
Número de respostas: 6

Imagino ter encontrado uma resposta para a questao 5.3.3-CLRS, se estah certa...eh outra estória, rs

Bom, a questao trata do fato se a função Permute-with-all(A) produz uma permutação aleatória uniforme, ou não.

Permute-with-all(A)

 (1)                   n = comp.[A]

 (2)                   for i=1 to n

 (3)                          do trocarA[i] = A[RANDOM(1,n)]

 

Solução:

Façamos, antes de mais nada, um pequeno teste.

Tomemos um vetor de tamanho igual a 3. Assim, teremos 3 chamadas a função Random, a qual, retornará um dos 3 valores ( do vetor ) possíveis, logo teremos 27 possíveis saídas para a chamada de Permute-with-all(A).

Porém, nao podemos nos esquecer que dado um vetor de 3 posições teremos um total de 3! = 6 permutações possíveis. Logo, se Permute-with-all(A) produz uma distribuição (aleatória) uniforme, então cada permutação deverá ocorrer com uma probabilidade igual a 1/6.

Agora, fazendo-se com que T, seja o número de vezes que uma dada permutação ocorra, assim teremos:

( T / 27 ) = ( 1 / 6 )

Como podemos observar, não há valor inteiro para T que satisfaça esta equação, assim conclui-se que Permite-with-all (A) não produz uma permutação aleatória uniforme.

Bom, não sei...parece certo.

Se alguém ajudar ....agradeço.

 

 

Em resposta à sandro vilela

Re: aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por Domingos Soares -
Oi Sandro,

Até que enfim alguém mandou uma mensagem para o fórum. sorriso
Bom, eu não encontrei nenhum erro na sua solução. Aliás, ela é parecida com a que o Coelho comentou comigo na segunda-feira. Dá para extender para o caso geral apenas observando que o número de saídas possíveis para o algoritmo será igual a n^n. Você ficará com T/(n^n) = 1/n!

Abraços,

Domingos.
Em resposta à Domingos Soares

Re: aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por sandro vilela -

OI, Domingos

Muito obrigado pela ajuda.Não tinha pensado em extender para o caso geral, boa idéia.

Valeu

Sandro

Em resposta à sandro vilela

Re: aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por Daniel Ribeiro -
Alguém conseguiu demonstrar que (n-1)! não divide n^(n - 1) (que é o que falta para mostra que T = n^n / (n!) não é inteiro)? O caso para n primo é bem fácil, mas para n composto o negócio complica...
Em resposta à Daniel Ribeiro

Re: aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por Paulo Salem -
Se para n primo a tese não vale, então não é verdade que existe um n a partir do qual ela passa a valer sempre, pois os primos são infinitos. Ou seja, não podemos dar uma garantia assintótica de que o algorítimo é correto. Isso não prova para todo n, mas já é uma afirmação mais forte do que os contra-exemplos que utilizamos antes.

Se bem que, a rigor, temos que dizer para n primo maior do que 2, pois com n = 2 a divisão é inteira.
Em resposta à Paulo Salem

Re: aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por Daniel Ribeiro -
É verdade, mostrar que a proposição não vale para um conjunto infinito de números inteiros é um excelente contra-exemplo, e é suficiente para provar que ele não gera permutações equiprováveis para qualquer n.

Contudo, a pergunta fica: para n's compostos, ele pode gerar as permutações de modo equiprovável?
Em resposta à Daniel Ribeiro

Re: aula exercicios 6 - questao 15.A ( 5.3.3 CLRS)

por Lucas Gadani -
Não pode... Se n é primo, é fácil. Se n=4, 6 não divide 64. Se n=6, 120 não divide 625. [edit: oops, errei aqui. deveria ser: se n=6, 120 não divide 7776]. Se n é composto e n>=8 suponha, por absurdo, que (n-1)! divide n^(n-1). Como n é composto, (n-1)! contém como fatores todos os primos entre 2 e n. Logo, como (n-1)! divide n^(n-1), n^(n-1) necessariamente também contém todos os primos entre 2 e n como fatores. Se n = p1^a1 p2^a2 ... pk^ak é uma fatoração de n em números primos, então n^(n-1) = p1^(a1(n-1)) p2^(a2(n-1)) ... pk^(ak(n-1)), logo, n necessariamente precisa conter todos os primos entre 2 e n como fatores. Agora, pelo teorema de Chebyshev, sabemos que dado um inteiro m, existe um primo entre m e 2m. Logo, existe um primo entre _|n/2|_ (chão de n/2) e n. Como n>=8, _|n/2|_ é pelo menos 4. Logo, se q é esse primo, 2*3*q = 2*3*_|n/2|_ >= 2*3*(n-1)/2 = 3*(n-1) > n para n >= 8, absurdo. Então (n-1)! não pode dividir n^(n-1).