Registro:
| Documento: | Tesis de Grado |
| Título: | Secuencias completamente equidistribuidas basadas en secuencias de De Bruijn |
| Autor: | Almansi, Emilio Guido |
| 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: | 4 de Septiembre 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 |
| Jurado: | Figueira, Santiago Daniel; Marenco, Javier Leonardo |
| Idioma: | Español |
| Palabras clave: | SECUENCIA ALEATORIA; EQUIDISTRIBUCION COMPLETA; SECUENCIA DE DE BRUIJN; ALGORITMO FKM; SECUENCIA DE FORD; SECUENCIA DE KNUTHRANDOM SEQUENCE; COMPLETE EQUIDISTRIBUTION DE BRUIJN SEQUENCE; FKM ALGORITHM; FORD SEQUENCE; KNUTH SEQUENCE |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000601_Almansi |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000601_Almansi.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000601_Almansi |
| Ubicación: | Dep.COM 000601 |
| 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. Almansi, Emilio Guido. (2019). Secuencias completamente equidistribuidas basadas en secuencias de De Bruijn. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000601_Almansi |
Resumen:
En este trabajo estudiamos una secuencia de números reales completamente equidistribuidos publicada por Donald Knuth en 1965. La noción de equidistribución completa se utiliza en su sentido clásico; es decir, que para una secuencia dada, todas sus subsecuencias finitas y contiguas de cualquier longitud presentan una distribución uniforme. En un artículo de 1963, Joel Franklin considera esta propiedad como un primer requerimiento de pseudoaleatoriedad en secuencias determinísticas, y prueba que la equidistribución completa implica muchas otras propiedades importantes de las secuencias aleatorias. El trabajo de Knuth se basa en secuencias de De Bruijn, las cuales tienen también una relación cercana con la noción de equidistribución y pueden ser generadas en tiempo constante amortizado por el algoritmo FKM (Fredricksen, Kessler, Maiorana, 1978). Presentamos una variante de la secuencia de Knuth mediante una construcción similar, aunque más sencilla, y damos una prueba elemental de que la secuencia generada también es completamente equidistribuida.
Abstract:
In this work, we study a construction published by Donald Knuth in 1965 yielding a completely equidistributed sequence of real numbers. Complete equidistribution is interpreted in its classic sense; namely, that finite contiguous subsequences of any length have a uniform distribution within a given sequence. Joel Franklin in a paper from 1963 suggests this as a first requirement for pseudorandomness in deterministic sequences, and proves that complete equidistribution implies many other important statistical properties shared by all random sequences. Knuth’s work is based on De Bruijn sequences, which are also closely related to equidistribution and can be generated by the FKM algorithm (Fredricksen, Kessler, Maiorana, 1978) in amortized constant time. We provide a variant of Knuth’s sequence via a similar, albeit simpler, construction and give an elementary proof showing that the sequence it yields is also completely equidistributed.
Citación:
---------- APA ----------
Almansi, Emilio Guido. (2019). Secuencias completamente equidistribuidas basadas en secuencias de De Bruijn. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000601_Almansi
---------- CHICAGO ----------
Almansi, Emilio Guido. "Secuencias completamente equidistribuidas basadas en secuencias de De Bruijn". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/seminario_nCOM000601_Almansi
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000601_Almansi.pdf
Distrubución geográfica
