Logo of the LIAFA

Journées SDA2 2007

4-5 octobre 2007, LIAFA, Paris

Logo of the CNRS   Logo of University Paris Diderot-Paris 7
La réunion du 4-5 octobre 2007 constitue les premières Journées annuelles du Groupe de Travail « Systèmes Dynamiques, Automates et Algorithmes » (GT SDA2) du GDR Informatique Mathématique.

Le thème du GT SDA2 est centré autour de la notion de « système dynamique » en algorithmique, avec trois thématiques principales :

NOTA BENE : Le GT peut prendre en charge la participation aux Journées de quelques participants. N'hésitez pas à vous adresser à Jean Mairesse.

Organisateurs

Jean Mairesse (LIAFA)
Christiane Frougny (LIAFA)
Wolfgang Steiner (LIAFA)

Lieu

Les journées ont lieu à Chevaleret (175 rue du Chevaleret, 75013 Paris), salle 0D01.

Programme

Jeudi 4 octobre 2007

  9:30 - 10:00  café au LIAFA, 6ème étage, tour A (les exposés sont au rez-de-chaussée, tour D !)
10:00 - 11:00 Bruno Gaujal Mots de Sturm et arbres équilibrés pour l'optimisation I
11:15 - 12:15 Wolfgang Krieger Présentations des systèmes dynamiques symboliques par des graphes orientés étiquetés I
12:15 - 14:00 déjeuner
14:00 - 14:45 Guillaume Theyssier  Pré-ordres de simulation et automates cellulaires
14:45 - 15:30 Mathieu Sablik Automates cellulaires et dynamique directionnelle
15:30 - 16:00 pause café
16:00 - 16:45 Julien Cassaigne Le mot de Fibonacci est-il toujours optimal ?
16:45 - 17:30 Cyril Nicaud Génération aléatoire d'automates finis déterministes
19:30 dîner

Vendredi 5 octobre 2007

  9:30 - 10:30  Wolfgang Krieger  Présentations des systèmes dynamiques symboliques par des graphes orientés étiquetés II
11:00 - 12:00 Bruno Gaujal Mots de Sturm et arbres équilibrés pour l'optimisation II
12:00 - 13:45 déjeuner
13:45 - 14:30 Wolfgang Steiner Bêta-développements de poids minimal
14:30 - 15:15 Thierry Monteil Régularité et Induction
15:15 - 15:45 pause café
15:45 - 16:30 Anne Siegel Topologie de fractals et automates
16:30 - 17:00 discussion : vie du groupe, ...

Mini-cours

Bruno Gaujal (INRIA Grenoble)

Mots de Sturm et arbres équilibrés pour l'optimisation (I et II)

Dans cet exposé, on montrera les liens qui existent entre les mots de Sturm et plusieurs décompositions en fraction continues, avec leurs applications algorithmiques (reconnaissance de suites équilibrées en temps optimal et allocation optimale de service dans les systèmes de polling). On étendra ensuite certaines notions des mots de Sturm aux arbres. On montrera en particulier les liens qui unissent les notions d'équilibre, de densité et de complexité pour les arbres non-planaires. Une première application des arbres de Sturm en optimisation sera aussi evoquée.

Wolfgang Krieger (Université de Heidelberg)

Présentations des systèmes dynamiques symboliques par des graphes orientés étiquetés (I et II)

On étudie des présentations des systèmes dynamiques symboliques par des graphes orientés avec un étiquetage 1-resolvant, autrement dit, par des systèmes de transition déterministes. Les graphes employés sont des graphes compacts ou des graphes dénombrables fortement connectés. Dans le cas d'un graphe dénombrable on essaye d'imposer des conditions utiles qui sont basées sur des notions de synchronisation.

Exposés

Julien Cassaigne (IML, Marseille)

Le mot de Fibonacci est-il toujours optimal ?

Thierry Monteil (LIRMM, Montpellier)

Régularité et Induction

Dans cet exposé, on cherche à déterminer dans quelle mesure une notion de régularité pour un système dynamique (resp. un mot infini) comme l'entropie, l'uniforme récurrence, etc... est stable par induction (resp. par dérivation (mots de retour)).

Cyril Nicaud (IGM, Marne-la-Vallée)

Génération aléatoire d'automates finis déterministes

Nous présenterons deux bijections qui nous permettent de voir les automates déterministes, complets et accessibles avec $n$ états comme certaines partitions d'ensembles. Ces constructions nous permettent, dans un premier temps, de reformuler un résultat de dénombrement de Korchounov avec les nombres de Stirling de deuxième espèce.
Toutes ces transformations pouvant se construire en temps linéaire, nous pouvons les utiliser pour réaliser un générateur aléatoire uniforme d'automates en générant ces partitions d'ensembles. On utilise pour cela un générateur de Boltzmann, couplé avec un algorithme de rejet. La complexité finale moyenne de cet algorithme est en $O(n\sqrt{n})$, alors que les précédentes méthodes connues, utilisant des décompositions récursives, sont au moins en $O(n^2)$.
Ceci est un travail réalisé en collaboration avec F. Bassino.

Mathieu Sablik (ENS Lyon)

Automates cellulaires et dynamique directionnelle

Pour étudier la dynamique d'un automate cellulaire F sur A^{Z^D}, on considère généralement la N-action de F sans se préoccuper de la Z^D-action du shift notée s. Cependant, il peut être intéressant de considérer la Z^D*N-action (s,F) pour mettre en évidence la structure spatio-temporelle engendrée par l'automate cellulaire. On étudie la dynamique topologique de l'action conjointe (s,F). Plus particulièrement, on caractérise les ensembles de directions ayant une propriété dynamique donnée (équicontinuité, expansivité...). On aboutit à une classification qui généralise celle proposée par R. Gilman ou P. Kurka. Différentes applications de cette classification sont possibles: mise en évidence des transferts d'informations, recherche de mesures invariantes, études des attracteurs...

Anne Siegel (IRISA, Rennes)

Topologie de fractals et automates

Les beta-numérations sont des généralisations des développements en base entière (décimal ou binaire par exemple) à des bases non entières. Dans ce cadre là, les nombres entiers (c'est-à-dire ceux dont le développement n'admet pas de partie fractionnaire) ne sont pas régulièrement répartis mais dispersé sur la droite réelle selon une structure de quasi-cristaux. Les tuiles centrales ou fractales de Rauzy sont des représentations compactes de l'ensemble des nombres entiers. La connexité, la simple connexité, la position de 0 à l'intérieur de la tuile, ou la structure du groupe fondamental ne semblent pas être des invariants. Nous montrerons comment on peut caractériser les propriétés topologiques des tuiles en fonction de la structure de certains automates qui exploitent la structure autosimilaire de la tuile et son intégration dans un pavage. Ce travail est une collaboration avec J. Thuswaldner (Leoben, Autriche).

Wolfgang Steiner (LIAFA, Paris)

Bêta-développements de poids minimal

Pour la cryptographie avec courbes elliptiques, il est intéressant de minimiser le nombre d'opérations nécessaires à multiplier un point par un entier n. Le plus souvent, on utilise un développement de n en base 2 avec des chiffres signés -1,0,1 où le nombre de chiffres non nuls (le poids) est minimal. Dans cet exposé, nous parlons des bêta-développements de poids minimal et leur equivalent pour la représentation des entiers, les développements avec des suites satisfaisant des récurrences linéaires, qui peuvent réduire le nombre d'opérations. Dans le cas du nombre d'or (ou du système de numération avec les nombres de Fibonacci), il est possible de décrire tous les développements de poids minimal à l'aide d'un automate. Plus généralement, ceci est vrai pour une certaine classe de nombres de Pisot.

Guillaume Theyssier (LAMA, Chambéry)

Pré-ordres de simulation et automates cellulaires

Les automates cellulaires sont des systèmes dynamiques discrets définis par une règle locale qui agit uniformément sur un réseau de cellules. Le caractère discret du réseau amène une notion naturelle d'échelle à partir de laquelle on peut formaliser différentes relations de comparaison multi-échelle entre automates. Ces différentes relations, interprétées comme des relations de simulation, structurent l'ensemble des automates cellulaire en pré-ordre. L'objectif de cet exposé est de montrer que ces pré-ordres constituent un outil central dans l'étude des dynamiques des automates cellulaires : ils permettent de formaliser la notion d'émergence, de classifier finement les dynamiques et ils sont à la base de la notion d'universalité intrinsèque. Nous présenterons les principaux résultats obtenus dans ce domaine depuis une dizaine d'années ainsi que plusieurs problèmes ouverts.

Autres participants

Pierre Arnoux (Marseille)
Lubomíra Balková (Paris)
Alexis Ballier (Marseille)
Cyril Banderier (Paris)
Marie-Pierre Béal (Marne-la-Vallée)
Florent Becker (Lyon)
Julien Bernat (Nancy)
Anne Bouillard (Rennes)
Thierry Bousch (Paris)
Julien Cristau (Paris)
Antoine Genitrini (Versailles)
Pierre Gouillon (Marne-la-Vallée)
Emmanuel Hyon (Paris)
Emmanuel Jeandel (Marseille)
Raphaël Jungers (Louvain-la-Neuve)
Idrissa Kaboré (Bobo-Dioulasso)
Éric Laugerotte (Rouen)
Florence Levé (Amiens)
Sylvain Lombardy (Marne-la-Vallée)
Glenn Merlet (Paris)
Pierre Nicodème (Palaiseau)
Jean Moulin Ollagnier (Palaiseau)
Nicolas Ollinger (Marseille)
Damien Regnault (Lyon)
Éric Rémila (Lyon)
Jacques Sakarovitch (Paris)
Rodrigo de Souza (Paris)
Eric Thierry (Paris)
Brigitte Vallée (Caen)
Elise Vaslet (Marseille)
Wiesław Zielonka (Paris)

Dernière mise à jour : 2 octobre 2007