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.

Suite du cours !

(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.

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.

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."

Cours numéro 4 !

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.

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.

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.

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

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.

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.

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.

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.

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