Biblioteca Digital | FCEN-UBA

Biblioteca Digital ¿Por qué?
Objetivos
Impactos
Estadísticas
Documentos
Presentaciones
Notas
Autores y derechos
¿Por qué depositar?
¿Cómo depositar?
Autorización
Depositar y publicar
Editoriales
Publicar mi tesis Formulario Tesis Posgrado
Formulario Tesis Grado
Normativa
Res. CD 2053/05
Res. CD 2533/09
Res. CD 0272/13
Res. CD 2793/15

Colecciones Tesis Doctorales
Fotografías
Publicaciones
Archivo
Libros
Reportes Técnicos

Tesis > TEMA

Computación [ 80 tesis ]

Aleatoriedad Algorítmica [ 2 tesis ]

Tetzlaff, Guillermo Tomás. "Procesos de ramificación con tipos no acotados y simulación de redes con pérdida" (2004) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Esta tesis extiende la teoría de procesos estocásticos de ramificación al caso de tipos no acotados. Éstos surgen de no asumir que el número esperado de hijos es una función acotada del tipo del padre. Tampoco se supone que existe un entero m tal que se tiene una cota inferior positiva, uniforme sobre el tipo del ancestro, para la probabilidad de que una población esté extinguida en la m-ésima generación. Demostramos que una condición más débil que la existencia de tal m lleva a la extinción con probabilidad ! si la sucesión de las esperanzas de los tamaños de las generaciones no tiende a infinito. También se obtienen criterios que aseguran una probabilidad positiva de que no haya extinción. Se proveen ejemplos extendiendo a nuestro contexto de tipos no acotados dos aplicaciones bien conocidas: la dinámica poblacional de Leslie y los procesos de ramificación asociados a percolación continua. Ésta última se desarrolla hasta obtener resultados sobre percolación continua orientada, que dan condiciones suficientes de factibilidad para la simulación exacta de redes con pérdida con objetos no uniformemente acotados. Luego de resolver el problema de la generación de clusters de percolación con este tipo de objetos, se proponen algoritmos de simulación de percolación y de una red con pérdida que se implementa en lenguaje C.

Abstract:
This thesis extends the theory of stochastic branching processes to the case of unbounded types. These arise from not assuming that the expected number of children is a bounded function of the parent's type. It is neither supposed that there exists an integer m such that there is a lower positive bound, uniform over the ancestor's type, for the probability that a population is extinct at the m-th generation. We prove that a weaker condition than the existence of such an m leads to extinction almost surely if the sequence of expected generation sizes does not tend to infinity. Some criteria for a positive probability of nonextinction are also obtained. Examples are provided by extending to our unbounded-types setting two well known applications, namely Leslie population dynamics and processes associated to continuum percolation. The latter application is developed until results are obtained about oriented continuum percolation, which give conditions of feasibility for the exact simulation of loss networks with not uniformly bounded objects. After solving the problem of generating percolation clusters with this kind of objects, algorithms are proposed for the simulation of percolation and of a loss network, which is implemented in C language.

Figueira, Santiago Daniel. "Aspectos de aleatoriedad" (2006) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
En esta tesis, investigamos algunos aspectos de aleatoriedad y trivialidad definidos por la teoría de largo de programa. Primero abordamos la aleatoriedad y la absoluta normalidad de números reales. Ambos conjuntos de reales tienen medida de Lebesgue 1 y son nociones que implican varias propiedades de estocasticidad. A pesar de esto, no ha sido fácil dar ejemplos concretos en estas clases. Probamos que existen números absolutamente normales que son computables y damos dos algoritmos para construirlos. El primero está basado en una reformulación computable de un resultado de Sierpinski de 1916. El segundo es parte de nuestra reconstrucción de un manuscrito inédito de Turing sobre números normales. En cuanto a ejemplos de aleatoriedad, generalizamos la probabilidad de detención de Chaitin y analizamos la probabilidad de que una máquina universal se detenga y devuelva un resultado en un conjunto dado X. Estudiamos la relación entre las propiedades de X provenientes de la teoría de la computabilidad y las propiedades de aleatoriedad de la probabilidad inducida. El segundo aspecto de aleatoriedad que tratamos es el estudio de una variante de la complejidad clásica de largo de programa que no involucra oráculos, y nos preguntamos si esta noción conduce a una definición más estricta de aleatoriedad. Definimos nuestra función de complejidad en base a máquinas de Turing monótonas que realizan cómputos infinitos. Investigamos algunas propiedades de esta función y consideramos las definiciones inducidas de aleatoriedad y trivialidad. Con esta última noción caracterizamos a los reales computables. El último aspecto se vincula con la anti-aleatoriedad y la posibilidad de caracterizar a los reales llamados K-triviales con nociones que no involucren directamente a la complejidad de largo de programa libre de prefijos. Proponemos e investigamos dos nociones de lowness que tienen sus raíces puramente en la teoría de la computabilidad, reforzando otras ya existentes en la literatura. Relacionamos la complejidad de largo de programa plana C y libre de prefijos K con estas nociones, considerando variaciones de K-trivialidad y C-trivialidad. Concluimos con una lista de las principales preguntas que quedaron abiertas.

Abstract:
In this thesis we investigate some aspects of randomness and triviality defined by the theory of program-size. We first deal with randomness and absolute normality of real numbers. Both sets of reals have Lebesgue measure 1 and they are notions that imply several properties of stochasticity. Despite that fact, it has not been easy to give concrete examples in such classes. We prove that there are absolutely normal numbers which are computable and we give two algorithms for constructing such numbers. The former is a computable reformulation of a result of Sierpinski of 1916. The latter is part of our reconstruction of an unpublished manuscript of Turing on normal numbers. For examples of randomness, we generalize Chaitin's halting probability and we analyze the probability that a universal machine halts and gives an output in a given set X. We study the relationship between the computability theoretic properties of X and the randomness properties of the induced probability. The second aspect of randomness that we tackle is the study a variant of the classical definition of program-size complexity which does not involve oracles, and we ask whether it leads to a stronger notion of randomness. We define our complexity function based on monotone Turing machines performing unending computations. We investigate some properties of this function and we consider the induced definitions of randomness and triviality. With this last notion we characterize the computable reals. The last aspect deals with anti-randomness and the possibility to characterize the so called K-trivial reals in terms of notions that do not directly involve the prefix-free program-size complexity. We propose and investigate two computability theoretical combinatorial lowness notions by strengthening other notions already existing in the literature. We relate the plain C and the prefix-free program-size complexity K with these notions by considering variations of K-triviality and C-triviality. We conclude with a list of the main questions that remain open.

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