english  
English

INRIA logo  Algo team logo                               UPMC logo   LIP6 logo   APR logo  

   

Basile MORCRETTE                        

Classe Prépa

Contact : prenom.nom@gmail.com

Docteur de l'Université Pierre et Marie Curie

photo BM

Mon CV.

Recherche     Exposés     Publications     Enseignement     Contact

Recherche:

Ma thèse, Combinatoire analytique et modèles d'urnes, a été soutenue
                    le 26 juin 2013
                          à 12h30
    en Salle 105, Couloir 25-26, 1er étage.
                UPMC, Jussieu, Paris
                        Pour venir
Une version du manuscrit est disponible ici.

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.

Exposés récents:

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

Publications:

-- 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

Enseignement:

Actuellement, je suis professeur de Classes Préparatoires, en Mathématiques et Informatique.

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.

Contact:

Contact : prenom.nom@gmail.com