Catálogo de publicaciones - tesis
Título de Acceso Abierto
Una perspectiva computacional sobre números normales
Pablo Ariel Heiber Verónica Becher
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
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.Palabras clave – provistas por el repositorio digital
NUMEROS NORMALES; COMPLEJIDAD ALGORITMICA; COMPLEJIDAD DESCRIPTIVA; AUTOMATAS FINITOS; COMPRESIBILIDAD; NORMAL NUMBERS; ALGORITHMIC COMPLEXITY; DESCRIPTIVE COMPLEXITY; FINITE AUTOMATA; COMPRESSIBILITY
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2014 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2014
Información sobre licencias CC
