Este EP gerou um exercício para MAC 242
Laboratório de Programação II.
Veja o enunciado e outras explicações na página
http://www.ime.usp.br/~is/ddt/mac5711/anagramas-perl.html
Uma solução do EP1, em Perl, devido ao Professor Arnaldo Mandel.
Uma outra solução, ainda em Perl, mais eficiente em espaço e tempo.
Em ambas as soluções acima Você deve tornar os arquivos executáveis em algum sistema Unix e processá-los com um único argumento, que deve ser o arquivo do vocabulário. Experimente e compare a eficiência destes programas com o seu!
Uma solução, em C, foi feita pelo Professor Yoshiharu Kohayakawa. Esta solução esmera pela documentação e pelo uso de estruturas de dados sofisticados.
Um grupo de alunos (Jean e Gustavo) achou uma solução muito eficiente, usando um hashing (espalhamento) muito engenhoso. A rigor a solução deles funciona neste caso, mas não há garantia de que funcione com qualquer arquivo. Mesmo assim, a idéia merece destaque por ser uma técnica muito usada em computação. Veja o capítulo 14 do livro do Sedgewick. Seria muito interessante "consertar" a solução com hashing e colocá-la nesta página.
Uma outra aplicação de hashing está embutida nos programas sum e cksum do Unix. As fontes destes programas são disponíveis, o cksum se baseia num padrão POSIX.2 para a técnica de CRC (Cyclic Redundancy Check). Consulte a página cyclic redundancy check from FOLDOC.
MAC 122 Princípios de Desenvolvimento de Algoritmos
e-mail:
Imre Simon <is@ime.usp.br>