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...

Full description

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
id UNAB2_82962c08813f57b9d6b79758162ecf11
oai_identifier_str oai:repository.unab.edu.co:20.500.12749/9066
network_acronym_str UNAB2
network_name_str Repositorio UNAB
repository_id_str
spelling Iliopoulos, Costas S.ffba1a2c-7947-42f1-9e5b-e5c721da8a2dPinzón Ardila, Yoan513a8859-d422-4f7d-9ccd-4539a63d7c50Grupo de Investigación Tecnologías de Información - GTIGrupo de Investigaciones Clínicas2020-10-27T00:21:31Z2020-10-27T00:21:31Z2002-06-012539-21151657-2831http://hdl.handle.net/20.500.12749/9066instname:Universidad Autónoma de Bucaramanga UNABrepourl:https://repository.unab.edu.coAquí 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.Here we make use of word-level parallelism to recover a longest common subsequence of two input strings both of length n in O(n2/w)  time and space, where w is the number of bits in a machine word. For the special case where one of the input atrings is close to w its complexity is reduced to linear time and space.Keywords: Longest Common Subsequence, Bit-parallelism.application/pdfspaUniversidad Autónoma de Bucaramanga UNABhttps://revistas.unab.edu.co/index.php/rcc/article/view/1107/1079https://revistas.unab.edu.co/index.php/rcc/article/view/1107L. Allison and T.L. Dix, A bit-string longest common subsequence algorithm, Inform. Process. Lett., 23, 305-310, (1986).Derechos de autor 2002 Revista Colombiana de Computaciónhttp://creativecommons.org/licenses/by-nc-sa/4.0/http://creativecommons.org/licenses/by-nc-nd/2.5/co/Atribución-NoComercial-SinDerivadas 2.5 Colombiahttp://purl.org/coar/access_right/c_abf2Revista Colombiana de Computación; Vol. 3 Núm. 1 (2002): Revista Colombiana de Computación; 41-51Recuperando una LCS en O (n ^ 2 / w) tiempo y espacioRecovering an LCS in O(n^2/w) time and spaceinfo:eu-repo/semantics/articleArtículohttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/redcol/resource_type/CJournalArticleLongest common subsequenceBit-parallelismSystem designInvestigationInformation technologyInformation sciencesDiseño de sistemasInvestigaciónTecnología de la informaciónCiencias de la informaciónSubsecuencia común más largaParalelismo de bitsTHUMBNAIL2002_Recuperando_una_LCS.pdf.jpg2002_Recuperando_una_LCS.pdf.jpgIM Thumbnailimage/jpeg9335https://repository.unab.edu.co/bitstream/20.500.12749/9066/2/2002_Recuperando_una_LCS.pdf.jpg307445e8811afc9641d53097cff047e5MD52open accessORIGINAL2002_Recuperando_una_LCS.pdf2002_Recuperando_una_LCS.pdfArtículoapplication/pdf627004https://repository.unab.edu.co/bitstream/20.500.12749/9066/1/2002_Recuperando_una_LCS.pdf17e3c5ac4f608e451ed81bfa7898e1e4MD51open access20.500.12749/9066oai:repository.unab.edu.co:20.500.12749/90662024-01-19 15:32:40.274open accessRepositorio Institucional | Universidad Autónoma de Bucaramanga - UNABrepositorio@unab.edu.co
dc.title.none.fl_str_mv Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
dc.title.translated.none.fl_str_mv Recovering an LCS in O(n^2/w) time and space
title Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
spellingShingle Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
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
title_short Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
title_full Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
title_fullStr Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
title_full_unstemmed Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
title_sort Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio
dc.creator.fl_str_mv Iliopoulos, Costas S.
Pinzón Ardila, Yoan
dc.contributor.author.spa.fl_str_mv Iliopoulos, Costas S.
Pinzón Ardila, Yoan
dc.contributor.researchgroup.spa.fl_str_mv Grupo de Investigación Tecnologías de Información - GTI
Grupo de Investigaciones Clínicas
dc.subject.keywords.eng.fl_str_mv Longest common subsequence
Bit-parallelism
System design
Investigation
Information technology
Information sciences
topic 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
dc.subject.lemb.spa.fl_str_mv Diseño de sistemas
Investigación
Tecnología de la información
Ciencias de la información
dc.subject.proposal.spa.fl_str_mv Subsecuencia común más larga
Paralelismo de bits
description 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.
publishDate 2002
dc.date.issued.none.fl_str_mv 2002-06-01
dc.date.accessioned.none.fl_str_mv 2020-10-27T00:21:31Z
dc.date.available.none.fl_str_mv 2020-10-27T00:21:31Z
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/article
dc.type.local.spa.fl_str_mv Artículo
dc.type.coar.none.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.redcol.none.fl_str_mv http://purl.org/redcol/resource_type/CJournalArticle
format http://purl.org/coar/resource_type/c_7a1f
dc.identifier.issn.none.fl_str_mv 2539-2115
1657-2831
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/20.500.12749/9066
dc.identifier.instname.spa.fl_str_mv instname:Universidad Autónoma de Bucaramanga UNAB
dc.identifier.repourl.none.fl_str_mv repourl:https://repository.unab.edu.co
identifier_str_mv 2539-2115
1657-2831
instname:Universidad Autónoma de Bucaramanga UNAB
repourl:https://repository.unab.edu.co
url http://hdl.handle.net/20.500.12749/9066
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1107/1079
dc.relation.uri.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1107
dc.relation.references.none.fl_str_mv L. Allison and T.L. Dix, A bit-string longest common subsequence algorithm, Inform. Process. Lett., 23, 305-310, (1986).
dc.rights.none.fl_str_mv Derechos de autor 2002 Revista Colombiana de Computación
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.uri.none.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.rights.creativecommons.*.fl_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
rights_invalid_str_mv Derechos de autor 2002 Revista Colombiana de Computación
http://creativecommons.org/licenses/by-nc-sa/4.0/
http://creativecommons.org/licenses/by-nc-nd/2.5/co/
Atribución-NoComercial-SinDerivadas 2.5 Colombia
http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
dc.source.none.fl_str_mv Revista Colombiana de Computación; Vol. 3 Núm. 1 (2002): Revista Colombiana de Computación; 41-51
institution Universidad Autónoma de Bucaramanga - UNAB
bitstream.url.fl_str_mv https://repository.unab.edu.co/bitstream/20.500.12749/9066/2/2002_Recuperando_una_LCS.pdf.jpg
https://repository.unab.edu.co/bitstream/20.500.12749/9066/1/2002_Recuperando_una_LCS.pdf
bitstream.checksum.fl_str_mv 307445e8811afc9641d53097cff047e5
17e3c5ac4f608e451ed81bfa7898e1e4
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional | Universidad Autónoma de Bucaramanga - UNAB
repository.mail.fl_str_mv repositorio@unab.edu.co
_version_ 1814277362605359104

Publicaciones similares