Encadrement : J'ai commencé ma thèse en Septembre 2010 à l'INRIA Rocquencourt, dans l'équipe Algorithms, sous la direction de Philippe Flajolet. Suite à son décès brutal en mars 2011, et au déménagement de l'ancienne équipe ALGO à Palaiseau, je poursuis ma thèse sous la direction de Philippe Dumas (SpecFun, Palaiseau). Je suis co-encadré par Michèle Soria au LIP6 (UPMC, Paris 6).
Mots-clés : combinatoire analytique, lois limites, urnes de Pólya et applications, algorithmique et calcul formel, équations aux dérivées partielles.
Résumé :
Ma thèse étudie les urnes de Pólya à travers le prisme de la combinatoire analytique. Les urnes sont des modèles, conceptuellement très simples, de dynamique de croissance ou d'extinction dont les comportements limites sont extrêmement variés. Ces modèles sont largement étudiés par des approches probabilistes mais la compréhension précise des diverses lois limites reste une question ouverte. Les travaux de Flajolet et al. en 2005 ont illustré que pour ces questions, une approche par combinatoire analytique peut se révéler très fructueuse : l'étude des propriétés (nature, singularités) des séries génératrices associées aux urnes donne accès à des lois limites avec grande précision.
Ma recherche s'inscrit dans la continuité de ces travaux.
Dans un premier temps, nous procédons à l'identification des séries des urnes de nature algébrique, grâce à un algorithme sophistiqué issu du calcul formel (Divination/Preuve automatique). Pour les classes d'urnes algébriques, nous menons des analyses, exacte et asymptotique, afin de connaître avec précision les comportements limites (structures des moments, vitesse de convergence, aspects limites locaux). Puis, l'étude d'urnes non algébriques est faite au travers d'exemples concrets portant sur la modélisation de réseaux sociaux, ainsi que sur la combinatoire des formules booléennes. Enfin, à travers des modèles d'urnes plus généraux (absence d'équilibre et présence d'aléa au sein des règles de substitution), nous montrons que l'approche symbolique de la combinatoire analytique est robuste. En particulier, une étude combinatoire générale des urnes sans condition d'équilibre est réalisée pour la première fois, unissant toute urne à une équation aux dérivées partielles.
Avant la thèse :
Avant de me lancer à corps perdu dans ce sujet, j'ai effectué mon stage de Master 2 MPRI au même endroit. J'ai ainsi pu me familiariser avec les modèles d'urnes. Vous pouvez consulter mon rapport de stage, ainsi que les slides de la soutenance.
Avant de découvrir le monde de la combinatoire, j'ai effectué un stage
de Master 1 à l'université d'Aix-la-Chapelle RWTH
Aachen avec
Wolfgang Thomas, sur un sujet mêlant model-checking, logique du
second ordre et graphes infinis.
Exposé
à la RWTH Aachen, août 2008, MSO-Model-Checking over Infinite Graphs : Taking Caucal to the Limit slides.
Slides (francais) de la soutenance de M1, ainsi
que le rapport de stage : Model-checking des MSO-formules sur des structures infinies.
Août 2014 : Summer School in Nablus, Palestine : Cours d'introduction à la combinatoire analytique, école d'été "Random structures, Analytic and Probabilistic Approaches"
Juin 2013 : ANR Boole , Paris : Journées de clôture de l'ANR Boole
Mai 2013 : AofA 2013, Espagne : On unbalanced urn models
Novembre 2012 : Séminaire combinatoire du LIX, Ecole Polytechnique : Algebraic Analytic Urns
Du 5 au 7 Septembre 2012 : French-British Workshop on Analytic Combinatorics, University of Oxford, UK. A gentle introduction to Analytic Combinatorics, for PhD students.
Août 2012 : PCC 2012, University of Warwick, UK : Exactly Solvable Pólya Urn Models via Analytic Combinatorics slides
Juin 2012 : AofA 2012, Montreal, Canada : Exactly solvable balanced tenable urns with random entries via the analytic methodology slides
Avril 2012 : LATIN 2012, Arequipa, Pérou : Fully Analyzing an Algebraic Pólya Urn Model slides
Mars 2012 : ALEA 2012, CIRM Luminy : Urnes de Pólya équilibrées: qui est algébrique ? slides
Février 2012 : Séminaire CALIN, LIPN (Paris 13) : Pólya Urn Models : an Analytics Combinatorics Approach
Décembre 2011 : Philippe Flajolet and Analytic Combinatorics, Paris-Jussieu, 14-15-16 Décembre 2011. Journées en hommage à Phillipe Flajolet. Pólya Urn Models : The Analytic Approach slides
Juin 2011 : ANR Boole , Nantes : Urnes de Pólya par la combinatoire analytique slides
Juin 2011 : AofA 2011, Bedlewo, Pologne : Analysis of an algebraic class of Pólya urn models slides
Mars 2011 : ALEA 2011, CIRM Luminy : Urnes de Pólya : analyse d'une classe algébrique slides
Septembre 2010 : Soutenance M2 : Combinatoire analytique et modèles d'urnes slides
Septembre 2008 : Soutenance M1 : Model-checking des MSO-formules sur des structures infinies slides
Août 2008 : RWTH Aachen : MSO-Model-Checking over Infinite Graphs : Taking Caucal to the Limit slides
-- Exactly solvable balanced tenable urns with random entries via the analytic methodology , B.Morcrette and Hosam M.Mahmoud pdf , accepté à AofA 2012 (Montreal, 17--22 juin 2012). 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms. DMTCS Proceedings, vol. AQ, pp. 219--232
-- Fully Analyzing an Algebraic Pólya Urn Model , B.Morcrette pdf , accepté à LATIN 2012 (16--20 avril 2012), Latin American Symposium on Theoretical Informatics. LNCS 7256, pp. 568-581, Springer, 2012.
-- Rapport de stage M2 MPRI : Combinatoire analytique et modèles d'urnes , B.Morcrette P.Flajolet, Septembre 2010, pdf
-- Rapport de stage M1 MPRI : Model-checking des MSO-formules sur des structures infinies , B.Morcrette W.Thomas, Septembre 2008, pdf
Durant ma thèse, j'ai été Moniteur à l'UPMC (Jussieu).
Entre 2010 et 2013, j'ai effectué les enseignements suivants :
-- TD et TP du cours Programmation Récursive en Scheme, Licence 1 d'Informatique (LI101),
voir site
du cours.
-- TP du cours Structures discrètes (automates, logique), Licence 2 d'Informatique (LI214), voir la page du cours.
-- TD du cours Algorithmique élémentaire, Licence 2 d'Informatique (LI216).
En 2009-2010, j'ai donné des colles en classe préparatoire MPSI au Lycée Condorcet, Paris 9ème arrondissement.