Direction de recherche : Michele SORIA

Structures arborescentes complexes : analyse combinatoire, génération aléatoire et applications

Ce travail a pour but l'application des techniques d'analyse et de génération aléatoire de la combinatoire analytique à des problèmes issus de domaines variés où apparaissent des structures arborescentes. Dans un premier temps, nous étudions les propriétés des k-arbres, une famille de graphes qui généralise celle des arbres. Les k-arbres jouent un rôle central en algorithmique des graphes et apparaissent aussi (sous le nom de réseaux apolloniens aléatoires ou triangulations en pile) comme modèle pour les graphes de terrain. Notre contribution consiste en une bijection entre k-arbres et une famille simple d'arbres et son utilisation pour analyser certaines propriétés des k-arbres sous la distribution uniforme: distribution des degrés en loi de puissance avec chute exponentielle, distance moyenne en racine carrée de la taille et profil qui suit une loi de Rayleigh. La seconde partie a pour objet la génération aléatoire de structures arborescentes avec la méthode de Boltzmann. Nous avons mis en place un cadre générique et efficace que nous avons appliqué à la génération de données issues de plusieurs domaines logiciels : instances de types de données algébriques, instances de méta-modèles et de documents XML selon une grammaire. La complexité linéaire des algorithmes de génération rend ces outils bien adaptés aux tests de robustesse et de performance.

Soutenance : 26/01/2010

Membres du jury :

Frédéric Chyzak
Philippe Duchon
Philippe Flajolet
Mihyun Kang
Matthieu Latapy
Christian Queinnec
Gilles Schaeffer
Michèle Soria, directrice

Publications 2007-2016

• 2016
  • A. Darrasse, H.‑K. Hwang, M. Soria : “Shape Measures of Random Increasing k-trees”, Combinatorics, Probability and Computing, vol. 25, pp. 668-699, (Cambridge University Press (CUP)) (2016)
• 2012
  • A. Darrasse, K. Panagiotou, O. Roussel, M. Soria : “Biased Boltzmann samplers and generation of extended linear languages with shuffle”, Discrete Mathematics and Theoretical Computer Science, vol. DMTCS Proceedings vol. AQ, 23^rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings, Montreal, Canada, pp. 125-140, (Discrete Mathematics and Theoretical Computer Science) (2012)
• 2011
  • F. Chyzak, A. Darrasse : “Using camlp4 for presenting dynamic mathematics on the web: DynaMoW, an OCaml language extension for the run-time generation of mathematical contents and their presentation on the web”, ICFP 2011 - 16^th ACM SIGPLAN International Conference on Functional Programming, Tokyo, Japan, pp. 259-265, (ACM) (2011)
• 2010
  • A. Darrasse : “Structures arborescentes complexes : analyse combinatoire, génération aléatoire et applications”, soutenance de thèse, soutenance 26/01/2010, direction de recherche Soria, Michele (2010)
  • A. Darrasse, K. Panagiotou, O. Roussel, M. Soria : “Boltzmann generation for regular languages with shuffle”, GASCOM 2010 - Conference on random generation of combinatorial structures, Montréal, Canada (2010)
  • A. Darrasse, H.‑K. Hwang, O. Bodini, M. Soria : “The connectivity-profile of random increasing k-trees”, Workshop on Analytic Algorithmics and Combinatorics (ANALCO), Austin, United States, pp. 99-106, (Society for Industrial and Applied Mathematics) (2010)
• 2009
  • B. Canou, A. Darrasse : “Fast and sound random generation for automated testing and benchmarking in Objective Caml”, 2009 ACM SIGPLAN Workshop on ML, Edinburgh, United Kingdom, pp. 61-70, (ACM) (2009)
  • A. Darrasse, M. Soria : “Limiting distribution for distances in k-trees”, 20^th International Workshop on Combinatorial Algorithms, IWOCA 2009, vol. 5874, Lecture Notes in Computer Science, Hradec nad Moravicí, Czechia, pp. 170-182 (2009)
  • A. Mougenot, A. Darrasse, X. Blanc, M. Soria : “Uniform random generation of huge metamodel instances”, Fifth European Conference on Model-Driven Architecture Foundations and Applications (ECMDA-FA 2009), Enschede, Netherlands, pp. 130-145 (2009)
• 2008
  • A. Darrasse : “Random XML sampling the Boltzmann way”, (2008)
  • O. Bodini, A. Darrasse, M. Soria : “Distances in random Apollonian network structures”, Discrete Mathematics and Theoretical Computer Science, vol. DMTCS Proceedings vol. AJ, 20^th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), DMTCS Proceedings, Viña del Mar, Chile, pp. 307-318, (Discrete Mathematics and Theoretical Computer Science) (2008)
• 2007
  • F. Peschanski, A. Darrasse, N. Guts, J. Bobbio : “Coordinating mobile agents in interaction spaces”, Science of Computer Programming, vol. 66 (3), pp. 246-265, (Elsevier) (2007)
  • A. Darrasse, M. Soria : “Degree distribution of random Apollonian network structures and Boltzmann sampling”, Discrete Mathematics and Theoretical Computer Science, vol. DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings, Juan les Pins, France, pp. 313-324, (Discrete Mathematics and Theoretical Computer Science) (2007)