Artículos
Algoritmos exacto y de kernelización para el problema de la subsecuencia de caracteres más próxima
Editorial: UNITRU
Licencia: Creative Commons (by-nc)
Autor(es): Latorre, Omar
Licencia: Creative Commons (by-nc)
Autor(es): Latorre, Omar
En este artículo abordamos el problema de la subsecuencia de caracteres más próxima que surge en la búsqueda web, la teoría de la codificación y la biología molecular computacional. Para resolverlo debe se encontrar una subsecuencia de caracteres que minimice la distancia de Hamming máxima de un conjunto dado de subsecuencias, dicho problema está en NP-hard. Este artículo propone dos algoritmos de tiempo lineal, uno para el caso general, un algoritmo de kernelización, y el otro para tres subsecuencias de caracteres, un algoritmo de tiempo lineal llamado Algoritmo de la primera minimización (MFA). Se expresa una prueba formal para verificar la corrección y complejidad computacional de los algoritmos propuestos.
[2020]
Compartir:
Esta es una vista previa de los documentos vistos recientemente por el usuario.
Una vez que el usuario haya visto al menos un documento, este fragmento será visible.
Una vez que el usuario haya visto al menos un documento, este fragmento será visible.