Contributions à l'étude des structures aléatoires et des méthodes probabilistes
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis contains a few contributions to the study of randomness and probabilistic methods in theoretical computer science. Some of them deal with random sequences and probabilistic complexity classes, the others with concrete problems. We introduce a new mathematical model of imperfect physical sources of randomness and we show how to convert the output of these sources into quasi-random sequences which are indistinguish able from truly random ones in a strong sense. We show the existence of pseudo-random number generators which can reduce efficiently the error probability in probabilistic algorithms. We present a separation result for the relativized interactive probabilistic proof-systems. We study in a probabilistic model the optimal distribution of processors in a network, when they are subject to failure. We compute the radius of certain graphs on alphabets and we obtain tight bounds on the parallel complexity of the searching problem in multi-dimensional cubes by using proba bilistic arguments.
Abstract FR:
Cette thèse contient quelques contributions à l'étude des structures aléatoires et des méthodes probabilistes en informatique théorique. Certaines d'entre elles étudient les séquences aléatoires et les classes de complexité probabilistes, d'autres traitent des problèmes concrets. Nous introduisons un nouveau modèle mathématique des sources physiques aléatoires imparfaites et nous montrons comment transformer la sortie de ces sources en séquences quasi-aléatoires qu'on ne peut pas distinguer, dans un sens très fort, des séquences parfaitement aléatoires. Nous démontrons l'existence des générateurs de nombres pseudo-aléatoires pour réduire efficacement la probabilité d'erreur des algorithmes probabilistes. Nous présentons un résultat de séparation pour les systèmes de preuve interactifs probabilistes relativisés. Nous étudions dans un modèle probabiliste la distribution optimale des processeurs dans un réseau quand ceux-ci peuvent tomber en panne. Nous déterminons le rayon de certains graphes sur al phabets et nous obtenons des bornes sur la complexité en parallèle de la recherche dans les cubes multi-dimensionnels en utilisant des arguments probabilistes.