•  » Accueil  

Recherche

•  » Piles de sable  
•  » Automates de sable  
•  » Publications  

RECIF

•  » Séminaires  

» Piles de sable

---

3. Généralisations

Les résultats précédents sont complets, mais manquent de généralité. On peut se poser principalement deux questions, que nous avons résolues dans différents articles.

• Que se passe-t-il si la configuration initiale n'est pas réduite à une colonne ?
• Comment définir un modèle similaire qui pourra s'effondrer dans plusieurs directions (et plusieurs dimensions) ?

3.1 Condition initiale

L'étude complète de SPM et IPM(k) avec des conditions initiales quelconques se trouve dans [5] pour SPM, et dans [6] pour IPM(k).

En partant d'une configuration c quelconque, le problème est beaucoup plus compliqué. On ne pourra pas en général déterminer le point fixe en temps constant, par contre nous avons mis au point un algorithme rapide qui calcule en temps O(l.min(l,n)) un point fixe, le théorème suivant suffit à montrer qu'il est le bon.

Théorème 3 [6]. Pour tout k, pour toute configuration c, le graphe des orbites de c pour IPM(k) est un treillis fini.

Grossièrement, l'algorithme utilisé découpe la configuration en petits morceaux qu'il sait traiter, les fusionne dès que possible et boucle jusqu'à ce qu'il ne puisse plus fusionner, suivant le schéma suivant.

Algorithme de calcul de point fixe pour piles généralisées.

Pour plus de détails, veuillez vous reporter à [5, 6].

3.2 Modèle symétrique

Nous avons également cherché à trouver un modèle de piles de sable symétrique (qui tombe à droite et à gauche) pour obtenir un modèle plus réaliste que SPM. Le principal problème qui se pose est que toutes les définitions intuitives d'un tel modèle aboutissent à des graphes des orbites qui ne sont pas des treillis. Nous avons contourné ce problème en définissant dans [7] un modèle pour lequel ce graphe a quand même une structure très simple.

Le modèle SSPM (Symmetric Sand Pile Model [7]) est défini par deux règles verticales concurrentes. L'une déplace les grains vers la droite et l'autre vers la gauche, toujours quand la différence entre les hauteurs des deux colonnes concernées excède 2 :

Règles verticales de SSPM.

Au non-déterminisme de SPM (choix de l'endroit où appliquer la règle) s'ajoute maintenant le choix de la règle à appliquer. On obtiendra par exemple le graphe des orbites suivant, en partant d'une configuration à une colonne et à 5 grains.

Graphes des orbites de (5) pour SSPM.

Bien que ce graphe ne soit pas un treillis, il est possible de caractériser ses éléments (voir [7] pour les détails), et donc d'identifier et de compter ses points fixes. Le résultat est surprenant de simplicité :

Proposition 4 [7]. Pour tout n, le graphe des orbites de (n) pour SSPM possède ⌊√n⌋ points fixes.

---

Bibliographie

[1]	P. Bak, C. Tang, et K. Wiesenfeld. Self-organized criticality. Physical Review A, 38(1):364−374, 1988.
[2]	E. Goles et M. A. Kiwi. Games on line graphs and sand piles. Theoretical Computer Science, 115(2):321−349, 1993.
[3]	E. Goles, M. Morvan, et H. D. Phan. Sand piles and order structure of integer partitions. Discrete Applied Mathematics, 117:51−64, 2002.
[4]	T. Brylawski. The lattice of integer partitions. Discrete mathematics, 6:201−219, 1973.
[5]	E. Formenti et B. Masson. On Computing Fixed Points for Generalized Sandpiles. International Journal of Unconventional Computing, 2(1):13−25, Old City Publishing, 2006.
[6]	E. Formenti et B. Masson. A note on fixed points of generalized ice pile models. International Journal of Unconventional Computing, 2(2), Old City Publishing, 2006.
[7]	E. Formenti, B. Masson et T. Pisokas. On symmetric sandpiles. Dans Cellular Automata for Research and Industry (ACRI 2006), Lecture Notes in Computer Sciences, Springer-Verlag, 2006.