Modèles d'urnes et phénomènes de seuils en combinatoire analytique.

Vincent Puyhaubert 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Résumé : Cette thèse traite de phénomènes de seuils et de modèles d'urnes, en adoptant le point de vue de la combinatoire analytique. On traite ici trois problèmes qui illustrent cette approche: la transition de phase du problème k-sat, les modèles d'urnes triangulaires de Polya-Eggenberger et le modèle de duel de Ok Corral. La transition de phase du problème k-sat se manifeste par le fait la densité d'une formule caractérise de manière presque sûre sa satisfaisabilité. Nos travaux visent à mettre en évidence une partie de ce phénomène et se relient à un modèle d'urne à jets. Le modèle d'urne de Polya-Eggenberger utilise une urne contenant des boules de diverses couleurs, soumises à des règles de pioches et de substitutions. En utilisant une technique de Flajolet-Gabarro-Pekari, nous déterminons la distribution limite de la composition des modèles dits triangulaires. Le modèle de duel de Ok Corral intervient dans une problématique plus générale de Lanchester de gestion des conflits, selon laquelle on cherche à prédire l'issue de duels entre plusieurs forces armées, en environnement aléatoire. Nous utilisons un lien pré-établi entre ce modèle et une urne de type Polya-Eggenberger pour donner de nouvelles expressions des probabilités du modèle et raffiner les résultats récents de Kingman.
Type de document :
Thèse
Combinatoire [math.CO]. Ecole Polytechnique X, 2005. Français
Liste complète des métadonnées

Littérature citée [75 références]  Voir  Masquer  Télécharger

https://pastel.archives-ouvertes.fr/pastel-00001348
Contributeur : Ecole Polytechnique <>
Soumis le : mardi 27 juillet 2010 - 14:24:28
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : jeudi 28 octobre 2010 - 11:31:41

Identifiants

  • HAL Id : pastel-00001348, version 1

Collections

Citation

Vincent Puyhaubert. Modèles d'urnes et phénomènes de seuils en combinatoire analytique.. Combinatoire [math.CO]. Ecole Polytechnique X, 2005. Français. 〈pastel-00001348〉

Partager

Métriques

Consultations de la notice

523

Téléchargements de fichiers

971