Registro:
| Documento: | Tesis de Grado |
| Título: | Extensión de secuencias de Bruijn en alfabetos más grandes |
| Título alternativo: | Extending de Bruijn sequences to larger alphabets |
| Autor: | Cortés, Lucas |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2023-04-02 |
| Fecha de defensa: | 2018-12-13 |
| Fecha en portada: | 28 de noviembre de 2018 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Director: | Becher, Verónica Andrea |
| Idioma: | Inglés |
| Palabras clave: | SECUENCIAS DE BRUIJN; CICLOS EULERIANOSBRUIJN SEQUENCES; EULERIAN CYCLES |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000446_Cortes.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000446_Cortes |
| Ubicación: | Dep.COM 000446 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Cortés, Lucas. (2018). Extensión de secuencias de Bruijn en alfabetos más grandes. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes |
Resumen:
Un secuencia circular de Bruijn de orden n en k colores es una secuencia en la que cada palabra de longitud n ocurre exactamente una vez. En esta tesis demostramos que para cada secuencia circular de Bruijn v de orden n en k colores hay otra secuencia circular de Bruijn w de orden n pero en k + 1 colores tal que v es una subsecuencia de w y entre cualesquiera dos ocurrencias sucesivas del nuevo símbolo en w hay a lo sumo n + 2k − 2 símbolos consecutivos de v. Damos un algoritmo que recibe una tal secuencia v y produce la secuencia w. Damos además un algoritmo mucho más rápido que recibe una tal secuencia v y produce una secuencia w pero sin la garantía de que el nuevo símbolo esté balanceado.
Abstract:
A circular de Bruijn sequence of order n in k colors is a sequence in which every possible word of length n occurs exactly once. In this thesis we show that for any given circular de Bruijn sequence v of order n in k colors there is another circular de Bruijn sequence w of order n but in k + 1 colors such that v is a subsequence of w and such that in between two successive occurrences of the new colored symbol in w there are at most n + 2k − 2 consecutive symbols of v. We provide an algorithm that given such an input sequence v produces the output sequence w. And we give a much faster algorithm that also receives as input such a sequence v and outputs a sequence w without the guarantee of the fair distribution of the new colored symbol.
Citación:
---------- APA ----------
Cortés, Lucas. (2018). Extensión de secuencias de Bruijn en alfabetos más grandes. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes
---------- CHICAGO ----------
Cortés, Lucas. "Extensión de secuencias de Bruijn en alfabetos más grandes". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2018.https://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000446_Cortes.pdf
Distrubución geográfica
