Systèmes dynamiques et modélisation en algorithmique
AS CNRS/STIC numéro 80
Christiane Frougny, Jean Mairesse, Brigitte Vallée
Responsables:
Objectifs
L'action specifique "Systèmes dynamiques et modélisation en algorithmique" est un moyen de réunir les differentes équipes d'informaticiens qui utilisent la notion de système dynamique. Cette notion est souvent utilisée de manière très diverse, et les échanges et réunions liés à l'AS permettront à chacun de comprendre ce que font les autres et
de lancer des collaborations.
Thèmes
scientifiques
-
1. Modélisation et analyse en moyenne des
algorithmes par des systèmes dynamiques.
Dans le domaine de l'analyse en moyenne des
algorithmes, si on considère
un algorithme comme un système dynamique, on peut
utiliser l'opérateur de
transfert du système comme un opérateur générateur
qui remplace la série
génératrice inutilisable quand l'algorithme est trop
corrélé. On construit ainsi
une nouvelle méthode, l'analyse dynamique des
algorithmes, et on l'applique à deux domaines
larges, l'algorithmique arithmétique et
l'algorithmique du texte. La méthode prouve son
efficacité en résolvant des problèmes inaccessibles
à la méthode classique d'analyse en moyenne.
- 2. Dynamique discrète : aspects logiques et
structurels.
En dynamique symbolique on considère des ensembles
de mots infinis écrits sur des
alphabets finis, qui sont stables par décalage et
fermés.
On rencontre ainsi les systèmes de type fini et les
systèmes sofiques qui sont
liés à la fois à des problèmes de codage,
d'automates et de numération.
En particulier, certaines propriétés mathématiques
des quasi-cristaux
sont descriptibles grâce à une modélisation
discrète, liée aux numérations irrationnelles.
Systèmes dynamiques discrets. Il s'agit d'étudier le
comportement de
systèmes évoluant selon des règles discrètes, comme
les automates cellulaires
et les réseaux de Petri. En particulier on cherche à
caractériser et étudier les
propriétés de l'ensemble des états atteignables de
ces systèmes.
Une approche similaire est utilisée pour l'étude du
graphe du web, et de son évolution dynamique.
-
3. Dynamique temporelle et probabiliste.
L'objectif est ici d'étudier le comportement de
systèmes temporisés.
Les modèles sont ceux décrits au point 2 auxquels
s'adjoint une dimension
temporelle : chaque événement a une durée,
éventuellement aléatoire.
On s'intéresse ainsi aux réseaux de Petri temporisés
aléatoires ou
aux systèmes itérés de fonctions max-plus linéaires.
Les applications concernent en particulier l'étude
du réseau Internet et du mécanisme
de contrôle de flux TCP.
.
Troisième édition des Journées de l'AS : 9/10 décembre 2003
Les troisièmes journées de l'AS auront lieu à Caen. Elles commenceront le 9 décembre à 11h15 et se termineront le 10 décembre après le repas du midi.
Orateurs prévus :
Informations diverses :
- Programme (provisoire)
- Liste des participants
- Informations pratiques :
- pour venir à l'université depuis la gare, le plus simple est de prendre le tramway, ligne A, direction Caen Campus 2. L'université est au terminus de la ligne.
- plan d'accès au campus II (PDF)
- plan du campus II (PDF)
- une liste d'hotels est disponible ici.
Seconde édition des Journées de l'AS : 19 mai 2003
Les secondes journées de l'AS se sont déroulées le 19 mai 2003 à l'ENS. Différents exposés ont été donnés :
Première édition des Journées de l'AS : 28/29 Novembre 2002
Les premières journées de l'action spécifique ont eu lieu
les 28 et 29 novembre 2002 à
l'ENST, 46 rue Barrault, 75013 Paris. Ces journées sont l'acte "fondateur" de l'AS proposée par
Christiane Frougny, Jean Mairesse et Brigitte Vallée.
Des exposés de synthèse des differents domaines ont été donnés par :
- Francois Baccelli, LIENS, Paris
- Marie-Pierre Béal, IGM, Marne-la-Vallée
- Christiane Frougny, LIAFA, Paris
- Jean Mairesse, LIAFA, Paris
- Michel Morvan, LIP, Lyon
- Jacques Sakarovitch, ENST, Paris
- Brigitte Vallée, Greyc, Caen
Vous trouverez des informations supplementaires dans les deux pages ci-dessous.
Equipes
- GREYC, Caen (B. Vallée, A. Akhavi, J. Bourdon, B. Daireaux, L. Lhote, J. Fayolle)
en collaboration avec une équipe de dynamiciens parisiens et dijonnais
- LIAFA, Paris (Ch. Frougny, J. Mairesse, M. Latapy, S. Lombardy, D. Rossin, L. Vuillon)
- IGM, Marne-la-Vallée (M.P. Béal, F. Bassino, J. Clément)
- LIENS, Paris (Projet TREC: F. Baccelli, D. Hong)
- LIP, ENS-Lyon (M. Morvan, J. Mazoyer, B. Gaujal, E. Remila).
- LIRMM, Montpellier (A. Jean-Marie, V. Berthé)
- LTCI, ENST Paris (J. Sakarovitch)