Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
Aquí utilizamos el paralelismo a nivel de palabra para recuperar una subsecuencia común más larga de dos cadenas de entrada, ambas de longitud n en O (n2 / w) & nbsp; tiempo y espacio, donde w es el número de bits en una palabra de máquina. Para el caso especial en el que una de las cadenas de e...
- Autores:
-
Iliopoulos, Costas S.
Pinzón Ardila, Yoan
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2002
- Institución:
- Universidad Autónoma de Bucaramanga - UNAB
- Repositorio:
- Repositorio UNAB
- Idioma:
- spa
- OAI Identifier:
- oai:repository.unab.edu.co:20.500.12749/9066
- Acceso en línea:
- http://hdl.handle.net/20.500.12749/9066
- Palabra clave:
- Longest common subsequence
Bit-parallelism
System design
Investigation
Information technology
Information sciences
Diseño de sistemas
Investigación
Tecnología de la información
Ciencias de la información
Subsecuencia común más larga
Paralelismo de bits
- Rights
- License
- Derechos de autor 2002 Revista Colombiana de Computación
| Summary: | Aquí utilizamos el paralelismo a nivel de palabra para recuperar una subsecuencia común más larga de dos cadenas de entrada, ambas de longitud n en O (n2 / w) & nbsp; tiempo y espacio, donde w es el número de bits en una palabra de máquina. Para el caso especial en el que una de las cadenas de entrada está cerca de w, su complejidad se reduce a tiempo y espacio lineales. Palabras clave: Subsecuencia común más larga, paralelismo de bits. |
|---|