Description
Date depot: 1 janvier 1900
Titre: Combinatoire analytique et modeles d'urnes
Directrice de thèse:
Michèle SORIA (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Les processus d'urnes constituent une classe très étendue de modèles dont l'application va des probabilités et statistiques classiques à l'épidémiologie, la physique statistique, ou encore la génétique des populations.
En informatique fondamentale, ces processus rendent compte, mais encore seulement très partiellement, d'arbres de recherches 'à cas le pire garanti'' (par exemple, arbres 2-3 et 'B-trees'' des bases de données) ou encore de la croissance de réseaux dits sociaux (modèles d'attachement préférentiel, graphes du web ou de l'internet).
On pressent aussi un voisinage avec certains problèmes de l'informatique répartie dont l'analyse dans des conditions naturelles d'utilisation qui sont probabilistes est très largement ouverte (processus sur un anneau du type 'dining philosophers'', par exemple). Enfin, par leur capacité à prendre en compte divers problèmes d'allocation, ces modèles d'urnes doivent servir à l'analyse de diverses stratégies de hachage (collectionneur de coupons; hachage avec 'essais linéaires''), éventuellement dans un contexte de mémoires hiérarchisées (pagination).
Jusqu'aux années 2005, l'analyse des propriétés quantitatives de ces modèles reposait presqu'exclusivement sur des approches stochastiques. On sait désormais que la combinatoire analytique a beaucoup à apporter, voire renouvelle, une partie de ce sujet très vaste et très riche.
Le stage de Master aura permis de tester la méthodologie proposée sur des modèles conceptuellement simples, mais au traitement analytique souvent délicat : modèles de mélange de Laplace-Bernoulli; modèle de conflit dit 'OK Corral'', modèle de transmission de la chaleur d'Ehrenfest, modèle de Paterson du 'cookie monster'' en relation avec les méthodes de hachage. Etant donnée la puissance de description des processus d'urnes, la thèse proposée est assez interdisciplinaire (informatique et mathématiques).
Ce projet de thèse nécessite une bonne connaissance de la théorie des fonctions analytiques et un goût marqué pour l'analyse complexe et ses applications, ainsi qu'une bonne appréhension des méthodes générales de la combinatoire analytique et une bonne aptitude au calcul, tant manuel qu'assisté par les systèmes de manipulation symbolique (calcul formel).
Le thème de la thèse pourra inclure des incursions dans le domaine voisin de la combinatoire énumérative et analytique des chemins plans. Ceux-ci servent par exemple à décrire l'évolution de systèmes (files d'attente, processeurs) couplés et l'on commence à y apercevoir un riche ensemble de propriétés au carrefour entre la combinatoire, la théorie des équations fonctionnelles, l'analyse complexe, la théorie des fonctions spéciales, et le calcul formel.
Doctorant.e: Morcrette Basile