Dans ce travail, nous nous sommes intéressés à l'étude asymptotique d'objets combinatoires aléatoires. Deux thèmes ont particulièrement retenu notre attention : les cartes planaires aléatoires et les modèles combinatoires liés à la théorie des fragmentations. La théorie mathématique des cartes planaires aléatoires est née à l'aube de notre millénaire avec les travaux pionniers de Benjamini & Schramm, Angel & Schramm et Chassaing & Schaeffer. Elle a ensuite beaucoup progressé, mais à l'heure où ces lignes sont écrites, de nombreux problèmes fondamentaux restent ouverts. Résumons en quelques mots clés nos principales contributions dans le domaine : l'introduction et l'étude du cactus brownien (avec J.F. Le Gall et G. Miermont), l'étude de la quadrangulation infinie uniforme vue de l'infini (avec L. Ménard et G. Miermont), ainsi que des travaux plus théoriques sur les graphes aléatoires stationnaires d'une part et les graphes empilables dans $\R^d$ d'autre part (avec I. Benjamini). La théorie des fragmentations est beaucoup plus ancienne et remonte à des travaux de Kolmogorov (1941) et de Filippov (1961). Elle est maintenant bien développée (voir par exemple l'excellent livre de J. Bertoin), et nous ne nous sommes pas focalisés sur cette théorie mais plutôt sur ses applications à des modèles combinatoires. Elle s'avère en effet très utile pour étudier différents modèles de triangulations récursives du disque (travail effectué avec J.F. Le Gall) et les recherches partielles dans les quadtrees (travail effectué avec A. Joseph).

Ce manuscrit est un document de synthèse et de présentation d'une majorité des travaux que j'ai effectués entre septembre 2008 et septembre 2013 (voir la liste des publications ci-dessous1). Les publications [P1-6] sont issues de la thèse ainsi qu'une grande partie de [P11]. Afin de présenter un document concis et cohérent nous avons choisi de ne pas traiter les publications [P3], [P5], [P9] et [P10]. Que mes co-auteurs m'excusent. Le document est construit autour de deux parties principales : les arbres aléatoires d'une part et les cartes planaires aléatoires d'autre part. Les contributions originales sont signalées par des théorèmes encadrés et sont numérotés 1, 2, 3, . . ..

The research work presented in this manuscript is of algorithmic kind: it is mainly composed of polynomial, fixed parameter and approximation algorithms, while hardness results are also mentioned.<br /> <br />This work is about building and comparing labelled trees. These objects find application in different areas, but notoriously in phylogenetics, where they represent evolutionary relationships of organisms or sequences.<br /><br />Most of this work can be considered as investigating solutions to so-called \emph{supertree} problems. Supertrees are large trees built by a dynamic programming approach from smaller trees. For instance, the latter are gene trees from which a comprehensive tree on many living species is to be built, such as the \emph{Tree of Life}. <br /><br />First definitions are introduced, then a part of the manuscript is dedicated to quartet tree building methods. The next part details tree comparison methods, mainly variants of the maximum agreement subtree method. Next follows a part on supertree problems in all generality. <br />The manuscript ends with a report of the research plan for the next few years. <br /><br />Several journal papers illustrating the material described in this manuscript are adjoined in appendix.

Nous présentons dans cette thèse une approche probabiliste pour déterminer les valeurs manquantes des objets incomplets pendant leur classement dans les arbres de décision. Cette approche est dérivée de la méthode d'apprentissage supervisé appelée Arbres d'Attributs Ordonnées (AAO) proposée par Lobo et Numao en 2000, qui construit un arbre de décision pour chacun des attributs, selon un ordre croissant en fonction de l'Information Mutuelle entre chaque attribut et la classe. Notre approche étend la méthode de Lobo et Numao, d'une part en prenant en compte les dépendances entre les attributs pour la construction des arbres d'attributs, et d'autre part en fournissant un résultat de classement d'un objet incomplet sous la forme d'une distribution de probabilités (au lieu de la classe la plus probable). <br />Nous expliquons notre méthode et nous la testons sur des bases de données réelles. Nous comparons nos résultats avec ceux donnés par la méthode C4.5 et AAO. <br /><br />Nous proposons également un algorithme basé sur la méthode des k plus proches voisins qui calcule pour chaque objet de la base de test sa fréquence dans la base d'apprentissage. Nous comparons ces fréquences avec les résultats de classement données par notre approche, C4.5 et AAO. Finalement, nous calculons la complexité de construction des arbres d'attributs ainsi que la complexité de classement d'un objet incomplet en utilisant notre approche, C4.5 et AAO.

Thèse (M.Sc.)--Université Laval, 2007. / Bibliogr.: f. [110]-113. Publié aussi en version électronique dans la Collection Mémoires et thèses électroniques.

Mémoire (M.Ress.Renouv.)--Université du Québec à Chicoutimi, 1997. / Document électronique également accessible en format PDF. CaQCU

Mémoire (M.Ress.Renouv.)--Université du Québec à Chicoutimi, 1999. / Document électronique également accessible en format PDF. CaQCU

Mémoire (M.Ress.Renouv.)--Université du Québec à Chicoutimi, 2001. / Document électronique également accessible en format PDF. CaQCU

Thesis (Ph. D.)--University of Nebraska, 1916. / Vita. Published also in Nebraska university. University studies, vol. XVI, nos. 1-2, p.l-89. Bibliography: p. 88-89.

Dans cette thèse on étudie certains phénomènes d'interactions entre caractéristique positive et caractéristique nulle. Dans un premier temps on s'occupe du problème de relèvement locale d'actions de groupes. On y montre des conditions nécessaires pour l'existence de relèvement de certains actions du groupe Z/pZ x Z/pZ. Pour une action d'un groupe fini quelconque, on y étudie les arbres de Hurwitz, en montrant que chaque arbre de Hurwitz admet un plongement dans le disque unitaire fermé de Berkovich et que ses données de Hurwitz peuvent être décrites de façon analytique. Dans une deuxième partie nous construisons un analogue de la représentation de Weil à coefficients dans un anneau intègre, et nous montrons que cela satisfait les mêmes propriétés que dans le cas de coefficients complexes / In this thesis, we study the interplay between positive and zero characteristic. In a first instance, we deal with the local lifting problem of lifting actions of curves. We show necessary conditions for the existence of liftings of some actions of Z/pZ x Z/pZ. Then, for an action of a general finite group, we study the associated Hurwitz tree, showing that every Hurwitz tree has a canonical metric embedding in the Berkovich closed unit disc, and that the Hurwitz data can be described analytically.In the last chapter, we define an analog of the Weil representation with coefficients in an integral domain, showing that such representation satisfies the same properties than in the case with complex coefficients