Systèmes Max-Plus
Cours de base (30 h de cours, 30h de TD)
Cours : Bruno Gaujal (Bruno.Gaujal)
TD : Anne Bouillard (Anne.Bouillard)
présentation du cours
Dans ce cours, on étudie théoriquement des systèmes discrets (réseaux de
télécommunication, systèmes informatiques distribués, systèmes de production) dont l'évolution
est décrite par une équation de la forme Xn = f(Xn-1, un).
Xn est l'état à l'étape n, f donne la dynamique du système et
un est un ensemble de paramètres.
La première partie du cours étudie le cas où f est une fonction qui
ne fait intervenir que les opérations max et plus, ce qui est courant
dans les réseaux de communication.
La deuxième partie étudie le cas où f est une fonction linéraire et
un est une variable aléatoire, ce qui correspond aux chaînes de
Markov.
La dernière partie s'intéresse à l'optimisation et au contrôle de tels systèmes.
Plan du cours
-
Systèmes à événements discrets déterministes
-
Systèmes (max,plus)-linéaires
- Automates (max,plus) et jeu de Tetris
- Systèmes à événements discrets stochastiques
-
Chaînes de Markov (discrètes et continues)
- Processus de décision Markoviens
Les deux premiers cours (un peu abrégés) ainsi qu' un plan détaillé du
cours
sont disponibles sur http://www-id.imag.fr/Laboratoire/Membres/Gaujal_Bruno/perso.html.
which behavior can be written as Xn =
f(Xn-1,un), where Xn is the state at step n, f models the
dynamics and un is a set of parameters.
The first part concerns the case where f only involves the max and
the plus operators.
The second part presents the case where f is linear and un is a
random variable.
The last part of this course shows how to control and optimize such systems.
Bibliographie
-
F. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, Synchronization and Linearity, Wiley, 1992.
- P. Brémaud, Markov Chains, Springer-Verlag, 1998.
- D. Bertsekas, Dynamic programming and optimal control,
Athena Scientific, 1995.