Convertir cet algorithme en Java

**napanh** · 14/08/2011, 12h14

bonjour les expert

Je m'adresse à ce forum dans l'espoir de trouvez une aide, j'ai un algorithme est je voudrais le convertir en code java , pour mon application ,Est-ce que quelqu'un peut me aider , s'il vous plait j'ai bien besoin de cette travaille ...
merci d'avance

voilà l'algorithme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
Données deux automates à états finis A1, A2.
Résultat un automate produit A. 
Variable 
A1 : Fichier de texte ; /*  représente les états et les transitions de l’automate A1  */
    A2 : Fichier de texte ; /*  représente les états et les transitions de l’automate A2 */
    A : Fichier de texte ; /*  représente les états et les transitions de l’automate A */
Variable i : entier ;
    Variable E etat-produit : Ensemble : chaîne de caractère ;
/* sauvegarde les états de l’automate produit*/
X alph-produit : Ensemble : chaîne de caractère ;
   /* sauvegarde les alphabets de l’automate produit*/
II trans-produit : Ensemble : chaîne de caractère ; 
/* sauvegarde les transitions de l’automate produit*/
L_ E_trait : Vector      /*sauvegarde des états déjà traités.*/
L_ N_etat: Vector      /*sauvegarde des nouveaux états à traités. */
List_trans_prod : Vector    /* contient les transitions de l’automate produit A. */
Ens_etatf_prod: Vector    /* contient les états finaux de l’automate produit A.*/
Etat :(Si,Sj)     /* couple des états tell que Si € E1 et Sj € E2.*/
Début 
Ajouter ((S01, S02), List_Nouv_etat)  /* S01 état initial de A1, S02 état initial de  A2 */
Tant que   List_Nouv_etat <> null Faire   /*parcourir la liste des nouveaux états  */
Etat ← retirer_premier_element (List_Nouv_etat),    Si  ←  Etat.Si,   Sj  ←Etat.Sj ; 
Vector  List_trans1 ← Suivant (Si, A1) ; 
Vector List_trans2 ← Suivant (Sj, A2) ;  
/* Suivant (e, A) retourne toutes les transitions ayant l’état e comme état source dans le fichier  A   .les transition sont de type (source, alphabet, destination).  */         
Pour chaque transition trans1= Si>alph1> dst1 ∈  List_trans1 Faire 
Si   il existe une transition trans2=Sj>alph1>dest2 ∈ List_trans2 alors 
/* une transition de  List_trans2  ou on peut  lire le même alphabet  alph1 
ajouter ((Si,Sj),alph1 ,(dst1,dst2)), liste_tans_prod) ; 
    supp_element(List_trans2,tran2)  
/*  Supprimer la transition trans2 de List_trans2 */
 Si  (dst1, dst2)   n’appartient  pas  (Etat_trait   U  Nouv_etat) alors 
Ajouter ((dst1, dst2), Nouv_etat) ;  
FSi 
Si  (dst1∈  ens_etf1 et dst2∈  ens_etf2)  ajouter ((dst1, dst2) ,ens_etf) ; FSi   
/* ens_etf1 représente l’ensemble des états finaux dans A1, ens_etf2 les états   finaux dans   A2,  et  ens_etf dans A.*/
Sinon 
Ajouter ((Si,Sj),alph1 ,(dst1,Sj)),liste_tans_prod)  
Si (dst1, Sj)   n’appartient  pas  (Etat_trait   U  Nouv_etat) alors 
Ajouter ((dst1, Sj), Nouv_etat)     
Fsi       
Si  (dst1∈ ens_etf1 et Sj∈ ens_etf2) ajouter ((dst1, Sj) ,ens_etf); FSi                                      
Fsi                     
Fin Pour

**druzy** · 14/08/2011, 12h33

Il va falloir que tu sois plus clair dans ce qu'est ton algorithme et à quoi correspond les automates etc.

Connais-tu un peu java ?

**napanh** · 14/08/2011, 13h44

donc merci pour votre repense ,

bah j'ai bien étudier les automates à état finis, j'ai construire cette algorithme pour la composition des automate à état finis , alors cette algorithme basé sur le produit cartésien ...

donc je suis débutant en JAVA , est j'ai bien besoin de votre aider s'il vous plais

enfin si vous pouvez me aidée , je vais vous envoyez un fichier contient l'algorithme ainsi un exemple d'application !?

merci d'avance

**druzy** · 14/08/2011, 15h19

Je ne comprends pas votre message,il va falloir faire un effort de français.

**Ivelios** · 14/08/2011, 15h49

Explique nous directement ce que l'algorithme est supposé faire.
Simplement nous dire qu'il s'agit d'automate n'est pas suffisant.

ça sera plus simple de le refaire directement en JAVA depuis le début plutôt que de vouloir faire une traducteur mot à mot. Sachant que dans notre position, nous ne pouvons pas d'aider si nous n'avons pas plus de détails.

En attente de news

**napanh** · 15/08/2011, 12h23

@ Ivelios , Merci pour votre repense ,
ok je vais vous expliquez plus détaillé ,
donc , Cet algorithme est basé sur le produit cartésien des automates à états finis. , nous devons composer leurs automates à états finis deux à deux.
La composition de deux automates à états finis consiste à construire un automate composé (X, Q, q0, II, F) à partir de deux automates (X1, Q1, q1, II1, F1) et (X2, Q2, q2, II2, F2).

* Principe de fonctionnement de l'algorithme:

Soit A1 et A2 deux automates , A leurs automate produit. Pour la composition, on construit les états et transitions de l’automate A en parcourant les transitions de ces deux automates en parallèle comme suit :

Soit (Si, Sj) un état de l’automate produit A telle que Si est un état A1, et Sj est un état de l’automate A2. Pour déterminer les transitions sortantes de l’état (Si, Sj) dans l’automate produit on récupère les transitions sortantes de Si dans A1 et les transitions sortantes de Sj dans A2, si on lit le même alphabet on ajoute la transition ((Si, Sj), alph, (suivant Si, suivantSj)) à l’automate A. Sinon on ajoute les deux transitions ((Si, Sj), alph1, (suivant Si, Sj)) et ((Si, Sj), alph2, (Si, suivant Sj)).
on répète le même processus pour chaque nouveau état .l’état initial de l’automate produit A est le couple des deux états initiaux de l’automate A1 etA2.les états finaux sont les couples contenant un état final de A1 et un autre état final de A2.

donc voilà comment cet algo fonctionne .
s'il vous plait En attente de votre aider !?

merci davance
enfin voilà fichier doc de l'algorithme ainsi un exemple d'application .
algof.docx

**kolodz** · 15/08/2011, 12h52

Bonjour,

Je vais me faire l'avocat du diable pendant ces quelques lignes :

1. Le forum n'a pas vocation à coder votre application à votre place.

En effet, c'est votre travail. Vous en recevez le crédit au près de votre enseignant/employeur.

2. Le but est que vous sachiez résoudre votre problème à la fin de la discutions.

Vous avez un problème de compréhension, on vous explique.
Vous ne savais pas faire un point particulier de votre application, on vous montrer comment on peut le réalisé.

En l’occurrence, vous nous donnez simplement ce que doit faire votre application. Quelle est votre VRAI problème ?
La création des classes Automate/Etat/Transition ?
L'implémentation du parcours que vous nous décrivez si bien ?
Franchement, je ne comprend pas où cela peux bloquer :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Soit (Si, Sj) un état de l’automate produit A telle que Si est un état A1, et Sj est un état de l’automate A2.
//Instanciation de A et récupération des états initiaux de A1 et A2 ?
Pour déterminer les transitions sortantes de l’état (Si, Sj) dans l’automate produit
//Création d'une fonction ?
 on récupère les transitions sortantes de Si dans A1 et les transitions sortantes de Sj dans A2,
//Utilisation de getter ? et une boucle for peut-être ?
 si on lit le même alphabet on ajoute la transition ((Si, Sj), alph, (suivant Si, suivantSj)) à l’automate A.
//Un test ? et une affectation en fonction ?
 Sinon on ajoute les deux transitions ((Si, Sj), alph1, (suivant Si, Sj)) et ((Si, Sj), alph2, (Si, suivant Sj)).
//Le else du test précédant ?
on répète le même processus pour chaque nouveau état .
//Une boucle for c'est cool ça !
l’état initial de l’automate produit A est le couple des deux états initiaux de l’automate A1 etA2.les états finaux sont les couples contenant un état final de A1 et un autre état final de A2.
//Un test encore et une affectation.

Avez-vous un problème de conception ou doit-on vous donner un tutoriel sur les bloques de code if/else ?

Cordialement,
Patrick Kolodziejczyk.

**napanh** · 15/08/2011, 13h28

salut merci pour votre repense ,

donc comme j'ai l'avant dit , je suis débutant en JAVA , est j'ai bien besoin de d'implémenter cet algorithme avec java .

est je m'adresse à ce forum dans l'espoir de trouvez une aide ,
donc mon probléme c'est que:
La création des classes Automate/Etat/Transition !?
aide moi s'il vous plais !?

merci d'avance

**kolodz** · 15/08/2011, 13h53

Soit, c'est un problème de connaissance du langage.
Soit, c'est un problème de conception.

Pour le premier cas.
Voici un résumé assez rapide :

Code :

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

1
2
3
4
5
6
7
8
 
// Délaration d'une classe :
public class MyClassName{
    //Déclaration d'un attributs :
    private MyAttributeClass myAttributeName;
    //Déclaration d'une liste d’attribut et initialisation de la liste:
    private List<MyAttributeClass> myAttributeListName =new ArrayList<MyAttributeClass>();
}

Voici pour la connaissance pratique.

Pour le second cas.
Je vais vous renvoyer à votre propre citation :

un automate composé (X, Q, q0, II, F)

De mémoire cela donne :
1. un état initial
2. une état final
3. une listes d'états
4. une liste de transitions
Un état :
1. un nom/id ?
2. des transitions entrante sortante ?
Une transition :
1. un nom/id ?
2. un état départ/arrivé ?

Cordialement,
Patrick Kolodziejczyk.

**napanh** · 15/08/2011, 14h22

@ kolodz merci
donc mon problème exact c'est la connaissance du langage java ,
alors si vous pouvez me donnez un exemple comment traduire mon algorithme ,
en code java ,c'est t y vraiment plaisir de votre part

voilà mon algorithme :

algof.docx

**kolodz** · 15/08/2011, 14h35

Alors, je te conseil de te rendre sur la partie Java Tutoriel du site.
Il y a tout ce qu'il faut pour traduire ton algorithme.
Apprendre un langage, c'est un investissement à long terme.

Cordialement,
Patrick Kolodziejczyk.

**napanh** · 15/08/2011, 15h46

merci bien pour votre conseil je voudrais juste me dire :
comment je peux déclarer :

X Ensemble : chaîne de caractère ;
L_ E_trait : Vector
Etat (Si,Sj) /* couple des états tell que Si € E1 et Sj € E2

est je voudrais connais est ce que on peut implémenter "Ajouter ((S01, S02), List_Nouv_etat) " comme une foction add ?
si oui , comment ?

é merci davance

**kolodz** · 16/08/2011, 10h30

Bonjour,
Je vous conseil de tester par vous même. Si vous n'y arrivez pas et que vous ne comprenez pas pourquoi revenez ici.

C'est en forgeant qu'on devient forgeron !

Cordialement,
Patrick Kolodziejczyk.

**napanh** · 16/08/2011, 11h15

Bonjour,
oui je c'est , est merci bien pour votre conseille ,
mais s'il vous plais ,je voudrais juste comment faire la déclaration c tout !?
est après je vais continuer tout seule ,

donc voilà ce que je entrain de faire un peut de déclaration :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
 
		public class Main {
 
			public class Couple<Si, Sj> extends java.lang.Object {
 
				private Si a;
				private Sj b;
 
				Couple (Si S01, Sj S02) {
				    a = S01;
				    b = S02;
				}
 
			    }
 
 
	public void Automates(){
 
		int i;
		 String[]Eetat_produit;
		 String[]Xalpha_produit;
		 String[]IItrans_produit;
 
		 Vector List_Etat_trait = new Vector(); 
		 Vector List_Nouv_etat = new Vector();
		 Vector List_Trans_prod = new Vector();
		 Vector Ens_Etatf_prod = new Vector();
 
 
 
 
	}	
 
			public static void main(String argv[]) {
 
		    }

est ce que c'est juste ou pas !?

merci d'avance

**kolodz** · 16/08/2011, 11h45

Bonjour,

Je vais reprendre avec vous votre code qui me fait mal au cœur.
Évitez autant que possible les classes internent. Cela s'utilise dans les cas particulier et encore là beaucoup, ne sont pas d'accord sur leur utilisation.
Donc plus de :

Code :

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

1
2
3
4
public class toto{
     public class tata{
     }
}

Surtout quand la classe englobante ne sert strictement à rien !

Code :

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

public class Couple<Si, Sj> extends java.lang.Object {

Absolument, toutes les classes Java hérite de la classe Object.
Donc pas besoin de le dire.
Pour ce qui est du <Si, Sj> , je pense que vous n'en connaissez même pas la signification réel.
En Java, <T> est utilisé pour la templetisation de classe.
Par exemple, une liste d'objet T :

Code :

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

List<MyObject>

Donc là votre classe, elle déclare un couple de valeur a et b de classe X et Y. Autant vous dire que c'est très flou...

Je reprendrai votre automate après manger parce qu'il y a aussi beaucoup de choses à dire.

Cordialement,
Patrick Kolodziejczyk.

**napanh** · 16/08/2011, 13h10

Bonjour ,

merci bien

j'attende votre conseille monsieur Patrick Kolodziejczyk, est s'il vous plais je voudrais un exemple sur mon algorithme

merci autre fois , bon appétit

**kolodz** · 16/08/2011, 13h35

Envoyé par Par moi, le Divin !

De mémoire cela donne :
1. un état initial
2. une état final
3. une listes d'états
4. une liste de transitions
Un état :
1. un nom/id ?
2. des transitions entrante sortante ?
Une transition :
1. un nom/id ?
2. un état départ/arrivé ?

Code :

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

1
2
3
4
5
6
public class StateMachine{
     private State initial;
     private List<State> final;
     private List<State> states;
     private List<Transition> transisions;
}

Code :

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

1
2
3
4
public class State{
     private String id;
     private List<Transition> outputss;
}

Code :

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

1
2
3
4
5
public class Transition{
     private String id;
     private State departure;
     private State arrived;
}

Après, il peut semblé judicieux de crée une classe héritière de State qui permet de représenter votre état "(Si, Sj)".
Mais il serait peut-être plus judicieux d'avoir seulement des States et d'avoir dans chacun d'entre eux une liste de marqueurs. Un marqueur pouvant aussi bien être un label que l'état d'une variable.
Dans un premier temps je vous conseil d’utilisé l'id suivant pour un couple :

Code :

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

1
2
3
4
 
PUBLIC FINAL STATIC String SEPARATOR = "&";
...
coupledState.setId(Si.getId()+SEPARATOR+Sj.getId())

Un split sur l'id vous permettra de retrouver les id des deux états de base.

Code :

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

1
2
coupledState.getId().split(SEPARATOR)[0];//==Si.getId()
coupledState.getId().split(SEPARATOR)[1];//==Sj.getId()

Je vous conseil de toujours partir du plus simple et non du plus compliqué...

Cordialement,
Patrick Kolodziejczyk.

**napanh** · 17/08/2011, 13h04

Bonjour merci bien pour votre conseille ,

j'ai compris des chose , donc voilà ce que je fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
public class Automate {
 
	public class StateMachine{
	     private State initial;
	     private List<State> finale;
	     private List<State> states;
	     private List<Transition> transisions;
	}	
	public class State{
	     private String id;
	     private List<Transition> outputss;
	}	
	public class Transition{
	     private String id;
	     private State departure;
	     private State arrived;
	}
	public class coupledState extends State {	
 
		public final static String SEPARATOR = "&";
 
		coupledState.setId(Si.getId()+SEPARATOR+Sj.getId())	
 
		coupledState.getId().split(SEPARATOR)[0]; //==Si.getId()
		coupledState.getId().split(SEPARATOR)[1];//==Sj.getId()
 
	}	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}
 
}
}

j'ai créer une classe héritière de State ,mais toujours ya erreur !?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
	public class coupledState extends State {	
 
		public final static String SEPARATOR = "&";
 
		coupledState.setId(Si.getId()+SEPARATOR+Sj.getId())	
 
		coupledState.getId().split(SEPARATOR)[0]; //==Si.getId()
		coupledState.getId().split(SEPARATOR)[1];//==Sj.getId()
 
	}

donc Le principe d'un split est de diviser un string en un tableau se string selaon un caractere ici notre exemple la est "&"!?

alors comment déclarer un variable Etat / Etat: (Si,Sj) !?

s'il vous plait je voudrais un peux détailler

, est merci d'avance

en l'attende je votre conseille

**kolodz** · 17/08/2011, 13h36

Vous n'avez visiblement aucunes des bases nécessaires à la programmation Java.
Vous n'avez clairement aucune chance de développer votre application sans celle-ci. Il est UTOPIQUE de croire le contraire.
Le rôle de ce forum n'est pas de vous enseigner ces bases. Nous pouvons tout au plus vous indiquer où vous pourrez trouver ces bases. Et si nécessaire dans un SECOND temps expliquer un point de détail.

Je vous conseil donc ceci :
Allez dans une librairie ou une bibliothèque un minimum sérieux.
Allez à la section informatique.
Trouvez un livre sur les bases de Java.
Et lisez-le !

Option bonus :
Proposition de livres.
Complément aux livres.

Cordialement,
Patrick Kolodziejczyk.

PS: Merci de ne plus faire d’atrocité dans ce type :

Code :

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

1
2
3
4
5
6
7
8
9
10
	public class coupledState extends State {	
 
		public final static String SEPARATOR = "&";
 
		coupledState.setId(Si.getId()+SEPARATOR+Sj.getId())	
 
		coupledState.getId().split(SEPARATOR)[0]; //==Si.getId()
		coupledState.getId().split(SEPARATOR)[1];//==Sj.getId()
 
	}

JAMAIS de code volant au milieu d'une classe.
Et une classe doit avoir commencer par une Majuscule. C'est une convention de nommage !

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class State {	
 
	public final static String SEPARATOR = "&";
	private String id;
 
	public State(String id){
		this.setId(id);
	}
	public State(State i, State j){
		this(i.getId()+SEPARATOR+j.getId());
	}
	// On définit des getter et des Setter comme je l'avait dit dans mon précédant messages
	public void setId(String id) {
		this.id = id;
	}
 
	public String getId() {
		return id;
	}
	public static void main(String[] args) {
		State a = new State("a");
		State b = new State("b");
		State ab = new State(a,b);
		System.out.println(ab.getId());
		System.out.println(ab.getId().split(SEPARATOR)[0]);
		System.out.println(ab.getId().split(SEPARATOR)[1]);
	}
}

Le principe que je vous proposait était le suivant :

Code :

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

1
2
3
4
5
6
public class Automate {
	public class StateMachine{
		//....
	}
	//...
}

Je vous ai déjà dit que l'imbrication de classe est ~~une absurdité~~ à éviter.
Et pour le coup, un automate EST une machine d'état.
Je vous conseil d'apprendre la notion de package...

**napanh** · 17/08/2011, 15h44

Bonjour Patrick ,

donc je suis toujours avec vos conseille ,
voilà ce que je fais mais jusqu'à maintenant j'ai pas bien compris

après la création de classe state .....
maintenant comment je peux déclarer le variable Etat: (Si,Sj)
pour démarrer l'implémentation de mon algorithme !?

voilà la déclaration des variable :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
		int i;
		 String[]Eetat_produit;
		 String[]Xalpha_produit;
		 String[]IItrans_produit;
 
		 Vector List_Etat_trait = new Vector(); 
		 Vector List_Nouv_etat = new Vector();
		 Vector List_Trans_prod = new Vector();
		 Vector Ens_Etatf_prod = new Vector();
 
 
                 State etat ;

est ce que c'est juste !?

j'attende toujours votre conseille

merci d'avance

Convertir cet algorithme en Java

Java

Discussions similaires

Partager

Partager