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.