Dimitri Watel: Cette présentation présente des notions de complexité algorithmique et de bases de cycles dans les graphes, ces notions seront introduites aussi pédagogiquement que possible. On s'intéresse à un problème de graphes appliqué en chimie moléculaire. On souhaite prévoir l'évolution d'une molécule en terme d'énergie potentielle ou de forme. Pour cela, on peut passer par le calcul d'une base de cycles de poids minimum dans le graphe de la molécule. La difficulté est que les liaisons et donc les cycles de la molécule peuvent changer au cours du temps. Il faut donc chercher, pour chaque état de la molécule, une base de cycles différente ; pour caractériser au mieux la molécule, ces bases de cycles doivent se ressembler le plus possible. Cela nous amène au problème suivant : connaissant k graphes G1 G2 … Gk, trouver pour chaque graphe Gi une base de cycles de poids minimum Bi de sorte à maximiser le nombre de cycles appartenant à toutes les bases. La présentation s'intéressera à la difficulté théorique de résoudre ce problème. On verra en particulier qu'il est peu probable qu'il existe un algorithme polynomial pour le résoudre dans le cas général ; mais qu'il existe des cas particuliers où un tel algorithme existe.

Hugo Marival: The Importance Markov chain is a novel algorithm bridging the gap between rejection sampling and importance sampling, moving from one to the other through a tuning parameter. Based on a modified sample of an instrumental Markov chain targeting an instrumental distribution (typically via a MCMC kernel), the Importance Markov chain produces an extended Markov chain where the marginal distribution of the first component converges to the target distribution. For example, when targeting a multimodal distribution, the instrumental distribution can be chosen as a tempered version of the target which allows the algorithm to explore its modes more efficiently.
We obtain a Law of Large Numbers and a Central Limit Theorem as well as geometric ergodicity for this extended kernel under mild assumptions on the instrumental kernel. Computationally, the algorithm is easy to implement and preexisting librairies can be used to sample from the instrumental distribution.

Marc Escudier: The estimation of an unobservable process x from an observed process y is often performed in the framework of Hidden Markov Models (HMM). We propose to use a more general model called Pairwise Markov Models (PMM) by assuming that the pair $(x, y)$ is Markovian, to obtain a prediction of $x$ by $y$. We will focus on the particular case of a gaussian, stationary, reversible PMM for which it is easy to write the expression of the prediction and the associated mean squared error. Using a recursive calculation, some plots describing the variation of the prediction error as a function of the covariances will be presented and compared to the prediction error for the HMM.