L'un des nombreux problèmes posés par S. Ulam concerne l'asymptotique du cardinal maximal d'une sous-suite croissante d'une permutation aléatoire uniforme de [1,n]. Ce problème est résolu, du moins au premier ordre, en 1979, indépendamment par Logan et Shepp à l'Ouest et par Kerov et Vershik à l'Est, dans leur étude de la forme limite des tableaux de Young sous la mesure de Plancherel. Il en ressort que la plus longue sous-suite croissante est de cardinal équivalent à 2√n. Des fluctuations en n^{1/6} autour de ce résultat, faisant intervenir la loi de Tracy-Widom, ont été montrées en 1999 par Baik, Deift et Johansson, dans un travail faisant date.

Auparavant, en 1972, à l'occasion du sixième Symposium de Probabilités et Statistiques à Berkeley, Hammersley, dans un exposé sur une liste de sujets qui lui paraissent porteur, propose une approche probabiliste pour attaquer ce problème, mettant en jeu un processus de Poisson homogène sur un carré (qui engendre la permutation uniforme). Cependant, Hammersley ne mène pas à bout cette approche dans son texte. C'est Cator et Groeneboom, en 2007, qui arrivent à l'exploiter pour retrouver l'asymptotique en 2√n. Nous présenterons cette approche dans un contexte un peu simplifié, qui permet de bien en appréhender le principe.

Nous verrons ensuite comment cette même méthode permet de résoudre au premier ordre le problème de percolation de dernier passage appelé "Corner Growth Model" et résolu par H. Rost en 1981 par la théorie des systèmes de particules.

Nous verrons dans la séance d'exercices comment des variantes de ces cas peuvent être traités par cette même méthode.

Le cours ne demande pas de prérequis de probabilités très sophistiqués.

Comment prouver qu’un algorithme est optimal ? Nous nous intéresserons à donner un sens à cette question, et à présenter des techniques classiques pour y répondre. Le cours se concentrera sur des problèmes qui ont des solutions algorithmiques rapides (il ne s’agit donc pas d’un cours de classe de complexités, P, NP, …) et l’on abordera la question pour la complexité pire cas et pour la complexité d’algorithmes probabilistes (randomized). On verra notamment les méthodes par comptage et par adversaire, la technique de Ben-Or et le principe de Yao.

Reconfigurer une solution d'un problème donné, c'est lui appliquer des opérations élémentaires successives sans quitter l'espace des solutions. Un tel besoin apparaît naturellement dans des situations dynamiques où une solution donnée est déjà en place et doit être modifiée, sans qu'une rupture de service puisse être envisagée. C'est également un outil utile pour l'énumération ou le sampling uniforme de solutions. Plusieurs grandes questions sont étudiées : quelles opérations élémentaires garantissent que toute autre solution peut être ainsi atteinte ? À opérations fixées, quelle est la complexité de décider si une autre solution donnée peut être atteinte ? Que dire du nombre d'opérations nécessaires pour cela ?

Dans cet exposé, nous discuterons de divers résultats positifs et négatifs dans le cas particulier de la coloration de graphes.

Les nombres eulériens mixtes ont été introduits par Alex Postnikov dans un contexte de géométrie des polytopes. Ils forment une famille d'entiers avec une riche combinatoire, et incluent en particulier les coefficients binomiaux et les nombres eulériens classiques. Nous expliquerons ici comment obtenir ces nombres à partir d'un simple processus probabiliste. Cela permet d'en définir naturellement une q-déformation polynomiale, raffinant ainsi les propriétés des nombres initiaux. Si le temps le permet, nous expliquerons aussi leur relation avec un certain problème de calcul de Schubert, qui était notre motivation initiale. Travail en commun avec Vasu Tewari, Université de Hawaï.