Lista de Discussão de MAC 5726 - Biologia Computacional

[Prévia por Data][Próxima por Data]
[Prévia por Assunto][Próxima por Assunto]
[Índice por Data][Índice por Assunto]
[Envie uma nova mensagem para a lista] [Responda esta mensagem]

Re: Notas de Biologia Computacional


O problema principal foi fazer uma prova por indução em n da
afirmação:
"A rotulação obtida pelo algoritmo Fitch-Hartigan é ótima".

Nas demonstrações, a árvore T é dividida em raiz + T1 + T2.
Por hipótese de indução, T1 e T2 têm rotulações ótimas obtidas pelo
algoritmo. Como juntar essas rotulações com a raiz e obter uma
rotulação também ótima?
Eu não sei como fazer isso. 
E é falso que se T1 e T2 têm rotulações ótimas, então é possível
juntar a raiz e obter uma rotulação ótima sem mexer nas rotulações de
T1 e T2. 

Também é falso que se a rotulação de T é ótima, então as rotulações de
T1 e T2 são ótimas.

É fato que a árvore ótima não é única. Somente uma delas é obida pelo
algoritmo. Como garantir que, talvez com outra rotulação ótimas nas
subárvores T1 e T2, o resultado global não seja melhor?

Zé Augusto

=?iso-8859-1?Q?Rog=E9rio?= Brito wrote (on Dec 13, 2001):
 > On Dec 13 2001, Jose Augusto R. Soares wrote:
 > > Ao pessoal da pós, que fez demonstração da corretude do algoritmo de
 > > Fitch-Hartigan, somente um de vocês, que já foi avisado, fez
 > > realmente uma prova. As outras tentativas estão erradas. Se você
 > > quiser conferir, passe na minha sala!
 > 
 > 	Oi, professor.
 > 
 > 	Apenas por curiosidade em relação à parte mais didática da
 > 	coisa (algo com que eu tenho me preocupado mais ultimamente
 > 	que estou escrevendo a dissertação), quais foram os erros
 > 	principais cometidos nas tentativas de demonstração?
 > 
 > 
 > 	Abraços, Roger...
 > 
 > -- 
 > =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 >   Rogério Brito - rbrito@ime.usp.br - http://www.ime.usp.br/~rbrito/
 > =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=