Séminaire
Vendredi 19 septembre 1997 - 14h00
Salle de conférences Michel Métivier
Une introduction à l'algèbre (max, +)
Les semi-anneaux exotiques comme le "semi-anneau max-plus"
(R U {-infini}, max, +) ou
le "semi-anneau tropical" (N U {+infini}, min, +)
ont été inventés et réinventés par plusieurs communautés depuis la fin
des années cinquante, pour des motifs variés. Ces structures sont
apparues naturellement :
- en évaluation de performance de systèmes de production (problème
central de l'ordonnancement) et plus généralement en théorie des
systèmes à événements discrets ;
- en théorie des graphes (recherche de chemins de poids maximum), en
décision Markovienne et commande optimale déterministe,
- en calcul asymptotique (asymptotiques à température nulle en physique
statistique, grandes déviations) ;
- en théorie des langages (décision de la propriété de la puissance
finie).
Derrière cette variété d'applications apparaît finalement un petit
nombre de résultats de base, en général peu connus en dehors du petit
monde maxplusien, et qui semblent être utiles dans la plupart des cas
concrets.
On propose une visite guidée de ces principaux résultats, illustrée par
quelques exemples, empruntés pour l'essentiel aux systèmes à événements
discrets.
Parmi les techniques de base, citons :
- l'analogue max-plus de la
théorie de Perron-Frobenius et sa version "séries rationnelles", qui
donnent une compréhension complète et intuitive des systèmes dynamiques
linéaires sur ces semi-anneaux ;
- la résolution de systèmes
d'équations linéaires par résiduation, symmétrisation et emploi de
déterminants exotiques.
On terminera par quelques questions d'actualité (systèmes dynamiques
min-max-plus, problèmes algorithmiques ouverts).
Références bibliographiques
- F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat. Synchronization
and Linearity. Wiley, 1992.
- Z.Q. Cao, K.H. Kim, and F.W. Roush. Incline algebra and applications.
Ellis Horwood, 1984.
- R.A. Cuninghame-Green. "Minimax Algebra". Number 166 in
Lecture notes in
Economics and Mathematical Systems. Springer, 1979.
- S. Gaubert and M. Plus. Methods and applications of (max,+) linear
algebra. In R. Reischuk and M. Morvan, editors, STACS'97, number 1200 in
LNCS, Lübeck, March 1997. Springer.
- J. Gunawardena, editor. Idempotency. Publications of the Newton
Institute. Cambridge University Press, 1997. to appear.
- V. Maslov and S. Samborskii, editors. Idempotent analysis, volume 13 of
Adv. in Sov. Math. AMS, RI, 1992.
- U. Zimmermann. Linear and Combinatorial Optimization in Ordered
Algebraic Structures. North Holland, 1981.
| Page d'accueil Irisa | Séminaires
Irisa 1997 | Manifestations
scientifiques | Comment se rendre
à l'Irisa ? |
webmaster@irisa.fr, septembre 1997