Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Recherche - Piles de sable (2)
[go: Go Back, main page]

» Piles de sable

2. Rappels

Nous reprendrons à peu de choses près le formalisme et les résultats introduits dans [2, 3].

2.1 Définitions

Une pile de sable (ou configuration) est une suite finie d'entiers non nuls c = (c1, ... , cl), où l est la longueur de la configuration.

Un système de piles de sable est un système dynamique discret travaillant sur ces configurations. Il est défini par des règles locales qui permettent de faire évoluer une configuration. Par exemple le modèle le plus courant, SPM (Sand Pile Model [2]), est défini par une règle verticale : dès qu'une colonne ci a au moins 2 grains de plus que sa voisine de droite ci+1, celle de gauche peut perdre un grain sur sa droite.

Règle verticale

Règle verticale de SPM.

On obtient ainsi une nouvelle configuration, et après itération sur cette nouvelle configuration on obtient l'orbite de la configuration initiale : un chemin fini, sans cycles. Il faut noter que parfois on peut appliquer la règle en plusieurs endroits à la fois. Si l'on trace alors toutes les orbites sur un graphe orienté (les noeuds sont les configurations, il y a une arête entre 2 noeuds si l'on peut obtenir le second en appliquant la règle quelque part dans le premier) on crée le graphe des orbites.

Graphe des orbites de (8)

Graphe des orbites de la configuration initiale (8) pour SPM.

Comme on peut le voir sur cet exemple, il n'y a toujours qu'un point fixe. Quel que soit l'endroit où la règle est appliquée le point fixe est le même, ce qui sera prouvé dans la partie suivante.


Il existe aussi un ensemble de modèles courant, IPM(k) (Ice Pile Model [3]), qui est en fait une généralisation de SPM. Ils regroupent la règle verticale, et une règle horizontale qui fait glisser des grains. Si pour k donné il existe i < j tels que ci = ci+1 + 1 = ... = cj + 1 = cj+1 + 2, j - i < k, alors un grain peut glisser de la colonne i vers la colonne j+1.

Règle horizontale

Règle horizontale de IPM(k).

Avec cette définition, on remarque que SPM est exactement IPM(1). Selon les cas, SPM sera donc considéré soit comme un cas particulier d'IPM(k), soit comme un modèle à part entière quand l'énoncé général est trop compliqué. On peut également définir le graphe des orbites de la même manière que pour SPM, lui aussi semble n'avoir qu'un point fixe.

Graphe des orbites de (7)

Graphe des orbites de la configuration initiale (7) pour IPM(3).

2.2 Résultats

Théorème 1 [3]. Pour tous entiers k, n, le graphe des orbites de (n) pour IPM(k) est un treillis fini.

Ce théorème majeur implique qu'il n'y a nécessairement qu'un point fixe pour une configuration initiale à une colonne donnée, quel que soit le chemin emprunté. Le lemme suivant complète ce résultat en caractérisant les éléments du graphe.

Lemme 2 [3]. Pour tous k, n, une configuration c à n grains appartient au graphe des orbites de (n) pour IPM(k) si et seulement si pour tous i < j, j - i ≤ k(ci - cj + 1).

Dans le cas de SPM, ce lemme signifie qu'une configuration est atteignable si et seulement si elle est décroissante, et si entre deux plateaux consécutifs il y a au moins une falaise. En d'autres termes, s'il y a deux plateaux l'un d'eux doit pouvoir être détruit par un éboulement situé entre les deux.

C'est de cette manière que l'on peut se représenter l'énoncé du lemme pour IPM(k) : entre deux plateaux de taille k+1, une des règles doit être applicable pour qu'une configuration soit atteignable.

On peut alors décrire le point fixe de (n) pour IPM(k), qui est l'unique configuration décroissante à n grains n'ayant que des plateaux de taille k, et au plus un de taille k+1 et un de taille k' < k au sommet. Par exemple, le point fixe de (18) pour IPM(2) est le suivant :

Exemple de point fixe

Point fixe de (18) pour IPM(2).

Pour l'expression exacte du point fixe, veuillez vous référer à l'article [3].


On peut également calculer la longueur du transitoire (nombre d'itérations avant d'obtenir le point fixe) maximale pour les modèles IPM(k), son expression exacte se trouve dans [3]. Il faut noter que pour SPM, tous les chemins ont la même longueur, mais dans tous les autres cas, la longueur minimale est encore inconnue.

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.