Une urne de Pólya est un processus stochastique décrivant la composition d'une urne contenant des boules de différentes couleurs. L'ensemble des couleurs est usuellement un ensemble fini {1, ..., d}. A chaque instant n, une boule est tirée uniformément au hasard dans l'urne (notons c sa couleur), remise dans l'urne accompagnée de R(c,i) boules de couleur i pour toute couleur i.
Je présente dans cet exposé une généralisation de ce modèle à un ensemble infini, et même potentiellement indénombrable de couleurs. Dans ce nouveau modèle, la composition de l'urne est une mesure (potentiellement non-atomique) sur un espace Polonais.
Ceci est un travail en collaboration avec Jean-François Marckert.[-]

Si l'hypothèse P $\neq$ NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l'obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question de SAT, de graphes, de complexité (classique et parfois paramétrée), de problèmes difficiles mais aussi de problèmes polynomiaux.[-]

We introduce a family of geometrical lattice models generalising the well-known loop model on the hexagonal lattice. These models have a $U_q(sl_n)$ quantum group symmetry, the loop model being the $n=2$ case. The general models give rise to branching webs and describe, at a special point, the interfaces in $Z_n$ symmetric spin models. We mainly discuss the $n=3$ case of bipartite cubic webs, which is based on the Kuperberg $A_2$ spider. We exhibit a local vertex-model reformulation, analogous to the well-known correspondence between the loop model and the nineteen-vertex model. The local formulation allows us in particular to study the model by means of transfer matrices and conformal field theory. We find that it has a rich phase diagram, including a dense and a dilute phase that generalise those known for the loop model. Based on joint work with Augustin Lafay and Azat Gainutdinov (arXiv:2101.00282 and 2107.10106).[-]

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.[-]

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.[-]