Por favor, use este identificador para citar o enlazar este ítem:
https://repositorio.ufba.br/handle/ri/20213
metadata.dc.type: | Trabalho de Conclusão de Curso |
Título : | Um estudo avançado do problema da Maior Subsequência Comum |
Autor : | Paoli, Antonio Roberto |
metadata.dc.creator: | Paoli, Antonio Roberto |
Resumen : | 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. |
Palabras clave : | Maior Subsequência Comum LCS bit-paralelo paralelização diagonal longest common subsequence |
metadata.dc.subject.cnpq: | Matemática Ciência da Computação |
metadata.dc.publisher.country: | Brasil |
metadata.dc.publisher.initials: | UFBA |
metadata.dc.rights: | Acesso Aberto |
URI : | http://repositorio.ufba.br/ri/handle/ri/20213 |
Fecha de publicación : | 31-ago-2016 |
Aparece en las colecciones: | Trabalho de Conclusão de Curso (Graduação) - Ciência da Computação (IC) |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
LCS_TCC-Final.pdf | 3,39 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.