Busca avançada
Ano de início
Entree

Problemas de transformação de strings por operações de rearranjo

Processo: 19/13312-7
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de junho de 2020
Vigência (Término): 31 de maio de 2021
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Carla Negri Lintzmayer
Beneficiário:Gustavo da Silva Teixeira
Instituição-sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
Assunto(s):Algoritmos   Otimização combinatória   Ordenação   Símbolo   Problema computacional   Análise de algoritmos

Resumo

Nos Problemas de Transformação de Strings (ou Ordenação de Permutações) por Operações de Rearranjo, dadas duas sequências de símbolos - onde cada símbolo aparece o mesmo número de vezes em cada sequência - e um conjunto de operações de rearranjo permitidas, deseja-se encontrar uma sequência de menor custo, contendo operações de rearranjo, que transforme uma sequência de símbolos na outra. O custo desta sequência ótima de operações representa a distância entre as duas sequências de símbolos dadas. Se considerarmos que as sequências possuem apenas uma cópia de cada símbolo, podemos representá-las como permutações, sendo esta a abordagem mais tradicional para lidar com os problemas de Transformação por Operações de Rearranjo. Porém, outra abordagem é a que considera que há pelo menos um símbolo com mais de uma cópia dentro das sequências. Nestes casos, a representação se dá por meio de strings. Desde o final da década de 1970, quando Gates e Papadimitriou publicaram sobre limitantes para o Problema das Panquecas (ou Ordenação de Permutações por Reversões de Prefixo), vários trabalhos foram desenvolvidos a fim de obter resultados para problemas relacionados. Os principais esforços têm por objetivo encontrar algoritmos que retornem soluções próximas à solução ótima, visto que grande parte dos problemas relacionados são NP-difíceis. No entanto, comparando a abordagem que considera strings com a abordagem que considera permutações, ainda pode-se observar a falta de resultados algorítmicos na literatura para os problemas sobre strings. Este projeto de Iniciação Científica tem por objetivo estudar os Problemas de Transformação de Strings por Operações de Rearranjo, do ponto de vista teórico, investigando os resultados obtidos na área até então e as técnicas algorítmicas que podem vir a ajudar na obtenção de novos resultados, com a intenção de propor novos algoritmos para os problemas.