TABLE DES MATIÈRES Conclusion et Perspectives Bibliographie

A Ordres partiels B Transformées de Laplace et de Borel I Contexte général D'innombrables activités humaines sont aujourd'hui supportées par des logiciels de complexité et de taille croissante. Avec l'avènement des architectures multi-coeurs embarquées, des facteurs importants de cette complexité sont liés au parallélisme et à la concurrence.

Un programme concurrent est composé de plusieurs unités logiques : les processus. Chaque processus a un comportement qui lui est propre : il exécute ses actions de façon séquentielle. Quand plusieurs processus s'exécutent en parallèle, l'ordre d'exécution des actions du programme global n'est plus déterminé. En pratique, ce parallélisme peut être matériel (architecture multicoeur, clusters de machines, etc.) ou logiciel (ordonnanceur de système d'exploitation, etc.).

Un objectif important est de s'assurer que de tels système concurrents complexes sont exempts de défaut. Cette problématique est étudiée depuis les années 60 dans le cadre de la théorie de la concurrence (cf. [Pet62],[Hoa78] et [Mil80]). De nombreuses techniques et méthodes d'analyse ont été proposées : model checking, analyse statique, tests automatisés, etc. Ces approches diverses se rejoignent sur un problème commun connu dans le folklore comme le phénomène d'"explosion combinatoire". Car si l'ordre d'exécution des actions n'est pas déterminé, c'est surtout le grand nombre d'exécutions possibles qui pose problème. Cette thèse s'inscrit dans un projet à long terme d'étude quantitative de ce phénomène en exploitant notamment les outils de la combinatoire analytique [FS09]. Dans des travaux précédents ont notamment été étudiés le principe d'entrelacement [BGP16] et le non-déterminisme [BGP13].

Notre objectif est d'aborder une autre composante fondamentale de la concurrence : la synchronisation. Ce principe permet aux processus de communiquer entre eux. Par exemple, dans le cas d'un programme parallèle, plusieurs processus vont effectuer des sous-calculs indépendants avant de se synchroniser pour produire le résultat final. En pratique, la synchronisation peut être faite avec un mécanisme de mémoire partagée (mutex, sémaphore, etc.) ou en utilisant des canaux de communications (CSP, CCS, etc.).

Les travaux précédents mettent en exergue un lien très fort entre concurrence et combinatoire des structures croissantes (cf. [Gen17] pour une vue d'ensemble). Les études précédentes étaient principalement basées sur l'étiquetage croissant de structures arborescentes mais l'approche proposée dans cette thèse nécessite l'introduction des graphes dirigés acycliques (DAG en anglais).

De nombreux formalismes restreignent la structure de contrôle des programmes à un graphe dirigé acyclique. Des exemples illustratifs sont les langages synchrones [PEB07] et la programmation fonctionnelle réactive (FRP en anglais) [ACRS16]. On retrouve aussi cette contrainte en Une autre approche est celle proposée par Jean Mairesse et ses coauteurs sur le monoïde de traces (cf. [KMM02], [AM15]). Il s'agit d'un modèle de "vraie concurrence", dans le sens où les actions atomiques de processus en parallèle peuvent s'exécuter en même temps, sans entrelacement. Les résultats obtenus sur ce modèle vont de l'analyse de plusieurs paramètres combinatoires jusqu'à la génération aléatoire d'éléments du monoïde : analogue des traces d'exécutions.

Enfin, les travaux de Johan Oudinnet et ses coauteurs se sont concentrés sur le modèle de système de transitions tels que ceux analysés dans le cadre du model checking (cf. [ODG `11]). Une des motivations principales est d'ailleurs de fournir un algorithme de génération aléatoire uniforme de chemins dans ces systèmes et ainsi fournir une brique efficace et non biaisée dans le cadre du model checking statistique introduit dans [GS05].

Ces travaux sont d'un point de vue technique assez éloignés de ceux présentés dans cette thèse. Nous avons choisi de détailler les travaux connexes plus proches au début de chaque chapitre.

Contributions de la thèse

Nous introduisons la famille de DAGs que nous nommons les diamants. Pour différentes classes de diamants nous obtenons des formules closes pour leurs séries génératrices notamment en terme de fonctions elliptiques et de fonctions dites spéciales. Pour ces séries nous obtenons des équivalents asymptotiques de leurs termes généraux. Nous présentons également une analyse en moyenne du degré de leur racine. Enfin, nous exhibons des bijections avec d'autres familles d'objets croissantes.

Sur la classe des graphes Fork-Join correspondant aux ordres Série-Parallèle, nous introduisons un opérateur dit de produit ordonné ainsi qu'un produit coloré pour spécifier les étiquetages croissants de ces graphes. Ces opérateurs désormais intégrés à la méthode symbolique ont un intérêt au-delà de la synchronisation des processus concurrents. Nous montrons notamment leur utilisation dans la spécification des arbres binaires de recherche, les permutations intervalles généralisées, les partitions d'entiers et les nombres de Bell. Sur ces opérateurs nous sommes capables de proposer des propriétés intéressantes notamment des théorèmes de transfert assez généraux. Sur les graphes Fork-Join croissants nous obtenons un équivalent asymptotique pour le nombre de graphes d'une taille donnée.

Les contributions sur les ordres partiels sans cycles sont plus mesurées. Tout d'abord nous proposons une décomposition simple des DAGs permettant de les caractériser. Cette décomposition nous permet de construire une formule symbolique (de taille linéaire) de comptage du nombre d'extensions linéaires. Les problèmes de comptage effectif et de génération aléatoire efficace restent ouverts.

Concernant la génération aléatoire uniforme nos contributions sont les suivantes. Nous proposons différents générateurs de Boltzmann pour les structures croissantes dont la série génératrice vérifie une équation différentielle d'ordre 2. Nous l'appliquons notamment aux diamants croissants. Enfin, nous proposons aussi un générateur aléatoire uniforme d'extensions linéaires pour les ordres partiels Série-Parallèle. Cet algorithme est optimal en nombre de bits aléatoires consommés.

C 1

D C

Les diamants croissants sont le point de départ de notre étude. Du point de vue de la combinatoire analytique, on peut les spécifier en utilisant le produit boîte [Gre83] de la méthode symbolique et l'étude de leur séries génératrices suit une méthodologie assez classique. La principale difficulté rencontrée dans l'analyse de ces différentes classes d'objets provient de l'originalité de leur séries génératrices qui s'expriment en terme de fonctions elliptiques ou encore de fonction d'erreur.

Du point de vue des programmes concurrents, ils représentent des modèles très simplifiés de programmes Série-Parallèle. La classe des diamants croissants peut être vu comme la classe non-triviale la plus simple utilisant les constructions de parallélisme et de synchronisation de processus concurrents.

 [START_REF] Valiant | A bridging model for parallel computation[END_REF]) et en ordonnancement (cf. [START_REF] Jarry | Dagsim : a simulator for dag scheduling algorithms[END_REF]). Du point de vue de la combinatoire l'étude des DAGs croissants est une problématique complexe. Un résultat fondamental établi dans [START_REF] Brightwell | Counting linear extensions[END_REF] est que le problème de compter le nombres d'extensions linéaires d'un ordre partiel arbitraire (correspondant au nombre d'exécutions possibles d'un programme) est 7P-complet. Cela signifie que même pour ce modèle simplifié de concurrence, l'étude du phénomène d'explosion combinatoire est complexe.

Dans cette thèse notre approche est de considérer des sous-classes de programmes, donc de DAGs, pour lesquelles le problème de comptage semble plus accessible. Tout d'abord, nous nous intéressons à la classe des diamants croissants pour lesquels nous avons pu exploiter les outils de combinatoire analytique (cf. [BDF `16]). Ensuite, dans l'article [START_REF] Bodini | The ordered and colored products in analytic combinatorics : Application to the quantitative study of synchronizations in concurrent processes[END_REF] nous avons étudié une classe de programmes correspondant aux ordres partiels Série-Parallèle et pour lesquels nous avons pu produire des résultats asymptotiques, mais en passant par des techniques plus ad-hoc. Enfin, nous abordons une classe beaucoup plus expressive, les ordres partiels sans cycle, pour laquelle nous n'avons que des résultats préliminaires (encourageants).

Si cette étude est principalement théorique, nous envisageons cependant à plus long terme des applications pratiques. Une motivation importante de notre travail concerne en effet la vérification automatique du bon fonctionnement de programmes concurrents. L'analyse exhaustive du comportement des programmes concurrents se heurte au phénomène d'explosion combinatoire. De nombreuses techniques de réduction de l'espace d'états ont été proposées : compression, abstraction, élimination des symétries, etc. Une autre approche complémentaire consiste en une vérification statistique du programme.

Pour parer à l'explosion combinatoire, une idée est d'abandonner l'exhaustivité de la vérification en adoptant une approche probabiliste. L'objectif est de s'assurer que quelques exécutions choisies au hasard sont "bonnes". Il a été observé que si le hasard est biaisé pour favoriser une petite fractions des exécutions possibles, alors les résultats de la vérification peuvent se révéler mauvais (cf. [START_REF] Grosu | Monte carlo model checking[END_REF])). Au contraire, une plus grande uniformité semble donner de meilleurs résultats (cf. [ODG `11]). De part les nombreux liens existants entre combinatoire et génération aléatoire, nous nous intéressons donc aussi au problème de la génération aléatoire uniforme d'exécutions. Enfin, une dernière motivation, pouvant s'appliquer à la concurrence mais plus large dans les faits, concerne la génération aléatoire uniforme de programmes. De même que générer aléatoirement des exécutions possibles d'un programme pour le vérifier, on peut générer aléatoirement un programme pour vérifier que les outils travaillant sur les programmes (compilateurs, analyseurs, ...) fonctionnent correctement. Cette idée a déjà été fructueuse, par exemple dans le cadre du test de compilateurs C (cf. [START_REF] Yang | Finding and understanding bugs in c compilers[END_REF]).

Approches alternatives

D'autres travaux adoptent un point de vue combinatoire sur l'étude de la concurrence. En combinatoire analytique, des travaux abordent la problématique du shuffle de langages réguliers généralement sur des alphabets disjoints, donc sans synchronisation (cf. [GDG `08] et [START_REF] Darrasse | Biased boltzmann samplers and generation of extended linear languages with shuffle[END_REF]). Plus récemment, Nicolas Basset et ses coauteurs introduisent plusieurs algorithmes de génération aléatoire uniforme de mots reconnus par des automates synchronisés (cf. [START_REF] Basset | Uniform sampling for networks of automata[END_REF]).

INTRODUCTION

Plan du manuscrit

Le chapitre 1 présente dans le détail l'ensemble des résultats obtenus sur les diamants croissants.

Les ordres Série-Parallèle ainsi que la classe des graphes Fork-Join sont présentés dans le chapitre 2. Les résultats sur les produits ordonné et coloré qui ne sont pas spécifiques à ces classes sont regroupés en fin de chapitre.

Le chapitre 3 est dévolu à la génération aléatoire. On rappelle ce qu'est la méthode de Boltzmann et comment on construit des générateurs de Boltzmann pour les structures croissantes. S'en suit la présentation de l'algorithme de génération aléatoire d'extensions linéaires pour les ordres Série-Parallèle. On trouvera aussi une étude pratique poussée de ces algorithmes à travers diverses expérimentations.

Ensuite dans le chapitre 4 nous présentons la décomposition et le comptage symbolique d'extensions linéaires pour les ordres partiels sans cycle. Une petite expérimentation pratique est aussi proposée.

Le manuscrit se termine par une conclusion suivi d'un panorama des perspectives de recherche.

Deux annexes sont ajoutées à la fin du manuscrit. L'annexe A rappelle un certain nombre de définitions sur les ordres partiels. L'annexe B rappelle les définitions et quelques propriétés des transformées de Laplace et Borel combinatoires.

Présentation

Introduction

Les diamants sont des graphes dirigés et acycliques possédant une unique source (un noeud sans prédécesseur) et un unique puits (un noeud sans successeur). 1

En combinatoire analytique [START_REF] Flajolet | Analytic combinatorics[END_REF], nous caractérisons les objets étudiés via une décomposition (récursive) que nous synthétisons dans une spécification des objets. La classe combinatoire non étiquetée D d'une famille de diamant est spécifiée par D " Z `Z ˆGpDq ˆZ, où G est la fonction des degrés et des règles de construction de la famille de diamants (binaire, ternaire, plans, cycliques, etc).

6

CHAPITRE . DIAMANTS CROISSANTS

Dans ce cas non étiqueté, la spécification des diamants peut être interprétée comme une spécification d'arbres simplement générés (cf. [START_REF] Flajolet | Analytic combinatorics[END_REF]). De fait, la littérature à propos de ces arbres est vaste et le comportement de la plupart des paramètres structurels sont bien connus.

Notre étude s'intéressant à l'aspect quantitatif des exécutions de programmes concurrents, on cherche donc à étudier des classes de diamants étiquetées de manière croissante, car une exécution est en correspondance directe avec un étiquetage croissant de la structure.

Les diamants croissants sont des diamants étiquetés, c'est-à-dire que tous les noeuds ont une étiquette unique représentée par un entier naturel et tel que l'ensemble des étiquettes d'un diamant est un intervalle de N commençant par 1. De plus, ils sont croissants : la suite d'étiquettes obtenues le long de tout chemin de la source vers le puits est croissante et c'est les entiers de cette suite sont consécutifs. où G est un opérateur spécifiant le type de diamants par degré et par règle de construction (planarité). Les symboles ˝et ' sont les opérateurs boîtes (cf. [START_REF] Hill | Labelled formal languages and their uses[END_REF] et [START_REF] Flajolet | Analytic combinatorics[END_REF]p. 139]). Ils représentent, respectivement, la plus petite et la plus grande étiquette d'une structure. La Figure 1.1 présente des exemples de telles structures. La Spécification (1.1.1) se traduit en équation fonctionnelle satisfaite par la série génératrice f pzq " ÿ ně0 a n z n n! de la famille de diamants :

f 2 pzq " Gpf pzqq, avec f p0q " 0 et f 1 p0q " 1.

(1.1.2)

On autorisera aussi d'autres conditions initiales, par exemple f p0q " f 1 p0q " 0.

. . PRÉSENTATION

Remarque 1:

Dans les cas que nous étudions, issus de problèmes combinatoires, la solution est garantie comme existante et unique grâce au théorème de Cauchy-Lipschitz.

Par la suite nous étudierons, dans le détail, différentes familles de diamants en fonction de l'opérateur G : des familles polynomiales (degrés des noeuds fixés, par exemple binaire ou ternaire) et des diamants généraux, plans et non-plans (degrés des noeuds non-fixés). Les résultats que nous obtenons sur ces différentes classes sont :

-l'énumération asymptotique des objets d'une taille fixée -le degré moyen de la source des diamants croissants de taille fixée -et dans certains cas, des bijections avec d'autres objets combinatoires déjà connus.

Motivations

Du point de vue de la concurrence, les diamants sont une classe simple mais non-triviale de programmes concurrents où les constructions de parallélisme et de synchronisation sont présentes. Ils sont néanmoins peu expressifs car le mécanisme de synchronisation suit une discipline de pile : toute création de k processus en parallèles est suivi par une synchronisation de ces k mêmes processus sans poursuite possible du flot de contrôle. Néanmoins, ils ont l'intérêt d'être analysable à l'aide des outils de combinatoire analytique existants. C'est pour cela qu'ils sont un bon point de départ pour l'étude quantitative de la synchronisation.

Les bijections exhibées entre diamants croissants et objets croissants de la littérature mettent en liens nos travaux avec des travaux déjà existants. Elles permettent notamment de réutiliser les résultats obtenus pour certains paramètres sur ces objets de la littérature (et vice-versa).

Travaux proches

Ce travail sur les diamants a pour point de départ les travaux effectués par mes encadrants et O. Bodini, à propos de la combinatoire des programmes concurrents utilisant seulement la construction parallèle. Dans [START_REF] Bodini | A Quantitative Study of Pure Parallel Processes[END_REF], ils explorent la combinatoire des programmes purement parallèles où l'opérateur de composition parallèle n'est pas limité en nombre d'opérandes (vu comme une S ou un S ), tandis que dans (avec N. Rolin) [START_REF] Bodini | Associativity for Binary Parallel Processes : A Quantitative Study[END_REF], ils étudient la restriction binaire de cet opérateur. Dans tous ces cas, ils calculent le nombre moyen d'exécutions possibles de programmes d'une taille fixée, c'est-à-dire le nombre moyen d'étiquetages croissants d'arbres de taille fixée.

Concernant l'analyse de nos diamants croissants, elle est très similaire à celles des arbres croissants, étudiés par F. Bergeron, P. Flajolet et B. Salvy dans [START_REF] Bergeron | Varieties of Increasing Trees[END_REF]. Ces derniers se placent dans le cadre assez générique de l'étude de familles croissantes d'arbres simplement générés, de spécification T " Z `Z˝‹ GpT q.

Leur analyse se concentre donc sur l'équation différentielle du premier ordre f 1 pzq " Gpf pzqq, avec f p0q " 0.

Ils utilisent alors les outils de combinatoire analytique pour calculer les asymptotiques et lois limites de différentes grandeurs : nombre moyen de feuilles, degré moyen de la racine et longueur de cheminement moyenne. Plus récemment, Les équations différentielles rencontrées lors de notre étude des diamants croissants on aussi été rencontrées par A. Panholzer et M. Kuba lors de leurs études de modèles d'arbres doublement étiquetés croissants. Notamment, ils dérivent plusieurs formules closes, dites "des équerres", calculant le terme général de plusieurs des séries génératrices (cf. [START_REF] Kuba | Combinatorial families of multilabelled increasing trees and hook-length formulas[END_REF]).

Plan du chapitre

Nous commencerons par présenter dans le détail les différentes spécifications des objets et leur séries génératrices quand une formule close est connue. Nous ferons alors un petit détour dans notre étude quantitative en présentant des bijections avec d'autres objets connus de la littérature. Dans la section suivante, nous présenterons une étude détaillée des différents comportements asymptotiques des familles déjà présentées. Enfin, nous étudierons le degré à la racine moyen de ces familles.

Combinatoire des diamants croissants 1.2.1 Cas général

En multipliant les deux côtés de l'équation (1.1.2) par 2f 1 , on obtient 2f 2 f 1 " 2Gpf qf 1 , ce qui implique : f 1 pzq 2 " f 1 p0q 2 `ż z 0 2Gpf ptqqf 1 ptqdt " f 1 p0q 2 `2G pf pzqq, où G pzq :" ş z 0 Gptqdt. Donc f 1 pzq " ˘af 1 p0q 2 `2G pf pzqq, soit :

˘ż f pzq 0 1 a f 1 p0q 2 `2G ptq dt " z.
(1.2.1)

Lemme 1: La solution de l'équation différentielle f 2 " Gpf q avec f p0q " 0 est implicitement définie par :

ż f pzq 0 1 a f 1 p0q 2 `2G ptq dt " z. (1.2.2)
Démonstration. En faisant un développement de Taylor du membre gauche de l'équation (1.2.1), on trouve que la solution négative n'est pas possible et on en conclut l'équation (1.2.2).

La solution (1.2.2), malgré le fait qu'elle soit implicite, reste utile dans notre analyse asymptotique, même quand aucune simplification n'est possible.

Comme dans [START_REF] Bergeron | Varieties of Increasing Trees[END_REF], il faut faire attention au caractère périodique où non des séries que nous considérons.

Définition 1 (de [START_REF] Bergeron | Varieties of Increasing Trees[END_REF]): Une fonction φ est dite périodique si il existe une fonction ψ telle que φpzq " ψpz p q pour p ě 2. Le plus grand p possible est appelé période de φ. Si p " 1, on dit de ψ qu'elle est apériodique.

Dans le cas de [START_REF] Bergeron | Varieties of Increasing Trees[END_REF], la périodicité vient de la fonction φ telle que f 1 " φpf q. Ici, on considère des équations différentielles du deuxième ordre avec des conditions initiales plus générales.

Proposition 1:

Soit une équation différentielle de diamants (1.1.2) telle que :

f 1 pzq "
a pf 1 p0qq 2 `2 ¨G pf pzqq " gpf pzqq.

Si l'on note p la période de g, f est périodique de période valpf q ¨p où val est la valuation 2 de f . Démonstration. Soit p la période de g. On a alors f 1 pzq " gpf pzqq. Donc, il existe ψ telle que :

f 1 pzq " ψpf p pzqq " ÿ kě0 g k f p¨k pzq " ÿ kě0 g k ˜ÿ ně0 f n z n ¸p¨k
En notant v la valuation de f , on obtient :

f 1 pzq " ÿ kě0 g k pz v¨p q k ˜ÿ něv f n z n´v ¸p¨k
On en déduit que f 1 est périodique de période v ¨p. Une intégration symbolique du développement en série de f 1 nous permet de conclure que f a la même période.

Ainsi, on adapte le lemme fondamental de [START_REF] Bergeron | Varieties of Increasing Trees[END_REF] à notre étude des diamants.

Lemme 2:

La singularité dominante ρ (réelle et positive) de la fonction f , solution de (1.1.2), est :

ρ " ż ρ G 0 dt b f 1 p0q 2 `2 ş t 0 Gpvqdv
, où ρ G est le rayon de convergence de ş z 0 Gptqdt. De plus, si l'équation de la série f est apériodique, alors ρ est la seule singularité dominante de f . Si l'équation de f a une période p ě 2, alors il existe une série apériodique f telle que f pzq " f pz p q et ρ 1 p est son unique singularité dominante.

2. La valuation d'une série est le rang de son premier terme non nul.

10

CHAPITRE . DIAMANTS CROISSANTS

La preuve du lemme précédent est similaire à celle du Lemme 1 de [START_REF] Bergeron | Varieties of Increasing Trees[END_REF] avec une correction sur les bornes de l'intégrale expliquée par la proposition suivante.

Proposition 2: Soit f solution de l'équation différentielle f 2 pzq " Gpf pzqq. La singularité dominante de ş z 0 Gptqdt est la limite de f pzq quand z tend vers ρ.

Démonstration. Soit ρ la plus petite singularité réelle positive de f , dont l'existence est garantie par le théorème de Pringsheim. Par la suite on notera f pρq " lim zÑρ ´f pzq la limite inférieure de f en ρ (sur la droite des réelles).

On sait que G est bien définie sur r0, f pρqr. De plus, on sait que f est croissante sur r0, ρr et donc on peut définir son inverse compositionnel f ´1 sur ce segment. On a alors Gpzq " f 2 pf ´1pzqq pour z dans r0, f pρqr.

Montrons que f pρq est la singularité dominante réelle de G. Par définition, G n'a pas de singularité sur r0, f pρqr. Or, f pρq est une singularité de f 2 pf ´1pzqq, car ρ est singularité de f et donc de f 2 . On en déduit donc que f pρq est singularité de G, de plus, c'est sa plus petite singularité réelle positive.

Cas avec solution explicite

Dans cette sous-section, on s'intéressera aux différentes familles de diamants pour lesquelles l'équation (1.1.2) peut être résolue explicitement. Ainsi, dans tous les cas qui suivent on trouve une formule close pour le nombre de diamants croissants d'une taille fixée.

Diamants tricolores

Les diamants croissants tricolores sont donnés par la spécification suivante T " Z `Z˝‹ S pT q ‹ S pT q ‹ S pT q ‹ T ' .

(1.2.3) Le produit de trois séquences peut être interprété comme un produit de trois séquences de trois couleurs différentes, d'où leur nom de diamants tricolores.

Théorème 1:

Les diamants croissants tricolores ont pour fonction génératrice exponentielle T pzq " 1 ?1 ´2z. Son rayon de convergence est 1{2 et le nombre t n de diamants croissants tricolores de taille n est

t n " n!rz n sT pzq " n ź k"1 p2k ´1q " p2n ´1q!! où le symbole !! représente la double factorielle.
Démonstration. Dans ce cas, l'équation différentielle (1.1.2) est résolue de façon élémentaire :

T 2 pzq " p1 ´T q ´3 2 T 1 pzq T 2 pzq " 2 T 1 pzq p1 ´T q ´3
en multipliant par 2T 1 pzq pT 1 pzqq 2 ´1 " p1 ´T q ´2 ´1 par intégration T 1 pzq ´T 1 pzq T pzq ´1 " 0 T 2 pzq ´2T pzq `2z " 0 par intégration T pzq " 1 ´?1 ´2z après choix de la "bonne" branche On retrouve alors une fonction algébrique classique, dont on extrait facilement le terme général :

n!rz n sT pzq " n ź k"1 p2k ´1q

Diamants généraux non-plans

Cette classe P de diamants est définie par la spécification

P " Z `Z˝‹ S pPq ‹ Z ' . (1.2.4)
Elle correspond donc au cas G " S dans l'équation (1.1.1).

Théorème 2:

Les diamants croissants généraux non-plans ont pour fonction génératrice, la solution de (1.1.2) avec G " exp. Son rayon de convergence est π 2 et le nombre p n de diamants croissants généraux non-plans de taille n est

p n " 2 n`1 pn ´1q! π n `8 ÿ j"´8 1 p1 `4jq n .
Note: On peut réécrire p n pour n ě 2 en terme de fonction zeta d'Hurwitz 3 ξpn, sq :

p n " pn ´1q! ¨ξpn, 1 4 q `p´1q n ξpn, 3 4 q 2 n´1 π n . 3. ξpn, sq " 8 ÿ k"0 pk `sq ´n
Démonstration. En résolvant l'équation (1.1.2) avec G " exp, on trouve une expression pour P 1 : P 2 pzq " e P pzq 2 P 1 pzq P 2 pzq " 2 P 1 pzq e f pzq en multipliant les deux côtés par 2 P 1 pzq pP 1 pzqq 2 ´1 " 2 e P pzq ´2 en intégrant entre 0 et z des deux côtés, 2P 2 pzq 1 `pP 1 pzqq 2 " 1 car P 2 " e P , z " 2

ż z 0 P 2 ptq 1 `pP 1 ptqq 2 dt z " 2 ż P 1 pzq 1 1 1 `t2 dt " rarctanptqs t"P 1 pzq t"1 P 1 pzq " tanpzq `1 cospzq d'où, après simplification P pzq " ´logp1 ´sinpzqq
On observe que les singularités de P 1 sont les ρ k " π 2 `2kπ pour k P Z et notamment que sa singularité dominante est π 2 . On utilise alors la formule de Cauchy rz n sP 1 pzq " 1 2iπ ¿ γ P 1 pξq ξ n`1 dξ valable pour un cercle γ de centre 0 de rayon plus petit que π 2 .

On utilise alors le théorème des résidus pour calculer cette intégrale :

1 2iπ ¿ γ N P 1 pξq ξ n`1 dξ " Res " P 1 pzq z n`1 ; 0  `N ÿ j"´N Res " P 1 pzq z n`1 ; π 2 `2jπ  " rz n sP 1 pzq `N ÿ j"´N Res " P 1 pzq z n`1 ; π 2 `2jπ  (1.2.5)
avec γ N un cercle de centre 0 et de rayon N

On calcule le résidu de P 1 en ρ j :

Res

" P 1 pzq z n`1 ; ρ j  " 1 z n`1 pz ´ρj qP 1 pzq ˇˇˇz "ρ j " zÑρ j z ´ρj ρ n`1 j ¨sinpρ j q `1 cospzq " zÑρ j z ´ρj ρ n`1 j ¨2 cospz ´ρj `ρj q " zÑρ j z ´ρj ρ n`1 j ¨2 ´sinpz ´ρj q par identité trigonométrique " zÑρ j z ´ρj ρ n`1 j ¨2
´"pz ´ρj q ´pz´ρ j q 3 3!

`o ppz ´ρj q 3 q ı " ´2 ρ n`1 j Soit, en remplaçant dans l'équation (1.2.5) :

1 2iπ ¿ γ N P 1 pξq ξ n`1 dξ " rz n sP 1 pzq `N ÿ j"´N Res " P 1 pzq z n`1 ; π 2 `2jπ  " rz n sP 1 pzq ´2n`2 π n`1 N ÿ j"´N 1 p1 `4jq n`1 .
(1.2.6)

On remarque que l'intégrale 1 2iπ ű γ N P 1 pξq ξ n`1 dξ tend vers 0 quand N tend vers l'infini, ainsi :

¿ γ P 1 pξq ξ n`1 dξ ď ¿ γ ˇˇˇP 1 pξq ξ n`1 ˇˇˇd ξ ď sup tPr0,1s ˇˇˇP 1 pγptqq γptq n`1 ˇˇˇ¨ż 1 0 ˇˇˇd γ dt ˇˇˇd t ď 1 R n`1 ¨sup θPr0,2πs ˇˇˇt an ´Re iθ ¯`1 cos pRe iθ q ˇˇˇ¨2 πR ď 2π R n ˆtanpRq `1 cospRq ˙Ñ N Ñ8 0 avec R " `π 2 `2N π `
˘le point de γ N le plus proche de la singularité ρ N . D'où en passant la limite (de N vers l'infini) dans l'équation (1.2.6) :

rz n sP 1 pzq " 2 n`2 π n`1 `8 ÿ j"´8 1 p1 `4jq n`1 .

CHAPITRE . DIAMANTS CROISSANTS

Soit, après renormalisation :

p n " n! rz n sP pzq " pn ´1q! rz n´1 sP 1 pzq " 2 n`1 pn ´1q! π n `8 ÿ j"´8 1 p1 `4jq n`1 .

Diamants de Weierstrass

On s'intéresse maintenant aux des diamants binaires :

B " Z `Z˝‹ pE `B ‹ Bq ‹ Z ' .
(1.2.7) et plus généralement aux diamants pour lesquelles l'opérateur G est un polynôme de degré 2.

Premièrement, considérons le cas plus général où G est un polynôme de degré 2 :

f 2 pzq " af 2 pzq `bf pzq `c. (1.2.8)
En multipliant les deux côtés par 2f 1 pzq et intégrant, on obtient : pg 1 pzqq 2 " 4g 3 pzq ´g2 gpzq ´g3 .

pf 1 pzqq 2 " ãf 3 pzq `bf 2 pzq `cf pzq `d.
(1.2.9) où g 2 et g 3 sont des constantes. Or, d'après [START_REF] Lawden | Elliptic Functions and Applications[END_REF], les solutions de cette équation différentielle sont des fonctions elliptiques ℘ de Weierstrass. La famille de fonctions ℘ est l'ensemble de fonctions complexes doublement périodiques sur un réseau du plan complexe, telles que chaque cellule du réseau contienne un unique pôle d'ordre 2 en un coin. Plus formellement :

℘pz; ω 1 , ω 2 q " 1 z 2 `ÿ n 2 `m2 ‰0 1 pz `mω 1 `nω 2 q 2 ´1 pmω 1 `nω 2 q 2 .
où ω 1 et ω 2 sont les deux périodes de la fonction.

La forme générale des solutions de l'équation (1.2.8) est donc :

f pzq " A℘pz `C; g 2 , g 3 q.
Les calculs permettant de trouver ω 1 et ω 2 à partir de g 2 et g 3 , dans le cas général, sont présentés dans [START_REF] Abramowitz | Handbook of mathematical functions : with formulas, graphs, and mathematical tables[END_REF]. Ici, nous présentons le cas particulier des diamants binaires avec :

B 2 pzq " 1 `Bpzq 2 .
Premièrement, en utilisant le Lemme 2, on peut calculer la singularité dominante ρ B de Bpzq (qui est apériodique) :

ρ B " ż 8 0 dt b 2 3 t 3 `2t `1 .
Puis, par identification, on trouve :

Bpzq " 6℘pz `C; ´1 3 , ´1 36 q.
Par définition, la fonction ℘ a un pôle d'ordre 2 en zéro, on en déduit :

Bpzq " 6℘pz ´ρB ; ´1 3 , ´1 36
q.

On note ω 3 la somme des deux périodes fondamentales de B : ω 3 " ω 1 `ω2 . De [START_REF] Abramowitz | Handbook of mathematical functions : with formulas, graphs, and mathematical tables[END_REF], on sait que les racines e 1 , e 2 et e 3 du polynôme P " 4X 3 ´g2 X ´g3 " 4X 3 `1 3 X `1 36 vérifient ℘pω i {2q " e i . Après calcul on obtient :

$ ' ' ' ' ' ' ' & ' ' ' ' ' ' ' % e 1 " 3 ? 4 ´1 12 3 ? 2 ´i? 3 1 `3 ? 4 12 3 ? 2 e 2 " 3 ? 4 ´1 12 3 ? 2 `i? 3 1 `3 ? 4 12 3 ? 2 e 3 " 1 6 ˆ1 3 ? 1 ´3 ? 2 Ḋe [Dav62]
, on sait que :

ω 1 " 2Kpkq ? e 1 ´e2 et ω 2 " 2iK 1 pkq ? e 1 ´e2 avec k " c e 3 ´e2 e 1 ´e2
, et K désignant l'intégrale elliptique complète de première espèce :

Kpkq " ż 1 0 dx a p1 ´x2 qp1 ´k2 x 2 q et K 1 pkq " Kpk 1 q où k 1 est tel que k 2 `k12 " 1.
On obtient donc un développement en série pour B et son terme général :

Bpzq " 6 » - 1 pz ´ρB q 2 `ÿ pk, qPZ 2 ztp0,0qu ˆ1 pz ´ρ ´kω 1 ´ ω 2 q 2 ´1 pkω 1 ` ω 2 q 2 ˙fi fl
dont on extrait le terme général

rz n sBpzq " 6 n `1 ρ n`2 B ÿ pk, qPZ 2 1 ´1 `kω 1 ρ B ` ω 2 ρ B ¯n`2 (1.2.10)

CHAPITRE . DIAMANTS CROISSANTS

Diamants de Jacobi

Nous considérons maintenant le cas des diamants ternaires, sans diamants de taille 1 (T 1 p0q " 0) :

T " Z ˝‹ pE `T ‹ T ‹ T q ‹ Z ' . (1.2.11)
et plus généralement le cas des diamants où G est un polynôme de degré 3, que l'on supposera unitaire sans perte de généralité :

f 2 pzq " f 3 pzq `af 2 pzq `bf pzq `c.
Pour ce faire, on utilise la méthode de résolution proposée dans [START_REF] Thayer | Introduction to Nonlinear Differential and Integral Equations[END_REF].

On multiplie les deux côtés de la précédente équation par 2f 1 , puis en on intègre, pour obtenir :

pf 1 pzqq 2 " f 4 pzq `âf 3 pzq `bf 2 pzq `ĉf pzq `d où d dépend des conditions initiales de l'équation. On calcule les 4 racines α, β, γ et δ du polynôme caractéristique associé à cette équation : X 4 `âX 3 `bX 2 `ĉX `d. Puis, on définit la fonction g telle que :

g 2 " β ´δ α ´δ ¨f ´α f ´β .
(1.2.12)

Après calcul, on trouve que g est solution d'une équation différentielle de la forme :

g 1 pzq " M a p1 ´g2 pzqqp1 ´k2 g 2 pzqq.
Or, les solutions de cette équation sont de la forme de la fonction sinus de Jacobi :

gpzq " snpM z; kq.

Comme la fonction ℘ de Weierstrass, la fonction sinus de Jacobi est définie sur le plan complexe et est doublement périodique sur un réseau. Dans le cas de la fonction sn, il y a deux singularités de type pôles, et d'ordre 1, pour chaque cellule du réseau.

Il ne reste donc plus qu'à inverser l'équation (1.2.12) pour obtenir une expression de f en fonction de sn. L'étude de f doit alors se faire au cas par cas.

Revenons donc sur notre cas particulier des diamants ternaires :

" T p0q " T 1 p0q " 0 T 2 pzq " 1 `T 3 pzq
En utilisant la méthode précédemment décrite, on obtient :

T pzq " 2 2{3 snpM x; kq 2 1 ´j ´snpM x; kq 2

(1.2.13) avec k 2 " e iπ{3 , M " 2 ´5{6 p1 ´jq 1{2 où j est la racine troisième de l'unité e i 2π 3 .

Par définition, la fonction snp¨; kq est doublement périodique. On note K et K 1 ses quarts de période, définis par :

K " ż 1 0 dt a p1 ´t2 qp1 ´k2 t 2 q et K 1 " ż 1 0 dt a p1 ´t2 qp1 ´k12 t 2 q avec k 1 le comodule vérifiant k 12 " 1 ´k2 . La fonction sn 2 étant 2K et 2iK 1 périodique, T est 2K M et 2iK 1 M périodique. On notera dans la suite Q 1 " K M et Q 2 " iK 1
M . De l'équation (1.2.13), on déduit directement que les singularités de T ne viennent pas des pôles de sn mais de l'annulation de son dénominateur. On trouve donc que la singularité dominante ρ T de T est solution de 1 ´j ´snpM z; kq 2 " 0 :

ρ T " 1 M Arcsnp a 1 ´jq " 1 M ż ? 1´j 0 dt a p1 ´t2 qp1 ´k2 t 2 q .
En utilisant diverses identités et la périodicité de sn on trouve que les singularités de T se trouvent aux points congrus à ρ T modulo 2Q 1 et 2ρ T modulo 2Q 2 . De plus, toujours grâce à [START_REF] Lawden | Elliptic Functions and Applications[END_REF], on a que les résidus de T en ces deux différents types de pôles sont respectivement ´?2 et ?

2. Comme dans le cas des Diamants généraux non-plans, on utilise alors le théorème des résidus pour pouvoir calculer la formule de Cauchy donnant le terme général de T . Après calcul, on obtient :

rz n sT pzq " ÿ pk, qPZ 2 ? 2 pρ `2kQ 1 `2 Q 2 q n`1 ´?2 p2ρ `2kQ 1 `2 Q 2 q n`1 " ? 2 ρ n`1 ÿ pk, qPZ 2 1 ´1 `3k 2 `i ? 3 2 pk `2 q ¯n`1 ´1 ´2 `3k 2 `i ? 3 2 pk `2 q
¯n`1 .

Bijections

Plusieurs familles de diamants croissants dont certaines sont énumérées par les même séries que des objets déjà connus. Ici, nous exhibons des bijections entre ces familles. Dans chacune des bijections présentées, l'idée fondamentale est que les structures que nous considérons peuvent être décomposées en arbre. L'intérêt de présenter ces bijections est double :

-cela permet de donner une méthode plus ou moins systématique de construction de bijections avec des diamants croissants, -cela permet d'utiliser les calculs de paramètres moyens pour d'autres structures. Ces différentes bijections montrent l'intérêt de notre étude sur les diamants croissants en présentant d'autres objets pour lesquels nos résultats peuvent être généralisés.

Cactus triangulaires avec ponts

La première famille à laquelle nous nous intéressons est la famille des diamants généraux plans. Leur spécification est la suivante :

F " Z `Z˝‹ S pFq ‹ Z ' (1.3.1)
et leur fonction génératrice est solution de l'équation différentielle suivante :

" F 2 pzq " 1 1´F pzq F p0q " 0 et F 1 p0q " 1 (1.3.2)
Les premiers termes de la série (n-ième terme multiplié par n!) sont :

G " Z ˝‹ S ˆG `C "2 pGq ˙.
On lira cette spécification ainsi : un graphe de G est soit un noeud isolé (un noeud avec un ensemble vide), soit un noeud de plus petite étiquette, racine d'un ensemble de cycle de taille trois (un noeud et un cycle de taille deux) et d'un ensemble de graphes de G. La direction des arcs de ce graphe est naturellement induite par l'étiquetage croissant de ses noeuds.

Via la méthode symbolique, on en déduit que la fonction génératrice G est solution de l'équation différentielle :

# Gp0q " 0 G 1 pzq " e Gpzq`G pzq 2 2 (1.3.3)
En remarquant que F 1 pzq ´1 satisfait aussi l'équation différentielle (1.3.3) on en déduit que ces deux classes d'objets sont bien comptées par les même séries génératrices, à un décalage près. Les spécifications de ces deux types d'objets sont très différentes : les diamants sont plans (opérateur S ) tandis que les cactus ne le sont pas (opérateur S ). Pour trouver une bijection, on va donc manipuler les équations différentielles (1.3.2) et (1.3.3) en les interprétant de manière combinatoire.

Étant donné que G " F 1 ´1, une intuition consiste à dériver les deux équations différentielles pour obtenir :

F 3 " F 1 ¨1 p1 ´F q 2 et G 2 " p1 `Gq ¨`G 1 ˘2
En interprétant combinatoirement l'opérateur de dérivation comme l'opération de suppression d'un noeud d'étiquette particulière (comme dans le cas des espèces combinatoires [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF]), on obtient deux nouvelles décompositions de nos structures :

-F 3 " F 1 ¨1 p1´F q 2 : si l'on supprime les noeuds d'étiquettes 1, 2 et n à un diamant croissant (F 3 ), on obtient un diamant croissant amputé de sa racine (F 1 ) avec une séquence de diamants croissants à sa droite ( 1 1´F ) et une autre à sa gauche ( 1 1´F ), -G 2 " p1 `Gq ¨pG 1 q 2 : un cactus 2-3 enraciné et croissant où l'on supprime les noeuds d'étiquettes 1 et 2 est scindé en trois cactus : les cactus enracinés en 1 et 2 amputés de leur racine (G 1 ¨G1 ) et un cactus (G), vide (1) si 1, 2 ne sont pas dans un cycle de taille trois. On peut transcrire cette description sous la forme de la fonction Ψ (ci-dessous) qui transforme récursivement des cactus en diamants. Afin de lire la définition suivante, notez que (et ces notations seront reprises par la suite pour d'autres bijections) :

a, b désignent les deux étiquettes les plus petites de la structure et a ă b, -c est l'étiquette du troisième noeud dans un cycle contenant les noeuds d'étiquettes a et b, -les sous-graphes A, B et C sont disjoints, -les lignes en tirets dénotent des contractions d'arcs entre des sommets : les deux sommets aux extrémités d'une ligne en tirets sont fusionnés en un seul dont l'étiquette est celle de la racine ou du puits fusionné, -max e pT q désignent la plus grande étiquette du graphe T .

-T "x est le graphe T tel que ses étiquettes (dans l'ordre croissant) pe 1 , . . . , e n q sont remplacées par px, e 1 , . . . , e n´1 q -on pose ΨpA, |A| `1q " ΨpAq :

$ ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' % Ψ p' a , nq " ' a ' n Ψ ¨'a ' b A B , n ‹ ‹ ‹ ‹ ' " ' a ' b ' n ΨpA, nq ΨpB, nq Ψ ¨'a ' b ' c A B C , n ‹ ‹ ‹ ' " ' a ' n ΨpA, nq ΨpB, nq ΨpC "b ,maxepCqq
Dans le cas où ΨpA, ¨q ne serait qu'une chaîne de deux noeuds, la contraction des noeuds fait disparaître l'arc restant. Le deuxième paramètre n de Ψ, permet d'ajuster l'étiquette du puits du diamant obtenu à partir de C, dans le dernier cas. Par soucis pédagogique, illustrons cette construction sur un exemple :

CHAPITRE . DIAMANTS CROISSANTS On veut calculer ΨpT q où T " ' 1 ' 2 ' 3 ' 4 ' 5 ' 6 ' 7 ' 8 ' 9 ' 10 ' 11 ' 12 A B C .
Il faut donc calculer ΨpA, 13q, ΨpB, 13q et ΨpC "2 , 11q :

ΨpA, 13q " ' 1 ' 3 ' 13 ΨpB, 13q " ' 2 ' 10 ' 12 ' 4 ' 5 ' 6 ' 13 ' 9 ΨpC "2 , 11q " ' 2 ' 7 ' 8 ' 11 D'où, en recollant les morceaux : ΨpT q " ' 1 ' 2 ' 3 ' 4 ' 5 ' 6 ' 7 ' 8 ' 9 ' 10 ' 11 ' 12
' 13 En pratique, cette bijection est simple à implémenter de manière efficace : avec complexité linéaire en nombre de noeuds. Elle permet notamment, en utilisant les algorithmes développés durant ce travail de thèse, d'obtenir un algorithme de génération aléatoire uniforme efficace de graphes cactus triangulaires croissants.

Arbres unaire-binaires non-plans

En utilisant la même méthode, consistant à manipuler les équations différentielles pour trouver des similarités entre objets combinatoires, on obtient une bijection entre les diamants généraux, non-plans et les arbres unaire-binaires croissants plans. Dans le cas de cette bijection, les deux types de structures ne sont pas plongés dans le plan.

La spécification de la classe A des arbres unaires-binaires non-plans est une spécification d'arbre croissant simplement généré, comme dans les cas traités par [START_REF] Bergeron | Varieties of Increasing Trees[END_REF].

A " Z ˝‹ S ď2 pAq . . BIJECTIONS 21 Toujours grâce à la méthode symbolique, on obtient une équation différentielle dont la solution est la série génératrice exponentielle A de ces arbres : Comme précédemment, un petit jeu de manipulation d'équations nous donne les relations suivantes :

# Ap0q " 1 A 1 pzq " 1 `Apzq `
P 3 " P 1 ¨P 2 et A 2 " p1 `Aq ¨A1 avec P 1 " 1 `A.
On obtient donc les décompositions suivantes : -P 3 " P 1 ¨P 2 : un diamant général non-plan dont on supprime les deux noeuds de plus petites étiquettes. Celui de plus grande étiquette (P 3 ) est scindé en un diamant général non-plan sans racine pour le diamant enraciné en le noeud d'étiquette 2 (P 1 ) et un ensemble de diamants (ou un diamant sans racine ni puits) pour le diamant enraciné en 1 (P 2 ), -A 2 " p1 `Aq ¨A1 : si l'on supprime les deux plus petites étiquettes d'un arbre unairebinaire non-plan (A 2 ), il reste un de ses sous arbres sans racine, celui qui était enraciné en 2 (A 1 ) et un arbre unaire-binaire (A), vide si la racine initiale était unaire (1). De la même façon, que précédemment, on utilise cette décomposition pour construire une bijection Φ. On suppose que a et b sont les plus petites étiquettes.

$ ' ' ' ' ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' ' ' ' ' % Φ pH, nq " ' n Φ p' a , nq " ' a ' n Φ ¨'a ' b A B C , n ‹ ‹ ' " ' a ' n Φ ´'b A B , n ΦpC "b ,maxepCqq
ΦpAq " ΦpA, |A| `1q

Comme précédemment, voici un exemple :

Φ ¨'1 ' 2 ' 3 ' 4 ' 5 ' 6 ' 7 ' 8 ' 9 ' 10 ' 11 ' 12 ' 13 ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ' " ' 1 ' 2 ' 3 ' 4 ' 5 ' 6 ' 7 ' 8 ' 9 ' 10 ' 11 ' 12 ' 13 ' 14

Arbres généraux plans

Dans ce dernier cas, on présente une bijection entre les diamants croissants tricolores et les arbres généraux plans et croissants.

On rappelle que la spécification de la classe combinatoire T des diamants croissants tricolores est la suivante :

T " Z `Z˝‹ S pT q ‹ S pT q ‹ S pT q ‹ T ' et que la spécification de la classe combinatoire C des arbres généraux plans et croissants est :

C " Z ˝‹ S pCq.

Dans ce cas, les deux séries sont les même et leurs premiers termes (normalisés par une factorielle) sont p1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075, . . . q connus sous le nom de A001147 dans OEIS. On sait que le terme général de ces séries est la double factorielle des nombres impaires : n! rz n sCpzq " n! rz n sT pzq " p2n ´1q!! " n ź k"1 p2n ´1q.

On obtient donc directement les deux décompositions suivantes : -C 2 " C 1 p1´Cq 2 : si l'on supprime la racine et le noeud d'étiquette 2 d'un arbre général plan et croissant, on obtient deux séquences d'arbres de Catalan croissants séparées par une troisième séquence fille du noeud d'étiquette 2 -T 2 " 1 p1´T q 3 : un diamant croissant tricolore peut être décomposé en une racine, un puits et trois séquences de diamants tricolores de trois couleurs différentes De cette décomposition on obtient simplement une bijection entre les deux types de structures. Mais encore, la gestion des étiquettes demande un peu de précaution : le noeud d'étiquette 2 est envoyé sur le puits du diamant et toutes les autres étiquettes sont décrémentées. Dans la description, ci-dessous, de la bijection Ξ, on utilise l'annotation " ´1 pour le signifier. De plus, par soucis esthétique, on fait l'amalgame entre la transformation d'une séquence et la séquence des transformations : ΞppA 1 , . . . , A n qq " pΞpA 1 q, . . . , ΞpA n qq.

$ ' ' ' ' ' ' & ' ' ' ' ' ' % Ξ p' a q " ' a Ξ ¨t " ' a ' b . . . . . . . . . ‹ ‹ ' " ' a ' |t| Ξp. . . " ´1q Ξp. . . " ´1q Ξp. . . " ´1q
Note: Nous n'avons pas présenté les preuves que les fonctions Φ, Ψ et Ξ sont des bijections car dans les trois cas les preuves sont des inductions structurelles simples.

Comportement asymptotique 1.4.1 Familles polynomiales

Dans le cas des familles de diamants ayant pour opérateur G un polynôme comme par exemple les diamants de Weierstrass ou de Jacobi, le comportement asymptotique du terme général est facilement obtenu en suivant la même méthode que [START_REF] Bergeron | Varieties of Increasing Trees[END_REF].

Diamants binaires

Dans le cas des diamants binaires que nous avons étudié G est le polynôme 1 `X2 et est donc apériodique au sens de [START_REF] Bergeron | Varieties of Increasing Trees[END_REF]. On peut donc utiliser le Lemme 2 directement.

Commençons par calculer la singularité dominante ρ B de Bpzq :

ρ B " ż 8 0 dt b 2 3 t 3 `2t `1 .
On rappelle que dans ce cas l'équation (1.2.2) nous donne :

z " ż Bpzq 0 dt b 2 3 t 3 `2t `1 .
En utilisant ces deux égalités, on obtient le développement asymptotique de B :

z ´ρB " ż 8 Bpzq dt b 2 3 t 3 `2t `1 " zÑρ B ż 8 Bpzq dt b 2 3 t 3 2 " ? 6 a Bpzq et donc Bpzq " zÑρ B 6 pz ´ρB q 2 .
Soit en utilisant le théorème de transfert standard de [START_REF] Flajolet | Singularity analysis of generating functions[END_REF] :

n!rz n sBpzq " nÑ8 6pn `1q! ρ n`2 B .
On rappelle que ce résultat peut directement obtenu à partir de la formule (1.2.10) qui est une formule close pour le terme général.

Diamants Ternaires

Dans le cas des diamants ternaires, l'asymptotique n'est pas aussi direct à calculer. La condition initiale T 1 p0q " 0 implique la 6-périodicité de T :

z Þ Ñ a T 1 p0q 2 `2G pzq est de période 3 :

a T 1 p0q 2 `2G pzq " d 2 ˆz `z4 4
" ? 2z ÿ ně0 n´1 ź k"0 ˆ1 2 ´k8 n n! pz 3 q n .
-la valuation de f est 2 ñ la période de f est donc 2 ¨p3 ´1q `2 " 6.

En utilisant la même méthode que pour les diamants binaires, on obtient :

z ´ρT " ż 8 T pzq 2dt ? 2t 4 `8t " zÑρ T ż 8 T pzq dt ? 2t 2 " ? 2 T pzq et donc T pzq " zÑρ T ? 2 pz ´ρT q .
Or ce raisonnement est le même pour les 6 singularités dominantes de T . En sommant les contributions de chacune et en utilisant le théorème de transfert, on obtient

rz n sT pzq " nÑ8 6 ? 2 ρ n`1 T .

Cas des diamants polynomiaux

Dans le cas général d'une famille de diamants définie par la spécification (1.1.1) avec G un polynôme de degré m, on obtient le résultat théorème suivant.

Théorème 3:

Soient G " ř m k"0 g k X k un polynôme et f la série génératrice de diamants polynomiaux spécifiés par :

F " Z `Z˝‹ GpFq ‹ Z ' .

(1.4.1) que l'on suppose apériodique.

Quand n tend vers l'infini on a :

f n " n! ˜a2pm `1q pm ´1q ? g m ¸2 m´1 n ´m´3 m´1 Γp 2 m´1 q ρ ´n´2 m´1 ´1 `O ´n´4 m´1 ¯¯,
pour m ě 2, où ρ est donné par le théorème 2, c'est-à-dire :

ρ " ż 8 0 dt b 1 `2 ş t 0 ř m k"0 g k k`1 v k`1 dv .
Remarquons que l'équivalent asymptotique de f n ne dépend pas des conditions initiales dans ce cas.

Remarque 2:

Dans le cas périodique, il faut multiplier cet équivalent asymptotique par le nombre de singularités présentes sur le cercle de convergence.

Démonstration. Comme dans les cas précédents, on part du théorème 2 pour obtenir :

ρ ´z " ż 8 f pzq 1 b 1 `2 ř 0ďjďm g j j`1 t j`1 dt " f pzqÑ8 ? m `1 pm ´1q ? 2g m f pzq ´m´1 2 ´gm´1 ? m `1 mg 3{2 m f pzq ´m`1 2 `¨¨¨,
quand z tend vers ρ. On peut alors inverser l'équation pour obtenir :

f pzq " ˜pm ´1q ? g m a 2pm `1q ¸´2 m´1 pρ ´zq ´2 m´1 ´1 `O ´|ρ ´z| 2 m´1 ¯¯,
quand z tend vers ρ. On utilise alors le théorème de transfert standard pour conclure.

Cas des diamants plans

Ici, on s'intéresse à la famille des diamants généraux plans : G " S . Dans ce cas, la méthode est la même mais l'analyse est plus compliquée car elle fait apparaître des fonctions dites spéciales.

Théorème 4:

Le nombre f n de diamants généraux plans de taille n vérifie, quand n tend vers l'infini :

f n " pn ´1q! ρ 1´n n ? 2 log n ˆ1 `log log n ´3 ´2γ `log 2 `2 log ρ 8 log n `O ˆplog log nq 2 plog nq 2 ˙˙.
En fait, on peut prouver un développement complet de la forme :

rz n sF
ρ ´z " zÑρ ? e expp´F 1 pzq 2 2 q F 1 pzq 8 ÿ n"0 p´1q n p2n ´1q!! F 1 pzq 2n .
Alors, en gardant le terme dominant de la somme et en utilisant la relation F 12 ´1 " ´2 logp1 ´F q (obtenu par multiplication par 2F 1 , puis intégration de F 2 " 1 1´F ) :

logpρ ´zq " zÑρ 1 ´F 1 pzq 2 2 ´logpF 1 pzqq " zÑρ logp1 ´F pzqq.
On se sert alors de cette relation comme ansatz en substituant logp1 ´F pzqq par logpρ ´zq dans (1.4.4), en prenant de plus en plus de termes de la somme. On obtient alors la série de calcul suivant pouvant être développé aussi loin que souhaité :

logp1 ´F pzqq " zÑρ logpρ ´zq ´1 2 log logp 1 1 ´F pzq q `1 2 log 2 " zÑρ logpρ ´zq ´log log 1 ρ ´z ´1 2 log 2 `1 4 log 2 `log log 1 ρ´z logpρ ´zq `O ˜ˆlog logpρ ´zq logpρ ´zq ˙2¸.
Pour conclure la preuve, on utilise le théorème de transfert standard (cf. [START_REF] Flajolet | Analytic combinatorics[END_REF]) pour dériver l'asymptotique de f n .

On remarquera que la forme de l'asymptotique est assez originale et que le terme d'erreur a une décroissance extrêmement lente. En fait, on pourrait améliorer ce développement en utilisant un développement en fonction W de Lambert à la place de la fonction erf.

Degré à la racine

On détaille ici l'analyse du degré à la racine moyen de différentes classes de diamants. Cela permet de donner un exemple d'analyse d'un paramètre typique. De plus, les résultats obtenus diffèrent de ceux obtenus pour les arbres croissants, ce qui montre bien l'originalité du comportement des diamants croissants.

Cas général

Soit F une famille de diamants croissants de spécification (1.1.1) et de série génératrice f . On s'intéresse maintenant à l'analyse asymptotique du degré moyen de la racine de tels graphes. On rappelle que le degré d'un noeud est le nombre d'arcs entrants et sortants de celui-ci.

Soit, Rpz, tq la fonction génératrice bivariée satisfaisant :

Rpz, tq " ÿ n,rě0
a n,r t r z n n! , où a n,r est le nombre de diamants de taille n dont la racine a un degré r. Cette fonction satisfait l'équation suivante, obtenue en marquant les fils de la racine par une variable t :

Rpz, tq " z `Gp0qpt ´1q z 2 2 `ż z 0 ż u 0 Gpt ¨f pvqqdvdu.
Le terme Gp0qpt ´1q z 2 2 permet de juste de marquer la chaîne d'atomes de taille 2, si il y en a (quand Gp0q ‰ 0).

Le degré moyen de la racine est donc obtenu en calculant la moyenne pondérée des a n,r , c'est-à-dire en calculant ř n r"0 r ¨an,r f n . Si l'on note R n la variable aléatoire correspondant à l'arité d'un diamant croissant de taille n, on obtient donc la formule classique ([FS09, chapitre 3]) suivante qui est juste une réécriture de la précédente en terme de séries génératrices :

ErR n s " rz n s BR Bt ˇˇt"1 rz n sf pzq .

Par la suite on notera rpzq " BR Bt ˇˇt"1 et on remarque que r est solution de l'équation différentielle : r 2 pzq " Gp0q `f pzq ¨G1 pf pzqq, avec rp0q " 0 et r 1 p0q " 0.

(1.5.1)

Du fait que r 2 ne dépend que de f et G, on obtient simplement les équivalents asymptotiques recherchés pour calculer ER n , en utilisant les résultats de la section 1.4.

Diamants tricolores

Théorème 5: Soit T la famille de diamants définies par la spécification (1.2.3), avec Gpzq " p1 ´zq ´3. Quand n tend vers 8, le degré moyen de la racine d'un diamants de T de taille n est :

ErR n s " nÑ8 3 2 ? π n `O p1q .

CHAPITRE . DIAMANTS CROISSANTS

Démonstration. On connaît la fonction génératrice de T : T pzq " 1 ´?1 ´2z. Ainsi, en utilisant l'équation (1.5.1), on obtient :

rpzq " z 2 2 `3z 2 ´3 ´3 4 logp1 ´2zq `3? 1 ´2z.
Puis on applique le théorème de transfert standard pour obtenir le résultat attendu.

Diamants généraux non-plans

Théorème 6: Soit P la famille des diamants définies par la spécification (1.2.4), avec Gpzq " e z . Quand n tend vers 8, le degré moyen de la racine d'un diamants de P de taille n est :

ErR n s " nÑ8 2 log n `O p1q .
Démonstration. On utilise le fait que G 1 " G, ainsi l'équation (1.5.1) se simplifie en r 2 pzq " 1 f pzq ¨f 2 pzq. Après une première intégration par partie et en utilisant f 1 pzq 2 " 2 exppf pzqq 1 " 2f 2 pzq ´1, on obtient r 1 pzq " f pzqf 1 pzq ´2f 1 pzq `z `2. Et donc, puisque rp0q " 0 :

rpzq " 1 2 f pzq 2 ´2f pzq `z2 2 `2z.
La fonction f pzq " ´logp1 ´sin zq a le développement asymptotique suivant :

f pzq " zÑ π 2 log ˆ8 π ˙´2 log ˆ1 ´z π{2 ˙`O ˜ˆ1 ´z π{2
˙2¸.

On en déduit celui de r :

rpzq " zÑ π 2 log ˆ8 π ˙ˆ1 2 log ˆ8 π ˙´2 ˙`2 log ˆ1 ´z π{2 ˙2 `O ˆlog ˆ1 ´z π{2
˙˙.

On utilise alors le théorème de transfert classique [START_REF] Flajolet | Analytic combinatorics[END_REF] :

n!rz n sf pzq " a n " nÑ8 2 n ˆ2 π ˙n n! n!rz n srpzq " nÑ8 4 log n n ˆ2 π ˙n n!.
De ces deux extractions, on calcule directement ErR n s.

Familles Polynomiales

Théorème 7: Soit F une famille polynomiale de diamants croissants, définies par un polynôme G de degré m (cf. équation (1.4.1)). Quand n tend vers 8, le degré moyen de la racine d'un diamants de T de taille n est :

ErR n s " nÑ8 m. . . CONCLUSION 29
Démonstration. En utilisant l'équation (1.5.1), on prouve :

r 2 pzq " zÑρ 1 `mf 2 pzq.
Le résultat s'en déduit trivialement.

Diamants plans

Théorème 8: Soit F la famille des diamants généraux plans : Gpzq " 1 1´z . Quand n tend vers 8, le degré moyen de la racine d'un diamants de T de taille n est :

ErR n s " nÑ8 n ρ ? 2 log n .
Démonstration. Dans la preuve du théorème 4, on a montré :

F pzq " zÑρ 1 ´?2ρ ˆ1 ´z ρ ˙dlog 1 1 ´z ρ .
Ici, l'équation (1.5.1) se simplifie en :

r 2 pzq " 1 `f pzq p1 ´f pzqq 2 . Donc 1 p1 ´f pzqq 2 " zÑρ 1 2ρ 2 ´1 ´z ρ ¯2 log 1 1´z ρ .
Ainsi, on en déduit :

r 2 pzq " zÑρ 1 `1 2ρ 2 ´1 ´z ρ ¯2 log 1 1´z ρ .
L'extraction du coefficient de rz n´2 sr 2 permet de conclure :

r n " nÑ8 n 2ρ 2 log n ρ ´n`2 pn ´2q!.
Informellement, ce dernier théorème suggère que le profil des diamants plans croissants est très "aplati" : ils sont très large et peu haut.

Conclusion

Dans cette section nous avons introduit le modèle de diamants croissants qui malgré sa simplicité à décrire n'est pas si simple à analyser combinatoirement.

Nous avons aussi présenté des bijections avec des objets connus dans la littérature, reliant ainsi notre étude à des travaux déjà existants : un intérêt motivant l'étude des structures croissantes. C 2 O P S -P

Introduction

Les ordres partiels Série-Parallèle sont présents dans une multitude de travaux et ont de nombreuses applications. Ils se caractérisent par leur structure inductive. La plupart des problèmes dits combinatoires sont résolus en temps polynomial et même souvent linéaire. Malgré cette apparente simplicité et leur histoire assez ancienne, l'énumération asymptotique des extensions linéaires de ces ordres n'a jamais été étudiée. C'est donc un des principaux problèmes que nous allons étudier dans ce chapitre.

Du point de vue des programmes concurrents, les ordre partiels Série-Parallèle sont des modèles réalistes. On peut les retrouver dans différents modèles de calcul parallèle, notamment le Bulk Synchronous Parallel model (BSP) introduit dans [START_REF] Valiant | A bridging model for parallel computation[END_REF]. Parmi les intérêts de ce modèle de programmation parallèle on notera :

-sa grande abstraction : le modèle de calcul BSP permet de s'abstraire de la plupart des problèmes courants de la programmation concurrente et parallèle (race condition, dead lock, live lock, etc), -sa facilité à être analysé statiquement : de par les contraintes qu'il impose, le modèle BSP permet des analyses statiques et des preuves de programmes quasi-automatiques et précises.

Bien sûr, la contrepartie est que ce modèle n'est pas aussi expressif que d'autres comme les algèbres de processus (CSP, π-calcul, etc).

Dans ce chapitre, nous présenterons nos résultats sur l'étude du comportement asymptotique du nombre de graphes Fork-Join. Pour ce faire nous aurons besoin d'introduire les produits ordonné et coloré. Enfin, nous finirons sur un développement autour de quelques propriétés fondamentales de ces opérateurs.

32

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE

État de l'art

La première apparition des ordres partiels Série-Parallèle remontent à la fin des années 70 [START_REF] Valdes | The recognition of series parallel digraphs[END_REF]. Ils sont eux-même inspirés des travaux sur les circuits de résistances électriques Série-Parallèle [START_REF] Richard | Topology of series-parallel networks[END_REF].

L'énumération des ordres partiels Série-Parallèle a été faite par R. Stanley dans [START_REF] Richard | Enumeration of posets generated by disjoint unions and ordinal sums[END_REF]. L'auteur donne les séries génératrices ordinaires et exponentielles de classes d'ordres partiels générées à partir d'un ensemble fini d'ordres et des compositions en série et parallèle. De là on peut en déduire différentes équations de récurrences sur les coefficients de ces séries ainsi que leur équivalent asymptotique, notamment pour celle des ordres partiels Série-Parallèle.

Du point de vue du dénombrement des extensions linéaires d'un ordre donné, l'article [START_REF] Möhring | Computationally tractable classes of ordered sets[END_REF] est, à notre connaissance, le premier à donner une formule inductive pour ce calcul. De cette formule on extrait (trivialement) un algorithme qui se trouve être de complexité (en nombre d'opérations arithmétiques) linéaire en la taille de l'ordre en entrée. Pour obtenir ce résultat, l'ordre est décomposé en un arbre de compositions série et parallèle dont l'existence provient directement de la définition de ces ordres.

Du point de vue de l'énumération de toutes les extensions linéaires d'ordres Série-Parallèle de taille n, il n'existe, à priori, pas de résultats antérieurs à nos travaux sur les diamants (cf. chapitre 1). On peut néanmoins, citer l'apparition de l'opérateur ordinal product dans le cadre de la théorie des espèces combinatoires de [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF], réutilisé dans [START_REF] Darrasse | Biased boltzmann samplers and generation of extended linear languages with shuffle[END_REF]. Cet opérateur, permet de contraindre l'étiquetage de structures, à la manière du produit boîte.

Ordres Série-Parallèle et Graphes Fork-Join

Pour commencer, donnons les définitions formelles des compositions série et parallèle permettant de définir la classe des ordres Série-Parallèle.

Définition 3 (Compositions série et parallèle):

Soit pP, ĺ P q et pQ, ĺ Q q deux ordres partiels disjoints, c'est-à-dire tels que P X Q " H.

-La composition parallèle pR, ĺ R q de pP, ĺ P q et pQ, ĺ Q q, notée R " P Q, est l'ordre partiel obtenu par l'union disjointe des ensembles P et Q et telle que la relation d'ordre ĺ R sur R est définie par :

@E P tP, Qu, @x, y P E, x ĺ R y ssi x ĺ E y.
-La composition série pS, ĺ S q de pP, ĺ P q et pQ, ĺ Q q, notée R " P.Q, est l'ordre partiel obtenu par l'union disjointe des ensembles P et Q et telle que la relation d'ordre ĺ S sur S est définie par :

@x, y P P Y Q, x ĺ S y ssi $ & % x P P et y P Q x, y P P et x ĺ P y x, y P Q et x ĺ Q y .
Définition 4 (Ordres partiels Série-Parallèle): La classe des ordres partiels Série-Parallèle est la plus petite classe contenant l'ordre singleton et close par compositions série et parallèle.

Comme nous l'avons précédemment fait sur les diamants, ici aussi nous ne travaillerons pas directement sur les ordres partiels mais sur les plongements combinatoires des couvertures de ces ordres, c'est-à-dire sur leur représentation graphique intransitive et planaire. De plus, principalement pour simplifier notre algorithme de génération aléatoire uniforme d'extensions linéaires, nous choisissons de travailler sur une représentation "binaire" des ordres Série-Parallèle. Pour ce faire, nous introduisons la famille des graphes Fork-Join.

D " ' `' D t `' `D D r D `D t " ' `' D t `' D D r D `D r " D t `D D r

D

Un graphe Fork-Join de D est soit un noeud isolé ' ou bien une source (ou racine) à laquelle pend un graphe de D t , ou encore une source (un noeud noir ' ou blanc ˝) avec un fils gauche appartenant à D et un fils droit appartenant à D r , tous les deux suivis (composition séries) par un graphe de D ou un noeud blanc ˝. Par la suite, on désignera ces différents sous-graphes par "le sous-graphe gauche, droit ou du dessous".

La classe D t correspond aux couvertures connectées n'ayant qu'une seule source tandis que la classe D r correspond aux couvertures connectées en général.

Théorème 9:

Les graphes Fork-Join sont en bijection avec les plongements combinatoires des couvertures d'ordres partiels Série-Parallèle.

Nous construisons la preuve de ce théorème étape par étape. Tout d'abord nous exploitons le principe "gauchisant" (left-leaning en anglais). Il est utilisé dans [START_REF] Sedgewick | Left-leaning red-black trees[END_REF] afin de donner une représentation canonique d'arbres rouges-noirs. Le principe est une simple retranscription de l'associativité à gauche de l'opérateur de composition parallèle, associé au plongement combinatoire :

P 1 P 2 ¨¨¨ P n est équivalent à p. . . pP 1 P 2 q . . . q P n .
Ce théorème permet ainsi de passer d'une représentation "n-aire" (un nombre indéfini d'ordres en parallèles) à une représentation binaire. Pour ce faire, les graphes Fork-Join sont composés

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE ' b ' c ' d ' e ' f ' i ' j ' k ' l 'b ' c ' d ' e ' f ˝' i ' j ' k ' l 'b ' e ' d ' c ' f 'i ' j ' k ' l 'b ' e ' d ' c 'f 'i ' j ' k ' l 'b ' e ' d 'c ' f 'i ' j ' k ' l ' b ' e ' d ' c ' f ' i ' j ' k ' l F
2.1 -(De gauche à droite) La couverture d'un ordre Série-Parallèle P ; son graphe Fork-Join correspondant ; l'ensemble des tris topologiques de la même classe d'équivalence et leur extension linéaire associée de noeuds noirs, correspondant aux noeuds originaux de la couverture de l'ordre, et de noeuds blancs, correspondant à des noeuds ajoutés afin de connecter et "binariser" la couverture.

Par exemple, dans la figure 2.1, sur la gauche, un ordre partiel est représenté par sa couverture et au milieu on peut voir le graphe Fork-Join correspondant. On voit bien que les noeuds blancs ont été ajoutés pour remplir la contrainte binaire.

Note: Par abus de language, nous supposerons par la suite que tous les graphes (et donc les couvertures) sont combinatoirement plongés.

Définition 6:

Soit Ψ la fonction de l'ensemble des couvertures d'ordres Série-Parallèle dans l'ensemble des graphes Fork-Join, inductivement définie par :

$ ' ' ' ' ' ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' ' ' ' ' ' % ΨpHq " ˝Ψp'q " ' Ψ ¨' . . . ' ‹ ‹ ' " ' . . . ' ΨpP.pQ Rq.Sq " ΨpP q ΨpQq ΨpRq ΨpSq , où P, Q, R et S sont des couvertures d'ordres Série-Parallèle. P et S peuvent être vides. Q et R ne sont pas vides et R vérifie pDR 1 , R 2 , R " R 1 R 2 q.
Quand l'ordre ressemble à P 1 P 2 ¨¨¨ P n , la condition sur R dans la dernière règle signifie que R " P n . Notons que la seule contrainte sur P et S est que ce sont des couvertures Série-Parallèle pouvant être vides. Ainsi, l'application de la dernière règle est non-déterministe, dans le sens où elle peut être appliquée plusieurs fois mais dans un ordre arbitraire. Ce système de règle est trivialement confluent.

Proposition 3:

Ψ est une bijection.

Esquisse de preuve. La preuve se fait par une simple induction structurelle. Les cas concernant l'ordre vide, le singleton et la chaîne sont triviaux. Dans le dernier cas, la contrainte sur l'ordre R (qu'il n'est pas une composition parallèle de sous-ordres) garantit que le graphe obtenu aura bien la bonne forme (un profil gauchisant). Ensuite il suffit de vérifier que les noeuds blancs ne peuvent se retrouver qu'en position de source ou puits.

La preuve du théorème 9 est donc un corollaire direct de cette proposition. Vu que notre étude s'intéresse aux ordres partiels à travers leur ensemble d'extensions linéaires, une propriété fondamentale des graphes Fork-Join est qu'il conserve le nombre d'extensions linéaires de l'ordre initial, si l'on oublie les noeuds blancs :

-comme nous l'avons déjà énoncé, les tris topologiques d'un plongement combinatoire de la couverture sont isomorphes aux extensions linéaires de l'ordre lui même, -dans le cas de nos graphes Fork-Join, les tris topologiques incluent les noeuds blancs, qui ne font pas partie de l'ordre initialement. On va donc les "oublier" en considérant des classes d'équivalences d'ordres topologiques sur ces graphes.

Définition 7:

Soit un ordre Série-Parallèle P et S " ΨpP q son graphe Fork-Join associé. On définit la fonction ρ, de l'ensemble des tris topologiques de S dans l'ensemble des extensions linéaires de P , qui appliquée à un tri topologique supprime tous ses noeuds blancs.

Définition 8:

Soit P un ordre Série-Parallèle et S " ΨpP q son graphe Fork-Join associé. On dit que deux tris topologiques s 1 et s 2 de S sont équivalents si et seulement si ρps 1 q " ρps 2 q. Soit e une extension linéaire de P , on peut donc définir la classe d'équivalence de e des tris topologiques de S : ts P S | ρpsq " eu .

Par exemple, dans la figure 2.1 sur le côté droit, nous avons représenté trois tris topologiques équivalents de l'extension linéaire b ĺ e ĺ d ĺ c ĺ f ĺ i ĺ j ĺ k ĺ l.

On remarquera que les extensions linéaires n'ont pas toutes le même nombre de tris équivalents. Par exemple, l'extension linéaire c ĺ f ĺ b ĺ d ĺ e ĺ i ĺ j ĺ k ĺ l n'a qu'un seul tri équivalent. Cela a pour conséquence qu'un tirage aléatoire et uniforme d'un tri topologique du graphe Fork-Join S " ΨpP q ne donnera pas une extension linéaire uniforme de P (après application de ρ).

Définition 9:

Soit P un ordre Série-Parallèle et S " ΨpP q son graphe Fork-Join associé. Soit e une extension linéaire de P , on appelle représentant de e le tri topologique de la classe d'équivalence engendrée par e tel que

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE

-tous les noeuds blancs apparaissent le plus tôt possible dans le tri, -si deux noeuds blancs sont incomparables, celui le plus à gauche (dans S) apparaît en premier.

On a donc maintenant moyen de lier les extensions linéaires de P et les tris topologiques de ΨpP q. Par exemple, dans la figure 2.1, sur le côté droit, des trois tris topologiques présentés, c'est le troisième qui est le représentant de l'extension linéaire de droite.

Proposition 4:

Soit P un ordre Série-Parallèle et S " ΨpP q son graphe Fork-Join associé. Une extension linéaire de P tirée aléatoirement selon la loi uniforme est obtenue par tirage aléatoire et uniforme d'un représentant dans S puis application de la fonction ρ.

Pour conclure cette section, nous discutons rapidement de la complexité de construire un graphe Fork-Join à partir d'un ordre Série-Parallèle.

Proposition 5:

Le graphe Fork-Join correspondant à un ordre Série-Parallèle sur n éléments est construit en Opnq opérations élémentaires (ajouts ou suppressions de noeuds ou d'arcs dans un graphe dirigé).

Le nombre de noeuds noirs du graphe Fork-Join ainsi construit est n et celui de noeuds blancs est au plus 2pn ´1q.

Démonstration. La complexité annoncé se prouve simplement par induction, en utilisant la bijection Ψ. Pour le nombre de noeuds blancs, le pire cas est l'ordre contenant n noeuds incomparables.

Graphes Fork-Join croissants et produit ordonné

Comme dans le cas des diamants, la spécification des graphes Fork-Join est en fait très similaire à une spécification d'arbres. On cherche donc maintenant un moyen de spécifier les étiquetages croissants des noeuds noirs des graphes Fork-Join. Dans ce cas, on voit bien que l'opérateur boîte n'est pas suffisant : il ne permet de contraindre l'étiquette que d'un seul atome alors que nous voudrions ajouter une contrainte plus globale entre toutes les étiquettes des sous-graphes du dessus (gauche et droit) et celle du sous-graphe du dessous. Pour cela nous introduisons un nouvel opérateur à la méthode symbolique : le produit ordonné.

Définition du produit ordonné

Dans la littérature un opérateur, analogue au produit ordonné, apparaît dans le domaine de la combinatoire algébrique et plus particulièrement des espèces (cf. [BLL98, Chapitre 5]). Dans ce contexte, il est appelé produit ordinal (ordinal product en anglais). Le nom de produit ordonné est introduit dans l'article [START_REF] Darrasse | Biased boltzmann samplers and generation of extended linear languages with shuffle[END_REF], où il est utilisé en tant que outil technique, dans le contexte de la génération à la Boltzmann de langages quasi-réguliers. La fonction f |α| est une fonction de réétiquetage, décalant de `|α| les étiquettes de son argument.

On étend alors le produit ordonné de structures étiquetées aux classes combinatoires étiquetées :

A ‹ B " ď αPA, βPB α ‹ β.
En fait, le produit ordonné A ‹ B contient les objets du produit étiqueté A ‹ B tels que toutes les étiquettes de la composante de A sont plus petites que celles de la composante de B. Dans le cadre de la méthode symbolique, on s'intéresse à la "traduction" de cet opérateur en terme d'opérations sur les séries génératrices exponentielles. Pour ce faire, on rappelle les définitions des transformées (combinatoires) de Laplace que nous noterons L c et Borel 1 que nous noterons B c . D'un point de vue combinatoire, elles définissent un pont entre fonction génératrice ordinaire et exponentielle. Soit, formellement :

L c ˜ÿ ně0 a n z n n! ¸" ÿ ně0 a n z n ; B c ˜ÿ ně0 a n z n ¸" ÿ ně0 a n z n n! .
D'un point de vue analytique, elles correspondent aux transformations intégrales suivantes :

L c pf q " ż 8 0 expp´tqf pztqdt; B c pf q " 1 2iπ ż c`i8 c´i8 exppztq t f ˆ1 t ˙dt,
où c est une constante réelle plus grande que la partie réelle de n'importe quelle singularité de f p1{tq{t.

De façon analogue à la transformée de Laplace usuelle, le produit de transformée de Laplace combinatoire peut être exprimé comme un produit de convolution :

z ¨Lc pf q ¨Lc pgq " L c ˆż z 0 f ptqgpz ´tqdt ˙.

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE

où de façon équivalente :

L c pf q ¨Lc pgq " L c ˆż z 0 f ptqg 1 pz ´tqdt `gp0qf pzq ˙.
On notera f ˚g la convolution combinatoire : f ˚g " ş z 0 f ptqg 1 pz ´tqdt `gp0qf pzq.

Proposition 6:

Soit A et B deux classes combinatoires étiquetées. La série génératrice exponentielle Cpzq associée à la classe C " A ‹ B est donnée par les trois formulations équivalentes suivantes :

Cpzq " B c pL c Apzq ¨Lc Bpzqq " ÿ ně0 ř n k"0 a k b n´k n! z n " Apzq ˚Bpzq.
Maintenant le produit ordonné défini dans le cadre de la méthode symbolique, explorons quelques unes de ses propriétés.

Graphes Fork-Join croissants

Maintenant ces nouveaux outils présentés, nous pouvons nous recentrer sur le sujet principal de ce chapitre : les graphes Fork-Join croissants.

Pour simplifier les choses, nous ne considérerons qu'une sous-classe de graphes Fork-Join : les graphes Fork-Join monochromes. Dans cette sous-classe, les noeuds sont tous noirs. Cette approche permet de travailler avec une série génératrice monovariée, au lieu de bivariée. On définit donc les graphes Fork-Join monochromes et croissants par la spécification suivante :

F " Z `Z˝‹ F `Z˝‹ pF 2 ‹ Fq.
(2.3.1)

On notera que la spécification non-étiquetée de ces graphes est similaire à une spécification d'arbres unaire-ternaires :

T " Z `Z ˆT `Z ˆT 3 . (2.3.2)
Dans cette section, nous présenterons un premier résultat sur l'asymptotique du nombre de graphes Fork-Join monochromes de taille n. Pour le moment, nous sommes capable d'obtenir ce résultat seulement grâce à des méthodes calculatoires. Il serait préférable d'utiliser des méthodes analytiques, généralisables à d'autre cas d'utilisation du produit ordonné. Pour le moment cela reste hors de notre de portée vu la forme complexe de l'équation vérifiée par la série génératrice.

Graphes Fork-Join monochromes Avant d'entrer dans le vif du sujet à propos des graphes Fork-Join croissants et monochromes, nous donnons un résultat classique concernant l'énumération des graphes Fork-Join monochromes non-étiquetés.

Théorème 10: Soit T la série génératrice des graphes Fork-Join monochromes définis par la spécification (2.3.2). Alors, on a :

rz n sT pzq " nÑ8 1 2 c 1 3 `1 2 2{3 τ ´n ? πn 3 , avec τ " ´1 `3 ¨2´2 3 ¯´1
le rayon de convergence de T .

La preuve de ce théorème est standard. Elle repose sur l'analyse de singularités de fonctions algébriques, théorie détaillée dans [START_REF] Flajolet | Analytic combinatorics[END_REF].

De la spécification (2.3.1) on déduit, grâce à la méthode symbolique, une équation différentielle et intégrale dont une solution est la fonction génératrice F des graphes Fork-Join croissants et monochromes :

F 1 pzq " 1 `F pzq `ż z 0 F 1 pz ´tq ¨F 2 ptqdt.
(2.3.3) D'un point de vue analytique, nous n'avons pas encore réussi à caractériser cette fonction génératrice : quel est le type de sa singularité ? est-elle algébrique ou holonome ? etc. Pour le moment, la seule information que nous avons est donnée par le lemme suivant. Néanmoins, malgré cette difficulté, nous sommes capables de calculer un équivalent asymptotique du nombre de graphes Fork-Join monochromes et croissants, de taille n.

Théorème 11:

Le nombre f n de graphes Fork-Join monochromes de taille n vérifie, asymptotiquement :

f n " 6n n! ρ ´n´2
où ρ est le rayon de convergence de F Démonstration. En partant de l'équation différentielle (2.3.3) vérifiée par F , on en déduit l'équation de récurrence vérifiée par le terme général pf n q ně0 de F :

f n " f n´1 `n´2 ÿ k"2 f n´1´k k´1 ÿ i"1 ˆk i ˙fi f k´i . (2.3.4)
On définit la suite pc n q ně0 définie par : @n, c n " fn n! . De cette définition et de la relation de récurrence sur les f n , on en déduit la relation de récurrence suivante, pour les c n :

c n " 1 n c n´1 `1 n n´2 ÿ k"2 c n´1´k k´1 ÿ i"1 c i c k´i `n´1 k ˘.
(2.3.5)

Pour faciliter les prochaines manipulations on réécrit cette équation ainsi :

c n " 1 n c n´1 `1 n ÿ i`j`k"n´1 i,j,kě1 c i c j c k `n´1 i`j ˘. (2.3.6)
Par la suite, on exploitera le fait que i et j sont symétriques et l'égalité `n´1

i`j ˘" `n´1 n´1´k ˘.
Pour prouver l'équivalent asymptotique annoncé, on va procéder par encadrement. Et pour prouver cet encadrement on utilisera une preuve par induction. Or nous sommes confrontés à deux problèmes dans ce raisonnement par induction :

-il ne fonctionne qu'à partir d'un certain rang, -nous n'avons pas d'expression close pour ρ. Dans la suite, nous montrons donc le principe général de la preuve qui peut être "affinée" au sens de :

@ ą 0, Dn 0 , @n ą n 0 , 6n n!pρ ´ q ´n´2 ď f n ď 6n n!pρ ` q ´n´2
Dans notre cas, nous considérerons n 0 " 2 et ρ P r 3 2 , 3s (numériquement on peut calculer ρ " 2.31198067 . . .). On veut donc prouver, pour n plus grand ou égal à 3 :

6n 3 ´n´2 ď c n ď 6n ˆ3 2 ˙´n´2 .
On va démontrer cette inégalité par récurrence. On commence donc par montrer qu'elle est vérifiée pour au moins un entier n plus grand ou égal à 3. On obtient le graphique suivant pour les termes de 3 à 100 (en échelle loglog) :

La preuve étant initialisée pour un certain entier n, passons à la preuve de l'hypothèse de récurrence. On ne fera le détail que pour l'inégalité de droite, celle de gauche étant totalement symétrique.

Pour ce faire, on réécrit l'équation (2.3.6) en remplaçant c 0 , c 1 et c 2 par leurs valeurs respectives 0, 1 et 1 2 et en tenant compte des symétries entre i et j :

c n " 1 n c n´1 `1 n « c n´5 4 `n´1 4 ˘p1q c n´4 `n´1 3 ˘`n´6 ÿ j"3 c j c n´3´j `n´1 j`2 ˘`p2q c n´4 `n´1 n´3 ˘`c n´5 2 `n´1 n´3 ˘`c n´3 `n´1 2 ˘`2 n´5 ÿ j"3 c j c n´2´j `n´1 j`1 ˘`p3q c n´4 `n´1 n´2 ˘`2 c n´3 `n´1 n´2 ˘`ÿ i`j`k"n´1 i,j,ką2 c i c j c k `n´1 n´1´k ˘`Op1q ¨1tnď7u `p4q 1 2 `n´1 n´3 ˘n´6 ÿ j"3 c j c n´3´j `p5q 1 `n´1 n´2 ˘n´5 ÿ j"3 c j c n´2´j ff p6q
Par hypothèse de récurrence forte, on a

@k, k ď n ´1 ñ c k ď 6k ˆ3 2 ˙´k´2
En injectant cette hypothèse dans la formule précédente, on obtient une majoration de c n . Alors, on observe que les différents termes de la somme (entre crochets) ont les ordres de grandeurs suivants 2 :

-Opn ´3q pour le terme de la ligne p1q -Opn ´2q pour le terme de la ligne p2q -Opn ´1q pour le terme de la ligne p3q -Op1q pour le terme de la ligne p4q (les termes contenus dans le Op1q ne sont présents que pour des valeurs de n entre 3 et 7) -Opnq pour le terme de la ligne p5q -Opn 2 q pour le terme de la ligne p6q Une fois tous ces termes multipliés par le facteur 1 n devant le crochet on a donc que seuls les termes des deux dernières lignes comptent : les autres sont de l'ordre de O `1 n ˘.

On somme donc les termes non négligeables (les deux dernières lignes et le terme correspondant 2. On rappelle l'identité ř n k"0 k ¨pn ´kq " 1 6 pn 3 ´nq.

42

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE à c n´1 ) et on obtient, en posant rpnq " 6 n 3 ´n´2 :

rpn ´1q n `1 2n `n´1 n´3 ˘n´6 ÿ j"3 rpjq ¨rpn ´3 ´jq `1 n `n´1 n´2 ˘n´5 ÿ j"3 rpjq ¨rpn ´2 ´jq " 3 ´n´2 6 `n2 ´6 n ´25 n ´1 `9 `n2 ´9 n ´10 pn ´1qpn ´2q ´18 n
`756 pn ´1qn `1296 pn ´1qpn ´2qn `18

En pratiquant une simple analyse de fonction, on montre que cette dernière expression est toujours inférieure à 6 n `3 2 ˘´n´2 ´3 et donc on en conclut, par induction, que c n ď 6 n `3 2 ˘´n´2 . En fait, on peut voir que les valeurs choisies pour borner ρ peuvent être aussi proches de ρ que l'on veut, du moment que l'on initialise la preuve en prenant un n 0 assez grand. Il faut alors découper la somme en morceaux contenant les termes pc n q tnďn 0 u . En le faisant on observerait le même genre de découpage avec un terme dominant de la forme 1

np n´1 n´2 q ř n´2n 0 ´1 j"n 0 `1 c j c n´n 0 ´j qui serait encore équivalent à 6 n pρ ˘ q ´n´2 .
De ce théorème, on obtient une réponse à propos de l'explosion combinatoire dans le cas des programmes Série-Parallèle : comme pour les ordres arborescents (cf. [START_REF] Bodini | A Quantitative Study of Pure Parallel Processes[END_REF]), on peut calculer l'asymptotique de la moyenne du nombre d'exécutions des programmes Série-Parallèle.

Corollaire 1:

Le nombre moyen d'exécutions des programmes Série-Parallèle de taille n quand n tend vers l'infini est équivalent à :

12 ? π ρ 2 b 3 ´1 `2´2 3 n 5 2 n! ˆτ ρ ˙n .
En remplaçant par des valeurs numériques : p4.054230 . . .q ¨p0.1496703 . . .q n n 5 2 n!. Il est intéressant de constater que la "dualité" entre produit ordonné et produit coloré, au niveau analytique (échange des rôles entre transformée de Laplace et transformée de Borel) s'interprète aussi à un niveau combinatoire. Dans [START_REF] Darrasse | Biased boltzmann samplers and generation of extended linear languages with shuffle[END_REF], le produit ordonné est utilisé comme analogue étiqueté du produit non-étiqueté pour spécifier l'opération de concaténation de langages quasi-réguliers. Ici, le produit coloré peut au contraire être vu comme un analogue non-étiqueté du produit étiqueté pour exprimer le mélange (shuffle) de langages.

Graphes Fork-Joins croissants de profondeur fixée et produit coloré

Une étude plus détaillée de ces interactions entre produits ainsi que la construction d'opérateurs itérés à base de produit coloré sont des questions ouvertes à étudier lors de futurs travaux.

Proposition 8:

Soit A une classe combinatoire non-étiquetée. La série génératrice ordinaire C associée à la classe A e S Z est similaire à la classique transformée binomiale [START_REF] Knuth | The art of computer programming[END_REF] de A.

Cpzq "

ÿ n n ÿ k"0 ˆn k ˙ak " 1 1 ´z A ˆz 1 ´z ˙.
Comme dans le cas du produit ordonné, on peut énoncer plusieurs théorèmes de fermetures pour le produit coloré. La preuve est simple et repose sur la décomposition en éléments simples des fractions rationnelles et la formule suivante L c p 1 1´a¨z q " e a¨z .

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE

Graphes Fork-Join de profondeur parallèle fixée

La profondeur parallèle est un paramètre inductif des graphes Fork-Join. Du point de vue des programmes concurrents, c'est le nombre de maximal de fils d'exécution pouvant s'exécuter au même moment. Avec un vocabulaire de théorie des ordres, c'est le logarithme en base 2 de la largeur de l'ordre ou la longueur de la plus longue antichaîne (la largeur d'un ordre Fork-Join monochromes étant une puissance de 2). Une autre définition est donnée ci-dessous, en utilisant une spécification combinatoire.

Définition 12:

On note N la classe combinatoire des graphes Fork-Join croissants de profondeur parallèle au plus . La suite N est définie inductivement par le système suivant :

N 0 " S ě1 Z, N " Z `Z ˝‹ N `Z ˝‹ ppN ´1 ‹ N ´1q ‹ N q .
Il est évident qu'un graphes Fork-Join de N a donc au plus 2 fils d'exécutions en parallèle.

En utilisant la méthode symbolique on obtient :

N 0 pzq " z 1
´z , N 1 pzq " 1 `N pzq `Bc rL c pN ´1pzqq ˆLc pN ´1pzqqs.

Soit, après une application de la transformée de Laplace et un peu de réécriture :

L c pN 0 pzqq " z 1 ´z , L c pN pzqq " z 1 ´z ´z L c pN ´1pzqq e L c pN ´1pzqq .
En utilisant la proposition 10 et un raisonnement par récurrence, on obtient que N est rationnel et donc holonome. De plus, on peut calculer les premiers termes de cette suite de série. Par récurrence on peut prouver que les degrés des polynômes au numérateur et au dénominateur sont égaux et régis par la récurrence suivante :

d 1 " 3; d " pd ´1 `1qpd ´1 `2q 2 .
Les premiers termes sont 3, 10, 66, 2278, . . . . En conséquence, il est difficile d'obtenir des résultats quantitatifs pour les classes après N 4 , mais on peut simplement obtenir "totalement" la combinatoire des classes N ď4 .

. . PRODUITS ORDONNÉ ET COLORÉ PROPRIÉTÉS FONDAMENTALES ET EXEMPLES 45

Produits ordonné et coloré : propriétés fondamentales et exemples

Les opérateurs de produits ordonné et coloré que nous avons développés pour les graphes Fork-Join sont en fait également intéressant pour d'autres types de spécifications. Dans cette section, nous établissons des propriétés fondamentales sur le produit ordonné dont nous n'avons pas eue besoin pour les graphes Fork-Join mais qui sont intéressantes d'un point de vue plus général. Nous donnons également des exemples d'utilisation de ces produits.

Quelques propriétés du produit ordonné Proposition 11:

Le produit étiqueté est associatif et "commutatif", dans le sens où la convolution associée l'est et on peut trivialement associer un objet de A ‹ B à un de B ‹ A.

De plus, il se distribue par rapport à l'union disjointe (ou addition sur les séries).

Proposition 12:

Soient A et B deux classes combinatoires étiquetées :

pApzq ˚Bpzqq 1 " Apzq ˚B1 pzq `A1 pzqBp0q

" A 1 pzq ˚Bpzq `B1 pzqAp0q.

On peut donner une interprétation combinatoire de ce résultat en s'inspirant de la théorie des espèces [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF]. On interprète l'opérateur de différentiation sur les séries comme celui correspondant à la suppression d'un atome de plus petite (première identité) ou plus grande (deuxième identité) étiquette. Par exemple, pour la première identité, la série pApzq ˚Bpzqq 1 correspond au produit ordonné de A et B dans lequel on a supprimé les atomes de plus grande étiquette à chaque élément. Étant donné que ces atomes appartiennent nécessairement aux objets de B (sauf dans le cas où B contient des objets de taille 0), cela est équivalent à supprimer tous les atomes de plus grande étiquette de B, puis de faire le produit ordonné avec A.

Avant de d'énoncer quelques propositions sur la fermeture de certaines classes de séries génératrices par produit ordonné, on rappelle la définition des séries holonomes (ou D-finies).

Définition 13:

Une série génératrice F pzq est dite holonome (ou D-finie) si elle est solution d'une équation différentielle dont les coefficients sont des polynômes (où de manière équivalente, des quotients de polynômes) en z : q 0 pzqF pzq `q1 pzqF p1q pzq `¨¨¨`q r pzqF prq pzq " 0, pour de quelconques polynômes q s (avec q r différent de 0), avec F piq pzq " Démonstration. La preuve repose sur l'équivalence entre séries holonomes et suites P-récurrentes. Il est simple de montrer que l'ensemble des suites P-récurrentes est clos par transformées de Laplace et Borel et donc par produit ordonné. Il s'en suit directement le même résultat sur les séries.

d i dz i F pzq.
Une autre classe de séries qu'il est commun de rencontrer en combinatoire est la classe des séries ou fonctions rationnelles.

Définition 14:

Soient P et Q deux polynômes, avec Q ‰ 0, alors F " P {Q est une fonction rationnelle.

Proposition 14: L'ensemble des fonctions rationnelles n'est pas clos par convolution combinatoire Démonstration. Soient Apzq " z et Bpzq " 1{p1 ´zq, un calcul simple donne Apzq ˚Bpzq " ´logp1 ´zq qui n'est pas rationnelle.

On se base maintenant sur le produit ordonné pour construire les opérateurs de produits itérés S , C et S .

Opérateurs de produits itérés

Commençons par définir l'exponentiation ordonnée d'une classe combinatoire étiquetée :

A ‹ k " A ‹ . . . ‹ A k fois
. On prendra la convention A ‹ 0 " E " t u. Donc, un objet de A ‹ k est un k-uplet où les atomes de chaque composante sont étiquetés par tous les entiers d'un intervalle de Nzt0u, tous ces intervalles sont disjoints deux à deux et leur union est un intervalle d'entier commençant à 1. De plus, par définition du produit ordonné, on a que pour tout k-uplet tα 1 , . . . , α k u de A ‹ k et tout couple d'entier i et j tel que i ă j, les étiquettes de l'objet α i sont plus petites que celles de l'objet α j .

Cette propriété nous permet d'interpréter les k-uplets de A ‹ k comme des représentations canoniques des ensembles de k objets de A étiquetés par des intervalles disjoints d'entiers. On utilise donc ces k-uplets pour construire des ensembles ordonnés. La preuve de cette proposition est une conséquence directe de la définition du produit ordonné et de la linéarité des transformées de Laplace et Borel.

On continue en définissant la séquence ordonnée. Dans les cas étiquetés et non-étiquetés, l'opérateur S peut être vu comme la linéarisation des opérateurs S et P S . Ici, on prend le même point de vue.

Définition 16:

La séquence ordonnée S ‹ pAq d'une classe combinatoire étiquetée A ne contenant pas d'objets de taille nulle est défini par :

S ‹ pAq " ď kě0 ď σPS k tσpα α αq | @α α α P A ‹ k u,
où S k désigne l'ensemble des permutations de taille k.

Proposition 16:

La série génératrice exponentielle S associée à S ‹ pAq vérifie :

S ‹ pApzqq " ÿ kě0 k! ¨Apzq ‹ k " B c pL c r 1 1 ´u spL c pApzqqqq.
C ‹ pAq " ď kě0 ď σPS k zshift k tσpα α αq | @α α α P A ‹ k u,
où S k zshift k est l'ensemble des permutations de taille k quotienté par la fonction shift k piq " imodk.

Proposition 17:

La série génératrice exponentielle C associée à C ‹ pAq vérifie :

C ‹ pApzqq " ÿ kě1 pk ´1q! ¨Apzq ‹ k " B c ˜Lc pApzqq ¨ÿ kě0 k! L c pApzqq k " Apzq ˚S ‹ pApzqq.

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE

Plusieurs exemples d'utilisation de ces opérateurs seront présentés dans la section 2.5.4.

Théorèmes de transferts

Dans le cadre de la combinatoire analytique, la question naturelle suivant l'introduction d'un nouvel opérateur dans la méthode symbolique concerne les propriétés analytiques de celui-ci. À la manière de [START_REF] Flajolet | Singularity analysis of generating functions[END_REF], on introduit un nouveau théorème de transfert pour le produit ordonné et un pour l'ensemble ordonné. Un théorème de transfert permet de faire le lien entre le comportement d'une série génératrice à l'approche de sa singularité et le comportement asymptotique du terme général de cette série : il transfère les connaissances du monde analytique au monde combinatoire.

Le premier théorème que nous présentons concerne le produit ordonné et est analogue au théorème de transfert de [START_REF] Bender | An asymptotic expansion for the coefficients of some formal power series[END_REF] dans le contexte des séries génératrices à croissance rapide.

Théorème 12:

Soient A et B deux séries génératrices exponentielles. On note a (resp. b) la valuation de A (resp. B). Si il existe un entier r tel que ř n´r k"r A k B n´k " OpA n´r `Bn´r q alors rz n sApzq ˚Bpzq " Pour tout ą 0, il existe un entier n 0 tel que pour tout entier n plus grand que n 0 , on a :

1 ´ ρ ď A n nA n´1 ď 1 ` ρ et 1 ´ ρ ď B n nB n´1 ď 1 ` ρ .
Ainsi, on note R " maxtn 0 , ru puis l'on décompose le terme C n en fonction des valuations de A et B :

C n " n´b ÿ k"a A k B n´k " A a B n´a `An´b B b `n´b´1 ÿ k"a`1 A k B n´k " A a B n´a `An´b B b `˜R´1 ÿ k"a`1 A k B n´k `n´b´1 ÿ k"n´R`1 A k B n´k `n´R ÿ k"R A k B n´k ¸.
On constate alors que le premier terme de la première somme est négligeable devant B n´a :

B n´pR´1q B n´a ¨R´1 ÿ k"a`1 A k B n´k B n´pR´1q " B n´pR´1q B n´a ¨R´1 ÿ k"a`1 A k B n´k B n´pk`1q B n´pk`1q B n´pk`2q ¨¨¨B n´pR´2q B n´pR´1q ď B n´pR´1q B n´a ¨R´1 ÿ k"a`1
A k ˆpn ´pa `1qp1 ` q ρ ˙R´1´k .

.

. PRODUITS ORDONNÉ ET COLORÉ PROPRIÉTÉS FONDAMENTALES ET EXEMPLES 49

Donc, pour n suffisamment grand, il existe une constante γ telle que

B n´pR´1q B n´a ¨R´1 ÿ k"a`1 A k B n´k B n´pR´1q ď B n´pR´1q B n´a ¨γ ˆpn ´pa `1qp1 ` q ρ ˙R´a´2 ď B n´pR´1q B n´pR´2q B n´pR´2q B n´pR´3q ¨¨¨B n´pa`1q
B n´a ¨γ ˆpn ´pa `1qp1 ` q ρ ˙R´a´2 ď γ ˆpn ´pa `1qqp1 ` q pn ´pR ´2qqp1 ´ q ˙R´a´2 ¨ρ pn ´pR ´2qqp1 ´ q .

On en déduit :

lim nÑ8 B n´pR´1q B n´a ¨R´1 ÿ k"a`1 A k B n´k B n´pR´1q " 0.
De la même façon, on prouve :

lim nÑ8 A n´pR´1q A n´b ¨n´b´1 ÿ k"n´R`1 A k B n´k A n´pR´1q " 0.
Par hypothèse, la dernière somme satisfait ř n´R k"R A k B n´k " OpA n´R `Bn´R q, et donc le théorème est prouvé dans ce cas. On peut étendre ce théorème au cas des ensembles ordonnés.

Théorème 13:

Soient A une classe combinatoire étiquetée sans élément de taille nulle et S la série génératrice exponentielle de S ‹ pAq. On pose Lpzq " L c pApzqq et on note ρ son rayon de convergence. Alors, le comportement asymptotique de rz n sSpzq quand n tend vers l'infini est 1. rz n sSpzq " nÑ8 rz n sApzq, si ρ " 0 et An A n´1 " Ω pn α q, où α est une constante strictement positive.

rz n sSpzq "

Démonstration.

1. Dans ce cas, on procède par induction. On définit S k " 1 `A ˚Sk´1 (et S 1 " 1 `A), qui est la série génératrice de l'ensemble ordonné contenant au plus k objets de A. Ainsi, on a rz n sS 1 " rz n sA. On pose donc comme hypothèse d'induction : il existe un entier k tel que rz n sS k " rz n sA. Maintenant, prouvons que rz n sS k`1 " nÑ8 rz n sA. Par définition S k`1 " 1 `A ˚Sk , donc rz n sS k`1 " rz n sA ˚Sk . Puisque An A n´1 " Ω pn α q, on peut utiliser le théorème 12 et on obtient rz n sS k`1 " nÑ8 A a rz n´a sS k `rz n sA où CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE a ą 0 est la valuation de A. De l'hypothèse d'induction, on déduit que rz n sS k`1 " nÑ8 A a rz n´a sA `rz n sA " nÑ8 rz n sA, ce qui conclut la preuve pour ce cas.

2. Le second cas est prouvé par application directe du théorème des asymptotiques des suites super-critiques [START_REF] Flajolet | General combinatorial schemas : Gaussian limit distributions and exponential tails[END_REF].

Exemples

On conclut cette section en revisitant quelques classes combinatoires classiques pouvant être spécifiées à l'aide des opérateurs ordonnés.

Arbres binaires de recherche

Soit B la classe combinatoire étiquetée des arbres binaires de recherche ayant pour clé l'ensemble des entiers compris entre 1 et la taille de l'arbre. Un arbre binaire de recherche est soit une feuille contenant 1, soit un noeud interne d'étiquette i père de deux sous-arbres, tel que toutes les étiquettes du sous-arbre gauche (resp. droit) sont plus petites (resp. grandes) que i.

En utilisant le produit ordonné on peut maintenant donner une spécification de cette classe :

B " E `pB ‹ Zq ‹ B.

Cette spécification se traduit en équation fonctionnelle

Bpzq " 1 `pBpzq ˚zq ˚Bpzq.

Par définition du produit ordonné, et après application de la transformée de Laplace combinatoire, on obtient L c pBpzqq " 1 `Lc pBpzqq ˆz ˆLc pBpzqq.

On y reconnaît l'équation classique de la série génératrice des arbres binaires. On peut donc en déduire directement le nombre d'arbres binaires de recherche de taille n.

3. G est fortement apériodique si il n'existe pas de fonction analytique h telle que Gpzq " hpz d q où d ě 2

. Par exemple, l'ensemble tt1, 2, 3u, t6, 5u, t7, 8, 9u, t4uu représente la composition 3 `1 2 `3 de 9.

On peut alors travailler sur la série génératrice exponentielle donnée par

B c ˆ1 1 ´Lc pe z ´1q ˙" B c ˆ1 ´z 1 ´2z ˙.
Notons que même si l'extraction du n-ième coefficient de cette série est simple, une application directe de notre théorème 13 donne aussi le même résultat (deuxième cas du théorème) :

rz n s B c ˆ1 ´z 1 ´2z ˙" 2 n´1 .

Permutations intervalles généralisées

Il est bien connu qu'une permutation peut-être décomposée de manière unique en un ensemble de cycles. De cette correspondance, on tire la spécification suivante, pour la classe étiquetée des permutations :

S pC pZqq.

On s'intéresse maintenant à une sous-classe de permutations introduite dans [KM12] et nommées permutations intervalles généralisées (PIG). Une PIG est une permutation dont les cycles une fois triés sont des intervalles d'entiers. Par exemple, la permutation p231489567q est une PIG car elle admet la décomposition

tp ÝÑ 123qp Ý Ñ 4 qp Ý ÝÝ Ñ 58697qu (où c " Ý ÝÝÝÝÝÝÝ Ñ a 0 . . . a n´1 est tel que cpa i q " a i`1 mod n ).
On peut donc naturellement spécifier ces permutations à l'aide de l'ensemble ordonné : S ‹ pC pZqq.

CHAPITRE . ORDRES PARTIELS SÉRIE-PARALLÈLE

Comme précédemment, on obtient simplement la série génératrice exponentielle de cette classe :

B c p 1 1 ´Lc plogp 1 1´z qq q.
On remarque alors que L c plog 1 1´z q " ř ně0 n! z n a un rayon de convergence nul et donc que la série a un rayon de convergence nul. Mais, on peut utiliser le premier cas du théorème 13 pour directement obtenir rz n s B c p 1 1 ´Lc plogp 1 1´z qq q " pn ´1q!.

Ensemble ordonné de diamants croissants binaires

Pour illustrer un autre cas d'application du théorème de transfert 13 et en relation avec la concurrence, nous présentons le modèle des ensembles ordonnés de diamants croissants binaires. Le modèle de diamants binaires D que nous considérons est spécifié ainsi :

D " Z `Z ˆpE `D `D2 q ˆZ Donc,
B " Z `Z˝‹ pE `B `B2 q ‹ Z ' " S ‹ pBq ´S ‹ pS ě1 pZqq `S pZq
On obtient alors l'équation fonctionnelle suivante pour :

" B c ˆ1 1 ´Lc pBpzqq ˙´z ¨e2z `ez
De cette équation on peut alors tirer le résultat suivant par utilisation de notre théorème de transfert 13.

¯.

Le second résultat est obtenu en calculant le quotient du nombre d'ensembles ordonnés de diamants croissants par celui du nombre de séquences de diamants non-étiquetés. D peut être vue comme la série génératrice ordinaire d'une famille simplement généré d'arbres et dont l'analyse asymptotique est bien connue [START_REF] Flajolet | Analytic combinatorics[END_REF]. Pour calculer le nombre asymptotique de séquences de diamants de taille n, on applique le théorème asymptotiques des suites super-critiques [START_REF] Flajolet | General combinatorial schemas : Gaussian limit distributions and exponential tails[END_REF].

Nombres de Bell

Les nombres de Bell, notés B n , sont connus pour compter le nombre de partitions d'un ensemble de n éléments. Ils vérifient l'équation de récurrence B n " ř n´1 k"0 `n´1 k ˘Bk (avec B 0 " 1). Une spécification classique de la classe étiquetée B des partitions d'ensembles est B " S pS ě1 Zq. Une partition d'un ensemble est un ensemble d'ensembles tel que la somme des tailles des ensembles internes est égale à la taille de l'ensemble partitionné. De cette spécification, en appliquant la méthode symbolique, on obtient une formule close pour la série génératrice exponentielle de B :

Bpzq "

ÿ ně0 B n z n n! " e e z ´1.
Ici, on se propose de revisiter cette classe dans un contexte non-étiqueté, en utilisant le produit coloré. Dans ce contexte, une partition d'un ensemble de n éléments en k parts est isomorphe à un coloriage à k couleurs de ces n éléments. Donc, on peut voir cette partition comme un premier ensemble de taille p (un coloriage de p éléments avec la première couleur) qu'on ajoute à l'ensemble d'une partition des n ´p éléments restants (un coloriage à k ´1 couleurs du reste des éléments).

On peut donc traduire cette décomposition, en utilisant la méthode symbolique et le produit coloré :

B " E `Z ˆpS pZq e Bq .

Le produit coloré sert à choisir les atomes appartenant à la première part de la partition (ceux colorier avec la première couleur) et ceux appartenant à la sous-partition.

On obtient donc une équation fonctionnelle vérifiée par la série génératrice ordinaire des nombres de Bell :

Bpzq " 1 `z ¨Lc ˆBc pBpzqq ¨Bc ˆ1 1 ´z ˙˙.

En appliquant la transformation de Borel, et en utilisant une des identités données dans l'annexe B, on obtient :

B c pBpzqq 1 " B c pBpzqq e z .
On résout simplement cette équation différentielle et on obtient le résultat attendu :

B c pBpzqq " e e z ´1.
C 3 G Ce chapitre traite de la génération aléatoire uniforme des différentes structures précédemment présentées dans ce manuscrit : les diamants et les étiquetages croissants de graphes Fork-Join.

Dans le cas des diamants, la génération aléatoire uniforme permet d'observer empiriquement les résultats obtenus théoriquement. On peut aussi l'utiliser pour générer des programmes aléatoires, dans le cadre du test de compilateurs ou d'outils d'analyse statique [START_REF] Yang | Finding and understanding bugs in c compilers[END_REF]. De plus, le cadre théorique de la génération de Boltzmann [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF], dans lequel nous nous plaçons, permet une grande généricité et modularité. Donc, ces algorithmes peuvent être utilisés plus généralement pour la génération aléatoire de structures croissantes définies à l'aide du produit boîte.

Comme pour les diamants, la génération aléatoire d'extensions linéaires a pour motivations ses vastes applications dans différents domaines : dans la vérification (model-checking statistique, cf. [START_REF] Grosu | Monte carlo model checking[END_REF]) et le test aléatoire (cf. [START_REF] Sen | Effective random testing of concurrent programs[END_REF]) de programmes concurrents, les problèmes de classement [SI09] ou d'inférence bayésienne [START_REF] Ellis | Learning causal bayesian network structures from experimental data[END_REF] et en bio-informatique [START_REF] Miklós | Sampling and counting genome rearrangement scenarios[END_REF]. Ici, nous présenterons un algorithme de génération aléatoire uniforme d'extensions linéaires pour les ordres partiels Série-Parallèle, ou dit autrement, un algorithme de génération d'étiquetages croissants de graphes Fork-Join.

Dans la suite de ce chapitre, nous présenterons les algorithmes de Boltzmann pour la génération aléatoire de diamants croissants ainsi que quelques expérimentations. Puis nous ferons de même pour l'algorithme de génération aléatoire d'étiquetages croissants de graphes Fork-Join.

56

CHAPITRE . GÉNÉRATION ALÉATOIRE

Génération aléatoire uniforme de Boltzmann

Introduction

Dans la suite de cette section, nous rappellerons les grandes lignes de la méthode de Boltzmann introduite par [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]. Puis en nous basant sur les travaux de O. Bodini [START_REF] Bodini | Autour de la génération aléatoire sous modèle de Boltzmann[END_REF] et [START_REF] Bodini | Boltzmann samplers for firstorder differential specifications[END_REF] (avec O. Roussel et M.soria), nous proposerons de nouveaux générateurs de Boltzmann pour les structures étiquetées croissantes.

La génération de Boltzmann de structures étiquetées génère uniquement les structures sans leurs étiquettes. Les diamants étant des graphes Fork-Join, on pourra donc naturellement utiliser l'algorithme de génération d'étiquetage présenté dans la section 3.3.

Distribution de Boltzmann pour les classes étiquetées

La méthode de Boltzmann consiste à construire automatiquement un générateur aléatoire d'une classe de structures F. Pour garantir une complexité linéaire du générateur, la génération se fait en taille approchée : dans un intervalle rn ´ , n ` s où n est la taille visée.

La loi de probabilité des structure générées est une loi dite de Boltzmann de paramètre x, c'est-à-dire, pour un objet γ de F :

P x pγq " x |γ| |γ|! F pxq avec F pxq " ÿ ně0 f n z n n! .
Remarquons que chaque objet de F, de taille n, a la même probabilité d'être tiré. La génération aléatoire de Boltzmann est donc uniforme pour les objets de même taille :

P x pN " nq " ÿ γPF ^|γ|"n P x pγq " f n x n n! F pxq .
Il est alors direct de calculer l'espérance de N :

E x pN q " ÿ ně0 nP x pN " nq " x F pxq ÿ ně0 ¨fn ¨xn´1 pn ´1q! " x F 1 pxq F pxq .
De cette équation on peut calculer x de façon à obtenir l'espérance souhaitée pour la taille des objets à générer. Dans le cas où l'on veut générer de très grosses structures, on peut aussi choisir de prendre un point x proche de la singularité dominante ρ de F pour obtenir une espérance infinie et donc générer de grandes structures.

Générateurs de Boltzmann usuels

Maintenant que nous avons décrit la sortie d'un générateur de Boltzmann, décrivons sa construction. Comme nous l'avons dit, un des intérêts principaux de la méthode de Boltzmann est de construire automatiquement un algorithme de génération aléatoire uniforme pour des objets d'une classe F à partir de sa spécification. On note ΓrFspxq le générateur de Boltzmann de paramètre x, d'une classe étiquetée F.

Commençons par le cas simple où F " A `B : On veut construire un générateur tel qu'un objet γ de F,soit générer avec probabilité

Générateurs de Boltzmann pour les équations différentielles du premier ordre

On rappelle que l'un de nos objectifs initiaux est d'obtenir un générateur de Boltzmann pour les diamants croissants du chapitre 1. Or les séries génératrices de ces objets sont solutions d'équations différentielles du deuxième ordre. Mais, le principe des générateurs de Boltzmann pour les équations du deuxième ordre est juste une adaptation de celui pour les équations du premier ordre. C'est pour cela que nous détaillons les précédents travaux de O. Bodini et al..

Cas général

On s'intéresse ici à la construction de générateurs de Boltzmann pour les classes spécifiées à l'aide d'un produit boîte. Plus exactement, on considère les classes dont la série génératrice F est solution d'une équation différentielle du premier ordre L'idée principale qui permet de construire de tels générateurs de Boltzmann est de modifier le paramètre x au fur et à mesure de la génération aléatoire. Cette modification se fait par multiplication de x par une variable aléatoire U distribuée selon une loi de densité δ F

x puq "

xF 1 puxq F pxq ´F p0q " xφpF puxq, uxq F pxq ´F p0q
L'algorithme 3 donne le pseudo-code nécessaire à la construction d'un générateur de Boltzmann pour F à partir de F 1 " φpF, Zq. Dans ce cas, on assimilera l'opérateur de dérivation à la suppression de l'atome de plus grande étiquette.

On constate que l'algorithme 3 construit bien un objet de F : soit il retourne un objet de taille nulle, soit il retourne un objet généré de la classe φpF, Zq c'est-à-dire un objet de F 1 , autrement dit, un objet de F privé de son atome de plus grande étiquette.

Algorithme 3 Générateur de Boltzmann de F à partir de F 1 " φpF, Zq et de paramètre x function ΓrFs(x) if B ´F p0q F pxq ¯then return un objet de F de taille 0, choisi uniformément else Tirer U dans r0, 1s selon la densité δ F

x Générer un objet γ 1 à partir de ΓrφpF, ZqspU xq return l'objet pZ, γ 1 q où Z a la plus grande étiquette Pour comprendre pourquoi cet objet est généré selon la bonne distribution (celle de Boltzmann), il suffit de calculer la probabilité de tirer un objet γ de taille n `1.

PpΓrFspxq " γq " ˆ1 ´F p0q F pxq ˙ż 1 0 PpΓrφpF, Zqspuxq " γ 1 q ¨δF x puq du " F pxq ´F p0q F pxq ż 1 0 puxq n n! φpF puxq, uxq xφpF puxq, uxq F pxq F p0q du " x n`1 pn `1q! F pxq
Pour une preuve plus complète de la correction de l'algorithme 3, on peut se référer à [START_REF] Bodini | Boltzmann samplers for firstorder differential specifications[END_REF]. Pour compléter la description de cet algorithme il reste à décrire comment tirer une variable aléatoire de densité δ F

x et comment évaluer F . Pour l'évaluation, on peut montrer que le choix, simple, d'utiliser un développement (borné) de Taylor en 0 de F est suffisamment précis pour garantir l'efficacité de l'algorithme. Mais de fait, cela introduit un biais sur la distribution des tailles des objets qui sont donc généralement plus petits.

Pour le tirage de U , on peut utiliser un algorithme tel que l'algorithme du Ziggourat (cf. [START_REF] Marsaglia | The ziggurat method for generating random variables[END_REF]). On peut aussi raisonner simplement sur la fonction de répartition de δ F

x . On a P x pU ď tq "

ż t 0 xF 1 puxq F pxq ´F p0q
du " F ptxq ´F p0q F pxq ´F p0q .

On peut donc tirer une variable aléatoire V uniforme sur r0, 1s et calculer numériquement pour quelle valeur de t on a V " P x pU ď tq : on doit résoudre, en t, l'équation suivante

F ptxq " V F pxq `p1 ´V qF p0q. (3.1.1)
Étant donné la croissance de δ F x (Lemme 2.2 de [START_REF] Bodini | Boltzmann samplers for firstorder differential specifications[END_REF]), on peut utiliser une recherche dichotomique ou une itération numérique, par exemple une itération de Newton numérique, pour résoudre cette équation (3.1.1).

Cas autonome

Dans le cas où l'équation différentielle considérée est autonome, c'est-à-dire quand F 1 " φpF q, l'algorithme peut être largement simplifié. Dans ce cas, la valeur de U x n'est pas nécessaire, seule la valeur de F pU xq l'est. On peut donc simuler la variable de densité δ F

x directement en utilisant la relation (3.1.1).

Dans ce cas, l'algorithme n'a donc pas besoin de simuler autre chose que des variables aléatoires de loi uniforme pour calculer F puxq. On peut notamment, en posant τ " F pxq, voir l'algorithme non plus comme un générateur de Boltzmann de paramètre x mais comme un générateur de Boltzmann de paramètre τ . Ces modifications sont détaillées dans l'algorithme 4.

Algorithme 4 Générateur de Boltzmann de F à partir de F 1 " φpFq function ΓrFs(τ ) if B ´F p0q τ ¯then return un objet de F de taille 0, choisi uniformément else Tirer U de loi uniforme sur r0, 1s τ Ð U τ `p1 ´U qF p0q Générer un objet γ 1 à partir de ΓrφpFqspτ q return l'objet pZ, γ 1 q où Z a la plus grande étiquette

Générateurs de Boltzmann pour les équations différentielles du second ordre

Nous pouvons maintenant présenter nos générateurs de Boltzmann pour les équations différentielles du second ordre. Comme pour les équations différentielles du premier ordre, le cas autonome permet des simplifications.

Cas général

Notre problème consiste en la construction d'un générateur de Boltzmann pour des objets dont la série génératrice vérifie à une équation différentielle du second ordre F 2 pzq " φpF pzq, zq.

Une première idée est d'utiliser deux fois l'algorithme 3 : un première fois pour générer un γ 1 à partir de Γ x rF 2 s, puis une seconde fois pour générer un γ 2 à partir de ce générateur de Γ x rF 1 s.

Si l'on utilise ce principe, on constate qu'on a alors besoin du produit de deux variables U et V distribuées selon deux distributions δ F et δ F 1 . Une simplification est donc possible en ne générant qu'une seule variable S " U V . Pour trouver la distribution de S, il suffit de résoudre en δF

x l'équation suivante, où n désigne la taille de γ

PpΓrFspxq " γq "

x n n! F pxq " p1 ´F p0q `xF 1 p0q F pxq q ż 1 0 P `ΓrφpF 2 , Zqspsxq " γ 2 ˘δ F x psqds " F pxq ´F p0q ´xF 1 p0q F pxq ż 1 0 psxq n´2 pn ´2q! F 2 psxq δF x psqds " F pxq ´F p0q ´xF 1 p0q F pxq x n´2 pn ´2q! ż 1 0 s n´2 F 2 psxq δF x psqds
On trouve alors la solution δF x psq "

x 2 p1 ´sqF 2 psxq F pxq ´F p0q ´xF 1 p0q .

On en déduit donc l'algorithme 5, un générateur de Boltzmann ΓrFs à partir de ΓrF 2 s. On génère un objet γ 2 P F 2 auquel on ajoute un atome de plus petite étiquette et un de plus grande.

Algorithme 5 Générateur de Boltzmann de F à partir de F 2 " φpF, Zq

function ΓrFs(x) W " U pr0, 1sq Ź U désigne la loi uniforme if W ă ´F p0q
F pxq ¯then return un objet de F de taille 0, choisi uniformément else if W ă ´F p0q`xF 1 p0q F pxq ¯then return un objet de F de taille 1, choisi uniformément else Tirer S dans r0, 1s selon la densité δF

x Générer un objet γ 2 à partir de ΓrφpF, ZqspSxq return l'objet pZ 1 , γ 2 , Z 2 q où Z 1 a la plus grande étiquette et Z 2 la plus petite

Cas autonome

Comme dans le cas des équations différentielles de premier ordre, le cas autonome F 2 pzq " φpF pzqq induit des simplifications pour l'algorithme.

La première idée est de réutiliser le principe d'inversion de la fonction de répartition :

PpS ď tq " ż t 0
x 2 p1 ´sqF 2 psxq F pxq ´F p0q ´xF 1 p0q ds.

Or, comme nous le constatons, il semble difficile de calculer cette intégrale dans le cas général. Une autre possibilité est d'appliquer deux fois l'algorithme 4. Pour ce faire, on essaye de se ramener à une équation du type F 1 " ΨpF q.

En multipliant F 2 pzq " φpF pzqq par 2F 1 puis en intégrant les deux côtés, on obtient

F 1 pzq " a 2ΦpF pzqq ´2ΦpF p0qq `F 1 p0q (3.1.2)
où Φptq " ş t 0 φpuqdu. Maintenant, il ne reste plus qu'à inverser cette équation pour obtenir le bon paramètre pour l'appel du générateur ΓrφpFqs. On rappelle que l'algorithme 4 fournit un générateur ΓrF s à partir de ΓrF 1 s. On cherche maintenant à obtenir un générateur de ΓrF 2 s à partir d'un générateur ΓrF 1 s.

Toujours d'après le raisonnement sur l'algorithme 4, pour obtenir le générateur ΓrF 2 s on multiplie le paramètre y par une variable aléatoire que la relation suivante nous abstient de simuler : F 1 ptyq " V F 1 pyq `p1 ´V qF 1 p0q avec V une variable aléatoire de loi uniforme sur r0, 1s. Or, le paramètre y est lui même de la forme F pxq car c'est celui d'un générateur ΓrF 1 spτ q obtenu à l'aide de l'algorithme 4. On cherche maintenant une relation sur F permettant de mettre à jour y.

Après inversion de l'équation (3.1.2), on obtient F pzq " Φ ´1p 1 2 pF 12 pzq `2ΦpF p0qq ´F 1 p0q 2 qq " ΨpF 1 pzqq où Φ ´1 désigne l'inverse compositionnel de Φ. En utilisant la relation (3.1.1), on obtient ainsi une nouvelle relation F ptτ q " Ψ `V Ψ ´1pF pτ qq `p1 ´V qF 1 p0q ˘.

On peut alors utiliser cette relation et la précédente pour mettre à jour le paramètre de Boltzmann dans l'algorithme 6.

Complexité

Comme nous l'avons vu dans les sections précédentes les objets pour lesquels nous utilisons les générateurs de Boltzmann présentés ont tous une singularité dominante de type pôle. Dans ces cas-là, le résultat de [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF] nous garantit une complexité linéaire en la taille des objets générés pour la génération en taille approchée.

Expérimentations : les diamants généraux

Pour terminer ce chapitre, nous présentons différentes expériences basées sur la génération aléatoire de diamants plans croissants ou non. Nous considérerons deux modèles : le modèle de diamants généraux croissants utilisant l'algorithme présenté dans la section précédente, et le modèle de diamants généraux non étiquetés N " Z `Z ˆS pN q ˆZ pour lesquels on tire aléatoirement et uniformément un étiquetage croissant.

Algorithme 6 Générateur de Boltzmann de F à partir de F 2 " φpFq avec τ " F pxq function ΓrFs(τ ) if B ´F p0q τ ¯then return un objet de F de taille 0, choisi uniformément else U " U pr0, 1sq σ Ð U τ `p1 ´U qF p0q Ź mise à jour pour ΓrF 1 s if B ´F 1 p0q Ψ ´1pσq ¯then return un objet de F de taille 1, choisi uniformément else V " U pr0, 1sq τ Ð ΨpV Ψ ´1pσq `p1 ´V qF 1 p0qq Ź mise à jour pour ΓrF 2 s Générer un objet γ 2 à partir de ΓrφpF, Zqspτ q return l'objet pZ 1 , γ 2 , Z 2 q où Z 1 a la plus grande étiquette et Z 2 la plus petite Ensuite, en utilisant la bijection entre diamants plans croissants et graphes cactus croissants, nous mènerons une étude empirique permettant de donner quelques intuitions sur les paramètres moyens de ces différents types de structures.

Nous avons choisi d'exploiter la bijection avec les graphes cactus car ceux-ci semblent les moins étudiés dans la littérature contrairement aux deux autres familles d'arbres croissants, étudiées dans de nombreux articles (par exemple [START_REF] Bergeron | Varieties of Increasing Trees[END_REF]).

Algorithmes de génération aléatoire uniforme

Diamants plans croissants

Ce modèle de diamants correspond à la spécification 1.3.1 page 17 :

F " Z `Z˝‹ S pFq ‹ Z ' .
Un générateur de Boltzmann pour ces diamants plans croissants est aisément obtenu en combinant l'algorithme 6 avec un générateur de Boltzmann pour l'opérateur S . Dans ce cas, Ψ et Ψ ´1 ont des formes très simples : On remarque que pour implémenter ce générateur pour S pFq il est nécessaire d'évaluer F en différents points. Dans notre cas F est définie implicitement comme étant l'inverse compositionnel de la fonction d'erreur erf 1. Cette définition n'étant pas des plus simples à exploiter pour obtenir des évaluations numériques de F nous avons fait le choix d'approximer F par son développement de Taylor en 0 à l'ordre 300. Ce choix empirique, a été suffisamment précis pour nous permettre de générer des structures de plusieurs milliers de noeuds comme celle présentée figure 3.1. Enfin, nous avons de choisi comme paramètre de Boltzmann initial, une approximation fine de ρ (nécessitant les 64 bits d'un flottant machine), calculée à l'aide de la formule 1.4.3 page 26 : ρ » 0.6556795424187984.

Ψpxq " 1 ´2 x 2 `1 , Ψ ´1pxq " c 2 1 ´x ´1.
L'étiquetage croissant des diamants est tiré uniformément parmi tous les étiquetages croissants possibles à l'aide de l'algorithme 9, présenté dans la section suivante.

Diamants plans ordinaires

Ce modèle de diamant non étiqueté correspond à la spécification 1.3.1 page 17 :

F " Z `Z ˆS pFq ˆZ.
Cette spécification est très classique au sens où on peut la voir comme une spécification d'arbres généraux dont les noeuds internes seraient comptés deux fois et les feuilles une seule fois. Un rapide calcul nous donne une formule pour F :

F pzq " z `1 ´?1 ´2z ´3z 2 2 .
De cette formule, on trouve directement que la singularité dominante provient de l'annulation du radical, et donc on calcule la plus petite racine réelle positive de 1 ´2z ´3z 2 qui est 1 3 . On remarque que

F p 1 3 q " 1 3 ``1 3 ˘2 1 ´2 3 " 2 3 .
On peut donc facilement construire le générateur de Boltzmann singulier (algorithme 8) à partir de l'algorithme 7.

De même que pour le cas croissant, on utilisera l'algorithme du chapitre suivant pour la génération de l'étiquetage croissant.

Comparaison des deux modèles de diamants

La première comparaison que l'on peut faire entre ces deux modèles est la comparaison des performances de leur algorithme de génération de Boltzmann associé.

Comme on le constate sur la figure 3.2, le temps pour générer des diamants ordinaires (non étiquetés) est très rapide : de l'ordre de quelques centièmes de secondes pour des diamants de

1. erfpxq " 1 ? π ş x ´x e ´t2 dt.
Algorithme 8 Générateur de Boltzmann de diamants plans non étiquetés function ΓrFs if B p 1 2 q then return un atome ' else k Ð G p 2 3 q return p', ΓrFspq, . . . , ΓrFspq, 'q avec k appels à ΓrFs Maintenant cette étude faite, on se concentre sur les différences de comportement structurel de ces deux modèles de diamants plans. Par la suite, nous considérerons les trois paramètres suivants :

-la hauteur : c'est la longueur du plus long chemin de la source au puits d'un diamant, -l'arité cumulée : c'est la somme des degrés sortants de chaque noeud du diamant, -la profondeur de branchement cumulée : pour chaque noeud, on définit la profondeur de branchement comme étant son nombre d'ancêtres "branchants" (ancêtre de la séquence dans la spécification). Dans le cas non étiqueté, les lois de probabilité limites pour la hauteur (cf. [START_REF] Govert De Bruijn | The average height of planted plane trees[END_REF]) et l'arité cumulée (obtenue simplement depuis la série génératrice) sont bien connues, on en trouve différentes analyses dans la littérature. La profondeur de branchement cumulée peut Pour le cas croissant, on s'attend à ce que la hauteur soit assez petite (devant celle des diamants ordinaires) et donc la profondeur de branchement aussi. Pour l'arité cumulée, on s'attend à ce qu'elle soit plus élevée. On suppose aussi que les diamants croissants sont plus aplatis et contiennent moins de chaînes d'atomes, au vu de l'arité moyenne de la racine (cf. section 1.5.5).

Pour confirmer cette intuition, nous avons généré uniformément des diamants croissants et ordinaires, de taille 10 à 900 et calculer ces différentes statistiques sur chacun. Les résultats sont récapitulés dans la figure 3.3.

Comme prévu, nos intuitions sont confirmées par ces expériences. On exploite maintenant la bijection de la section 1.3.1 pour faire quelque expérimentations sur le modèle de graphes cactus.

Comparaison entre les modèles de cactus

La bijection entre diamants plans et cactus est facilement implémentée. Dans la figure 3.4, on peut observer un exemple de cactus obtenu en appliquant la bijection au diamant figure 3.1. Les arêtes rouges sont celles appartenant à des cycles et le noeud bleu correspond au noeud d'étiquette 0.

Après plusieurs simulations, on décide de regarder deux paramètres qui semblent d'intérêt sur les cactus : le nombre de cycles et le diamètre du graphe (longueur du plus long chemin de la source à un puits).

Pour ces deux paramètres, on regarde les histogrammes normalisés (on a retranché la moyenne et divisé par la racine carré de la variance) des paramètres de diamants face à ceux des cactus. La figure 3.5 présente ces histogrammes pour des diamants de taille 100. C'est la taille la plus élevée pour laquelle nous avons réussi à générer un grand nombre de diamants (environ 50000) en un temps raisonnable (quelques heures).

Même si ces histogrammes n'ont qu'une valeur empirique, ils nous permettent d'émettre quelques hypothèses qu'il serait intéressant de vérifier théoriquement dans de futurs travaux : -dans les deux modèles (croissant et ordinaire), les distributions de la profondeur de branchement cumulée dans les diamants et du diamètre dans les cactus semblent fortement corrélées, -il en est de même pour les lois de l'arité cumulée des diamants et du nombre de cycles des cactus On observe aussi une corrélation entre hauteur et diamètre, mais vu la différence de comportement entre le modèle croissant et le modèle ordinaire, il semblerait que le phénomène soit plus probablement une expression de la corrélation "évidente" entre hauteur et profondeur de branchement dans les diamants.

Extensions linéaires d'ordres Série-Parallèle

Introduction

Nous présentons maintenant un algorithme de génération aléatoire uniforme d'extensions linéaires d'ordres Série-Parallèle. Un point a souligné est le caractère optimal de cet algorithme en terme de nombre de bits aléatoires utilisés.

Dans la suite de cette section, nous présentons des travaux connexes à cette problématique, puis nous décrirons l'algorithme et présenterons quelques expérimentations. L'algorithme utilise un certain nombre de primitives stochastiques que nous détaillerons dans une sous-section dédiée, du fait de leur généricité.

Travaux connexes

Il y a peu de travaux existants à propos de la génération aléatoire d'extensions linéaires. La plupart utilise des techniques probabilistes du type Monte-Carlo [BD99] (approximation) ou Couplage arrière (exacte) [START_REF] Huber | Fast perfect sampling from linear extensions[END_REF] (Coupling from the past en anglais). Tous ces travaux se basent une chaîne de Markov dites de Karzanov et Kachiyan [START_REF] Karzanov | On the conductance of order markov chains[END_REF]. Un intérêt différent du nôtre est commun à ces différents travaux : la mise au point de schéma d'approximation randomisé entièrement en temps polynomiale [START_REF] Jerrum | Random generation of combinatorial structures from a uniform distribution[END_REF] (Fully Polynomial Randomized Approximation Scheme (FPRAS) dans la littérature) pour le calcul de volume de corps convexes. On reviendra sur ce dernier point dans le chapitre suivant.

Dans un autre registre, on peut aussi citer les travaux consistants à énumérer toutes les extensions linéaires ([DLDMDB06], [START_REF] Pruesse | Generating linear extensions fast[END_REF]) . On peut utiliser ces algorithmes pour générer toutes les extensions linéaires puis en choisir une au hasard.

Enfin, il y a le précédent travail de mes co-auteurs qui traitent de ce problème dans le cas des tree posets [START_REF] Bodini | A Quantitative Study of Pure Parallel Processes[END_REF].

Algorithmes

La structure de données sur laquelle travaille l'algorithme est celle des graphes Fork-Join bicolores présentés dans le chapitre précédent (définition 5). On rappelle que seuls les noeuds noirs font partie de l'extension linéaire à générer, contrairement aux noeuds blancs qui son "muets".

CHAPITRE . GÉNÉRATION ALÉATOIRE

Cet algorithme peut-être décrit de deux manières totalement équivalentes qui ont chacune leur intérêt. Pour mieux comprendre la suite, l'intuition est de voir les graphes Fork-Join comme des arbres où le graphe du dessous est recollé à la racine comme fils le plus à droite (pour le distinguer). En fait, ce recollage définit une bijection entre graphes Fork-Join et une certaines familles d'arbres unaires-ternaires.

Par ce prisme, on peut définir l'algorithme par un schéma algorithmique bottom-up ou top-down. L'approche bottom-up a l'intérêt d'être simple à décrire et facilite le raisonnement car elle reprend la décomposition inductive des graphes Fork-Join. Tandis que l'approche topdown semble un peu plus complexe. Son intérêt réside dans le fait que l'on peut plus simplement l'implémenter en place (sans utiliser de copie). En théorie, les complexités spatiales et temporelles pour les deux algorithmes sont les mêmes. En pratique, la version en place est plus efficace, notamment grâce aux mécanismes de cache.

Algorithme 9 Verison bottom-up de la génération aléatoire uniforme d'extensions linéaires. function R L E -BU(P ) if P " ˝then return r s else if P " ' x then return rxs

else if P " ' x . T then return cons(x, R L E -BU(Q)) else if P " ˝. pL Rq . T then h :" S (R L E -BU(L), R L E -BU(R)) t :" R L E -BU(T ) if ˝" ' x then return concat(cons(x, h), t) else return concat(h, t)
La version bottom-up de l'algorithme est l'algorithme 9. On l'illustre en prenant comme exemple l'ordre de la figure 2.1 page 34. Premièrement, l'algorithme est récursivement appliqué aux deux sous-ordres en parallèle : celui contenant les d'étiquettes tb, d, eu et celui contenant les étiquettes tc, f u. Pour ce dernier, la seule extension linéaire possible est de prendre la première étiquette c puis f résultant en l'extension linéaire pc, f q. Pour la partie gauche l'étiquette b précède le mélange uniforme (S ) des extensions linéaires "atomiques" pdq et peq. L'algorithme de mélange sera présenté en détail par la suite, mais ici il consiste simplement à choisir entre les extensions linéaires pd, eq ou pe, dq avec une probabilité 1 2 pour les deux. En supposant le choix de pe, dq, on obtient alors l'extension linéaire pb, e, dq. Notons que rien n'est ajouté à la fin car le puits de ce sous-ordre est blanc. La prochaine étape consiste à mélanger pc, f q et pb, e, dq uniformément, un résultat possible étant pc, b, e, d, f q avec probabilité 1 10 . Alors, on concatène cette extension avec une extension du sous-ordre du bas. Par exemple, pc, b, e, d, f, i, j, k, lq est une extension linéaire possible et donc uns sortie possible de l'algorithme.

Ici, le caractère bottom-up de l'algorithme est caractérisé par le fait que les mélanges sont faits dans les ordres les plus profonds (les feuilles de l'arbre unaire-ternaire correspondant), puis propagés étape par étape à l'ordre entier.

La version top-down de l'algorithme est l'algorithme 10. La principale différence avec la version bottom-up est que l'algorithme génère les positions des étiquettes dans un tableau plutôt que directement les étiquettes. L'avantage est que la plupart des opérations peuvent donc être Dans notre exemple, initialement, positions est la liste r1, 2, 3, 4, 5, 6, 7, 8, 9s et la table d'association rankings est vide. Dans la première étape, la source blanche est simplement passée et les deux ensembles de positions possibles sont calculés : upP ositions prend les étiquettes de la partie haute de l'ordre, c-à-d r1, 2, 3, 4, 5s et botP ositions prends le reste : r6, 7, 8, 9s. L'algorithme réalise alors une partition uniforme (en deux parts de bonnes tailles) des positions 1 à 5, c-à-d en les ensembles l " t2, 3, 4u pour tb, d, eu et r " t1, 5u pour tc, f u. Les détails sur ce partitionnement sont donnés par la suite. Les rangs des étiquettes de chaque sous-ordre sont calculés récursivement. Encore une fois, on peut obtenir l'extension linéaire pc, b, e, d, f, i, j, k, lq, avec la même probabilité que dans l'algorithme précédent.

Les deux algorithmes 11 sont clairement duaux. Dans la version bottom-up, l'aléa vient du mélange (algorithme S ) qui est un dual du partitionnement (algorithme S ) au sens d'un co-produit. S prend deux listes (ou permutations) et les mélange en une seule, tandis que S prend une liste et la divise en deux. L'uniformité, et donc la correction, des deux versions de l'algorithme vient de l'uniformité des algorithmes S et S . Par exemple, il y a `5 2 ˘" 10 mélanges possibles entre les ensembles ta, b, cu et td, eu. De manière équivalente, il y a 10 partitionnements possibles de Ensuite, on définit la série génératrice bivariée C où la variable y compte le nombre d'écritures mémoires de l'algorithme et z la taille du graphe Fork-Join en entrée :

$ & % Cpz, yq " zy `zyCpz, yq `pzy `1qCpzy, yqC r pzy, yqpCpz, yq `1q C l pz, yq " zy `zy Cpz, yq `zyCpzy, yqC r pzy, yqpCpz, yq `1q C r pz, yq " C l pz, yq `Cpzy, yqC r pzy, yqCpz, yq On calcule sa dérivée par rapport à la variable y que l'on évalue en y " 1 :

ˆB By

Cpz, yq

˙|y"1 " z `1 `11z ´2z 2 ´p2z ´3q ? 11 ´6z `z2 4p11
´6z `z2 q .

Encore une fois, on applique le théorème de transfert de [START_REF] Flajolet | Singularity analysis of generating functions[END_REF] et on en déduit le résultat.

Coeur stochastique

Les deux versions de l'algorithme précédemment présenté dépendent du même coeur stochastique dont le point d'entrée est l'algorithme R C . Nous présentons ici l'ensemble des algorithmes permettant de répondre de manière optimale au problème de génération aléatoire d'une combinaison. Mais commençons par discuter de cette notion d'optimalité.

Mesure de complexité

Dans le contexte de la génération aléatoire et pour parler de complexité, on considère généralement un modèle de calcul tel que les machines de Turing probabiliste plutôt que le modèle plus standard de machine déterministe (et ses équivalents comme le modèle Random Access Machine). Une machine de Turing probabiliste est une machine de Turing déterministe possédant, en plus, un bandeau (infini) de bits aléatoires. En conséquence nous nous intéressons à cette ressource que sont les bits aléatoires.

La sortie d'un algorithme de génération aléatoire est un objet produit selon une certaine distribution. Il faut donc être capable d'estimer "la taille" d'une distribution de probabilités en nombre de bits aléatoires. Pour cela, on se base donc sur la théorie de l'information de Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF] et plus particulièrement sur la notion d'entropie. L'entropie est la quantité de bits minimale nécessaire à encoder une information parmi un ensemble d'informations possibles. Notre objectif, dans le reste de ce chapitre, est donc de définir un algorithme entropique : un algorithme qui utilise un nombre minimal de bits aléatoires.

Définition 18 (Algorithme entropique): Soit A un algorithme de génération aléatoire d'objets appartenant à un ensemble fini S, selon une mesure de probabilité µ. On dit de A qu'il est entropique si le nombre moyen de bits aléatoires n e qu'il utilise pour générer un objet e P S est proportionnel à l'entropie de µ, au sens de l'entropie de [START_REF] Shannon | A mathematical theory of communication[END_REF] : DK ą 0, @e P S, n e ď K ¨ÿ xPS ´µpxq log 2 pµpxqq.

Par la suite, on appellera constante d'entropie une constante K vérifiant une telle inégalité.

Algorithmes

Une manière naïve de générer des combinaisons de p éléments parmi p `q consiste à insérer successivement chacun des p éléments parmi les q initiaux. Dans ce cas l'algorithme utilise p entiers aléatoires de loi uniformes. Chacun de ces tirages coûtent Oplogpp `qqq bits aléatoires 2, ce qui est bien loin de l'entropie des combinaisons de p parmi p `q éléments, notamment quand p et q sont proches.

De cet algorithme naïf, on déduit qu'il faut limiter au plus l'utilisation d'entiers aléatoires de loi uniformes. L'idée clé est donc d'utiliser une loi beaucoup moins coûteuse à simuler : la loi de Bernoulli. C'est ce que propose l'algorithme 12. L'algorithme tire aléatoirement, et selon la loi uniforme, une liste l de booléens de taille p `q telle que p booléens soient de valeur True et q de valeur False.

Algorithme 12 Algorithme de génération aléatoire uniforme de combinaisons function R C (p, q) l :" r s 7True is the number of True in l 7False is the number of False in l rndBits :" a stream of random booleans produced with k-B ´p p`q īf p ą logpqq 2 ^q ą logppq 2 then while 7True ă" p ^7False ă" q do if pop(rndBits) then l :" conspTrue, lq else l :" conspFalse, lq remaining :" popplq else if p ă q then l :" a list of q times False remaining :" True else l :" a list of p times True remaining :" False for i :" 7True `7False ´1 to p `q ´1 do j :" uniformRandomIntr0 . . . is insert remaining at position j in l return l Malgré ce pseudo-code assez complexe, le principe de l'algorithme est assez simple. On distingue deux étapes. La première étape consiste en une boucle while qui remplit la liste l en tirant des booléens suivant une loi de Bernouilli de paramètre p p`q jusqu'à ce que l'une des deux valeurs de booléens soit suffisamment représentée (p True ou q False). La deuxième étape est 2. Pour tirer un entier aléatoire selon la loi uniforme d'un intervalle donné, il est optimal de tirer chacun des bits de la représentation binaire de cet entier, quitte à pratiquer un rejet de temps en temps. (cf. [START_REF] Knuth | The Art of Computer Programming[END_REF]) une boucle for qui insère, comme dans l'algorithme naïf, les booléens manquant. Le reste des tests n'est là que pour des raisons techniques que nous justifierons plus tard.

Pour terminer cette description, donnons un exemple d'exécution de l'algorithme avec les entrées p " 6 et q " 2. Dans la première étape, la liste l est remplie de True et de False avec les probabilités respectives p p`q et q p`q jusqu'à ce que l'une des deux valeurs soit assez représentée. Par exemple, on pourrait obtenir la liste l " F :: T :: T :: F :: T :: F :: T :: r s. Il faut alors supprimer le False tiré en trop (il y en a 3 au lieu de 2) : l'algorithme tire toujours une valeur en trop au cas où ce serait une des valeurs restantes à tirer (un True dans ce cas). Ainsi, on passe à la deuxième étape qui consiste en l'insertion uniforme de deux valeurs True dans la liste l. Soit, par exemple : l " T :: T :: F :: T :: F :: T :: r s ãÑ l " T :: T :: F :: T :: T :: F :: T :: r s ãÑ l " T :: T :: F :: T :: T :: F :: T :: T :: r s Il ne reste plus qu'à retourner l qui contient bien 2 False et 6 True.

Le premier test de l'algorithme (p ą logpqq 2 ^q ą logppq 2 ) consiste juste à vérifier que les entrées ne sont pas "trop petites". Dans le cas où l'une des entrée est "trop petite" par rapport à l'autre, il vaut mieux (pour économiser des bits aléatoires) directement insérer ce petit nombre de valeurs dans la liste contenant le bon nombre de l'autre valeur. Dans le détail, ce comportement est dû à un changement de régime dans la distribution des coefficients binomiaux. l est entièrement générée pendant la première étape de l'algorithme auquel cas elle est tirée avec probabilité ´p p`q ¯p ´q p`q ¯q (le produit des p `q tirage de Bernoulli de paramètres p p`q ). Cette probabilité ne dépend pas de l et est donc la même pour tout l : l est tirée uniformément parmi toutes les possibilités.

l est tirée après p `q ´k tirage de Bernoulli. En utilisant le même argument que dans le premier cas, cette combinaison de p `q ´k valeurs est tirée uniformément. Alors, chaque valeur restante est insérée de manière uniforme, ce qui garantit l'uniformité de la liste produite : il est facile de voir qu'un mot binaire de p `q ´k lettres est uniformément obtenu à partir d'un mot de p `q ´k ´1 lettres uniformément tiré dans lequel on insère une lettre. La complexité en nombre de bits aléatoires consommés est obtenue en supposant que l'algorithme 14 (k-B ) est entropique, ce que nous démontrons par la suite. Il ne reste donc qu'à analyser le nombre de bits du flux rndBits consommés et le nombre d'éléments à insérer.

Soit T la variable aléatoire comptant le nombre True et False de l à la fin de la première étape de l'algorithme. On a alors que T suit la loi suivante :

PpT " tq " ˆt p ˙ˆp p `q ˙p`1 ˆq p `q ˙t´p `ˆt q ˙ˆp p `q ˙q´t ˆq p `q ˙q`1

Pour obtenir le nombre moyens de bits consommés, on calcule l'espérance de T : ErT s. Pour ce faire, on introduit le lemme technique suivant.

Lemme 4: Soient p et q deux entiers tels que q ď p et q qui tend vers l'infini. On pose :

Lpxq " ln ¨?2π d q pp `qq p ˆp `q ´xb qpp`qq p p ˙ˆp p `q ˙p`1 ˆq p `q ˙q´x b qpp`qq p '.

De façon formelle, il faudrait ajouter des parties entières à certains endroits de cette formule. Par soucis de lisibilité, on les omet. Alors, pour tout x fixé, on obtient le développement suivant :

Lpxq " ´1 2

x 2 ´1 6 xpx 2 ´3q ? q `op 1 ? q q

Le lemme se démontre par applications de la formule de Stirling et calcul.

Soit, en posant t " x b qpp`qq p dans l'expression de PpT " tq et en appliquant le lemme 4, on obtient :

PpT " tq " 1 ? 2π e ´1 2
p´t `p `qq 2 q pp `qq p ? q a pp `qq p

`1 ? 2π e ´1 2
p´t `p `qq 2 p q pp `qq ? p a q pp `qq , quand p et q tendent vers l'infini. Ainsi, on peut calculer un équivalent asymptotique de l'espérance de T pour p et q grand :

ErT s " p `q ´pp `qq 3 2 ? 2pqπ .

Ce qui signifie donc ErT s " pp `qq `opp `qq quand p ą logpqq 2 (resp. q ą logppq 2 ). C'est cette condition qui justifie le test au début de la première étape de l'algorithme. Il ne reste plus qu'à compter le nombre de bits aléatoires consommés et à le comparer à l'entropie de la loi uniforme sur l'ensemble des combinaisons de p parmi p `q éléments, notée E p,q et telle que :

E p,q " log ˆp `q p ˙" p,qÑ8 pp `qq logpp `qq ´p logppq ´q logpqq.

On rappelle que la génération uniforme d'un entier appartenant à l'intervalle r0, ns nécessite (de manière entropique) Θplog nq bits aléatoires. On note B p,q l'entropie d'une loi de Bernoulli de paramètre p p`q , soit, par définition :

B p,q " ´p log p p `q ´q log q p `q .

On a donc que le nombre moyen de bits aléatoires utilisés par l'algorithme est équivalent à l'entropie de la loi uniforme sur l'ensemble des combinaisons de p éléments parmi p `q :

ErT sB p,q `opp `qqOplogpp `qqq " E p,q .

L'algorithme R C est entropique.

Pour compléter cette preuve, il reste à démontrer qu'il existe un algorithme entropique k-B qui simule des variables aléatoires de Bernoulli. Avant de présenter cet algorithme, on rappelle l'algorithme, du folklore de la génération aléatoire (notamment présenté dans [START_REF] Lumbroso | Optimal discrete uniform generation from coin flips, and applications[END_REF]), permettant de simuler une loi de Bernoulli de n'importe quel paramètre. Théorème 19: L'algorithme 13 simule une loi de Bernoulli en consommant, en moyenne, 2 bits aléatoires.

L'idée principale de l'algorithme est de pratiquer une sorte de recherche dichotomique du paramètre p dans l'intervalle r0, 1s. La différence est que le chemin emprunté par cette recherche dichotomique est aléatoire et donc peut ne pas trouver l'élément recherché : cela correspond à un échec de l'expérience de Bernoulli (et non un échec de la simulation).

Démonstration. La preuve de correction est directe. Il suffit de remarquer que l'algorithme parcours le préfixe (en base 2) du paramètre p et renvoie True avec probabilité p et False avec probabilité 1 ´p.

Si l'on note K la variable aléatoire comptant le nombre d'appels récursifs de l'algorithme, alors, le nombre de bits aléatoires consommés, en moyenne, est égale à l'espérance de K :

ErKs " 8 ÿ k"1 k ¨1 2 k " 1 2 ¨ˆd dz 1 1 ´z ˙ z" 1 2 " 2
Cet algorithme consomme donc, en moyenne, un nombre constant de bits aléatoires, quel que soit le paramètre de la loi de Bernoulli à simuler. Or, l'entropie d'une loi de Bernoulli dépend de son paramètre. Notamment, quand le paramètre est proche de 0 ou 1, l'entropie de la loi est proche de 0. Cet algorithme n'est donc, en général, pas entropique.

Au contraire, quand le paramètre est égal à 1 2 , l'entropie de la loi de Bernoulli est 1. L'idée, pour économiser des bits aléatoires, est donc de simuler le tirage de plusieurs variables de même loi de Bernoulli en utilisant le moins de simulations possibles de loi de paramètre 1 2 . C'est ce que fait l'algorithme 14.

Algorithme 14 Simulation de k variables aléatoires de loi de Bernoulli de paramètre p

function k-B (p) Ź p is less than 1 function k-B A (p) k :" Y log 1 2 log p ]
, i :" 0 v :" a vector of k times True while B (

ř i "0 `k ˘pk´ p1 ´pq ) do i :" i `1 j :" uniformRandomIntpr0 . . . k ´1sq vrjs :" False return v if p ă 1 2 then return negate(k-B A (1 ´p)) else return k-B A (p)
Plus précisément, le principe de l'algorithme est de simuler des lois de Bernoulli de paramètre p par paquets. Pour ce faire, on remarque que le succès d'une simulation de loi de Bernoulli de paramètre p k correspond aux succès de k simulations de la loi de Bernoulli de paramètre p. On choisit donc k de telle façon que p k soit le plus proche possible de 1 2 , c'est-à-dire k "

Y log 1 2 log p
] . On se ramène donc au problèmes de simuler, de manière entropique, une loi de Bernoulli de paramètre proche de 1 2 : ce que fait l'algorithme B . Avant de démontrer l'efficacité d'un tel algorithme, considérons un exemple d'exécution de l'algorithme avec l'entrée 2 7 . Dans ce cas, p " 1 ´2 7 " 5 7 et donc k " 2. On présente alors les différentes exécutions possibles sous forme d'un arbre de décision. On commence par simuler une loi de Bernoulli de paramètre `5 7 ˘2 :

-si c'est un succès, cela signifie le succès de deux expériences de Bernoulli de paramètre 5 7 . L'algorithme retourne donc un tableau contenant deux True (convertis en False, car nous voulons simuler l'événement contraire du fait de p " 1 ´2 7 " 5 7 ). -si c'est un échec, cela signifie qu'au moins une des expériences de paramètres 5 7 a échoué. Il faut donc simuler une nouvelle expérience pour savoir si il s'agit d'un ou de deux échecs. Dans le cas où il y a au moins un échec, l'événement où il y a exactement un échec se produit avec une probabilité de 5 7 `p1 ´5 7 q ¨5 7 , on simule donc cet événement : -si c'est un succès, alors il y a exactement un échec et il faut décider laquelle de la première où de la deuxième simulation est un échec. Cette décision est prise en insérant un False parmi les deux cases du tableau résultat. -sinon, cela signifie que les deux simulations sont des échecs : dans le cas où au moins deux expériences (parmi deux) sont des échecs, la probabilité que exactement les deux soient des échecs est de `5 7 ˘2 `2 ¨p1 ´5 7 q ¨5 7 ``1 ´5 7 ˘2 " 1 : c'est nécessairement un succès. Donc l'algorithme renvoie un tableau contenant deux False.

Théorème 20:

L'algorithme 14, qui simule

Y log 1 2 log p
] lois de Bernoulli de paramètre p, est entropique.

Démonstration. Soit N la variable aléatoire dénombrant le nombre d'itérations de la boucle while de l'algorithme k-B . On observe que le nombre de bits aléatoires consommés est supérieurement borné par 2N `N log k : le nombre de bits consommés pour les simulations de loi de Bernoulli plus les bits consommés pour tiré uniformément les entiers de r0 . . . ks. Donc, par définition, l'espérance de N est :

ErN s " k ÿ n"0 ˆk n ˙pk´n p1 ´pq n p2pn `1q `n log kq " 2 `p1 ´pqp2 `log kq.

Il ne reste qu'à moyenner cette somme par le nombre de simulation de loi de Bernoulli de paramètre p effectuées, c'est-à-dire k. Donc le nombre moyen de bits consommés pour simuler une loi de Bernoulli de paramètre p est 2 k `p1 ´pqp2 `log kq. Le minimum de cette fonction de k est atteint quand k vaut 2 log 2 1´p (on rappelle qu'ici p ą 1 2 ), autrement dit, quand le nombre moyen de bits consommés est supérieur ou égal à 2. En fait, ce cas correspond à k " 1, pour lequel il est préférable d'appeler l'algorithme B

. Sinon, pour k ą 1 le nombre moyen de bits consommés vaut :

Expérimentations

On présente ici quelques expérimentations des différents algorithmes présentés. L'implémentation des algorithmes a été faite dans le langage Ocaml.

On commence par constater que la complexité temporelle de nos algorithmes entropiques est moins bonne que l'approche "naïve" (par insertions, sans simulations de variables de Bernoulli). Théoriquement, dans les deux cas et en nombres d'écritures mémoires, l'ordre de grandeur de la complexité est le même : Opn ? nq où n est la taille du graphe. En pratique, les algorithmes entropiques pâtissent d'un sur-coût non compensé par la complexité du générateur de bits aléatoires qui est trop petite. On observe bien que l'approche top-down est plus rapide car en place. On observe aussi le léger surcoût, qui n'est pas plus grand qu'un facteur 2 entre les approches naïves et entropiques. Dans de futurs travaux, nous essaierons d'implémenter plus efficacement ces différents algorithmes entropiques pour effacer ce surcoût.

Concentrons nous maintenant sur les complexités en nombre de bits aléatoires consommés. , le nombre moyen de bits consommés est de l'ordre de 2 fois l'entropie, comme on l'avait estimé théoriquement. On le voit dans la figure 3.9. F 3.9 -Consommation de bits aléatoires de l'algorithme k-B

Ces expérimentations laissent entrevoir des améliorations possibles, autant du point de vue du temps d'exécution que du nombre de bits aléatoires consommés. Notamment, pour la génération de combinaisons, il serait intéressant de regarder plus précisément le phénomène qui se produit quand p " q 3 , proportion pour laquelle le nombre de bits consommés est le plus important.

Conclusion

Dans ce chapitre, nous avons présenté deux algorithmes de génération aléatoire uniforme. Le premier se plaçant dans le cadre de la méthode de Boltzmann et permettant de générer des structures étiquetées avec des contraintes de croissance (produit boîte). Nous avons aussi montré son efficacité pratique et une application à la génération de graphes cactus croissants.

Dans un avenir proche, nous aimerions être en mesure de générer des graphes Fork-Join croissants. Pour ce faire, on peut notamment utiliser le générateur de Boltzmann pour le produit ordonné, présenté dans [START_REF] Darrasse | Biased boltzmann samplers and generation of extended linear languages with shuffle[END_REF]. Mais dans cet algorithme, comme dans ceux présentés dans ce chapitre, un problème difficile reste à résoudre pour pouvoir générer de très grandes structures (plusieurs centaines de milliers de noeuds) : l'efficacité de l'oracle. Dans leur cas comme dans le nôtre, une grande partie du temps de calcul est prise par l'évaluation de séries génératrices en certains points. Des améliorations existantes dans le cas de générateur "classique" ([PSS12] ou [START_REF] Bodini | Analytic samplers and the combinatorial rejection method[END_REF]) pourrait s'adapter à nos cas. Une autre piste serait d'étudier des méthodes d'interpolations pour obtenir des fonctions plus simples à évaluer.

Le deuxième algorithme permet de générer uniformément un étiquetage croissant d'un ordre Série-Parallèle donné. On peut donc notamment s'en servir pour étiqueter les structures générées par les générateurs de Boltzmann. En partie, il répond aussi au problème de la génération aléatoire d'exécutions de programmes Série-Parallèle.

Comme dans le cas des ordres arborescents, il reste à générer des étiquetages croissants et partiels pour pouvoir gérer les programmes non-déterministes. L'approche de [START_REF] Bodini | The combinatorics of non-determinism[END_REF] peut, a priori, directement être adaptée à ce problème.

Enfin, il reste la question de la généralisation de ces algorithmes pour des classes d'ordres plus larges : sujet du chapitre suivant.

O :

Dans ce chapitre, nous revisitons le problème du dénombrement des extensions linéaires d'un ordre donné avec un point de vue géométrique. Cette interprétation se base principalement sur les travaux de [START_REF] Richard | Two poset polytopes[END_REF].

En partant de cette interprétation, notre contribution est un algorithme de décomposition d'ordres partiels. Cette décomposition permet, entre autre, de caractériser des sous-classes intéressantes d'ordres partiels. Le deuxième intérêt de cette décomposition est de produire une formule symbolique dont l'évaluation donne le nombre d'extensions linéaires de l'ordre en entrée.

Interprétation géométrique des ordres partiels

Dans [START_REF] Richard | Two poset polytopes[END_REF], l'auteur donne une interprétation géométrique des ordre partiels, comme ensemble d'extensions linéaires. L'idée de base est de plonger un ordre partiel sur n éléments dans l'hypercube unitaire de dimension n. Pour ce faire, on part du principe que chaque élément de l'ordre correspond à une dimension de l'espace, puis l'on fait correspondre la relation d'ordre à un découpage de l'hypercube par des hyperplans.

Définition 19:

Soit P " pE, ăq un ordre partiel de taille n. Soit C l'hypercube unitaire de dimension n, défini par C " tpx 1 , . . . , x n q P R n | @i, 0 ď x i ď 1u. Pour chaque contrainte i ă j P P on définit le sous-ensemble convexe S i,j " tpx 1 , . . . , x n q P R n | x i ď x j u. S i,j est le demi-espace obtenu en coupant R n avec l'hyperplan tpx 1 , . . . , x n q P R n | x i ´xj " 0u.

Alors, on défini C P , le plongement de l'ordre P dans l'hypercube C : De la même façon que pour les ordres, on peut plonger les extensions linéaires d'un ordre dans l'hypercube unitaire en les voyant comme des ordres totaux. Ainsi, le plongement de l'ensemble des extensions linéaires d'un ordre P forme une partition du plongement de l'ordre C p en simplexes.

C p " č iăjPP S i
C p0,1,0q B p1,1,0q A p1,0,0q O p0,0,0q E p0,0,1q D p0,1,1q G p1,1,1q F p1,0,1q C B A O E D G F C B A O E D G F F
4.1 -De gauche à droite : l'hypercube unitaire, le plongement de l'ordre total 1 ă 2 ă 3 et le plongement de l'ordre partiel P " pt1, 2, 3u, t1 ĺ 2uq divisé en ses trois extensions linéaires.

Un exemple de plongement d'un ordre et de ses extensions linéaires est donné dans la figure 4.1.

Étant donné que les simplexes représentant les extensions linéaires sont identiques à isométrie près, le volume du polytope C p est donc égal aux nombres d'extensions linéaires multiplié par le volume d'un simplexe.

Fait 1 ([Sta86, Corollaire 4.2]): Soit un ordre partiel P de taille n alors |LE pP q| " n! ¨VolpC P q, où VolpC P q est le volume, défini par la mesure de Lebesgue, du polytope C p : le plongement de P dans l'hypercube.

Ainsi, compter les extensions linéaires d'un ordre partiel donné revient à calculer le volume d'une union convexe de simplexes.

La décomposition Bottom, Intermediate, Top and Cycle (BITC)

En exploitant cette interprétation géométrique, nous présentons une décomposition agissant sur la couverture d'un ordre partiel (un DAG intransitif). Cette décomposition se veut être à la fois un outil théorique dans le cadre de l'étude du problème de comptage des extensions linéaires, mais aussi un outil algorithmique pour répondre à ce problème.

La Pour ce deuxième argument, la preuve est simple et repose sur la définition même de ce qu'est un volume. On illustre le principe de calcul sur un exemple probant.

z z x 1 x 2 x k x k`1 x k`2 x 2k . . . Ť σ x σ1 x σ 2k . . . Ψ 1 " ż 1 x Ψ.dy Ψ 1 " ż z x Ψ.dy Ψ 1 " ż z 0 Ψ.
Exemple 1 (Une décomposition BITC):

x 1 x 2 x 4 x 3
x 5

x 6 x 7 x 8

x 9 C p4,5,6,7q x 5

x 4

x 6

x 7

x 9

x 3

x 1 x 2

x 8 T 2 x 5

x 4

x 6

x 7

x 9

x 3

x 1

x 8 I 8 x 5

x 4

x 6

x 7

x 9

x 3 Le DAG à décomposer (à gauche) est de taille 9, les noeuds étant x 1 , . . . , x 9 . Les noeuds x 4 , x 5 et x 6 , x 7 forment un cycle (de taille 4) qui peut être déplié en 4 ordres totaux distincts et compatibles avec les contraintes d'ordre de ce cyle. Ainsi, la règle C décompose le DAG en 4 DAGs distincts où les éléments du cycle sont totalement ordonnés. Nous avons seulement repésenté le premier de ces 4 DAGs, mais les flèches indiquent quels éléments doivent être permutés pour obtenir les 3 autres. Notons qu'en terme d'extensions linéaires, il suffit simplement de sommer les 4 calculs restants. Maintenant, la règle T est appliquée au noeud x 2 . Il est important de remarquer que cela aurait pu être fait avant l'application de la règle C. La décomposition est non-déterministe, en ce sens où il n'y a pas d'ordre privilégié d'application des règles. La règle I peut être appliquée au noeud x 8 , et ainsi de suite. À la fin de cette décomposition, nous obtenons la formule symbolique suivante :

x 1 B . . . Ψ " 1 Ψ 1 " Ψ p4,
V olpP q " V olpP p4,5,6,7q q `V olpP p5,4,6,7q q `V olpP p4,5,7,6q q `V olpP p5,4,7,6q q " ż x 3 0 ´V olpP 1 p4,5,6,7q q `V olpP 1 p5,4,6,7q q `V olpP 1 p4,5,7,6q q `V olpP 1 p5,4,7,6q q ¯dx2 " ż 1

x 7 ż x 9

x 5 ż x 3 0 ´V olpP 3 p4,5,6,7q q `V olpP 3 p5,4,6,7q q `V olpP 3 p4,5,7,6q q `V olpP 3 p5,4,7,6q q ¯dx2 dx8 dx9 " ¨¨"

ż 1 0 ż 1 x 1 ż 1 x 3 ż 1 x 4 ż 1 x 5 ż 1 x 6 ż 1 x 7 ż x 9
x 5 ż x 3 0 1 dx2 dx8 dx9 dx7 dx6 dx5 dx4 dx3 dx1 `¨¨¨`¨¨¨`¨¨" 6 `6 `8 `8 9! " 28 9! .

Il y a donc 28 extensions linéaires distinctes dans cet exemple d'ordre partiel.

Remarque 8:

Cette approche n'est pas en contradiction avec le fait que le problème du comptage d'extensions linéaires soit 7P-complet. Par exemple, la règle cycle peut construire un terme de taille exponentielle.

Ordres partiels sans cycle

Pour en revenir à la preuve du théorème 21, nous avons besoin de montrer que la décomposition est complète, au sens où elle est capable de décomposer n'importe quels ordres partiels. Pour ce faire, nous allons montrer que les règles BIT décomposent une sous-classe d'ordre, introduites dans [START_REF] Duffus | Minimizing setups for cycle-free ordered sets[END_REF] : les ordres partiels sans cycle (cycle-free poset en anglais). Pour conclure, il ne restera à démontrer que la règle C décompose bien les cycles.

Les ordre partiels sans cycle représentent une classe assez peu étudiée de la littérature. Pour ce qui nous intéresse, on peut citer les travaux dans [START_REF] Ma | Cycle-free partial orders and chordal comparability graphs[END_REF] qui donnent un algorithme polynomial de reconnaissance de ces ordres. Ils sont définis par exclusion de motif.

Définition 20:

Un cycle alternant pair (de taille 2n) est un ordre partiel sur les éléments tx 1 , . . . , x n , y 1 , . . . , y n u tel que :

x 1 ĺ y 1 , y 1 ľ x n , x 2 ĺ y 2 , y 2 ľ x 3 , . . . , y n´1 ľ x n , x n ĺ y n .

Soit, le motif reconnut par la règle C de la décomposition BITC. Un ordre partiel sans cycle est un ordre ne contenant pas de cycle alternant pair.

Une autre manière de caractériser les ordres partiels sans cycle est de caractériser leur graphe de comparabilité.

Proposition 18 ([MS91]):

Le graphe de comparabilité d'un ordre partiel sans cycle est un graphe cordal : un graphe qui ne contient pas de cycle primitif 1 de taille plus grande que 3.

Remarque 9:

Les cycles primitifs rencontrés dans le graphe de comparabilité d'un ordre partiel sont nécessairement de taille paire. Pour s'en convaincre, il suffit de remarquer qu'il n'existe pas d'orientation transitive d'un cycle de taille impaire et donc d'ordre partiel associé.

Théorème 22:

La décomposition BIT (sans la règle C) caractérise en temps linéaire, en la taille de l'ordre partiel considéré, la classe des ordres partiels sans cycle.

On dit que la couverture un ordre partiel sans cycle est BIT-décomposable.

Un intérêt de la BIT décomposition est qu'elle est beaucoup plus élémentaire que d'autres algorithmes de reconnaissance (par exemple [START_REF] Ma | Cycle-free partial orders and chordal comparability graphs[END_REF]). Elle a la même complexité linéaire, modulo réduction transitive.

Avant de prouver ce théorème, on rappelle la définition de clique maximale, notion essentielle de la preuve.

Définition 21 (Clique maximale): Soit un graphe non dirigé G " pV, Eq. Une clique C Ď V est un ensemble de noeuds tel que toutes les paires pu, vq P C ˆC sont des arêtes de G. C'est une clique maximale si elle n'est contenue dans aucune autre clique.

Remarque 10:

Une clique maximale du graphe de comparabilité d'un ordre partiel correspond à un chemin entre une source et un puits de son DAG couvrant.

Démonstration. On procède par induction sur le nombre d'éléments de l'ordre partiel car chaque règle BIT supprime exactement un tel élément. Notre objectif est de montrer que si aucune des règles BIT ne peut être appliquée, alors l'ordre partiel considéré contient un cycle. Un cas spécial est que nous considérons la décomposition terminée quand l'ordre ne contient plus qu'un seul élément. Pour simplifier nous ne considérons que les ordres partiels connexes (dont la couverture est connexe), la généralisation au cas non connexe étant trivial. Comme cas de base, il est aisé de constater que tous les ordres de taille au plus 3 sont sans cycle et BIT-décomposables.

L'idée clé de cette preuve est d'interpréter les règles BIT en terme d'intersection des cliques maximales du graphe de comparabilité. Voici quelques observations préliminaires :

-si x ĺ y ĺ z sont en série, alors chaque clique maximale contenant x contient nécessairement y et z, et de même pour y et z ; -si x est un noeud "pendant", attaché à l'ordre par un autre noeud y, alors chaque clique maximale contenant x contient aussi y.

CHAPITRE . OUVERTURE ORDRES PARTIELS SANS CYCLE

Notre hypothèse d'induction est que la décomposition BIT caractérise les ordres sans cycle de taille n ´1. Montrons maintenant que c'est aussi le cas pour les ordres de taille n. Soient C v l'ensemble des cliques maximales du graphe de comparabilité contenant v et I v " Ş CPCv C (l'intersection des cliques maximales contenant v). Observons que @v, tvu Ď I v . Considérons donc les cas suivants :

1. si @v, I v " tvu alors aucune des règles BIT ne s'applique car les précédentes observations impliquent que l'application des règles nécessite au moins deux éléments dans l'intersection. Montrons que dans ce cas l'ordre contient un cycle de taille au moins 4. Premièrement, on peut trouver deux sources distinctes, ou si il n'y a qu'une source, deux voisins incomparables de cette source. Autrement, au moins une des règles s'appliquerait. Le même principe s'applique aux puits. Et puisque que les puits et sources sont connectés deux à deux, nous obtenons un cycle de taille au moins 4. Ainsi, l'ordre contient un cycle.

2. autrement, si Du, u ‰ v, I v " tv, uu, considérons deux sous cas :

-si v (ou u) est un noeud pendant alors la règle B ou T s'applique et fait décroître la taille de l'ordre sans créer de cycle. Nous considérons alors un ordre de taille n ´1 dont la caractérisation est décidée, par hypothèse d'induction.

-sinon, aucune des règles BIT ne s'appliquent. Cela signifie que pv, uq (ou u, vq) est un isthme de la couverture (un arc dont l'élimination entraîne déconnexion du graphe). On remarque qu'il est impossible que tous les autres noeuds soient dans ce cas là (sans violer l'hypothèse de connexité). On considère donc un autre noeud.

3. dans les cas où Dv, |I v | ě 3, deux cas sont possibles :

-un des noeuds de I v est en série et donc la règle I s'applique. Nous pouvons donc utiliser l'hypothèse d'induction pour conclure. -si la règle I ne s'applique à aucun des noeuds de I v , cela signifie que chacun des noeuds appartient à plusieurs chaînes de l'ordre et donc qu'il faut choisir un autre candidat. On remarque encore que tous les noeuds ne peuvent pas être dans ce cas là (sans violer l'hypothèse de connexité). On considère donc un autre noeud.

Corollaire 2:

Tout DAG intransitif est BITC décomposable.

Démonstration. Aucune des règles BIT ne crée pas de cycle. Tous les cycles peuvent être consommés par la règle C. Donc, après toutes les applications possibles de la règle C, il ne reste plus qu'à décomposer un ensemble d'ordres sans cycle avec les règles BIT.

Concluons cette étude de la décomposition BITC, par la proposition suivante qui donne une piste pour une étude plus approfondie de la complexité, au sens algorithmique, de la décomposition BITC.

Proposition 19:

Soit un ordre partiel P de taille n. L'expression symbolique Ψ construite à l'aide la décomposition BITC a une taille exponentielle en n. Précisément, chaque cycle de taille 2k donne lieu à la construction de pk!q 2 ¨2kpk´2q ordres de taille n.

. . EXPÉRIMENTATION 93 Si P est un ordre sans cycle, la taille de Ψ est linéaire en n, en nombre de variables et en nombre de symbole d'intégrale.

Démonstration. Pour le cas des ordres sans cycle, la preuve est une simple induction : Les règles BIT génèrent exactement un symbole intégral et une nouvelle variable pour chaque noeud consommé. Supposons que le DAG contienne un cycle de taille 2k partitionné en deux partitions p 1 et p 2 , où les arcs sont orientés de p 1 vers p 2 . Pour compter le nombre d'extensions linéaires compatibles avec ce cycle nous commençons par compter le nombre d'extensions linéaires du graphe dirigé, biparti et complet K k,k des deux partitions p 1 et p 2 . Ce graphe a pk!q 2 extensions linéaires, et si nous supprimons un arc entre entre deux noeuds u P p 1 et v P p 2 , ce nombre est doublé : on peut échanger la position de u et v dans toutes les extensions linéaires. Or, il faut supprimer kpk ´2q arcs pour retrouver le cycle initial (k ´2 arcs sont supprimés par noeuds pour chacun des k noeuds de p 1 , puisque 2 arcs par noeuds sont nécessaires pour former un cycle). Ainsi, nous construisons 2 kpk´2q extensions linéaires à partir des pk!q 2 extensions linéaires de K k,k . Donc, la formule symbolique résultante de l'application de la règle C a un total de pk!q 2 2 kpk´2q composantes.

Expérimentation

Dans cette section nous présentons une expérimentation basée sur la décomposition BITC. L'objectif est de vérifier si cette décomposition a un quelconque intérêt pratique. Pour cela nous avons récupérer des bases de données de DAGs issues des domaines de l'ordonnancement (T DAG , cf. [START_REF] Jarry | Dagsim : a simulator for dag scheduling algorithms[END_REF]) et du dessin de graphes (DAG-2). Les plus petits Dags ont seulement 10 noeuds et les plus grands dépassent les 400.

Base de données

C P

Dans ce manuscrit nous avons exploré la combinatoire d'une famille de programmes concurrents dont la structure de contrôle correspond à un DAG. Nous avons utilisé des outils de combinatoire analytique pour obtenir des résultats quantitatifs sur ces programmes, notamment sur leur expressivité, en calculant l'asymptotique du nombre moyen d'exécutions possibles d'un programme "diamant" ou Série-Parallèle. Dans ce cadre, nous avons notamment développé des outils dont la portée dépasse le cadre de la concurrence : produits ordonné et coloré. D'un point de vue pratique nous avons élaboré des algorithmes de génération aléatoire uniforme à la fois pour générer des exécutions de programmes et également pour générer des programmes concurrents. Si ces algorithmes ne sont pas encore applicables à des programmes réels, ils représentent des briques élémentaires qui nous permettent de l'envisager à plus long terme.

Perspectives

Étant donné les résultats présentés dans ce manuscrit, on peut dégager plusieurs pistes de recherche concernant la combinatoire des programmes concurrents et des structures croissantes. Dans cette section, nous détaillons les différents problèmes que nous aimerions résoudre dans un avenir plus ou moins proche.

Ordres partiels sans cycle

Complexité Dans [START_REF] Bouchitte | The Calculation of Invariants for Ordered Sets[END_REF] les auteurs conjecturent que le problème de comptage des extensions linéaires d'un ordre sans cycle est de complexité polynomiale. Nous avons montré que ce calcul pouvait se faire en évaluant une formule intégrale de taille linéaire en la taille de l'ordre en entrée. Même si ce résultat est encourageant, d'autres résultats semblent suggérer que le problème est dur (est-il 7P-complet ?). Dans [BBDL `11] un théorème statue que le problème d'intégrer un polynôme quelconque en n variables, sur un simplexe est NP-difficile.

Néanmoins, dans notre cas les polynômes sont homogènes et d'autres résultats de cet article peuvent (peut-être) être utilisés pour ce cas particulier.

Mais, le degré du polynôme et son nombre de variables semblent être les paramètres critiques du problème. Or, dans notre cas, le nombre de variables du polynômes et son degré correspondent à la taille de l'ordre.

Avec ces résultats en tête, il nous semble réalisable à moyen terme de trancher la question de la complexité du comptage des extensions linéaires des ordres sans cycles. 95 96

CONCLUSION ET PERSPECTIVES

De manière complémentaire, une partie de la complexité du problème de dénombrement des extensions linéaires semble provenir de la structure de cycle, et plus généralement, de celle de couronne. Dans l'article [START_REF] Brightwell | Counting linear extensions[END_REF], qui montre la difficulté de ce problème, les auteurs conjecturent la difficulté du problème pour les ordres de hauteur 2, qui contiennent les cycles et couronnes. Il nous semble intéressant d'aborder à plus long terme cette question.

Combinatoire D'un point de vue plus combinatoire, et particulièrement celui de la combinatoire analytique, la structure des ordres sans cycle semble être très compliquée à analyser. Pour le moment les deux idées pour mener cette étude sont :

-de partir du modèle d'ordre Série-Parallèle (graphes Fork-Join) et de le complexifier en ajoutant des paramètres, -de partir d'un modèle d'arbres croissants étiquetés avec autorisation des répétitions d'étiquettes pour signifier les synchronisations entre processus. Un autre objet d'étude intéressant est celui des graphes de comparabilité. Pour le moment, notre point de vue a été de considérer les couvertures des ordres et non leur graphe de comparabilité. Or, vus les travaux assez récents sur plusieurs sous-classes des graphes cordaux (réseaux apolloniens [START_REF] Soria | Degree distribution of random apollonian network structures and boltzmann sampling[END_REF], k-arbres [START_REF] Darrasse | Shape measures of random increasing k-trees[END_REF]), cette idée peut être le point de départ de nouvelles études.

Produit ordonné et coloré

D'un point de vue combinatoire, ces opérateurs permettent de spécifier des structures qui n'étaient pas spécifiables jusqu'à présent dans la méthode symbolique. Nous devons explorer l'expressivité de ces opérateurs.

Du point de vue de la combinatoire analytique, il reste encore beaucoup à comprendre de ces opérateurs pour pouvoir les utiliser simplement. Par exemple, dans le cas des graphes Fork-Join monochromes et croissants, nous aimerions comprendre les phénomènes en jeu au niveau des fonctions génératrices. Où sont exactement les singularités et quelles sont leur type ? Peut-on obtenir les termes des ordres inférieurs dans le développement asymptotique ?

Enfin, il nous reste aussi à étudier des paramètres inductifs des graphes Fork-Join croissants, tels que la profondeur de branchement maximale moyenne ou le nombre de noeuds blancs moyens.

Concurrence

Non-déterminisme Une des perspectives à court terme est d'adapter les résultats de [START_REF] Bodini | The combinatorics of non-determinism[END_REF] sur le non-déterminisme dans les processus arborescents aux processus Série-Parallèle décrit dans ce manuscrit. Nous pensons que la même technique d'étiquetage partiel peut encore mener à des algorithmes efficaces pour la génération aléatoire d'exécutions non-déterministes.

Applications Une des motivations principales de ce travail concerne l'apport des algorithmes de comptage et de génération aléatoire aux différentes techniques de model checking. Il serait donc intéressant de les expérimenter dans ce cas et donc d'implémenter un model checker proof-of-concept.

Itération Le formalisme concurrent que nous étudions dans cette thèse a été conçu dans l'idée de facilement être analysable (combinatoirement). De ce fait, il ne contient pas de construction itérative (boucles) ou récursive (appels récursifs). L'ajout de telles constructions rapprocherait beaucoup notre modèle de programmes plus réalistes.

Bisimulation Nous avons considéré que deux programmes étaient équivalents si leurs ordres partiels induits étaient isomorphes. Or, en théorie de la concurrence, il existe des notions plus fines d'équivalence entre processus, par exemple la bisimilarité ou l'équivalence de traces. D'un point de vue pratique, on peut voir ces relations d'équivalence comme une sorte de compression des comportements.

Une étude quantitative de ces différentes relations d'équivalence notamment en terme de taux de compression, nous semble très intéressante. Plus intuitivement, le plongement combinatoire d'un graphe donne un ordre à ses arcs sortants. On peut alors désigner les arcs sortants d'un noeud de l'arc "gauche" à l'arc "droit".

Quand on travaille sur les graphes, on fait naturellement un choix sur l'ordre de leurs arcs, que ce soit quand on les représente graphiquement ou quand ils sont parcourus par un algorithme. Ce choix correspond à un plongement combinatoire du-dit graphe.

Pour conclure cette section et bien comprendre l'approche utilisée dans nos travaux, on fait le lien entre extensions linéaires et étiquetages croissants de la couverture d'un ordre partiel.

Définition 27 (Étiquetage croissant): Un étiquetage d'un graphe dirigé acyclique G " pV, Aq, où V est l'ensemble de ses noeuds et A l'ensemble de ses arcs, est une bijection de V dans l'intervalle d'entier r1, . . . , |V |s.

Un étiquetage croissant de G, est un étiquetage de G tel que toute les suites d'étiquettes le long d'un chemin d'une source à un puits de G soient croissantes.

Théorème 23:

Étant donné un ordre partiel P , l'ensemble de ses extensions linéaires de P est en bijection avec l'ensemble des étiquetages croissants de sa couverture.

Démonstration. Étant donné une extension linéaire px 0 , . . . , x n´1 q de P , on construit de manière unique un étiquetage croissant de sa couverture en associant l'étiquette i au noeud Par définition, la transformée de Laplace usuelle est définie par Lf " ş 8 0 expp´ztqf ptqdt à la place de L c f " ş 8 0 expp´tqf pztqdt. Cet opérateur est clairement linéaire. Par un simple changement de variable on obtient Lf pzq " 1 z pL c f q `1 z ˘ou de manière équivalente L c f pzq " 1 z pLf q `1 z ˘. On remarque que ce changement de variable est une involution.

La transformée de Laplace admet un inverse fonctionnel nommé transformée de Borel. Cette transformée a aussi une formulation intégrale. Dans le cas de la transformée de Borel usuelle, on a Bpf q " 1 2iπ ş c`i8 c´i8 exppztqf ptqdt où c est plus grand que la partie réelle de toutes les singularités de f ptq.

De façon analogue, la transformée de Borel combinatoire est B c pf q " 1 2iπ ş c`i8 c´i8 exppztq t f p1{tqdt où c est plus grand que la partie réelle de toutes les singularités de f p1{tq{t. Le lient avec la transformée de Borel usuelle vient du changement de variable B c pf q " Bp1{zf p1{zqq ou de manière équivalente Bpf q " B c pf p1{zqq

  de diamants À l'aide de la méthode symbolique, on peut définir des classes de diamants croissants ainsiF " Z `Z˝‹ GpFq ‹ Z ' (1.1.1)

  pour ã, b et c judicieusement choisis et d dépendant des conditions initiales de l'équation différentielle. On pose alors gpzq " u ¨f pzq `v, en choisissant u et v judicieusement en fonction de a, b et c, et de manière à obtenir une équation de la forme :

  Soient A et B deux classes combinatoires étiquetées et α et β deux structures appartenant, respectivement, à A et B. On définit le produit ordonné de α et β, noté α ‹ β, comme : α ‹ β " pα, f |α| pβqq | f |α| p¨q décale les étiquettes par |α| ( .

  Dans le cas où une des opérandes du produit ordonné est réduite à la classe atomique, le produit ordonné correspond au produit boîte classique [FS09, p.139].

F

  Lemme 3: F a une singularité dominante ρ réelle et strictement positive.Démonstration. Le fait que la singularité soit réelle et positive est obtenu par application du théorème de Pringsheim (cf. [FS09, page 240]). La localisation de cette singularité est obtenue par un argument combinatoire simple : le nombre de graphes Fork-Join croissants de taille n est borné supérieurement par le nombre de graphes Fork-Join non-étiquetés de taille n multiplié par le nombre de permutations de taille n (c-à-d n!) ; on a donc que rz n sF pzq " O est une série exponentielle) et donc que le rayon de convergence de F est plus grand ou égal à τ ą 0.

  Soient deux séries génératrices ordinairesA et B, nous nous posons la question des objets énumérés par la série L c pB c pAq ¨Bc pBqq, c'est-à-dire en quelque sorte le dual du produit ordonné. En fait cette série est celle d'un opérateur sur les classes combinatoires que nous nommons le produit coloré. Cet opérateur nous permet d'étudier une classe intéressante de graphes Fork-Join de profondeur fixée. . . GRAPHES FORK-JOINS CROISSANTS DE PROFONDEUR FIXÉE ET PRODUIT COLORÉ 43 2.4.1 Définition du produit coloré Définition 11 (produit coloré): Soient A et B deux classes combinatoires, non-étiquetées et α et β deux objets respectivement de A et B. On définit la classe combinatoire non-étiquetée du produit coloré de α et β, noté α e β comme : α e β " ! pα, βq satisfaisant la condition (C) ) , (C) : α et β ont respectivement les structures de α et β et leurs atomes sont coloriés par deux couleurs, avec la contrainte que parmi les |α| `|β| atomes de pα, βq, |α| atomes sont coloriés avec la première couleur et donc, |β| atomes sont coloriés avec la deuxième. On étend, naturellement, ce produit coloré de structures à celui de classe combinatoire : Dans le cas où une des opérandes du produit coloré est la classe atomique, alors le produit coloré est relié à l'opérateur de pointage (qui consiste à marquer un noeud [FS09, p.86]) : Z e A " ΘpZ ˆAq Proposition 7: Soient A et B deux classes combinatoire non-étiquetées. La fonction génératrice Cpzq, associé à la classe C " A e B, satisfait l'équation suivante : Cpzq " L c pB c Apzq ¨Bc Bpzqq " k ˙ak b n´k z n .

Proposition 9 :

 9 Soient A et B deux séries génératrices ordinaires et holonomes. A e B est holonome. Proposition 10: Soient A et B deux fonctions génératrice ordinaires et rationnelles. Alors, la série génératrice Apzq e Bpzq est rationnelle.

  Soient A et B deux séries génératrices exponentielles et holonomes. A ˚B est holonome.

  Définition 15: L'ensemble ordonné S ‹ pAq d'une classe combinatoire étiquetée A ne contenant pas d'objets de taille nulle est défini par : S ‹ pAq " La série génératrice exponentielle S associée à S ‹ pAq vérifie : ORDONNÉ ET COLORÉ PROPRIÉTÉS FONDAMENTALES ET EXEMPLES 47 où A ˚k signifie A ˚¨¨¨˚A k fois .

où L c r 1 1

 1 ´u spF pzqq correspond à la composition de la transformée de Laplace de u Ñ 1 1´u et F . Enfin, toujours comme dans les cas étiqueté et non-étiqueté, on définit l'opérateur C comme le quotient de l'opérateur séquence (ordonnée dans ce cas) par la relation d'équivalence entre k-uplets dont l'un est obtenu par permutation cyclique des composantes de l'autre. Définition 17: Le cycle ordonné C ‹ pAq d'une classe combinatoire étiquetée A ne contenant pas d'objets de taille nulle est défini par :

  nÑ8 B b A n´b `Aa B n´a . Ce théorème permet donc d'obtenir le premier ordre du comportement asymptotique. Notons que dans de nombreux cas B b A n´b et A a B n´a ne sont pas du même ordre : les singularités dominante de A et B sont différentes, a et b sont distincts ou encore, les facteurs sous-exponentiels dans le comportement asymptotique de A n et B n sont différents.Démonstration. Démontrons ce théorème dans le cas où les rayons de convergence de A et B sont les même (on le note ρ) et sont dans l'intervalle s0, `8r. Les autres cas sont plus simples et reposent sur une légère adaptation de cette preuve.

  d'application du théorème 12 est généralement assez simple à démontrer. Par exemple, dans le cas standard où A n " O `nα ρ ´n A n! ˘et B n " O `nβ ρ ´n B n! ˘l'hypothèse est vérifiée : il existe r tel que ř n´r k"r A k B n´k " OpA n´r `Bn´r q.

  1 pσq ¨σn p1 `Cn q si ρ Ps0, `8r et lim zÑρ Lpzq ą 1, avec C une constante réelle telle que 0 ă C ă 1 et σ vérifiant Lpσq " 1.

F

  1 pzq " φpF pzq, zq et F p0q quelconque ou F pzq " ż t 0 φpF ptq, tqdt `F p0q.

  Le générateur pour la séquence est celui proposé dans l'article original [DFLS04] : F 3.1 -Diamant plan croissant de taille 3423

  Temps de génération en fonction de la taille taille inférieure à 900. Dans le cas étiqueté, ce temps peut considérablement s'allonger et atteindre une minute, même si il est généralement en dessous de 20 secondes. Néanmoins, on est capable de générer des diamants croissants de plusieurs milliers de noeuds : par exemple 4000 noeuds en 200 secondes. Pour les diamants ordinaires, on génère des objets de quelques millions de noeuds en moins d'une seconde.Ces grosses différences d'efficacité s'expliquent par le coût et la perte de précisions dûs à l'évaluation de F à quasiment chaque itération dans le cas des diamants croissants. Dans le cas ordinaire, aucun calcul n'est nécessaire et la précision est maximale.

  (a) Hauteur (b) Profondeurs de branchement cumulées (c) Arités cumulées Les mesures correspondantes au modèle croissant sont en violet (points plus foncés) et celles du modèle ordinaire en vert. F 3.3 -Différents paramètres sur les diamants être réinterprétée comme la longueur de cheminement, dont la loi de probabilité limite est aussi connue (cf. [Tak91]) et dont on peut aussi obtenir les moments par analyse de la série génératrice.

F 3. 4 -

 4 Cactus croissant de taille 3422 (a) Diamants croissants (b) Diamants ordinaire Les histogrammes en bleu correspondent aux paramètres des diamants et ceux en orange à ceux des cactus.F 3.5 -Histogrammes de différents paramètres sur des diamants de taille 100

Algorithme 10

 10 Verison top-down de la génération aléatoire uniforme d'extensions linéaires. function R L E -TD(P ) function R R L E -TD(P , rankings, positions) if P " ˝then return rankings else if P " ' x then rankingsrxs :" pop(positions) return rankings else if P " ' x . T then rankingsrxs :" pop(positions) return R R L E -TD(T , rankings, positions) else if P " ˝. pL | Rq . T then if ˝" ' x then rankingsrxs :" pop(positions) upP ositions :" positionsr 0 . . . |L| `|R| ´1 s botP ositions :" positionsr |L| `|R| . . . |P | ´1 s l, r :" S (upP ositions, |L|, |R|) rankings :" R R L E -TD(L, rankings, l) rankings :" R R L E -TD(R, rankings, r) return R R L E -TD(T , rankings, botP ositions) rankings :" an empty dictionary positions :" r 1 . . . |P | s return R R L E -TD(P , rankings, positions) faites en place, au prix d'un niveau d'indirection supérieure. La structure rankings est une table d'association entre les étiquettes et les positions dans l'extension linéaire générée. La structure positions est une pile qui, initialement, contient toutes les positions disponibles entre 1 et |P | (la taille de l'ordre en nombre d'étiquettes c-à-d les noeuds noirs).

  une liste de p True et q False, selon la loi uniforme. De plus il est entropique.Démonstration. Soit l une liste générée par R C contenant p True et q False. La preuve de correction distingue deux cas :

  On peut vérifier que ce nombre de bits est toujours inférieure à deux fois l'entropie d'une loi de Bernoulli de paramètre p tel que Y comme le montre la courbe ci-dessous (rapport entre le nombre de bits consommés par l'algorithme et deux fois l'entropie) :Cela permet de conclure que k-B est entropique, de constante d'entropie de 2.

F 3. 6 -

 6 Temps d'exécutions des algorithmes de génération aléatoire d'étiquetages croissants de graphes Fork-Join. Dans la figure 3.6, on a interpolé les temps d'exécution des algorithmes bottom-up et top-down dans les cas d'une génération entropique, ou non, des combinaisons.

F 3. 7 -

 7 Bits aléatoires consommés par les algorithmes de génération aléatoire d'étiquetages croissants de graphes Fork-Join.La figure 3.7 confirme bien que les algorithmes entropiques consomment bien moins de bits que leur pendant naïf. Pour l'algorithme entropique le nombre de bits consommés est une fonction linéaire de l'entropie contrairement au cas naïf (x Ñ x ?x). Dans le cas entropique, la constante d'entropie est proche de 95. Cette constante aussi importante est dû au modèle considéré : les graphes Fork-Join non-étiquetés. En moyenne ces graphes sont assez déséquilibrés : le graphe interne gauche est bien plus petit que le droit, ou l'inverse. Or ces cas correspondent aux pires pour l'algorithme R C , comme on le voit sur la figure 3.8. F 3.8 -Consommation de bits aléatoires de l'algorithme R C pour des combinaisons de 10000 éléments Par ailleurs, on voit sur la figure 3.8 que les sauts du nuage de points correspondent à des sauts aussi observés, mais dans une moindre mesure, dans la consommation de bits de l'algorithme k-B (cf. figure 3.9). Enfin, pour l'algorithme k-B

  figure 4.2 décrit les quatre règles de la décomposition. Les trois premières règles consomment toutes un noeud du DAG à décomposer : les règles B et T consomment, respectivement, un noeud avec exactement un arc entrant et un noeud avec exactement un arc sortant. La règle I consomme un noeud avec exactement un arc entrant et un arc sortant. La dernière règle B

  numérique de la formule symbolique construite par la décomposition BITC (multipliée par n!) est le nombre d'extensions linéaires du DAG décomposé.La preuve de ce théorème repose sur deux arguments : la décomposition BITC décompose bien tous les DAGs intransitifs et les règles de calcul intégrale correspondent bien au calcul du volume du plongement.

Fait 3 :

 3 Soit un ordre partiel P . Chaque extension linéaire de P correspond à un tri topologique des noeuds de la couverture de P .Définition 26 (Plongement combinatoire): Soit un graphe dirigé G. Un plongement combinatoire de G est le graphe G dont chaque noeud est décoré par une permutation de ses arcs sortants.

  x i . Cette construction est trivialement surjective. De même, elle est clairement injective : si deux étiquetages croissants sont différents alors leurs extensions linéaires correspondantes le sont aussi. C'est donc une bijection. La partie gauche de la figure A.1 donne un étiquetage croissant correspondant à l'extension linéaire a ĺ c ĺ b ĺ e ĺ f ĺ d ĺ g. rappelons les relations classiques entre les transformées de Laplace et de Borel usuelles et leur versions combinatoire.

  aussi connue sous le nom de A032035 dans OEIS (Online Encyclopedia of Integer Sequence). Or, cette suite énumère aussi les graphes cactus triangulaires avec ponts, enracinés et croissants. Commençons donc par vérifier que les deux classes d'objets ont bien la même série génératrice. Un graphe cactus est un graphe connexe, tel que toutes paires de cycles de ce graphe a au plus un noeud en commun.

	p1, 1, 1, 3, 13, 77, 573, 5143, 54025, 650121, 8817001, 133049339, . . . q
	Définition 2:

Dans notre cas, les graphes que nous considérons sont aussi : enracinés : le noeud d'étiquette 1 est distingué des autres et appelé racine, croissants : les graphes sont dirigés, chacun de leurs noeud a une étiquette différente de celles des autres. De plus, les étiquettes le long d'un chemin d'un graphe sont ordonnées de manière croissante triangulaires avec ponts : les cycles sont de taille deux (des arcs) ou trois (des triangles). Un exemple de tel graphe cactus est donné page 20. Enfin, on peut donner une spécification d'une telle classe G de graphes :

  Même si cette spécification est valable dans les cas étiquetés ou non, elle s'interprète plus facilement dans le cas non-étiqueté. Chaque entier est représenté par une séquence d'au moins un atome (S ě1 pZq) et la séquence de ces entiers représente la composition.À l'aide de l'opérateur d'ensemble ordonné, on peut donner une spécification "plus" étiquetée des compositions d'entiers. Dans ce contexte, il nous semble plus naturelle de représenter un entier k par un ensemble de k atomes étiquetés de 1 à k. Alors, une composition d'entiers devient un ensemble ordonné d'ensembles d'atomes étiquetés :

	. PRODUITS ORDONNÉ ET COLORÉ PROPRIÉTÉS FONDAMENTALES ET
	EXEMPLES	51
	Compositions d'entiers
	Une composition d'un entier n est une suite d'entiers strictement positifs dont la somme
	vaut n. Une façon de manipuler combinatoirement les compositions d'entiers est de spécifier
	leur classe non-étiquetée ainsi
	S pS	pZqq.
	ě1
	S ‹ pS

ě1

pZqq.

  avec α « 15.7042 . . . et β « 0.136896 . . . . Démonstration. Le premier asymptotique est obtenu par application direct du théorème 13. Le terme rz n se z `ze 2z étant négligeable devant celui de B c ´1 1´LcpBpzqq

	. . PRODUITS ORDONNÉ ET COLORÉ PROPRIÉTÉS FONDAMENTALES ET
	EXEMPLES				53
	-L'asymptotique de la moyenne du nombre d'étiquetages croissants de séquences de
	diamants binaires de taille n est
			rz n s Opzq rz n s p1 ´Dpzqq	´1 " nÑ8	6 D 1 pσq	σ n`1 ¨pn `1q! ρ n`2
	σ " 1 6 p	? 13 ´1q est une solution Dpzq " 1, et D 1 pσq "	?	13{σ.
	On peut approximer ces constantes ainsi
			rz n s Opzq rz n s p1 ´Dpzqq ´1 " nÑ8	α ¨βn`1 ¨pn `1q!
	Théorème 15:	-L'asymptotique du nombre d'ensembles ordonnés de diamants binaires
		croissants de taille n est équivalent au nombre de diamants binaires croissants :
				n! rz n sO " nÑ8	n! rz n sB.

  x |γ| |γ|! F pxq " Bpxq Apxq`Bpxq . En supposant que nous disposions de générateur de Boltzmann pour A et B, on en déduit donc l'algorithme 1 qui construit un générateur ΓrFspxq à partir de générateurs ΓrAspxq et ΓrBspxq. Générateur de Boltzmann de F " A `B et de paramètre x Générateur de Boltzmann de F " A ‹ B et de paramètre x

	Algorithme 2 function ΓrFspxq
	return pΓrAspxq, ΓrBspxqq
	De même, on peut dériver les algorithmes pour les opérateurs standards S , S et C . On
	trouvera le détails de ces algorithmes dans l'article original [DFLS04].
	x |γ| |γ|! pApxq`Bpxqq . Remarquons que la probabilité que γ soit dans A est
		P x pγ P A|γ P Fq "	ÿ ně0	ÿ γPF ^|γ|"n	x n n! pApxq `Bpxqq
		"	ÿ ně0	a n	x n n! pApxq `Bpxqq
		"	Apxq Apxq `Bpxq	.
	Algorithme 1 function ΓrFspxq
	if B	´ApXq Apxq`Bpxq ¯then
	return ΓrAspxq
	else
	return ΓrBspxq
	Dans le cas du produit, c'est-à-dire F " A ‹ B, l'algorithme est encore plus simple. Il suffit
	d'observer que
		P x ppα, βqq "	x |α|`|β| p|α| `|β|q! F pxq
		"	x |α|`|β| p|α| `|β|q! pApxq ¨Bpxqq
		"	1 `|α|`|β| |α| ˘x|α| |α|! Apxq	x |β| |β|! Bpxq	.
	Le coefficient binomial `|α|`|β| |α| ˘étant la conséquence du fait que nous travaillons avec des objets
	étiquetés. On peut donc directement dériver l'algorithme 2 de cette égalité.

De la même façon, on calcule P x pγ P B|γ P Fq "

  Notons que C P est aussi un sous-ensemble convexe car il est défini comme une intersection d'ensembles convexes.

	88	CHAPITRE . OUVERTURE ORDRES PARTIELS SANS CYCLE
	Remarque 7:
		,j X C

  de noeud mais "déplie" ce qu'on appelle des cycles de taille paire, où la notion de cycle est relative au graphe de comparabilité.À chaque règle de décomposition correspond une formule intégrale (donnée sous la description de la règle dans figure 4.2). Ces formules permettent de calculer le nombre d'extensions linéaires du DAG à décomposer. La décomposition commence avec Ψ " 1, puis tant que le DAG n'est pas réduit à un noeud, une des règles de décomposition est appliquée, où Ψ 1 est la formule après cette étape. Quand il ne reste plus de noeud à décomposer, la formule produite est close et donc évaluable numériquement.

		dy	Ψ 1 "	σ un ordre total ÿ	Ψ σ
				compatible
	F	4.2 -La décomposition BITC
	ne consomme pas

  Les résultats sont présentés dans la table 4.1. Pour les deux bases une proportion importante des DAGs sont BIT-décomposables. Pour ces DAGs en particulier nous avons autorisé au maximum 30 secondes pour calculer le nombre d'extensions linéaires selon la formule symbolique obtenue par la décomposition. Les calculs numériques sont délégués au logiciel de calcul formel Maxima. Au-delà d'une centaine de noeuds, les 30 secondes ne suffisent plus et accorder plus de temps ne change pas les résultats. Il est donc difficile de juger de la nature de la complexité du calcul numérique sous-jacent.2. http://www.graphdrawing.org/data.html

			7DAGs 7sans cycle	Comptage (max 30s)
	T	DAG	1297	740 (« 57%) 737 (« 57%)
	DAG-	910	727 (« 80%) 413 (« 45%)
		T	4.1 -DAG databases benchmark

  1 " B c p1{zf p1{zqq. Encore une fois, ce changement de variable est une involution.Maintenant, concentrons nous sur les versions combinatoires de ces opérateurs. La transformée de Laplace combinatoire permet de faire le pont entre série génératrice exponentielle

	(	ř ně0 a n	z n n!	) et série génératrice ordinaire (	ř ně0 a n z n ). Plus précisément :
				L c	˜ÿ ně0	a n	n! z n	¸" ÿ

ně0 a n z n . 109

Les diamants que nous présentons n'ont pas de rapport avec d'autres graphes diamants que l'on peut rencontrer dans la littérature.

on pourra se référer à l'annexe B dans laquelle on rappelle les transformées de Laplace et Borel usuelles et leurs liens avec leur version combinatoire

Un cycle primitif n'est contenu par aucun autre cycle.

Définition 5:

La classe D des graphes Fork-Join est définie par le système symbolique suivant :

Algorithme 7 Générateur de Boltzmann de S pFq à partir de celui de F function ΓrS pFqs(x) k Ð G pF pxqq Ź PpG ppq " kq " p k´1 p1 ´pq return le n-uplet pΓrFspxq, . . . , ΓrFspxqq de taille k où G désigne la loi géométrique.

Algorithme 11 Algorithmes de mélange et partitionnement uniformes function S (S, p, q) , r :" r s, r s i :" 0 v :" RandomCombination(p, q) for all e P v do if e then append Sris to else append Sris to r return , r function S ( , r) t :" r s v :" RandomCombination(| |, |r|) for all e P v do if e then append pop( ) to t else append pop(r) to t return t l'ensemble ta, b, c, d, eu en deux sous-ensembles, l'un de taille 3 et l'autre de taille 2. Les deux algoritmes procèdent de la même façon : ils tirent aléatoirement une combinaison de p éléments parmi p `q, puis mélangent ou partitionnent en utilisant cette combinaison. Si l'on suppose l'uniformité de cet algorithme de génération de combinaison, on obtient alors la correction des algorithmes de génération uniforme d'extensions linéaires.

Théorème 16:

L'algorithme 9 et l'algorithme 10 génèrent aléatoirement une extension linéaire d'un ordre Série-Parallèle, de taille n, de manière uniforme. Leur complexité au pire cas est en Θpn 2 q (en nombre d'écritures mémoires). Leur complexité moyenne est asymptotiquement équivalente à :

Théorème Pour calculer la complexité moyenne, on procède de manière classique (cf. [START_REF] Flajolet | Analytic combinatorics[END_REF]). On extrait l'asymptotique du terme général de la série génératrice F ordinaire des graphes Fork-Join obtenu par la méthode symbolique :

L'asymptotique s'obtient par théorème de transfert (cf. Définition 24 (Graphe de comparabilité): Le graphe de comparabilité d'un ordre partiel P est le graphe, non dirigé, transitif G " pV, Eq où V est l'ensemble des éléments de l'ordre partiel et E est l'ensemble des arêtes, défini par E " px, yq P V 2 | x ĺ y _ y ĺ x ( .

Le graphe au milieu de la figure A.1 est le graphe de comparabilité de l'ordre partiel pris en exemple précédemment.

Par la suite, on se permettra d'omettre les directions des arcs dans les représentations graphiques des couvertures, en prenant la convention que les arcs sont dirigés de bas en haut.

Définition 25 (Extension linéaire): Soit pP, ĺq un ordre partiel. Une extension linéaire est un ordre total et strict pP, ăq (une relation binaire, antisymétrique, transitive et non réflexive) sur les éléments de l'ensemble de P et compatible avec la relation de P : @x, y P P, px ă yq ^py ă yq ^px " yq @x, y P P, x ‰ y ^x ĺ y ùñ x ă y On note LE pP q l'ensemble des extensions linéaires de P .

De ces formules sur les séries génératrices, on obtient facilement les identités suivantes :

z q " pB c f q 1 . Comme pour la transformée de Laplace usuelle, le produit de transformées de Laplace combinatoires peut être exprimé à l'aide du produit de convolution :

De manière équivalente :

Le produit ordonné (cf. chapitre 2) donne donc une interprétation combinatoire à cette convolution. On notera f ˚g le produit de convolution combinatoire