Exercícios sobre a aula de 2007-03-19

Questões disponíveis em : http://www.ic.unicamp.br/~meidanis/courses/mo640/2007s1/exerc/2007-03-19.html

1) O Colega Celmar apresentou sua tabela com a solução dos exercícios (tabela
planilha_colega_celmar.xls em anexo). A tabela funciona da mesma forma que 
a que calcula alinhamento local, porém neste caso (pontas-livres) ela pode
ter valores negativos (não há a restrição de que as células têm que ser 
não negativas). 
Foi explicada a razão do alinhamento de pontas-livres não usar max(0,V(i,j)),
a saber : porque no alinhamento local o match começa de qualquer lugar, e no 
de pontas-livres não. No de pontas-livres uma seqüência pode acabar antes,
mas neste caso a outra deve continuar até o seu final,
por isso que se olha tanto na última linha quanto na última coluna pela 
resposta, e não só na última célula (como é feito no alinhamento global).

2) O colega Daniel apresentou sua tabela com as soluções (tabela planilha_colega_daniel.xls em anexo). Foi elogiado pelo uso de constantes 
simbólicas ao construir sua tabela. Apresentou as seguintes saídas :

- Alinhamento Global        : 13
- Alinhamento Local         : 16
- Alinhamento Pontas-Livres : 16

As tabelas do Local e Pontas-Livres foram exatamente idênticas. A razão
disso, após discussão da classe, foi apontada como sendo a escolha de 
pesos do professor, que atribui valor positivo para a penalidade do mismatch,
o que efetivamente faz com que em nenhum momento a tabela adquira valores
negativos no alinhamento de pontas-livres. O texto do Shamir, ao tratar das
pontuações, obrigava o mismatch a ser negativo.

3) O colega Mário César respondeu que sim, e a explicação, com a ajuda
do professor, ficou como sendo a seguinte : todo alinhamento global é
também um alinhamento de pontas-livres. Assim, um alinhamento de
pontas-livres com pontuação máxima terá tantos ou mais pontos que
qualquer alinhamento global, e, em particular, que os melhores
globais. Da mesma forma, todo alinhamento de pontas-livres é também um
alinhamento local.  Assim, um alinhamento local de pontuação máxima
terá tantos ou mais pontos que qualquer alinhamento pontas-livres, e,
em particular, que os melhores de pontas-livres.