Anagramas em PERL

Seguem o enunciado e um esclarecimento sobre o exercício da disciplina MAC 242 Laboratório de Programação II.

Date: Fri, 15 Oct 1999 12:11:45 -0300 
From: Arnaldo Mandel 
To: am-mac242@ime.usp.br
Subject: Lista 3
X-Mailer: VM 6.32 under Emacs 20.4.3

MAC-242 - Laboratório de programação II - Lista 3 
Dist: 15/10/99.  Entrega: 26/10/99.

Instruções:
a) A entrega deve ser feita por email, para o endereço:

   am-mac242-lista@ime.usp.br

   note bem que NÃO é para am-mac242@ime.usp.br ou am@ime.usp.br.
   Listas entregues em endereço errado terão uma penalidade de 2/3 da nota.
   Dúvidas, etc., devem continuar a ser enviadas para am-mac242@ime.usp.br.
   (Curioso que tem gente ainda errando a forma de entrega)

b) A mensagem deve ter como Subject 
   Lista 3
   Mande toda a lista como texto de um único mail; NÃO mande como attachment
   ou como vários arquivos.

Esta lista contem um único exercício, baseado no EP de 122

http://www.ime.usp.br/~pf/mac122/ep1/ep1.htm

Tentar fazer este exercício antes da prova pode ser um bom treino (embora as
questões da prova não sejam muito parecidas com esta).

Enunciado:

Você deve fazer um programa em perl cuja linha de comando receba um nome de
arquivo depois de algumas opções; uma dessas opções deve selecionar entre
algumas possíveis classes de equivalência de strings; outra dessas opções deve
selecionar entre diversas noções de "tamanho" de uma classe de equivalência.

O programa deve ler o arquivo e imprimir a maior classe de equivalência de
linhas (note que o \n não é considerado parte da linha), bem como seu tamanho.

Chamando o programa sem argumentos deve resultar numa mensagem de uso,
explicando as opções.

Você está livre para usar quaisquer módulos já instalados.

Pelo menos as seguintes relações de equivalência devem ser suportadas:

1) Anagrama ASCII: dois strings são equivalentes se têm exatamente os mesmos
   caracteres, com a mesma multiplicidade.
2) Anagrama BR: dois strings são equivalentes se têm exatamente as mesmas
   letras, com a mesma multiplicidade.  Note que isso significa considerar,
   por exemplo, A, a. Á. á, Â, â. À, à, Ã, ã como instâncias de uma mesma
   letra.

Pelo menos as duas medidas seguintes de tamanho devem ser suportadas:

1) Cardinalidade: número de strings na classe.

2) Peso: numero total de caracteres na classe.


O programa deve prever a introdução de futuras relações e futuras medidas de
tamanho; a documentação (pode estar nos comentários) deve explicar como
estender o programa.  Ele não precisa ser totalmente genérico - pode impor
restrições tanto às equivalências quanto aos tamanhos.  Por exemplo, exigir
que strings equivalentes tenham que ter o mesmo comprimento, ou exigir que
seja possível computar, a partir de um string dado, um representante canônico
da sua classe.

Para testes, use o arquivo 

/home/prof/am/pub/br

cuja origem está explicada na URL acima.

Veja quanto tempo seu programa gasta em cada chamada usando o comando time do
bash.  Envie os resultados junto com o programa.

Obs.: se seu programa tiver mais que 60 linhas de código, desconfie que algo
está muito errado.





Date: Wed, 20 Oct 1999 11:13:33 -0300 
From: Arnaldo Mandel 
To: am-mac242@ime.usp.br
Subject: Mais detalhes sobre a lista 3
X-Mailer: VM 6.32 under Emacs 20.4.3

Uma parte da especificação da lista 3 está um pouco vaga, por isso aí
vão mais detalhes.  Me refiro à forma de introduzir novas relações de
equivalência.  

A forma mais geral de se dar (computacionalmente) uma relação de equivalência
é através de uma função booleana de dois argumentos que devolve 1 ou 0
conforme os argumentos sejam ou não equivalentes.  Isto é um pouco
geral demais para ser interessante.

Aí vai uma outra sugestão:

Como vocês sabem (e quem não sabe é porque dormiu no curso de Álgebra I),
para toda relação de equivalência sobre um conjunto X existe uma função
definida em X tal que dois elementos são equivalentes se e só se têm a mesma
imagem.  Notem que o contradomínio da função fica ao gosto do freguês.

Dizemos que uma relação de equivalência sobre X é dada por *hashing* se existe
uma função *computável* definida em X tal que dois elementos são equivalentes
se e só se têm a mesma imagem.  Isto é, deve existir um *algoritmo* (digamos,
uma função em perl) que, dado x computa f(x).

Por exemplo, considere a seguinte equivalência: duas palavras são equivalentes
se têm a mesma sequência de vogais.  Uma função de hashing para essa relação
seria "apague todas as consoantes".  Outra: dois inteiros são equivalentes
(congruentes) módulo n se sua diferença é divisível por n; claro que uma
função de hashing é o resto da divisão por n.

Seria interessante que seu programa permitisse o acréscimo de novas relações
de equivalência dadas por funções de hashing.  Em particular, seria o caso de
descobrir funções de hashing para as relações descritas no enunciado da lista.


Aliás, essa lista é mais que uma simples lista, já é um pequeno EP.  Vai ser
tratado como tal.

------------------------------------------------------------

E que tem esse hashing a ver com tabelas de hashing?  

Imagino que alguns de vocês se estejam perguntando isso.  No caso de tabela de
hashing, começamos com um conjunto X de chaves e definimos uma função de
hashing sobre X com valores num intervalo inteiro, digamos 0..n .  A idéia é
usar um vetor indexado por 0..n para armazenar subconjuntos de X.  Entra aí a
idéia de "colisão": dois elementos "colidem" se são equivalentes relativamente
a essa função de hashing.

Normalmente, n é menor do que o tamanho do conjunto X e a teoria de hashing
vai atrás de formas de obter funções tais que as classes de equivalência
tenham mais ou menos o mesmo tamanho.  Em algumas situações existem funções de
hashing injetoras, isto é, a equivalência que representam é a identidade.
Essas funções são chamadas de "hashing perfeito".

Notem a diferença do ponto de vista: no exercício, o objeto de interesse é a
relação de equivalência e a função de hashing é um meio de representá-la; no
caso de tabelas de hashing, o objeto de interesse é a família de subconjuntos
de X, e a relação de equivalência é um acidente decorrente da
dificuldade/impossibilidade ocasional de se obter um hashing perfeito.

am

MAC 5711 Análise de Algoritmos