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é
|