Registro:
| Documento: | Tesis de Grado |
| Título: | On the extension of the lexicographically greatest de Bruijn sequence to larger alphabets |
| Título alternativo: | Sobre la extensión de la secuencia de Bruijn lexicográficamente máxima a alfabetos más grandes |
| Autor: | Thibeault Lüthy, Gabriel Eric |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2019 |
| Fecha en portada: | 29 de Julio de 2019 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Becher, Verónica Andrea |
| Director Asistente: | Carton, Olivier |
| Jurado: | Abriola, Sergio Alejandro; Heintz, Joos Ulrich; Lin, Min Chih |
| Idioma: | Español |
| Palabras clave: | SECUENCIAS DE BRUIJN; SECUENCIA FORD; CICLOS EULERIANOSDE BRUIJN SEQUENCES; FORD SEQUENCES; EULERIAN CYCLES |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000624_Thibeault |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000624_Thibeault.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000624_Thibeault |
| Ubicación: | Dep.COM 000624 |
| 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. Thibeault Lüthy, Gabriel Eric. (2019). On the extension of the lexicographically greatest de Bruijn sequence to larger alphabets. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000624_Thibeault |
Resumen:
Una secuencia de Bruijn de orden n en k símbolos es una secuencia en la que cada palabra de longitud n ocurre exactamente una vez. Se sabe que para cada secuencia circular de Bruijn v de orden n en k símbolos hay otra secuencia circular de Bruijn w de orden n pero en k + 1 símbolos tal que v es una subsecuencia de w. En esta tesis nos dedicamos a la secuencia de Bruijn lexicográficamente máxima, a la que llamamos dual-Ford. El nombre se debe a que la secuencia de Bruijn lexicográficamente mínima es conocida como la secuencia de Ford. Demostramos que la secuencia dual-Ford de un orden dado y un alfabeto dado es un sufijo de la secuencia dual-Ford del mismo orden en un alfabeto con un símbolo más. Dado que hay un algoritmo óptimo en tiempo (lineal relativo al tamaño de la salida) para generar las secuencias Ford y las duales-Ford, el resultado que presentamos determina un algoritmo óptimo en tiempo para generar la extensión de una en la otra.
Abstract:
It is known that for each circular sequence of Bruijn v of order n in k symbols there is another circular sequence of Bruijn w of order n but in k + 1 symbols such that v is a subsequence of w. In this thesis we focus on the lexicographically greatest de Bruijn, which we call dual-Ford. The name follows because the Bruijn lexicographically least de Bruijn sequence is known as the Ford sequence. In this work we show that the dual-Ford sequence of a given order and on a given alphabet is a suffix of the dual-Ford sequence of the same order on an alphabet with an additional symbol. Since there is a time-optimal (linear relative to the size of the output) algorithm that generates the Ford and the dualFord sequences, our result yields a time-optimal algorithm to generate the extension of one to the other.
Citación:
---------- APA ----------
Thibeault Lüthy, Gabriel Eric. (2019). On the extension of the lexicographically greatest de Bruijn sequence to larger alphabets. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000624_Thibeault
---------- CHICAGO ----------
Thibeault Lüthy, Gabriel Eric. "On the extension of the lexicographically greatest de Bruijn sequence to larger alphabets". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/seminario_nCOM000624_Thibeault
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000624_Thibeault.pdf
Distrubución geográfica
