Algoritmos de aproximacao e problemas com sequencias.

• Processo: 07/57151-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de dezembro de 2007
• Data de Término da vigência: 30 de novembro de 2008
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cristina Gomes Fernandes
• Beneficiário: Rafael Crivellari Saliba Schouery
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Algoritmos de aproximação Complexidade computacional Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao | Complexidade Computacional | Otimizacao Combinatoria

Resumo

Problemas envolvendo seqüências aparecem nas mais diversas áreas, como por exemplo em compressão de dados e em, biologia computacional. Um dos problemas bem conhecidos envolvendo seqüências é o problema da superseqüência comum mínima (shortest common supersequence), que denotamos por SCS: dadas seqüências s_1,...,s_n (finitas) de símbolos sobre um alfabeto, encontrar uma seqüência de comprimento mínimo que seja Superseqüência de cada s_i, para i=1,...,n. Sabe-se que o SCS é NP-difícil, e mesmo MAX SNP-difícil. Neste projeto o plano é estudar algoritmos de aproximação, suas análises e alguns resultados de complexidade computacional para o SCS Especial atenção será dada às análises de um algoritmo conhecido como algoritmo guloso para o SCS, e a uma conjectura relacionada a este algoritmo. (AU)