GT probabilité et informatique

Pour vous inscrire, c'est-à-dire recevoir les annonces des exposés et des différents événements :

- si vous faites partie du LaBRI https://www3.labri.fr/intranet/gt/script/index.php

- si ce n'est pas le cas, ou si c'est trop dur: envoyez moi un e-mail.


2013 - 2014

19 décembre 2013 à 14 h (Salle 178)
Xavier Pérez-Giménez (University of Waterloo)
Arboricity and spanning-tree packing in random graphs with an application to load balancing
We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the Erdös-Rényi random graph G(n,p). For all p(n) in [0,1], we show that, with high probability, T is precisely the minimum between δ and ⌊ m/(n-1)⌋, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals ⌊ m/(n-1)⌋ and A equals ⌈ m/(n-1) ⌉; and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k goes to ∞. This research is joint work with Pu Gao and Cristiane M. Sato.

14 novembre 2013 à 11 h
Thomas Selig (LaBRI)
Dessins de triangulations en pile
Les triangulations en pile sont les triangulations obtenues de manière récursive en partant d'un triangle et en insérant successivement des sommets dans des faces internes. Dans cet exposé, plutôt que de regarder l'aspect combinatoire de ces objets, nous nous intéressons aux propriétés de leurs dessins dans le plan, ceux-ci étant vus comme des sous-espaces compacts du plan. Nous définirons deux lois de probabilités sur les triangulations en pile, et nous étudierons certaines propriétés asymptotiques de leurs dessins sous ces deux lois.

7 octobre 2013 à 11 h
Hugo Gimbert (LaBRI)
The Value 1 Problem for Probabilistic Automata
The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? This problem was proved undecidable recently, even in the restricted case where the automaton has only one probabilistic transition. To overcome this undecidability result, subclasses of probabilistic automata of different nature were proposed in the literature, for which the value 1 problem is shown decidable. We introduce yet another class of probabilistic automata, called leaktight automata, which strictly subsume all subclasses of probabilistic automata whose value $1$ problem is known to be decidable. We prove that for leaktight automata, the value 1 problem is decidable (in fact, PSPACE-complete) by constructing an algorithm based on the computation of a monoid abstracting the behaviours of the automaton, and rely on algebraic techniques developed by Simon for the correctness proof.



2012 - 2013

1 juillet salle 178 à 14h
Eduardo Ferraz (Nancy et Rouen)
On random geometric simplicial complexes
Firstly, it will be presented the way how simplicial complexes can be defined in order to provide topological information about the coverage of a set of convex regions. Then, we consider a Poisson process on a d-dimensional torus, and we define its random geometric simplicial complex as the simplicial complex whose vertices are the points of the Poisson process and simplices are given by the Cech complex associated to the coverage of each point. Using concepts of algebraic topology and Malliavin calculus, we can obtain statistics concerning some topological properties of this random geometric simplicial complex.

27 mai salle 076 à 11h
František Kardoš (LaBRI)
Fractional colorings of cubic graphs with large girth (joint work with Dan Kráľ and Jan Volec)
We show that every (sub)cubic n-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978, which implies that it contains an independent set of size at least 0.4352n. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.

15 avril salle 076 à 11h
Valentin Féray (LaBRI)
Graphes de forte dépendance
Dans cet exposé nous nous intéressons aux graphes aléatoires d'Erdös-Rényi. Le problème consiste à décrire les fluctuations du nombre de triangles (ou d'occurrences d'un graphe fixé quelconque) quand la taille du graphe tend vers l'infini.
Le premier modèle de graphe aléatoire d'Erdös et Rényi consiste à fixer le nombre de sommets n et, pour chaque paire de sommets, les relier par une arête indépendamment avec probabilité p. Dans ce cas, il existe un outil classique permettant de répondre à la question ci-dessus : les graphes de dépendance. Dans la première partie de l'exposé, je présenterai cette théorie.
Un deuxième modèle de graphe aléatoire, aussi proposé par Erdös et Rényi consiste à fixer les nombres n et M de sommets et d'arêtes du graphe et à choisir uniformément un graphe à n sommets et M arêtes parmi toutes les arêtes possibles. Dans ce modèle, l'appartenance de deux arêtes différentes au graphe ne sont plus des événements indépendants. On ne peut donc plus utiliser les graphes de dépendance pour trouver les fluctuations du nombre de triangle. L'objectif de mon travail (encore en cours) est d'introduire la notion de graphe de forte dépendance qui généralise celle de graphe de dépendance et permet d'étudier ce deuxième modèle.

25 mars salle 076 à 11h
Guillem Perarnau (Universitat Politècnica de Catalunya)
A probabilistic approach to consecutive pattern avoiding in permutations
We present a new approach based on the probabilistic method, for the problem of enumerating permutations of length n that avoid a fixed consecutive pattern of length m. We use this approach to give alternative and shorter proofs for some known results as well as to provide new results that have not been shown using other techniques.

28 janvier salle 076 à 11h
François Caron
Modèles probabilistes et algorithmes d'inférence pour les graphes bipartis
Ces dernières années ont vu un intérêt croissant pour l'étude, la compréhension et la modélisation des réseaux/graphs complexes. Dans cet exposé, je propose un modèle probabiliste sur les graphes bipartis. Le modèle a notamment les propriétés suivantes: le nombre de noeuds de chaque type est très grand, potentiellement infini; pour certaines valeurs de paramètres, le graphe a des propriétés en loi de puissance; les paramètres du modèle peuvent être estimés de façon simple à l'aide d'un algorithme de Monte Carlo par chaine de Markov. Je montrerai également que ce modèle montre une bonne adéquation à plusieurs graphes bipartis réels. Référence: F. Caron. Bayesian nonparametric models on bipartite graphs. NIPS, 2012.

7 janvier salle 076 à 11h
Jean-Marc Vincent
Perfect Sampling of Non-monotone Markov Models
Perfect sampling techniques are widely applied for monotone Markov models. Monotonicity leads to efficient algorithms, only two trajectories are used to capture the dynamic of the process. Applied to queuing systems with index routing, the algorithm has a practical interest and is now used to compute performances of systems. Unfortunately, some classical events in queuing systems are not monotone, batch arrivals or services, join synchronizations, phase-type services break the monotonicity property. In this presentation, we propose two approaches to build a perfect sampler. The first approach consists in the computation of envelopes for the process, but envelopes modify the coupling time that could be, in some cases, arbitrary large. The second approach extend the state space of the process to make it monotone, this topic is still open, only ad-hoc solutions have been developed and applied for phase-type queuing systems. Most of these techniques have been implemented in the software psi, that could be used for a demo. This is a joint work with Bruno Gaujal and Ana Busic.

Le 12 novembre 2012 à 11 h salle 076 (LaBRI)
Jérôme Casse
Récurrence de la limite d'une suite de graphes planaires aléatoires enracinés uniformément et de degré uniformément borné et non-planarité de Z^3.
Il s'agit de mon mémoire de M2 effectué sous la direction de J.F. Le Gall à partir d'un article de I. Benjamini et O. Schramm.
Une marche aléatoire sur un graphe infini peut-être récurrente (elle visite presque sûrement infiniment souvent tout point du graphe) ou non (auquel cas elle est dite transiente). Sur Z^2 elle est récurrente, sur Z^3 transiente Pour faire court, on dit du graphe lui même qu'il est récurrent ou transient.
La récurrence est une propriété intéressante car elle permet d'en déduire d'autres sur le graphe comme par exemple le fait d'être de Liouville, i.e. toute fonction holomorphe bornée sur le graphe est constante.
L'objet principal de cet exposé est de montrer qu'un graphe (infini) qui est la limite d'une suite de graphes planaires aléatoires enracinés uniformément et de degré uniformément borné est récurrent. Nous expliquerons l'essence de ce résultat de nature combinatoire.
Une application et une "extension" seront évoquées: - nous donnerons une preuve simple du fait que Z^3 n'est pas planaire. - nous évoquerons le fait que la marche simple sur la triangulation planaire infinie uniforme est récurrente (O. Gurel-Gurevich et A. Nachmias, juin 2012).

15 octobre 2012 à 11 h salle 076 (LaBRI)
Philippe Duchon
Fontaines de Bernoulli et automates, d'apres Mossel et Peres
Le problème de la simulation exacte de variables de Bernoulli peut être vu de la manière suivante: étant donnée une pièce qui a probabilité p de tomber côté Pile, en simuler une qui ait probabilité q de le faire. Plus généralement, on peut vouloir "simuler" une fonction f au sens suivant: en décrivant un processus qui, sans connaître p, simule une Bernoulli de paramètre f(p) à partir d'une source de Bernoulli de paramètre p. La classe des fonctions "simulables" en ce sens, via des procédés a priori non algorithmiques, est connue; en 2005, Mossel et Peres ont entre autres montré que les fonctions simulables par un automate fini sont _exactement_ les fonctions rationnelles (sur Z) qui ne prennent que des valeurs strictement comprises entre 0 et 1 sur l'intervalle ouvert (0,1). Je présenterai leur preuve et diverses considérations connexes.

lundi 24 septembre à 11 h amphi du LaBRI
Jean-François Marckert
Convexes compacts du plan et théorie des probabilités.
Il s'agit d'un travail commun avec David Renault (LaBRI)
Existe-t-il une bonne notion de "convexe aléatoire" ? C'est en tournant autour de cette question que nous avons découvert un lien insoupçonné entre les notions de "compact convexe du plan" et "lois de proba. sur [0,2pi]".
Ce lien, connu dans un cadre non probabiliste depuis fort longtemps est très riche: il permet de re-découvrir, re-démontrer, et découvrir (tout court) certaines propriétés des convexes, et des opérations que l'on peut leur faire subir. Je m'attacherai à expliquer ces faits...
Dans une deuxième partie - très courte - j'expliquerai comment engendrer de "jolis" convexes aléatoires (non polygonaux).

Lundi 17 septembre 2012 à 11h salle 4 Bâtiment A29
Sean Cleary
Expected common edges in randomly-selected triangulations of n-gons
Rotation distance measures the difference in shape between two rooted binary trees and is equivalent to edge-flip distance between triangulations of polygons. The rotation distance question asks: given two trees of the same size, what is the minimum number of rotations to transform one tree to the other? The existence of common edges in the trees (or triangulations) makes instances of the problem more tractable by breaking the problem into several smaller problems. Here, we investigate the average extent to which randomly-selected triangulations of an n-gon have common edges and other features which make the edge-flip distance problem more tractable. This is joint work with Andrew Rechnitzer and Thomas Wong.



2011 - 2012

Lundi 12 mars 2012 à 11h salle 076
François Caron
Méthodes bayésiennes non paramétriques pour la classification non supervisée de données
Le processus de Dirichlet est un modèle Bayésien non paramétrique très populaire en statistiques et machine learning pour le clustering de données et l’estimation de densité. L’un des intérêts de ce modèle est que le nombre de clusters, ou de modes de la densité, ne doit pas être fixé par avance, mais est estimé à partir des données. Je présenterai le processus du restaurant chinois, qui définit la distribution a priori sur la partition aléatoire sous-jacente. Enfin, je présenterai des algorithmes de Monte Carlo par chaine de Markov pour estimer les paramètres de ce modèle.

Lundi 6 février 2012 à 11h salle 076
Yvan Le Borgne
Formulation d'énumérations d'animaux dirigés en terme de systèmes dynamiques probabilistes.
Depuis les années 80, on a mis en évidence une relation entre diverses énumérations des animaux dirigés sur le réseau carré et la densité de certains modèles de gaz sur la ligne. Je propose de revisiter cette relation pour formaliser un lien entre ces questions et des systèmes dynamiques probabilistes sur le carré unité. La preuve passe par l'analyse de l'exécution d'une sorte de machine de Turing probabiliste.

Lundi 23 janvier 2012 à 11h salle 076
Allyx Fontaine
Interprétation d'algorithmes probabilistes
Afin de prouver des propriétés d'algorithmes probabilistes à l'aide d'un assistant de preuve tel Coq, une nouvelle méthode a été introduite dans la bibliothèque Alea. Elle est basée sur l'interprétation monadique des programmes probabilistes vu en tant que distributions probabilistes. Nous présentons en premier lieu comment l'interprétation des algorithmes probabilistes comme des distributions a permis de constituer la bibliothèque Alea de preuves formelles de propriétés de ces programmes. Cette approche, qui ne concerne que les distributions discrètes, nous donne des règles pour analyser des fonctions récursives. Nous appliquerons ensuite cette théorie à l'exemple d'une marche aléatoire simple dont la terminaison avec probabilité 1 a été prouvée en Coq.

Lundi 9 et 16 janvier 2012 à 11h salle 076
Florent Foucaud
Méthode probabiliste pour les codes identifiants dans les graphes de degré maximum donné
Dans un graphe, un code identifiant est un ensemble de sommets qui est à la fois dominant et séparant, c'est-à-dire que chaque sommet est couvert par un sommet du code, et que pour chaque paire u,v de sommets, u et v ont des voisinages distincts dans le code. Les codes identifiants ont été introduits en 1998 par Karpovsky et al. et ont depuis été étudiés par une active communauté. Nous nous intéressons ici à des bornes sur la taille minimum d'un code identifiant. Dans un premier exposé, nous montrerons comment donner une borne supérieure sur ce paramètre en fonction de l'ordre et du degré maximum du graphe. La preuve utilise le lemme local de Lovasz couplé à l'inégalité de Chernoff. Dans un second exposé, nous montrerons que la borne du premier exposé peut être largement améliorée lorsque la maille du graphe et son degré minimum sont suffisamment grands. Nous appliquerons ce résultat pour montrer qu'avec forte probabilité, un graphe régulier tiré uniformément au hasard a un code identifiant relativement petit. Ce dernier résultat utilise le modèle de Bollobas dit "des configurations" pour les graphes aléatoires réguliers. Ces exposés se veulent pédagogiques et l'accent sera mis sur les techniques probabilistes utilisées.

Lundi 28 novemvre 2011 à 11h salle 076
Gilles Zémor
Percolation, codes correcteurs, et codes correcteurs quantiques
Un certain nombre de constructions modernes de correcteurs d'erreurs font appel à une structure de graphe sous-jacente. Le problème de la correction des effacements pour ces codes est proche des problématiques de percolation. Ce phénomène est encore plus apparent dans le domaine des codes correcteurs quantiques. Nous montrerons comment passer d'un point de vue à l'autre, et montrerons comment utiliser des bornes sur la capacité de correction d'effacements quantiques pour majorer la probabilité critique pour la percolation sur des pavages du plan hyperbolique (travail commun avec Nicolas Delfosse).

lundi 14 novembre 2011 à 11h salle 076
Valentin Féray
Étude asymptotique du nombre d'adjacences dans une permutation aléatoire uniforme.
On dit que i est une adjacence d'une permutation sigma si i+1 apparaît juste après i dans sigma. Il a été prouvé par différents auteurs que le nombre d'adjacences dans une grande permutation suit une loi de Poisson.
Notons que les images de i et de j dans une permutation aléatoire ne sont pas indépendantes car elles doivent être différentes. Nous allons montrer qu'elles sont "presque indépendantes" dans un certain sens (en utilisant des cumulants). Ceci permet de donner une nouvelle preuve et de nombreuses extensions du résultat ci-dessus.

lundi 7 novembre 2011 à 11h salle 076
Fabien Lotte
Introduction à la classification de signaux électroencéphalographiques (EEG) pour la conception d'interfaces cerveau-ordinateur
Les interfaces cerveau-ordinateur (ou BCI, terme venant de l'anglais Brain-Computer Interface) sont des systèmes de communication permettant à un utilisateur d'envoyer des commandes à un ordinateur en utilisant uniquement son activité cérébrale, celle-ci étant généralement mesurée par électroencéphalographie (EEG). Dans cette présentation, nous verrons d'abord brièvement comment marchent et à quoi servent les BCI, puis nous nous intéressons à comment traiter et classifier les signaux EEG afin d'identifier l'état mental de l'utilisateur. Nous aborderons ainsi quelques techniques d'apprentissage artificiel (machine learning) utilisées dans ce contexte.

lundi 24 octobre 2011 à 11h salle 076
JF Marckert
Élection dans un arbre
En algorithmique distribuée, le problème de l'élection est un problème crucial. Prosaïquement, on imagine un réseau de communication sous la forme d'un graphe, où les noeuds sont des entités communicantes et les arêtes des canaux de communication. Résoudre le problème de l'élection consiste à définir un algorithme que chaque noeud doit exécuter, de manière à ce qu'à la fin des opérations un noeud et un seul soit désigné "élu". Ceci doit se faire en utilisant uniquement les canaux de communication et doit marcher sur tout graphe, ou pour tout graphe dans une certaine classe (les noeuds, par dessus le marché, ne connaissent pas le graphe, mais uniquement l'ensemble de leurs voisins). Si le graphe est un arbre, alors une méthode consiste à ce que les feuilles s'auto-éliminent à des temps aléatoires. Le dernier en lice est décrété élu. On discute dans cet exposé de la loi du noeud finalement élu... (travail commun avec Akka Zemmari et Nasser Saheb-Djahromi).

lundi 17 octobre 2011 à 11h salle 076
Philippe Duchon
Convergence de chaines de Markov contrôlées par un adversaire
Beaucoup de chaînes de Markov permettant d'engendrer aléatoirement des structures discrètes peuvent être décrites par un petit nombre d'actions randomisées, chaque "pas" de la chaîne de Markov correspondant à un choix lui-même aléatoire de l'action à effectuer. En algorithmique distribuée, il n'est pas rare de modéliser le non-déterminisme d'un système en donnant à un adversaire le choix de l'action à exécuter. L'objectif du présent travail est d'explorer dans quelles conditions les résultats de convergence persistent dans ce genre de situation moins confortable.

lundi 3 octobre 2011 à 11h salle 076
Hugo Gimbert
Playing in the Dark
We consider partially observable Markov decision processes with finitely many states and actions. When playing in the dark, a player has no feedback about the decisions he takes: he does not know what is the state of the game or whether he has won or not. A classical result of Paz shows that the value of such games is not computable in general. We will survey recent negative and positive results: on one hand other similar decision problems are undecidable and on the other hand restricting the class of input games turns some of these decision problems into decidable problems.

2010 - 2011

lundi 30 mai 2011 à 11h salle 076
Jean-Francois Marckert
Convergence des structures combinatoires vers des objets continus
En combinatoire, mais cela est vrai également dans de nombreuses disciplines (physique, chimie, biologie, économie, probabilité, ... ), lorsqu'on observe globalement "un gros objet de nature discrète", on voit apparaître un objet plutôt de nature continue: la normalisation (utilisée pour visualiser notre objet discret) ayant écrasé les détails, on ne voit plus que "les grandes tendances", qui elles sont de nature continue.
Un résultat saillant en théorie des probabilités est la convergence des marches aléatoires vers le mouvement Brownien; ceci englobe le cas "combinatoire" des marches +1 ou -1 de longueur n, sous la loi uniforme.
Ces dernières années, de nombreux résultats du même type ont été obtenus pour des structures combinatoires plus complexes : correctement normalisées, elles convergent en distribution vers des objets continus aléatoires (c'est ce genre de résultats qui a valu à W. Werner la médaille Fields il y a quelques années).
Dans cet exposé que j'espère pédagogique, j'expliquerai l'utilité de ces résultats pour la compréhension des grands objets discrets.
Autour d'exemples, j'essaierai d'expliquer comment se prouvent de tels résultats.

lundi 16 mai 2011 à 11h salle 076
Nicolas Hanusse
Localiser une cible avec un agent guidé par des conseils non fiables: comment battre la marche aléatoire avec une montre ?
A cause de la taille et de la dynamique des réseaux, il est impossible de garantir que tous les noeuds disposent d'informations fiables. Supposons que seuls k d'entre eux ne sont pas fiables, comment effectuer un routage ou une recherche d'information ? Des solutions, basées sur des algorithmes déterministes et probabilistes, seront discutées.

lundi 2 mai 2011 à 11h salle 076
Eric Fusy
Génération de Boltzmann de structures combinatoires
On montrera comment, lorsqu'une famille combinatoire possède une décomposition naturelle "pas trop compliquée" (exemple : un arbre binaire est soit un noeud, soit une paire d'arbres binaires), on peut traduire cette décomposition en un générateur aléatoire de manière automatique.

lundi 11 avril 2011 à 11h salle 076
Ph. Duchon
11 -Chaîne de Markov et génération aléatoire
suite...

lundi 4 avril 2011 à 11h salle 076
Ph. Duchon
10 - Chaîne de Markov et génération aléatoire
suite...

lundi 28 mars 2011 à 11h salle 076
Valentin Feray
Pasep, permutations et distribution stationnaire limite
Le PASEP (Partially Asymetric Simple Exclusion Process) est un modèle simple de physique statistique. Il s'agit d'une chaîne de Markov sur les mots binaires de longueur n. Sa mesure stationnaire peut être décrite combinatoirement en utilisant des permutations (travaux de S. Corteel et L. Williams). Nous allons expliquer ces résultats, puis étudier le comportement de la mesure stationnaire quand n tend vers l'infini.

lundi 21 mars 2011 à 11h salle 076
Ph. Duchon
9 - Chaîne de Markov et génération aléatoire
suite...

lundi 2_ février et 7 mars 2011 à 11h salle 076
Paul Dorbec
La méthode probabiliste en théorie des graphes.
En gros, la méthode probabiliste repose sur le principe suivant : pour prouver l'existence d'un objet avec une propriété donnée, on définit un espace de probabilité sur une famille d'objets plus large et on montre qu'un élément de cet espace à la propriété requise avec une propriété positive. Dans cet exposé, nous présenterons cette méthode et traiterons quelques exemples d'utilisation de cette méthode en théorie des graphes.

lundi 14 février à 11h salle 076
Ph. Duchon
8- Chaîne de Markov et génération aléatoire
suite...

lundi 7 février 2011 à 11h salle 076
François Caron
Modèles statistiques et algorithmes pour le classement
Le modèle de Bradley-Terry est un modèle probabiliste utilisé lorsque des éléments d'un ensemble sont comparés les uns aux autres par paire. Dans cet exposé, je montrerai comment estimer les paramètres de ce modèle en utilisant deux algorithmes bien connus en statistiques, l'algorithme EM (Expectation-Maximisation) et l'algorithme de Gibbs. Je montrerai différents résultats sur le classement des équipes en ligue 1 de football et la prédiction de rencontres d'échecs. Enfin, je discuterai plusieurs extensions de ce modèle ainsi qu'un modèle de graphe aléatoire très proche du modèle de Bradley-Terry. Article:
http://hal.archives-ouvertes.fr/docs/00/53/36/38/PDF/rankingv13_inria.pdf

lundi 31 janvier 2011 à 11h salle 076
Ph. Duchon
7- Chaîne de Markov et génération aléatoire
suite...

lundi 24 janvier 2011 à 11h salle 076
Nasser Saheb
CPO des mesures
Afin de formaliser la sémantique dénotationnelle des programmes probabilistes, nous introduisons le cpo (complete partial order) des mesures de probabilité. Cette approche permet d'éviter les identifications non souhaitables, liées à un préordre imposé dans l'approche relationnelle du non-déterminisme. Nous étudions ensuite les propriétés importantes de cette construction.

lundi 17 janvier 2011 à 11h salle 076
Ph. Duchon
6- Chaîne de Markov et génération aléatoire
suite...

lundi 10 janvier 2011 à 11h salle 076
Hugo Gimbert
Optimal positional strategies in stochastic games
We consider Markov decision processes with finitely many states and actions. Roughly speaking, a Markov decision process is a Markov chain whose execution is influenced by a player: at each step, depending on the current state of the Markov chain, the player is allowed to choose which probability distribution will be used to make the transition to the next state. His choices are restricted to a finite set of distributions, also called actions.
The goal of the player is to maximize his expected payoff, which is computed by a payoff function. Such a function associates to each infinite sequence of states and actions a real number.
For arbitrary payoff function, the player may have to play very complex strategies to maximize his expected payoff.
We are interested in positional payoff functions that make the job very simple for the player: whatever is the Markov decision process, the player is able to play optimally with no memory at all. More precisely, for each state, the player can choose again and again the same action each time the process reaches this state.
We will present a theorem about positional payoff functions which provides a unified proof of several results previously known, as well as new examples of Markov decision processes in which simple optimal strategies are guaranteed to exist.

lundi 3 janvier 2011 à 11h salle 076
Ph. Duchon
5- Chaîne de Markov et génération aléatoire
suite...

lundi 13 décembre 2010 à 11h salle 076
François Queyroi
Graphes aléatoires : (quelques) modèles et algorithmes
Issus du célèbre modèle d'Erdös-Réyni introduit à la fin des années cinquantes, les graphes aléatoires ont suscité de nombreux travaux, particulièrement ces derniéres années. L'intérêt de tels objets est en effet multiple : détection de connexions manquantes, inférence sur des propriétés topologiques etc. On verra, au cours de ce bref état de l'art, que l'on peut distinguer deux approches, à savoir une approche algorithmique visant à reproduire certaines propriétés des réseaux et une approche statistique visant à estimer les paramètres d'un modèle probabiliste. On se focalisera sur la deuxième, peut-être moins connue au sein de la communauté informatique. Cette présentation sera également l'occasion de présenter une application des chaînes de Markov pour la maximisation de la vraisemblance d'un modèle.

lundi 6 décembre 2010 à 11h salle 076
Ph. Duchon
4- Chaîne de Markov et génération aléatoire
suite...

lundi 29 novembre 2010 à 11h salle 076
N. Bonichon
Routage à la boussole: comportement asymptotique sur un ensemble aléatoire de points
Nous étudions quelques algorithmes de routage glouton dans le plan. En particulier, nous nous intéressons à des résultats asymptotiques, lorsque le nombre de points tend vers l’infini et sont choisis selon une distribution de probabilité à support borné. Nous obtenons des résultats asymptotiques concernant la géométrie des trajectoires, le nombre de points visités et le comportement de différentes fonctions de coût. Travail réalisé en collaboration avec Jean-François Marckert.

lundi 22 novembre 2010 à 11h salle 076
Ph. Duchon
3- Chaîne de Markov et génération aléatoire
suite...

lundi 8 novembre 2010 à 11h salle 076
C. Johnen
Circulation auto-stabilisante d'un jeton dans les anneaux unidirectionnels et anonymes
Un des problèmes de base de l'algorithmique auto-stabilisante est la circulation de jeton. Nous étudierons ce problème dans un contexte particulièrement difficile : les anneaux anonymes unidirectionels où les processus sont asynchrones. Les vitesses respectives des processus varient au cours du temps et sont non bornées. Dans ce contexte, les techniques algorithmiques basées sur les marches aléatoires ne peuvent être utilisées. Nous présenterons la technique algorithmique utilisée et son analyse.

lundi 18 octobre 2010 à 11h salle 076
Ph. Duchon
2- Chaîne de Markov et génération aléatoire
suite...

lundi 11 octobre 2010 à 11h salle 075
A. Zemmari
Algorithmique distribuée et probabilité
En algorithmique distribuée, plusieurs problèmes n'admettent pas de solution déterministe sous certaines hypothèses (anonymat par exemple). On se retrouve donc à devoir concevoir une solution probabiliste à ces problèmes. Dans cet exposé, je montrerai quelques exemples de solutions probabilistes à des problèmes fondamentaux en algorithmique distribuée tels que le MIS, le coloriage ou la décomposition de graphes. Je présenterai en particulier une analyse d'un algorithme optimal pour réaliser le coloriage. Cet exposé présente des travaux menés en collaboration avec Y. Métivier, J.M. Robson et N. Saheb.

lundi 4 octobre 2010 à 11h salle 076
Ph. Duchon
1 - Chaînes de Markov et génération aléatoire
Les chaînes de Markov d'espace d'états fini sont un type de processus aléatoires simple, qui sont particulièrement faciles à utiliser pour la mise au point d'algorithmes de génération aléatoire (uniforme ou non) d'objets discrets.

lundi 27 septembre 2010 à 11h salle 076
JF Marckert
calculs et notions de base en probabilité