Discussion :

[Fahmi06]

Salut à tous,
Je suis en train d'etudier les différentes structures de données afin de choisir la meilleure pour représenter les automates temporisées.
Je pense aux arbres n-aires, mais je ne sais pas si ça va bien.
En fait dans les tps on n'a travailler qu'avec les arbres binaires et pas avec les automates temporisées (cad sans transitions).
Je voudrait avoir de l'aide de vos parts pour prendre une décision finale.
Merci d'avance.

[Fahmi06]

Salut,
Je vais poser la question autrement.
Quelle est la structure de donnée la plus adéquate qui permet d'introduire des transitions entre des états.
Merci d'avance.

[PRomu@ld]

En fait, un automate est un graphe, tu as plusieurs méthodes : listes d'adjacences, matrices d'adjacences.

Si tu veux plus de détails n'hésites pas.

[Fahmi06]

Merci pour votre aide.
En fait nous avons fait un petit apperçu sur les différents structures de données disant connus comme les listes, les piles, les files, les arbres binaires avec des petits tps introductifs. Mais ce que vous proposez est nouveau pour moi.
Donc si vous pouvez m'aidez à les comprendre je serai trés reconnaissant.
Ce qu'est un peu difficile à introduire est les transitions entre les états.
Merci d'avance.

[PRomu@ld]

Une matrice d'adjacence est un matrice carré relativement simple à comprendre, pour un automate à n états, la matrice associée sera une matrice n*n. Cette matrice sera composée de valeur suivant la règle suivante :

Le coefficient (i,j) vaut 0 (ou -1 ou toute autre valeur particulière et bien identifiable) s'il n'y a pas de transition entre l'état i et l'état j. Elle vaut la valeur de la transition si une transition existe. Le principal problème avec cette représentation est qu'elle est souvent peu efficace en terme d'occupation mémoire (mais elle a d'autres avantages), notamment lorsque le nombre de transitions est faible par rapport au nombre de sommets. La matrice est alors creuse.

Lorsque l'on est dans ce cas, le plus efficace (en terme d'occupation mémoire) est d'utiliser les listes d'adjacences. Ici encore, le concept est simple. On a un tableau de liste chaînées. Le tableau a autant de liste chaînées que d'états dans l'automate. Chacun des états va donc avoir une liste chaînée qui lui est associée. Cette liste chainée représente l'ensemble des transitions qui partent de ce sommet. Chacune ces cellules de ta liste chainée va contenir à la fois le sommet de destination et la valeur de la transition. Suivant les utilisations, on peut gérer deux listes chainées par état : une liste pour les transitions entrantes et une liste pour les transitions sortantes.