Journées SDA2 20074-5 octobre 2007, LIAFA, Paris |
Le thème du GT SDA2 est centré autour de la notion de « système dynamique » en algorithmique, avec trois thématiques principales :
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 |
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, ... |
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.
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.
Dernière mise à jour : 2 octobre 2007