Re: Dúvidas

[Giuliano Mega <megag@terra.com.br>]

    Essa questão também me pareceu um tanto estranha. Comecei procurando
por alguma condição
necessária para haver um perfect hashing. SE um perfect hashing for
apenas a ausência de colisões,
pensei o seguinte:
    Dadas m chaves arbitrárias, seja A um conjunto que as contenha.
Queremos M e 'a' tais que dados
x1, x2 chaves de A => a*x1(modM) != a*x2(modM) <=> a*x1 != a*x2 => x1 !=
x2; ou seja, queremos que
para cada elemento de A que seja uma chave exista uma e somente uma
classe de equivalência o contenha . O
problema é  que se x1 e x2 são arbitrários, a única maneira de
garantirmos que x1(modM) != x2(modM) é
fazendo M = a*(max{A} - min{A})Qualquer M menor que isso faz com que
duas chaves potencialmente possam
cair na mesma classe de equivalência.
"Ok, então qual a sua conclusão?" - alguém me pergunta.
Ok - eu digo - minha conclusão é que isso está errado por algum motivo
pois:

1 - É trivial demais
2 - O 'a' pode ser muitas coisas e, a rigor, não existe perda se a = 1
3 - Não precisa de um programa para achar isso
4 - É quase equivalente a achar o resto fazendo x1 - min{A}

Me ajudem, eu também não sei fazer.

Ok, o jeito da Flávia realmente parece melhor (gerar baseado no conjunto
de dados, mais especificamente
nas chaves). A única coisa que me pareceu talvez não funcionar foi o
seguinte:

> > Eu começo com M = n + 1 (para deixar um espaço vazio) e vou testando
> valores
> > aleatórios de a. A função colisao() retorna true se houver colisão
> entre as
> > chaves. Se não achar um valor adequado de a após 100 tentativas,
> aumento o
> > valor de M.

Meu problema com este pedaço é: o que me garante que o 'a' correto para
este M, caso exista, vai
sair em 100 iterações?

> Não sei não, talvez eu esteja errada, mas por ele pedir o valor de M
> tal que a*x%M é o menor possível, para que todas as chaves daquela
> tabela sejam diferentes, não seria muito interessante deixar a
> variável a ser um float, exatamente por estar em uma operação de
> módulo. Eu faria assim:int M, int a;for( M = N; ; M++)   //N é o
> número de elementos    for(a = 1; a < M; a++)        //testo as
> colisões de todas as chaves Assim, ele começa com um M de menor valor
> possível de se construir a tabela (que é o próprio número de elementos
> N), e, para cada valor de a que altere o resultado final módulo M
> (para isso, a tem que estar entre 1 e M-1), verifico se M satisfaz
> número de colisões = 0.

É, pode ser. Também pensei nisso, mas foi ao olhar o texto que
verifiquei que o Sedgewick usa a razão áurea como 'a' num exemplo.
Professor, o senhor poderia nos dar uma mão com este aqui??

[]'s

Giuliano