Discussion :

[Lupa99]

Bonjour,

Pour un certain automate cellulaire (bootstrap percolation pour ceux que ça intéresse), j'ai les règles suivantes : (j'appelle "case" tout élément de la matrice, on représente visuellement la matrice comme une grille avec des cases)
- On prend une matrice carrée de taille NxN, et chaque case est égale à 1 avec une probabilité p, 0 sinon. On dit qu'une case est active si le coefficient correspondant de la matrice est égal à 1, inactive sinon.
- Si à un instant T, une case C de la matrice est égale à 0, et si au moins 2 de ses voisins directs (c'est à dire, pas ceux qui sont sur les diagonales) sont actifs, alors C devient active à T+1.
Pour visualiser, cliquez ici

Je dois donc trouver des algorithmes efficaces pour pouvoir faire des simulations d'un grand nombre de ces situations. Je dois donc trouver des algorithmes permettant :

- De vérifier l'égalité entre deux matrices de manière optimale, pour vérifier si ma matrice de taille NxN finie remplie à la fin ou non.
- D'effectuer la transition entre l'état de la matrice de l'instant T à l'instant T+1.

J'ai besoin surtout de calculer le "temps" moyen, i.e. l'entier T du nombre d'étape avant que toute le carré soit rempli, mais ceci pour des matrices de taille 100 par 100 minimum, avec 10 000 calculs environs. J'ai fais pour le moment des algorithmes naïfs, qui consiste à parcourir la matrice, vérifier pour chaque case le nombre de voisin actifs, et ensuite passer à la suivante...

(J'utilise Python ou Caml, si vous avez des astuces pour ces langages je suis preneur).

Je vous remercie par avance !

[wiwaxia]

Bonjour,

Une information complète sur chaque élément de la matrice demande la connaissance
a) de l'état actuel (inactif = 0 , actif = 1) - soit 1 bit;
b) du nombre (n) de voisins actifs, allant de 0 à 4: - soit 1 bit (0 pour n<2, 1 au delà).
Une matrice de doublets de bits devrait donc suffire, et correspondrait à une compression maximale de la variable.
Deux matrices de bits occuperaient le même espace, mais leur utilisation serait plus souple.

Ne disposes-tu pas de fonctions performantes sur les matrices ? La sommation de tous les éléments, par exemple, le produit terme à terme et la comparaison terme à terme (à l'aide des opérateurs XOR et NXOR) devraient s'effectuer rapidement.

[Lupa99]

Bonjour,

Merci beaucoup pour cette réponse !

J'ai alors deux questions suite à votre message :

1) Donc je devrais plutôt fonctionner sur un matrice de doublets de 0 et 1 si je comprend bien ?
Deux matrices ne serait-il pas plus efficaces, en considérant pour la seconde matrice une matrice à "trous" stockant les bits (j'en ai entendu parlé, mais je sais ne connais pas ce genre de structure de données à vrai dire...) car, lors du passage de l'état T à l'état T+1, on a plus qu'à parcourir les éléments qui sont toujours inactifs ? (on supprime alors les éléments dès lors qu'ils sont actifs ?)

2) Ensuite, deuxième question : pour changer l'état du "bit de voisinage", je vois à peut prêt comment faire ; mais je vois pas comment gérer le stockage sur un seul bit ... Ce que j'imagine faire:
- lorsque j’initialise ma matrice, si je met un 1 pour une case, j'ajoute à tout les voisins +1 sur leur nombre respectif de voisin.
- lorsque j'utilise l'algorithme pour faire la transition, je vais regarder ceux qui ne sont pas actifs et qui ont déjà assez de voisins, je le rend actif et je fais pareil qu'au dessus.
Ce système fonctionne sur 3 entier : 0 si aucun voisin, 1 si un seul voisin, 2 si plus de deux voisins.

Qu'aviez-vous en tête comme système pour effectuer la transition ente un instant T et un instant T+1 ?

(Merci pour ces opérations : c'est vrai que sommer tout les éléments suffit, j'ai juste à vérifier que c'est différent de la matrice pleine de 1, i.e. de n^2)

[wiwaxia]

1) J'ai exprimé les idées comme elles me sont venues, prioritairement préoccupé par la recherche du moindre encombrement.
Deux matrices carrées à éléments booléens, l'une réservée aux états (E), l'autre au voisinages correspondant (V), devraient se prêter à des calculs plus rapides.

La première serait de dimension (N+2), et présenterait sur ses bords (i = 0 ou N+1 , j = 0 ou N+1) des valeurs constamment nulles; l'initialisation (E[i, j] = 0 ou 1) ne concernerait que la partie interne ((1 <= i <= N) et (1 <= j <= N));
La seconde, de dimension (N) seulement, pourrait être initialisée à zéro.
Supprimer les cases actives fait perdre de l'information essentielle concernant la disposition mutuelle des éléments, quel que soit leur état.

2) Le passage de (E) à (V) relève d'instructions classiques (naïves ); il devrait être cependant plus rapide en procédant comme suit, pour les (N²) éléments intérieurs:
a) Extraction depuis la matrice des états (E) de la sous-matrice carrée (X) d'ordre (3) et de centre (i, j);
b) Produit scalaire généralisé de (X) par une autre matrice (3x3) constante (Y), jouant le rôle de filtre, soit: p = X│Y ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
    << 0 , 1 , 0 >
y =  < 1 , 0 , 1 >
     < 0 , 1 , 0 >>

c) affectation du résultat à l'élément correspondant de (V): si (p>1) alors V[i, j]=1 sinon V[i, j]=0 .
d) détermination des nouvelles valeurs des éléments de (E), restreinte aux éléments non actifs puisque la désactivation est exclue:
Si ((E[i, j]=0) et (V[i, j]=1)) alors E[i, j]=1 .
La variation de la somme des éléments de (E) aux deux instants successifs (S_E(t) , S_E(t+1)) représentera le nombre d'éléments activés.
On doit pouvoir jouer sur la correspondance (False/True , 0/1) pour écrire les instructions les plus simples.

Je ne suis pas suffisamment familier de Python pour fournir des informations plus précises; d'autres pourraient apporter des renseignements plus complets.
Le produit des matrices (3x3) intervient en traitement d'images.

[wiwaxia]

Ces liens pourraient conduire à des informations intéressantes:

# Autres langages/Python & Zope/Calcul scientifique

# Filtres usuels en Traitement d'images

[Lupa99]

Merci pour votre réponse ! Ça va me servir pour mes concours
Je vous tiens au courant quand j'aurais implémenter tout ça !