Discussion :

[sandaff]

Bonjour;

Je voudrais votre idée sur la complexité de l'algorithme de ce programme ci-dessous:

Le programme consiste à faire la sélection de 100 ou 200 ou 300 Etudiants parmi 400 ou 500 etc pour l'acquisition d'un dortoir au campus;

Voici le code:

Code java :

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
package xxx;
 
import java.util.*;
 
public class xxx {	
 
	public static void main(String[] args ) {
 
		Scanner keby = new Scanner(System.in);	
 
		System.out.println("Veuillez saisir le nombre d’étudiants :");
                //la liste des étudiants;
	   	int n=keby.nextInt();
 
	   	 String [][] tabEtud = new  String[n][4];
 
	   	 System.out.println("Veuillez saisir le nombre pair d’étudiant incompatible :");
                //liste de pair étudiants incompatible dans le même dortoir
		 int n1=keby.nextInt();
 
		 String [][] tabEtudInc = new String[n1][2];
 
		 System.out.println("Veuillez saisir le nombre d’étudiants à sélectionné par pair :");
                 //duex étudiants par dortoir qui correspond à 2*nombres de dortoirs;
		 int m=keby.nextInt();
 
		 String [][] tabEtudSelect = new String[m][2];
 
		 Integer Indice=0;
 
		 String  clobalId="001";
 
	          String choix ; 	 	  
 
				do
 
		          {
		            System.out.println("------Menu principal ---------");
		            System.out.println("   1. Liste d’étudiants     "); 
		            System.out.println(" 2.Liste d’étudiants incompatibles  ");
		            System.out.println("  3. Sélection d’étudiants  ");
		            System.out.println("           4.Quitter      ");
		            System.out.println("      Taper votre choix : ");
		             choix = keby.nextLine();
 
		            switch(choix)
		            { 
		            case "1": saisieEtudiant (tabEtud, keby);
		                    break;
		            case "2": saisieIncompatibilite (tabEtudInc, keby);
		                    break;
		            case "3": Selection ( tabEtudSelect, tabEtud , tabEtudInc , keby, clobalId, Indice);
		                    break;     		           
		            default: System.out.println("Veuillez respecter le menu!");
		            }
 
		             }
		             while(choix!="4");		         
 
 
	}
 
	 public static  void saisieEtudiant(String [][] tabEtud, Scanner keby) {
 
	  int n=tabEtud.length; 
 
   	  int i=0;
 
   	  String idEtud; 
 
   	  String nom;
 
   	  String prenom;
 
   	  String adresse;
 
      	do {
 
   	  System.out.println("Veuillez saisir l’Id de l’étudiants :");
 
   	  idEtud=keby.nextLine();
 
   	  tabEtud[i][0]= idEtud;
 
   	  System.out.println("Veuillez saisir le nom de l’étudiants :");
 
   	  nom=keby.nextLine();
 
   	  tabEtud[i][1]=nom;
 
   	  System.out.println("Veuillez saisir le prénom de l’étudiants :");
 
   	  prenom=keby.nextLine();
 
   	  tabEtud[i][2]=prenom;
 
   	  System.out.println("Veuillez saisir l’adresse de l’étudiants :");
 
   	  adresse=keby.nextLine();
 
   	  tabEtud[i][3]=adresse;
 
 
   	  i =i+1;
 
   	 } while (i<n);   	   
 
   	  }
 
	 public static void saisieIncompatibilite (String [][] tabEtudInc, Scanner keby) {
 
		int n=tabEtudInc.length;
 
		String idEtud1;
 
		 String idEtud2; 
 
		 int i=0;
 
		 do {
 
		 System.out.println("Veuillez saisir l’Id de l’étudiant1 incompatible:");
 
		 idEtud1=keby.nextLine();
 
		 tabEtudInc[i][0]= idEtud1;
 
		 System.out.println("Veuillez saisir l’Id de l’étudiant2 incompatible:");
 
		 idEtud2=keby.nextLine();
 
		 tabEtudInc[i][1]= idEtud2;
 
 
		 i =i+1;
 
		 } while (i<n);
 
		 }
 
            //la selection se fait par tirage au sort;
 
	public static  void Selection (String [][] tabEtudSelect, String [][]tabEtud , String [][]tabEtudInc , Scanner 
                 keby,String  clobalId, Integer Indice) {
 
		 int n= tabEtud.length;
 
		 Boolean Ajouter =false ;	// à chaque selection Ajouter=vrai pur sortir du while et revenir dans for	
 
		 String [][] tabTirage = new String[1][2]; //les deux tirés sont rangés et puis remplacer au tirage suivant;
 
		 ArrayList<String> tabEtudCopy = new ArrayList< String > (); // mets la liste étudiant dans ArrayList 
                     par rendre facile le traitement;
 
		 ArrayList<String> tabEtudSelectCopy = new ArrayList< String > (); //recupère les selection et à la 
                  sortie recopierra dans tabEtudSelect
 
 
		 for(int i = 0; i<n; i++)  
		 {
 
              // transfert de la liste &tudiant dans la copie
 
		         tabEtudCopy.add ( tabEtud[i][0] ) ;	 
		 }
 
         System.out.println("Veuillez saisir le nombre de chambres:");
 
         // permet de saisir en fonction du nombres de dortoirs
 
		 int c = keby.nextInt();
 
		 String id1;
 
		 String id2;
 
		 String  idRe;
 
		 for(int i = 0; i<c; i++)  {
 
			 Ajouter=false; // chaque ajout egal vrai pour sortir du do while
 
		 do {		
 
		 Random random = new Random (); // tirage au sort ou nombre aleatoire
 
		 int nb;
 
		 n = tabEtudCopy.size() ; // determine le nombre elements dans etudiant
 
		 nb = random.nextInt(n); // choix dans l'intervale  0 et n
 
		 id1 = tabEtudCopy.get(nb); // si id1 est retenu alors l'etudiant de id1 serra selectionné
 
		 clobalId=id1;
 
		 idRe = recherche (tabEtudInc ,  clobalId, Indice); // est ce id1 est dans la liste des incompatibilié
 
		 if (idRe == "-1" ) {
 
			 // si non alors il est ajouté
 
		 tabTirage[0][0]=id1; // il est rangé dans le tirage;
 
		 tabEtudCopy.remove(nb); // supprimé dans ce tableau pour eviter de tombe sur la meme valeur au 
                 prochain tirage
 
		 n= tabEtudCopy.size();
 
		 nb = random.nextInt(n);
 
		 id2 = tabEtudCopy.get(nb);
 
		 tabTirage[0][1]=id2; // son binomme est aussi tiré (je crois que vous comprenez le processus)
 
		 tabEtudCopy.remove(nb);
 
		 Ajouter=true; // il est à vrai pour revenir dans for et passer au seconde chambre
 
		 }
		     else {
 
		    	 //sinon alors on cherche le second et on verifie s'il sont incompatibles
 
		       tabEtudCopy.remove(nb); // evidemment il faut supprimer id1 avant
 
		       n= tabEtudCopy.size();
 
		       nb = random.nextInt(n);
 
		       id2 = tabEtudCopy.get(nb);
 
		        if (((id1 == tabEtudInc[Indice][0]) && (id2 != tabEtudInc[Indice][1])) ||   ((id1 == tabEtudInc[Indice][1]) && (id2 != tabEtudInc[Indice][0]))){
 
		        	// si le marriage est possible alors on les tire tous les deux
 
		        	tabTirage[0][0]=id1;
 
		        	tabTirage[0][1]=id2;
 
		            tabEtudCopy.remove(nb);
 
		            Ajouter=true;
 
		             }
 
		             else
 
		               tabEtudCopy.add(id1); 
 
		        /*
		         sinon le mariage n'est pas possible alors 
		         on remet dans la table tabEtudCopy l'id1 qui a été supprimé pour recommencer
		         sans changer de chambre;
		         donc Ajouter reste toujours à false;
		         */
 
 
		     }
 
		    } while (Ajouter==false);
 
		 // les deux tirés sont rangés dans la selection
 
		     n = tabEtudSelectCopy.size() ;		
 
			 tabEtudSelectCopy.add ( tabTirage[0][0] ) ;		
 
			 tabEtudSelectCopy.add ( tabTirage[0][1] ) ;	
 
		 }
 
		 /*
		  recuperation de la selection en array ou tableau static si le travail est finit;
		  mais je dis à tabEtudCopy et tabEtudSelectCopy merci car leurs souplesses m'ont rendu
		  la tâche assez facile		 
		 */
 
		  int j=0;
		  for(String elem:tabEtudSelectCopy )
	       {
 
			tabEtudSelect[j][0]= elem; 	// recuperation	        
 
		      j++;
 
		    }
 
 
		 }
 
	 public static String  recherche (String [][]tabEtudInc , String  clobalId, Integer Indice){
 
		 int n= tabEtudInc.length;
 
		 String sortietest="-1"; // on cherche les incompatibilités et sort avec "-1" si id n'existe pas		 
 
		for( int i = 0; i < n ; i++) {
                for(int j = 0; j < 2; j ++ ) {
 
		  if (  clobalId.equals(tabEtudInc [ i ][ j ])  ) {
 
		    Indice= i ;
 
		    sortietest = tabEtudInc [ i ][ j ] ;
 
 
		                      }                        
		                      }
		                      }
 
		          return  sortietest  ;   
 
		 }
 
   }

[Guesset]

Bonjour,

Quand on soumet un code, il est bien de le rendre lisible pour les personnes à qui on s'adresse comme pour soi-même (pas de doubles sauts de ligne systématiques et un respect des indentations).

Il y a des erreurs de logique :

• Le nombre m de paires d'étudiants à sélectionner (soit le nombre de chambres ou son double) n'est jamais utilisé. Il y a systématiquement plus de places que d'étudiants ? Si oui pourquoi le saisir ?
• Par exemple, la saisie des incompatibilités est au moins en n*(n-1)/2 (apparemment n² ici) et non pas n (complexité en n²) En effet rien n'empêche un étudiant d'être incompatible avec tous les autres (n-1), un autre encore (n-2) etc.
• Il n'y a rien qui empêche d'avoir deux fois le même identifiant dans un couple incompatible (erreur de saisie des incompatibiltés non contrôlée).
• A contrario, un étudiant n'est, par défaut, pas incompatible avec lui-même. Comme le tirage au sort ne vérifie pas que le hasard a donné deux fois le même identifiant, il y a des chambres qui seront habitées par des couple d'une seule personne (c'est nouveau ).
• Si tout le monde est incompatible avec tout le monde (même si l'erreur dans la saisie des incompatibilités et celle sur les couples d'une personne cachent ce cas) comment on sort de la recherche de couples?
• etc

Par ailleurs, des facilités de java ne sont pas utilisées (par exemple Ajouter = true au lieu d'un break);.
Il y a une complexité inutile : tabTirage ne sert à rien, l'argument clobalId de Selection ne sert à rien (il est écrasé de suite),...

Le problème de la complexité suppose un algorithme qui fonctionne ce qui n'est pas le cas. L'usage de fonctions random donnera un estimation statistique de la complexité avec un valeur moyenne et une valeur dans le pire des cas.

Un conseil, faites tourner à la main (ie sans ordinateur) votre algorithme sur des cas très limités (par exemple 10 étudiants et 3 chambre pour 11 incompatibilités). C'est fastidieux mais évite beaucoup d'erreurs.

Salutations

[sandaff]

Bonsoir Monsieur Guesset ;

Je voudrais vous envoyer un message privé si vous n’aviez pas réagi aujourd’hui ;

Quand on soumet un code, il est bien de le rendre lisible pour les personnes à qui on s'adresse comme pour soi-même (pas de doubles sauts de ligne systématiques et un respect des indentations).

Il y a des erreurs de logique :

• Le nombre m de paires d'étudiants à sélectionner (soit le nombre de chambres ou son double) n'est jamais utilisé. Il y a systématiquement plus de places que d'étudiants ? Si oui pourquoi le saisir ?

m est bien utilisé :

-Ici :

Code :

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

1
2
3
4
5
6
 
System.out.println("Veuillez saisir le nombre d’étudiants à sélectionné par pair :");
  //duex étudiants par dortoir qui correspond à 2*nombres de dortoirs;
 int m=keby.nextInt();
 
 String [][] tabEtudSelect = new String[m][2];

-Ici: à la fin de sélection

Code :

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

1
2
3
4
5
6
7
8
9
10
 
int j=0;
 
for(String elem:tabEtudSelectCopy )
   {
     tabEtudSelect[j][0]= elem; 	// recuperation	        
 
     j++;
 
   }

Le nombre de chambre c est égale à m/2 ; donc m = 2* c ;

• Par exemple, la saisie des incompatibilités est au moins en n*(n-1)/2 (apparemment n² ici) et non pas n (complexité en n²) En effet rien n'empêche un étudiant d'être incompatible avec tous les autres (n-1), un autre encore (n-2) etc.

-Je n’ai pas compris la complexité ; ça boucle de 0 à n-1 seulement avec n< n saisie avec saisieEtudiant() ;

Code :

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

1
2
3
4
5
6
7
8
 
Int i=0 ;
 
do {
 
 i =i+1;
 
 } while (i<n);

- je ne me suis pas soucié du contrôle de saisie qui n’est pas l’objectif recherché ; mais on peut le faire et si je peu je le ferai ; seulement on suppose que la liste est correcte et a été bien fournit par la direction ou un décideur et non par l’informaticien ;

[*]Il n'y a rien qui empêche d'avoir deux fois le même identifiant dans un couple incompatible (erreur de saisie des incompatibiltés non contrôlée).[/LIST]

Cette question et comme le reste:

On suppose que la liste est correcte et on porte confiance à l’agent de saisie pour le moment;

Le résultat recherché ou ma question : est ce la complexité est polynomiale ?

Après on passera à la perfection avec le tableau ou List ; càd Class Etudiant etc..

vous avez tout à fait raison sur les avantage de java comme l'utilisation de break ; je voulais faire ça simple pour ressortir l'idée comme je ne suis pas balaise en code; d’ailleurs au départ je voulais m’arrêter à l'algo mais je sais que les gent poserait de question si je l'ai fait avec un programme;

-Pour la trace voici une trace :

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
Veuillez saisir le nombre d’étudiants :
15
Veuillez saisir le nombre pair d’étudiant incompatible :
2
Veuillez saisir le nombre d’étudiants à sélectionné par pair :
10
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
Veuillez respecter le menu!
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
1
Veuillez saisir l’Id de l’étudiants :
001
Veuillez saisir l’Id de l’étudiants :
002
Veuillez saisir l’Id de l’étudiants :
003
Veuillez saisir l’Id de l’étudiants :
004
Veuillez saisir l’Id de l’étudiants :
005
Veuillez saisir l’Id de l’étudiants :
006
Veuillez saisir l’Id de l’étudiants :
007
Veuillez saisir l’Id de l’étudiants :
008
Veuillez saisir l’Id de l’étudiants :
009
Veuillez saisir l’Id de l’étudiants :
010
Veuillez saisir l’Id de l’étudiants :
011
Veuillez saisir l’Id de l’étudiants :
012
Veuillez saisir l’Id de l’étudiants :
013
Veuillez saisir l’Id de l’étudiants :
014
Veuillez saisir l’Id de l’étudiants :
015
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
2
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
003
Veuillez saisir l’Id de l’étudiant1 incompatible:
006
Veuillez saisir l’Id de l’étudiant2 incompatible:
009
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
3
Veuillez saisir le nombre de chambres:
5
tabEtudSelect: 014
tabEtudSelect: 004
tabEtudSelect: 010
tabEtudSelect: 011
tabEtudSelect: 005
tabEtudSelect: 006
tabEtudSelect: 012
tabEtudSelect: 003
tabEtudSelect: 013
tabEtudSelect: 015
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
Veuillez respecter le menu!
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix :

Merci pour votre intervention

[tbc92]

Quel est l'intérêt de la question 'complexité de l'algorithme', 'complexité Polynomiale' ?
Une complexité polynomiale peut être pire qu'une complexité exponentielle dans plein de configurations.
Une complexité en n^10 (donc polynomiale) va créer des problèmes beaucoup plus tôt qu'une complexité exponentielle.

Tu ajoutes un compteur à un endroit stratégique.
Tu fais tourner ton algorithme avec 40 étudiants à choisir parmi 80, et tu regardes le résultat de ce compteur.
Puis tu recommences avec 40 étudiants à choisir parmi 120
Puis tu recommences avec 80 étudiants à choisir parmi 160
Tu essaies différentes configurations( une douzaine), et tu vois si quand tu multiplies ton nombre d'étudiants par 2, ce compteur est multiplié par 2, ou par 4, ou par 100.

Ou sinon, tu regardes ligne à ligne ce que fait ton code.

[sandaff]

Bonjour Monsieur tbc92;

Quel est l'intérêt de la question 'complexité de l'algorithme', 'complexité Polynomiale' ?

C'est très important de se situer avant de continuer;

D'abord j'ai fait la trace plusieurs fois sans détecter un résultat faux qui est un grand espoir; maintenant si vos analyses montre que c'est polynomiale cela ne veux pas dire que l'algo est parfait ; ça m’encouragera investiture mon temps afin de le transformer en un algorithme acceptable avec vous les experts;

Donc avec ou sans cette algorithme, on aura la certitude que le problème principal que je vais vous affiché ici serra résolu par quel qu’un qui a un meilleur algo que moi;

Donc j'ai besoin de le savoir !

Tu ajoutes un compteur à un endroit stratégique.

C'est ici je dois placer ce compteur? càd dans sélection

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
for(int i = 0; i<c; i++)  {
 
			 Ajouter=false;			 
		 do {		
 
                 compteur++ ;
 
		    } while (Ajouter==false);
 
 
		 }

Merci pour votre intervention

[tbc92]

Tu peux mettre compteur++ plusieurs fois, à plusieurs endroits. Comme ça, tu vas mesurer le cumul de plusieurs choses. Et tu ne vas pas passer à côté d'un traitement qui pourrait poser problème.

Ou tu peux chronométrer le temps d'exécution. Si quand on ajoute 5 étudiants (55 au lieu de 50) , le temps d'exécution augmente de 50%, c'est un bon indicateur pour dire que ça va exploser quand on va atteindre 100 ou 200 étudiants.

[Guesset]

Bonjour,

1. Quand je dis que m ne sert à rien c'est qu'il n'est pas utilisé dans la boucle principale de sélection qui utilise c (nombre de chambres) une valeur qui est saisie localement. Il n'y a aucune garantie que m = 2*c.
2. Dans une population de n personnes combien y a t'il de paires possibles ? C'est simple, c'est n*(n-1)/2 (la division par 2 vient du fait que la paire (a, b) = (b, a) ). Donc, dans le pire des cas (tous les étudiants sont des caractériels) la dimension sera n*(n-1)/2 (un triangle de la matrice carrée hors la diagonale). Si on ne veut pas se casser la tête on peut utiliser une matrice n² en prenant soin de rendre incompatible la diagonale (pas de couple avec soi-même) et en enregistrant systématiquement NoDuo[id1][id2] = true et NoDuo[id2][id1] = true au moment de la création des incompatibilités.

Un programme qui ne vérifie rien cours à l'échec d'autant qu'ici on utilise des saisies manuelles dont le taux d'erreur n'est jamais marginal.

Je répète que l'algorithme ne fonctionne pas. Outre les remarques précédentes, la possibilité d'avoir id1 = id2 n'est pas exclue dans la sélection et ça ce n'est pas une erreur de saisie mais de programmation. Un autre exemple, si c > n/2 la boucle de sélection ne s'arrête pas : après avoir "consommé" tous les étudiants il reste des chambres libre et l'algo va continuer à chercher à les remplir alors qu'il n'a plus personne à mettre dedans.

Salutations