Extensión de secuencias de Bruijn en alfabetos más grandes

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2018-12-13

Tipo de documento: 

info:eu-repo/semantics/bachelorThesis
 

Formato:

application/pdf

Idioma:

eng

Temas:

SECUENCIAS DE BRUIJN - CICLOS EULERIANOS - BRUIJN SEQUENCES - EULERIAN CYCLES

Descripción:

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.

Identificador:

https://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes