Una perspectiva computacional sobre números normales

Mostrar todas las versiones(3)

La normalidad es una forma débil de azar. Un número real es normal enuna base entera dada si su expansión en esa base es balanceada: todos los bloques dela misma cantidad de dígitos tienen igual frecuencia en la expansión. La normalidadabsoluta es normalidad en toda base. En esta tesis resolvemos va...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Heiber, Pablo Ariel
Otros Autores: Becher, Verónica
Formato: Tesis doctoral publishedVersion
Lenguaje:Inglés
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2014
Materias:
NUMEROS NORMALES
COMPLEJIDAD ALGORITMICA
COMPLEJIDAD DESCRIPTIVA
AUTOMATAS FINITOS
COMPRESIBILIDAD
NORMAL NUMBERS
ALGORITHMIC COMPLEXITY
DESCRIPTIVE COMPLEXITY
FINITE AUTOMATA
COMPRESSIBILITY
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n5450_Heiber
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5450_Heiber_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n5450_Heiber_oai
record_format dspace
spelling I28-R145-tesis_n5450_Heiber_oai2023-04-26 Becher, Verónica Heiber, Pablo Ariel 2014 La normalidad es una forma débil de azar. Un número real es normal enuna base entera dada si su expansión en esa base es balanceada: todos los bloques dela misma cantidad de dígitos tienen igual frecuencia en la expansión. La normalidadabsoluta es normalidad en toda base. En esta tesis resolvemos varios problemassobre 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 acuadrático. Mostramos que el conjunto de números absolutamente normales, como subconjuntode los reales, no tiene otras propiedades aritméticas que las impuestaspor la definición de normalidad. Técnicamente, demostramos que el conjuntode números absolutamente normales es π°3-completo. Extendemos la caracterización conocida de normalidad en términos de incompresibilidadmediante autómatas finitos. Analizamos exhaustivamente todaslas maneras de mejorar un simple autómata finito agregando memoria de diferentesformas, permitiendo no-determinismo y permitiendo la lectura de la entradamás de una vez. Demostramos que la normalidad se preserva bajo reglas de selección basadasen préfijos finitos o sufijos infinitos reconocidos por autómatas finitos, pero noambos simultáneamente. Esto extiende un resultado conocido para el caso deprefijos. Normality is a weak form of randomness. A real number is normalto a given integer base if its expansion in that base is balanced: all blocks of thesame number of digits occur with the same frequency in the expansion. Absolutenormality is normality to all bases. We solve several problems on normality: It was known that computable absolutely normal numbers exist, but no algorithmwas known to compute one in polynomial time. We give an algorithmthat computes one in just above quadratic time. We show that the set of absolutely normal numbers, as a subset of the realnumbers, has no other arithmetical properties than those imposed by the definitionof normality. Technically, we prove that the set of absolutely normalnumbers is π°3-complete. We extend the known characterization of normality in terms of incompressibilityby deterministic finite automata. We exhaust all ways of enhancing asimple finite state automaton by adding memory in different forms, allowingnon-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 bothsimultaneously. This extends a known result about the prefixes case. Fil: Heiber, Pablo Ariel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n5450_Heiber eng Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar NUMEROS NORMALES COMPLEJIDAD ALGORITMICA COMPLEJIDAD DESCRIPTIVA AUTOMATAS FINITOS COMPRESIBILIDAD NORMAL NUMBERS ALGORITHMIC COMPLEXITY DESCRIPTIVE COMPLEXITY FINITE AUTOMATA COMPRESSIBILITY Una perspectiva computacional sobre números normales A computational perspective on normal numbers info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5450_Heiber_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Inglés
orig_language_str_mv eng
topic NUMEROS NORMALES
COMPLEJIDAD ALGORITMICA
COMPLEJIDAD DESCRIPTIVA
AUTOMATAS FINITOS
COMPRESIBILIDAD
NORMAL NUMBERS
ALGORITHMIC COMPLEXITY
DESCRIPTIVE COMPLEXITY
FINITE AUTOMATA
COMPRESSIBILITY
spellingShingle NUMEROS NORMALES
COMPLEJIDAD ALGORITMICA
COMPLEJIDAD DESCRIPTIVA
AUTOMATAS FINITOS
COMPRESIBILIDAD
NORMAL NUMBERS
ALGORITHMIC COMPLEXITY
DESCRIPTIVE COMPLEXITY
FINITE AUTOMATA
COMPRESSIBILITY
Heiber, Pablo Ariel
Una perspectiva computacional sobre números normales
topic_facet NUMEROS NORMALES
COMPLEJIDAD ALGORITMICA
COMPLEJIDAD DESCRIPTIVA
AUTOMATAS FINITOS
COMPRESIBILIDAD
NORMAL NUMBERS
ALGORITHMIC COMPLEXITY
DESCRIPTIVE COMPLEXITY
FINITE AUTOMATA
COMPRESSIBILITY
description La normalidad es una forma débil de azar. Un número real es normal enuna base entera dada si su expansión en esa base es balanceada: todos los bloques dela misma cantidad de dígitos tienen igual frecuencia en la expansión. La normalidadabsoluta es normalidad en toda base. En esta tesis resolvemos varios problemassobre 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 acuadrático. Mostramos que el conjunto de números absolutamente normales, como subconjuntode los reales, no tiene otras propiedades aritméticas que las impuestaspor la definición de normalidad. Técnicamente, demostramos que el conjuntode números absolutamente normales es π°3-completo. Extendemos la caracterización conocida de normalidad en términos de incompresibilidadmediante autómatas finitos. Analizamos exhaustivamente todaslas maneras de mejorar un simple autómata finito agregando memoria de diferentesformas, permitiendo no-determinismo y permitiendo la lectura de la entradamás de una vez. Demostramos que la normalidad se preserva bajo reglas de selección basadasen préfijos finitos o sufijos infinitos reconocidos por autómatas finitos, pero noambos simultáneamente. Esto extiende un resultado conocido para el caso deprefijos.
author2 Becher, Verónica
author_facet Becher, Verónica
Heiber, Pablo Ariel
format Tesis doctoral
Tesis doctoral
publishedVersion
author Heiber, Pablo Ariel
author_sort Heiber, Pablo Ariel
title Una perspectiva computacional sobre números normales
title_short Una perspectiva computacional sobre números normales
title_full Una perspectiva computacional sobre números normales
title_fullStr Una perspectiva computacional sobre números normales
title_full_unstemmed Una perspectiva computacional sobre números normales
title_sort una perspectiva computacional sobre números normales
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2014
url https://hdl.handle.net/20.500.12110/tesis_n5450_Heiber
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5450_Heiber_oai
work_keys_str_mv AT heiberpabloariel unaperspectivacomputacionalsobrenumerosnormales
AT heiberpabloariel acomputationalperspectiveonnormalnumbers
_version_ 1766015800246796288

Ejemplares similares