On présentera des outils combinatoires, pour partie classiques, permettant de dénombrer les permutations sans sous-suite croissante de longueur k : correspondance de Robinson-Schensted, tableaux de Young, pour arriver à la formule déterminantale de Gessel comptant les permutations en question. On évoquera aussi les liens avec l'énumération des *involutions* sans longue sous-suite croissante.

Le but de ce mini-cours est d'introduire et d'illustrer des méthodes pour l'étude des systèmes désordonnés en mécanique statistique, sur l'exemple de modèles de polymères dirigés en interaction avec un environnement aléatoire. Le polymère est décrit comme une marche aléatoire simple sur le réseau, collectant des récompenses aléatoires disposées sur son chemin (marche aléatoire dans un potentiel dépendant du temps et de l'espace). Le modèle est donné par une mesure de Gibbs, qui interpole entre la loi uniforme sur l'ensemble des trajectoires possibles, et la géodésique du problème de percolation orientée de dernier passage. Si les récompenses sont suffisamment fortes, le polymère adopte un comportement totalement différent de celui de la marche aléatoire sous-jacente, afin de profiter des environnement favorables. Cela donne lieu à une transition de phase, entre phases localisée et délocalisée. Si le modèle est compliqué sur le réseau Z^d, il est explicitement résoluble sur l'arbre. (Exercices!!) Une application combinatoire sera donnée dans le cadre de la ρ-percolation : en chaque site du réseau N^(d+1) est placé un 0 ou un 1 aléatoirement, et l'on s'intéresse au nombre N(n) de chemins orientés (arêtes nord ou est) de longueur n pour lesquels la densité de 1 est au moins ρ (1 > ρ > p avec p la probabilité de tirer un 1). Nous déduirons des estimations de N(n). Quelques mots clés: 1- Mesures de Gibbs, energie (libre), entropie, diagramme de phases, transition de phases, percolation, polymères. 2- Méthode du second moment, martingales, inégalités de concentration, séries génératrices, inégalités de corrélation FKG.

1. Introduction
   1. Environnements distribués
   2. Modèle de système distribué et mesures de complexité
   3. Protocoles d'élection (rupture de symétrie) sur l'anneau
   4. Bilan de l'élection sur les anneaux avec identités
2. Algorithmes et protocoles fondamentaux (avec identités)
   1. Problèmes (E)-(AR)-(ARM)-(D) sur des réseaux quelconques
   2. Influence de l'information structurelle (SD) dans les réseaux
   3. Coût de l'orientation (SD) d'un réseau
   4. Coloration des sommets d'un graphe (autre rupture de symétrie)
3. Introduction aux réseaux anonymes
   1. Théorèmes d'impossibilité dans les réseaux anonymes
4. Introduction à l'algorithmique des réseaux sans fils
   1. Réseaux sans fils (anonymes)
   2. Réseaux radio, réseaux -- Réseaux de capteurs
   3. Protocoles dans les réseaux radio
5. \'Election quasi optimales dans les réseaux radio
   1. Deux algorithmes quasi optimaux, efficaces en énergie
   2. Complexité des deux algoritmes d'élection
6. Graphes géométriques aléatoires et réseaux sans fils
   1. Réseaux radio et graphes G(n,r)
   2. Protocole d'initialisation
   3. Analyse d'un algorithme d'élection
7. Convergence d'algorithmes d'élection
   1. Théorème général de convergence
   2. Généralisation du théorème
   3. Illustrations
   4. Applications à des variantes de Franklin

On s'intéressera au rang de la matrice d'adjacence d'un graphe aléatoire. On présentera des formules sur l'asymptotique du rang lorsque la taille du graphe tend vers l'infini. Cette question est étroitement reliée à la taille asymptotique d'un appariement maximal dans le graphe. On redémontrera une formule célèbre de Karp et Sipser sur les appariements maximaux des graphes d'Erdös-Rényi. Travail en collaboration avec Marc Lelarge (ENS, INRIA).

La structure des graphes aléatoires de types Erdös-Rényi change brutalement lorsque le degré moyen est proche de 1. Un des paramètres importants de ce type de graphes est la distribution des distances entre les noeuds. Lorsque le degré moyen est assez éloigné de 1, de nombreux résultats décrivent cette distribution et en particulier le diamètre des graphes. Dans la zone critique, lorsque le degré moyen est proche de 1, la structure des graphes devient plus complexe et les approches classiques de théorie des graphes ne permettent pas de caractériser précisément les distances. Lorsqu'il s'agit de distances, il s'avère pratique de voir un graphe comme un espace métrique. Nous verrons dans quelle mesure la distance de Gromov--Hausdorff permet de définir la convergence de graphes en tant qu'espaces métriques. Nous verrons aussi une méthode basée sur les combinatoires (bijection) et les probabilités (convergence faible, excursion Brownienne) qui permet de définir un objet limite pour les graphes aléatoires où le degré moyen est proche de 1. La distribution des distances dans les grands graphes se lit directement sur l'objet limite.

Les "configurations de boucles compactes" (FPL en anglais) sont des objets combinatoires formés de chemins dans une grille carrée, ne s'intersectant pas et "remplissant" la grille. Leur énumération est connue grâce à une bijection simple avec les matrices à signes alternants. Depuis quelques années un certain nombre de combinatoriciens cherchent à les compter selon les "schémas de couplage" qui décrivent la façon dont les chemins entrent et sortent de la grille, afin de démontrer une conjecture dûe aux physiciens Razumov et Stroganov, et qui s'exprime naturellement en termes de FPL aléatoires. Dans cet exposé, je me concentrerai sur les questions de génération aléatoire ou exhaustive de telles configurations. Lorsque l'on s'intéresse à l'ensemble de toutes les configurations d'une taille donnée, la génération exhaustive est simple, et la génération aléatoire uniforme est bien maitrisée (hors l'analyse de complexité qui reste à affiner) grâce à l'algorithme du "couplage depuis le passé" de Propp et Wilson. En revanche, la génération exhaustive efficace des configurations présentant un schéma de couplage donné, repose encore sur des hypothèses non démontrées.

Je présenterai un certain nombre de résultats récents décrivant la statistique des distances dans les grandes cartes planaires : distance entre deux sommets choisis uniformément au hasard, distances mutuelles entre trois sommets, et pour les cartes à bord: distance au bord ou entre deux sommets du bord. Je montrerai dans le cas particulier des quadrangulations comment accéder à ces propriétés statistiques au moyen de bijections avec des cartes "bien-étiquetées", et comment calculer exactement les fonctions génératrices de ces cartes grâce à un ensemble de formules explicites pour quelques "briques" combinatoires. Je décrirai enfin la limite universelle de ces lois statistiques dans le cas des cartes de grande taille.

Une suite de Fibonacci aléatoire (F_n)_n est définie par ses deux premiers termes, F_0 et F_1, et par la relation de récurrence F_n=|F_{n-1}\pm F_{n-2}|, où pour chaque n le signe \pm est déterminé par le résultat du lancer d'une pièce de monnaie suivant une loi de Bernoulli de paramètre p. Dans le cas p=1/2, Divakar Viswanath a montré en 1999 que presque toute suite de Fibonacci aléatoire se comporte asymptotiquement comme une suite exponentielle de facteur de croissance 1,1319... Ce facteur se calcule à l'aide de l'intégrale d'une fraction rationnelle le long d'une mesure explicite. Nous présentons ici une simplification et deux extensions de ces travaux, obtenue avec Thierry de la Rue et Élise Janvresse (CNRS - Université de Rouen), qui concernent les cas où p est quelconque ainsi que certaines généralisations des suites de Fibonacci aléatoires.

Nous apprenons tous à nos étudiants que la complexité moyenne de QuickSort (algorithme rapide de tri de $n$ clés) est en O(n log n), et que celle de QuickSelect (algorithme rapide qui trouve la clé de rang $m$ parmi $n$ clés) est en O(n). Ces analyses prennent en compte uniquement le nombre de comparaisons (entre clés) et non pas le nombre total de comparaisons entre symboles nécessaires pour effectuer ces comparaisons entre clés. Cet exposé présente l'analyse en moyenne de QuickSort et de QuickSelect quand l'unité de mesure est la comparaison entre symboles. Alors, la complexité moyenne de QuickSort n'est plus en O(n log n) et devient en O(n log ^2 n), tandis que celle de QuickSelect reste en O(n).

Given m sequences, what is the average length of the longest common part, of the second largest...? What is the average length of the last common suffix? For any size of the alphabet and any distribution of the letters, this question is covered by a variant of a famous model in population biology (the Moran model), which in turn can be converted into a random walk model in dimension m (with infinite negative drift, constrainted to remain nonnegative), indeed the maximal height of the walk gives the length of longest common part, and the final height gives the length of the last common part.

Un chemin auto-évitant sur le réseau carré est un chemin ne visitant pas deux fois le même sommet. Compter les chemins auto-évitants de longueur arbitraire est très difficile, et à l'heure actuelle seules des conjectures asymptotiques sont connues. Notre but sera de définir des classes naturelles de chemins auto-évitants à la fois grandes et qu'il soit possible de compter. Jusqu'à présent, la classe connue la plus grande est celle des chemins dits prudents trilatères (comptés par Bousquet-Mélou), avec une constante de croissance de 2,48. Nous présenterons deux nouvelles classes de chemins, basées sur l'idée de chemins dirigés, que nous avons pu dénombrer. Nous montrerons que leur constante de croissance est d'environ 2,54.

Les suites D-finies (on dit aussi "holonomes" ou "P-récursives") sont les suites a_n telles que la série génératrice A(z)=sum a_n z^n vérifie une équation différentielle linéaire à coefficients des polynomes en z. Il est équivalent de dire que a_n vérifie une récurrence linéaire à coefficients des polynomes en n ("polynomialement récursive, ou "P-récursive"). Les suites D-finies sont la plus importante classe de suites en combinatoire : la plupart des structures combinatoires sont énumérées par une suite holonome, elles apparaissent également en théorie des nombres, en bioinformatique, en physique statistique... par ailleurs, elles jouent un rôle fondamental en calcul formel (de par de nombreuses propriétés de clotures, au coeur de la preuve automatique de jolies identités). L'asymptotique d'une suite D-finie est du type : C A^n n^e où A est appelée la "constante de croissance", et e "exposant critique" (notamment chez les physiciens). Il existe diverses méthodes permettant de trouver A et e (qui sont typiquement des nombres algébriques), mais il demeure un problème ouvert d'accéder à C, d'avoir des renseignements sur sa nature et même de décider si C=0 !!! Très souvent, pour ce qui est de cette mystérieuse constante, les gens n'en donnaient qu'une approximation (quelques dizaines de chiffres dans les meilleurs des cas). Je montrerai ici comment on peut, pour une infinité de récurrences, accèder à la constante C, en donnant soit une formule explicite, soit un schéma numérique très rapide qui permet d'obtenir des milliers de chiffres de C en quelques secondes.

On étudie la classe des "pin-permutations" (ou permutations en épingles) qui sont celles possédant une représentation en épingles. Cette classe a été définie récemment dans une série d'articles de Brignall et al., où elle est utilisée pour rechercher des propriétés d'autres classes de permutations (algébricité de la série génératrice, décidabilité de l'appartenance à la classe), en fonction des permutations simples contenues dans ces classes. On donne une caractérisation des arbres de décomposition des permutations en épingles, qui nous permet de calculer la série génératrice de cette classe, prouvant ainsi la conjecture de Brignall concernant le caractère rationnel de cette série génératrice. En outre, on prouve que la base de la classe des permutations en épingles est infinie.

Je décrirai deux moyens de construire des cartes de genre g. La première, en "mélangeant" ensemble deux cartes polygonales de genre g1 et g2 telles que g1+g2=g. La seconde via le recollement bord à bord d'un arbre plan et d'une carte polygonale bipartie de genre g. Notre résultat principal est une bijection montrant que les objets obtenus par les deux méthodes sont les mêmes, qui généralise la bijection de Bernardi pour les cartes boisées planaires. On en déduira une nouvelle identité combinatoire, faisant le lien entre des formules connues jusque là par des méthodes abstraites.

Nous introduisons une chaîne de Markov à valeur dans les laminations géodésiques hyperboliques du disque unité. En faisant varier le paramètre d'autosimilarité de ces chaînes, nous obtenons différents modèles d'arbres croissants avec des comportements très différents. Cette approche permet de retrouver des résultats connus par les physiciens pour les modèles de structure secondaire d'ARN et des modèles dits "splitting-tree". Les résultats reposent sur la théorie des fragmentations de J. Bertoin.

En raison de leurs bonnes propriétés algorithmiques, les automates déterministes sont très souvents utilisés pour représenter en machine les langages rationnels. L'automate minimal d'un tel langage est l'unique plus petit automate déterministe qui le reconnaît. Pour le pire des cas, le meilleur algorithme connu pour calculer l'automate minimal est en O(n log n). Nous montrons qu'un autre algorithme, l'algorithme de Moore, qui est beaucoup plus simple à implanter mais souvent écarté à cause de sa complexité en O(n^2) dans le pire des cas, est de complexité O(n log n) en moyenne.

Les modèles de chaîne de Markov permettent de modéliser facilement un très grand nombre de systèmes aléatoires. Malheureusement, dès que le nombre d'acteurs dans ce système grandit, la complexité calculatoire devient rédhibitoire. Pour palier à ce problème, l'étude en champs moyen (en anglais Mean Field) permet de se ramener à un système déterministe lorsque le nombre d'acteurs devient grand. Les processus de décision markovien sont des modèles de décision lorsque le système est soumis à un aléa. A travers cet exposé, nous étudierons des propriétés de limites permettant de simplifier grandement l'optimisation des systèmes. Nous montrerons aussi des résultats de vitesse de convergence type théorème de la limite centrale.

Dans le système restreint à l'implication, nous avions présenté le résultat suivant : asymptotiquement, les logiques classique et intuitionniste sont identiques. Durant cet exposé, nous allons enrichir le système propositionnel et nous observerons quel connecteur engendre la modification suivante : asymptotiquement dans le système propositionnel complet, 5/8ème de la logique classique est intuitionniste.

Un modèle d'attachement préférentiel peut être vu comme un modèle d'urnes où la probabilité qu'une nouvelle boule tombe dans une urne dépend du remplissage des urnes. Ces modèles s'utilisent en physique, en démographie et en informatique, par exemple pour l'étude du graphe du web. Cet exposé présentera quelques résultats existants et décrira un nouveau modèle où le nombre d'urnes peut augmenter. Dans un cas particulier, ce modèle peut être résolu exactement et ses asymptotiques peuvent être calculées.

Apparus il y a quelques années, les tableaux de permutation sont un moyen pratique de décrire une permutation, en tant que diagramme de Young rempli de 0 et de 1 et évitant certains motifs. De nombreuses statistiques sur les permutations se lisent dans les tableaux de permutations : descentes, excédences, nombres de cycles, croisements... Une série génératrice bivariée sur les tableaux à permis d'obtenir un q-analogue des polynômes eulériens. Le but de cet exposé est de présenter cette série génératrice et quelques applications.

Nous introduisons un modèle d'épidémie qui généralise à la fois le modèle SIR et la 'bootstrap percolation'. Nous analysons ce processus sur des graphes aléatoires dilués. Ceci nous permet de retrouver des résultats connus (taille de la composante géante, seuil de percolation) et nouveaux (condition de cascade, impact de différentes vaccinations). Les preuves reposent sur des idées de couplages développées récemment par Janson.

The following dice game has been partially analyzed in the litterature. A player rolls a fair die successively, accumulating the scores so long as the outcome 1 does not occur. But should a 1 arise, the accumulated score is wiped out, and the turn ends. At any stage after a roll, she can choose to end her turn and bank her accumulated score. Several gambers in turn perform series of rolls. We present some results on optimal strategies and winning probability in a two players game.

A general tree algorithm processing a random flow of arrivals is analyzed. Capetanakis-Tsybakov-Mikhailov's protocol in the context of communication networks with random access is an example of such an algorithm. In computer science, this corresponds to a trie structure with a dynamic input. Mathematically, it is related to a stopped branching process with exogeneous arrivals (immigration). Under quite general assumptions on the distribution of the number of arrivals and on the branching procedure, it is shown that there exists a positive constant $\lambda_c$ so that if the arrival rate is smaller than $\lambda_c$, then the algorithm is stable under the flow of requests, i.e. that the total size of an associated tree is integrable. At the same time a gap in the earlier proofs of stability of the literature is fixed. When the arrivals are Poisson, an explicit characterization of $\lambda_c$ is given. Under the stability condition, the asymptotic behavior of the average size of a tree starting with a large number of individuals is analyzed. The results are obtained with the help of a probabilistic rewriting of the functional equations describing the dynamic of the system. The proofs use extensively this stochastic background. In this analysis, two basic limit theorems play a key role: the renewal theorem and the convergence to equilibrium of an auto-regressive process with moving average.

La génération aléatoire uniforme d'objets combinatoires ayan une composition prédéterminée en ses $k$ types d'atomes est motivée par l'étude des séquences et structures génomiques. Les meilleurs algorithmes existants pour engendrer m objets de ce type ont pour complexités $O(m.n^{k-1})$ pour les langages rationnels (Thèse de Radicioni) et $O(m.n^k)$ (Denise, Roques et Termier) et reposent sur des précalculs complexes ou coûteux. Dans ce travail collaboratif avec O. Bodini, nous étendons la génératio de Boltzmann à la celle d'objets de composition fixée ou approchée. Pour cela, nous commençons par généraliser la génération de Boltzmann aux structures combinatoires pondérées, introduites par (Denise, Roques et Termier). Nous supposons ensuite acquises des pondérations adéquates pour que les objets engendrés aient "en moyenne" la composition visée. Nous enchaînons enfin deux étapes de rejet, respectivement selon 1) La taille des objets engendrés puis 2) Leur composition. Dans le cas des grammaires de type simple et pour des tailles et compositions (raisonnables) exactes, les générateurs ainsi obtenus ont des complexités de l'ordre de $O(m.n^{2+k/2})$ sans autre étape de précalcul que celle de l'oracle de Boltzmann et des pondérations. Pour une tolérance de $\varepsilon n$ sur la taille et $\varepsilon n^{1/2}$ sur les nombres de chacun des $k$ d'atomes, les générateurs obtenus sont linéaires. Nous discuterons des extensions possibles de ces travaux aux classes décomposables générales, évoquerons les méthodes possibles pour calculer les pondérations, ainsi que les performances des étapes de rejet pour des compositions visées "pathologiques".

Les arbres m-aires de recherche peuvent être vus comme des urnes de Polya, et lorsque $m > 26$, l'asymptotique du vecteur composition de l'urne n'est pas gaussien. Pour identifier la loi de la limite de martingale qui apparaît, on utilise un plongement en temps continu qui fait apparaitre un processus de branchement. Ce sont les équations de dislocation écrites pour ce processus qui donnent un système différentiel sur la série de Laplace de la loi mystérieuse, qui va permettre de l'identifier.

Nous considérons un graphe où les cellules sont caractérisées par un état qui est soit noir, soit blanc. À chaque pas de temps, une cellule, choisie aléatoirement, se met à jour et passe dans l'état minoritaire dans son voisinage. L'évolution globale de ce processus ne semble pas dépendre de la topologie du graphe: dans un premier temps des régions, pavées par des motifs dépendant de la topologie du graphe, se forment rapidement. Puis dans un deuxième temps, les frontières entre ces régions évoluent jusqu'à devenir relativement stables. Nous étudions ce processus sous différentes topologies: arbres, anneaux, grilles, cliques. Ceci nous permet de montrer que même si ce processus se comporte à priori globalement de la même manière sur n'importe quel graphe, modifier la topologie influence la façon dont les régions sont pavées (rayures, damiers), la structure et les mouvements des frontières entre les régions, l'ensemble limite, le temps de relaxation (le temps nécessaire pour que le processus atteigne une configuration de l'ensemble limite). Ainsi, Minorité entraîne des comportements riches et variés qui se révèlent difficile à analyser. Comprendre cette règle simple est néanmoins nécessaire avant de considérer des règles plus compliquées.

Le travail introduit une nouvelle mesure de stabilité de consensus de résultats donnés par un ensemble de capteurs. Cette mesure s'appuie sur une moyenne liée à un processus Markovien simple. Nous comparons le cas sans mémoire et le cas avec mémoire.

Le modèle de Boltzmann, introduit par Duchon, Flajolet, Louchard et Schaeffer, est une approche très agréable et très puissante pour générer de façon efficace des structures combinatoires. Dans ce formalisme, seules certaines constructions sont autorisées (le produit, la séquence, ...). Le but de notre travail a été d'ajouter un opérateur -- l'opérateur boîte -- à la liste des constructeurs admissibles dans ce cadre. Il s'agit d'un opérateur bien connu en combinatoire qui permet de construire des objets ayant des contraintes internes d'ordre, des structures ordonnées. Quelques exemples de tels objets sont les permutations alternantes, les arbres croissants, certaines partitions d'ensembles ou d'entiers. Je présente donc l'idée principale qui a permis d'étendre le modèle de Boltzmann à cet opérateur, les détails de sa réalisation, et les problèmes qui apparaissent.

Cet exposé utilise le plongement d'une urne de Polya, en temps continu, pour retrouver la relation entre les lois limites des modèles à temps continu et celles des modèles à temps discret. Plusieurs arguments laissent penser que les lois limites des urnes dans le modèle continu sont infiniment divisibles. Nous verrons, à travers l'exemple des urnes triangulaires balancées à deux couleurs, que les lois limites qui apparaissent dans les grandes urnes sont déterminées par leurs moments (qui sont connus sous forme close) et qu'elles ne sont, en général, pas infiniment divisibles. Dans certains cas, la loi limite sera donnée par sa densité.

La question de l'importance de l'aléatoire est une des questions centrales en théorie de la complexité actuellement. C'est par l'apport de la théorie des probabilités que les avancées les plus significatives ont été possibles en informatique mathématique ces dernières années. Je vous propose de faire un tour de ces questions en vous présentant l'historique (de la cryptographie des années 70 à la théorie de la complexité des années 90-00), les techniques qui ont été mises au point pour explorer l'influence de l'aléatoire sur le calcul et surtout les liens qui ont été établis entre ces questions et les classes de complexité telles qu'on les connaît (question P!=NP et complexité de circuits).

La part de nos travaux récents présentée ici combine dans une même perspective d'attaque de problèmes modélisation markovienne et fonctions génératrices probabilistes. D'abord, on modélise avec des graphes génétiques les interactions entre gènes (les sommets), chaque gène à l'origine d'une arête agissant (positivement ou négativement) sur le gène à l'extrémité. Une question intervenant en biologie est la rareté ou l'abondance de sous-graphes (motifs génétiques), ce qui suppose un modèle probabiliste permettant de construire ces graphes. Ainsi se posent un problème pratique: compter les nombres d'occurrences de motifs topologiques fixés, et un problème théorique : décider si ces nombres d'occurrences indiquent rareté, abondance, ou normalité de l'apparition de ces motifs. Nous nous intéressons ici exclusivement au problème pratique de préciser un algorithme de comptage de ces motifs, s'appuyant sur une représentation hiérarchique du graphe d'interactions génétiques. Les mêmes idées s'appliquent avec un investissement supplémentaire au dénombrement de motifs colorés (un tel graphe non orienté avec des sommets colorés représente alors des réactions chimiques: un motif coloré est un sous graphe connexe de topologie quelconque, avec des sommets en nombre fixé occupant une gamme chromatique fixée). Ensuite, on résout deux questions de temps d'attente d'un message diffusé dans un réseau (graphe non orienté connexe): - le problème de la "ruine du joueur avec excès k" associé à une diffusion dans un réseau linéaire: à droite (à gauche) avec la probabilité p (1-p); alors qu'une modélisation markovienne classique donne juste la valeur moyenne du nombre X d'étapes jusqu'à l'arrêt (k^2 dans le cas équiprobable), la formulation ici du langage associé à l'automate donne dans le cas général via la fonction génératrice probabiliste associée tous les paramètres de X (espérance mathématique, variance, probabilité d'une valeur n...) - le temps d'attente moyen hii de retour au sommet émetteur i de degré d(i) d'un message diffusé selon une marche aléatoire équiprobable dans un réseau de e arêtes; si ce dernier est non biparti (i.e. admet au moins un cycle de longueur impaire, contrairement par exemple à une grille 2D de maille carrée) un calcul classique donne: 2*e/d(i), résultat qui se généralise ici de façon très différente à un réseau biparti ou non: en réécrivant par regroupement structurel lié aux degrés des sommets le système linéaire markovien des temps moyens d'attente hij des arrivées en i de messages issus de j; ceci s'applique aux grilles kD de maille carrée, graphes r-réguliers...