O Problema da subseqüência comum máxima sem repetições

Resumo:

Neste seminário abordamos o problema da subseqüência comum máxima sem repetições: dadas duas seqüências sobre um alfabeto desejamos encontrar uma subseqüência comum máxima das duas, na qual cada símbolo pode aparecer no máximo uma vez. Este problema tem aplicações em Biologia Computacional. Mostraremos resultados iniciais de uma investigação de um poliedro relacionado ao problema. Este trabalho está sendo realizado em conjunto com Cristina G. Fernandes, Christian Tjandraatmadja e Yoshiko Wakabayashi.