Liste des événements uniques du groupe Probabilité et informatique


2011-01-24CPO des mesures
11:00-12:00
076
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.
 Plus d'infos  


2011-01-17Chaîne de Markov et génération aléatoire
11:00-12:00
076
Suite du cours !
 Plus d'infos  


2011-01-10Optimal positional strategies in stochastic games
11:00-12:00
076
(Exposé en Français)

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.

 Plus d'infos  


2011-01-03Chaînes de Markov et génération aléatoire
11:00-12:00
076
cours 5 : 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.
 Plus d'infos  


2010-12-13Graphes aléatoires : (quelques) modèles et algorithmes
11:00-12:00
076
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."

 Plus d'infos  


2010-12-06Chaîne de Markov et génération aléatoire
11:00-12:00
salle 076
Cours numéro 4 !
 Plus d'infos  


2010-11-29Routage à la boussole : comportement asymptotique sur un ensemble aléatoire de points.
11:00-12:00
salle 76
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é par Jean-François Marckert.
 Plus d'infos  


2010-11-22cours 3 : chaîne de Markov et génération aléatoire
11:00-12:00
076
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.
 Plus d'infos  


2010-11-15chaîne de Markov et génération aléatoire
11:00-12:00
076
Cours 3: 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.
 Plus d'infos  


2010-11-15Cours de Philippe Duchon d'aujourd'hui : annulé
11:00-12:00

Le cours est reporté pour raison médicale. Désolés de prévenir si tard, c'est la faute aux microbes.

 Plus d'infos  


2010-11-08Circulation auto-stabilisante d'un jeton dans les anneaux unidirectionnels et anonymes
11:00-12:00
salle 76
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.
 Plus d'infos  


2010-10-18Chaînes de Markov et génération aléatoire
11:00-12:00
076
2ème cours !

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.
 Plus d'infos  


2010-10-11Algorithmique distribuée et probabilités
11:00-12:00
Attention : salle 075
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.
 Plus d'infos  


2010-10-04Chaînes de Markov et génération aléatoire
11:00-12:00
Salle 076
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.
 Plus d'infos  


2010-09-27Calculs et notion de base en probabilité
11:00-12:00
salle 076
Il s'agira ici de parler des toutes premières notions des probabilités : espace de proba, mesures, tribus, variables aléatoires, mesures images, indépendance, espérance... si le temps le permet.

-----------

Le programme pour les semaines suivantes se trouve à :
http://www.labri.fr/perso/marckert/GT-proba-info.html
 Plus d'infos  




Liste des événements répétitifs du groupe Probabilité et informatique




Retour
Retour à l'index