Tesis > Documento


Ver el documento (formato PDF)   Heiber, Pablo Ariel.  "Una perspectiva computacional sobre números normales"  (2014)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
La normalidad es una forma débil de azar. Un número real es normal en una base entera dada si su expansión en esa base es balanceada: todos los bloques de la misma cantidad de dígitos tienen igual frecuencia en la expansión. La normalidad absoluta es normalidad en toda base. En esta tesis resolvemos varios problemas sobre normalidad: La existencia de números absolutamente normales computables era conocida, pero no se conocía ningún algoritmo que computara uno en tiempo polinomial. Nosotros damos un algoritmo que computa uno en tiempo apenas mayor a cuadrático. Mostramos que el conjunto de números absolutamente normales, como subconjunto de los reales, no tiene otras propiedades aritméticas que las impuestas por la definición de normalidad. Técnicamente, demostramos que el conjunto de números absolutamente normales es π°3-completo. Extendemos la caracterización conocida de normalidad en términos de incompresibilidad mediante autómatas finitos. Analizamos exhaustivamente todas las maneras de mejorar un simple autómata finito agregando memoria de diferentes formas, permitiendo no-determinismo y permitiendo la lectura de la entrada más de una vez. Demostramos que la normalidad se preserva bajo reglas de selección basadas en préfijos finitos o sufijos infinitos reconocidos por autómatas finitos, pero no ambos simultáneamente. Esto extiende un resultado conocido para el caso de prefijos.

Abstract:
Normality is a weak form of randomness. A real number is normal to a given integer base if its expansion in that base is balanced: all blocks of the same number of digits occur with the same frequency in the expansion. Absolute normality is normality to all bases. We solve several problems on normality: It was known that computable absolutely normal numbers exist, but no algorithm was known to compute one in polynomial time. We give an algorithm that computes one in just above quadratic time. We show that the set of absolutely normal numbers, as a subset of the real numbers, has no other arithmetical properties than those imposed by the definition of normality. Technically, we prove that the set of absolutely normal numbers is π°3-complete. We extend the known characterization of normality in terms of incompressibility by deterministic finite automata. We exhaust all ways of enhancing a simple finite state automaton by adding memory in different forms, allowing non-determinism, and allowing to read the input more than once. We prove that normality is preserved by selection rules based on finite pre- fixes or infinite suffixes being recognized by finite automata, but not both simultaneously. This extends a known result about the prefixes case.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Una perspectiva computacional sobre números normales     =    A computational perspective on normal numbers
Autor : Heiber, Pablo Ariel
Director : Becher, Verónica
Consejero : Becher, Verónica
Jurados : Montalbán, Antonio  ; Pin, Jean-Eric  ; Vaggione, Diego josé
Año : 2014
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5450_Heiber
Idioma : Inglés
Area Temática : Computación / Métodos Numéricos
Palabras claves : NUMEROS NORMALES; COMPLEJIDAD ALGORITMICA; COMPLEJIDAD DESCRIPTIVA; AUTOMATAS FINITOS; COMPRESIBILIDAD; NORMAL NUMBERS; ALGORITHMIC COMPLEXITY; DESCRIPTIVE COMPLEXITY; FINITE AUTOMATA; COMPRESSIBILITY
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34