https://repositorio.ufba.br/handle/ri/20213
Tipo: | Trabalho de Conclusão de Curso |
Título: | Um estudo avançado do problema da Maior Subsequência Comum |
Autor(es): | Paoli, Antonio Roberto |
Autor(es): | Paoli, Antonio Roberto |
Abstract: | O problema da Maior Subsequência Comum é um problema clássico da Ciência da
Computação que consiste em encontrar a mais longa subsequência de caracteres comuns
a duas strings. A solução genérica é obtida pelo uso de uma matriz que combina estes
caracteres dois a dois, com alto custo de tempo e uso de memória. Este trabalho busca
soluções para o cálculo mais eficiente do comprimento da Maior Subsequência Comum.
Para isso, propõe dois novos algoritmos denominados limpeza de matriz e diagonal.
Para confirmar os resultados destes novos algoritmos são apresentadas e avaliadas as
implementações de diversos trabalhos bem estudados na literatura que são comparados nas
mesmas condições de ambiente. Adicionalmente, as soluções são submetidas ao repositório
do Sphere online Judge (SPOJ) para confirmar os resultados pelo confrontamento com
diferentes soluções de programadores de todo o mundo. The problem of Longest Common subsequence (LCS) is a classic problem of computer science which is to find the longest subsequence of characters common to two strings. The general solution is obtained by use of a matrix that combines these two by two characters, with a high time cost and memory usage. This work seeks solutions for more efficient calculation of the length of the LCS. To this end, proposes two new algorithms called matrix cleaning and diagonal. To confirm the results of these new algorithms are presented and evaluated the implementation of several works well studied in the literature and compared in the same environmental conditions. In addition, these solutions are submitted to Sphere online Judge (SPOJ) repository to confirm the results by confrontation with different programmer solutions worldwide. |
Palavras-chave: | Maior Subsequência Comum LCS bit-paralelo paralelização diagonal longest common subsequence |
CNPq: | Matemática Ciência da Computação |
País: | Brasil |
Sigla da Instituição: | UFBA |
Tipo de Acesso: | Acesso Aberto |
URI: | http://repositorio.ufba.br/ri/handle/ri/20213 |
Data do documento: | 31-Ago-2016 |
Aparece nas coleções: | Trabalho de Conclusão de Curso (Graduação) - Ciência da Computação (IC) |
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
LCS_TCC-Final.pdf | 3,39 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.