Bonsoir tout le monde;

je ne sais pas dans quelle rubrique poser cette question concernant la classe de complexité P et de NP;

Je vois partout que P ⊆ NP mais je ne trouve nul part la démonstration; donc si quelqu’un a un lien vers quoi on peu la trouver je serrai ravis;

Merci pour votre aide;

-
Edité par sandaff 6 novembre 2022 à 0:27:40

Bonjour,

Tu ne le trouves pas probablement parce que c'est trivial.

NP = classe des problèmes qu'on peut résoudre

P = classe des problèmes qu'on peut résoudre en temps polynomial

Si un problème est dans P, on peut le résoudre. Donc il est aussi dans NP. CQFD

Merci pour cet éclairage!

Je suis entrain de finaliser un article mais j'attends la détermination de la complexité de mon dernier algorithme;

Voici le lien sur le sujet sur developpez: https://www.developpez.net/forums/d2138008-3/general-developpement/algorithme-mathematiques/algorithmes-structures-donnees/aide-trouver-complexite-cet-algorithme/#post11890251

J'ai envoyé un message privé à celui qui m'a calculé la complexité du premier algo et j'attends sa réponse;

Mais voici cette solution ici:

Si le dortoir est une grande salle ou un couvant ou tous les sélectionnés sont ensemble alors:

J'ai conçu la fonction sélection comme suit:

J'ai créer une copie du tableau étudiant dont je pioche les sélectionnés;

Cette fois-ci la sélection se fait un à un au lieu de deux à deux comme la précédente;

Je tire un et je le supprime dans la copie ainsi que tous ceux qui sont incompatibles avec lui;

Il y a donc une recherche comme d'habitude et après tout, on obtiens une nouvelle liste;

-Si on a 400 étudiants, on tire un, ça reste 399; plus ses incompatibilités, admettons 5 qui sont ensuite supprimées, on a 394 restants;
-Si je tire un deuxième, on a 393, plus ses incompatibilités admettons 13, on a 380 restants qui sera la nouvelle liste;
ainsi de suite, ...

on arrête avec trois conditions:

-Tout le monde est incompatible avec tout le monde et un seul est tiré, la copie est vide donc on arrête; n1=0 qui est la taille du tableau;

-L’étudiant sélectionné est incompatible avec un autre, deux autres, trois autres, etc..
1- on arrête n1=0 donc la copie est vide et le nombre sélectionnés < 100 demandés, donc compteur<100;
2-on arrête avec le nombre sélectionnés = 100 demandés, donc compteur= 100; on ne se souci plus de n1;

Voyant donc l'algo, aucun tirage n’échoue et le nombre d'opération peut être < n;

Ma demande est de déterminer la complexité de cet algo?

je suis parti du constat que:

Dans le cas de voyageur de commerce, dire qu’entre tel nombre de villes peut on avoir un chemin inférieur à une distance de longueur L ?

Ne signifie pas que la distance trouvée de longueur d<L est la plus petite distance qu’on peut trouver ;

De même ici dire que parmi 400 cent étudiants peut on trouver une liste de 100 sans l’apparition d’aucun pair d’étudiants incompatibles ?

Ne signifie pas que le choix effectué est le meilleur par rapport à toutes les possibilités de choix qu’on peut avoir ;

 Donc ce n'est pas un choix de solution mais plutôt un résultat qui ne comporte aucun pair d'incompatibilité ou qui respect le critère de choix;

voici l'algo:

// Sélectionbis par tirage au sort deuxième version________________________________________________________________
		   public static void Selection2(String [][] tabEtudSelect, String [][]tabEtud,
		      String [][]tabEtudInc, Scanner keby,String clobalId) {
		      int n = tabEtud.length;		     
		      int  EI=tabEtudInc.length; // nombre étudiants incompatibles
		      String id1;		      
		      String idRe;		    
		      int n1;
		      String idSup;
		      int cpteur;
		      //int EC=n*n-1/2-EI; // nombre etudiants compatible		              
		      // Mets la liste étudiant dans ArrayList pour faciliter le traitement
		      ArrayList<String> tabEtudCopy = new ArrayList< String > (); 
		      // Récupère les selections et à la sortie recopierra dans tabEtudSelect
		      ArrayList<String> tabEtudSelectCopy = new ArrayList< String > ();		     
		      int c = tabEtudSelect.length; // Nombre de plce à pouvoir / qui est equivalent aux nombrex de chambres dans recherche1
		     //création de copy de la table etudiant
		      for(int i = 0; i < n; i++) {
		         tabEtudCopy.add(tabEtud[i][0]); // Transfert de la liste étudiant dans la copie
		      }	    		    	            
 
	            /*Sélection des étudiants  dans un couvant ou une grande salle*/
 
		      if(EI==n*n-1/2) {		    	 
		          // si tout le monde est incompatible avec tout le monde alors on n'entre pas dans la boucle;
		    	  // en plus on a deux choix
		    	  //1-afficher le message d'information
		    	  //2-faire une seule selection et sortir
		    	  System.out.println("Selection impossible, tout le monde est incompatible avec tout le monde!");
		         /* OU
		            Random random = new Random();        // Tirage au sort ou nombre aleatoire	        		                       
		            n1 = random.nextInt(n);              // Choix dans l'intervale  0 et n
		            id1 = tabEtudCopy.get(n1); 
		            tabEtudSelectCopy.add(id1);            // Si id1 retenu, l'etudiant sera selectionné			 		   			
 
		    	  */
		           } else {
 
		    	  cpteur=0;         
		         Random random = new Random();        // Tirage au sort ou nombre aleatoire
	                 int nb;
		         do {		           
		            n1  = tabEtudCopy.size();            // Détermine le nombre éléments restants dans la copie étudiantes; chaque sélection est supprimé dedans 
		   	   if(n1 == 1){ 
		   	   id1 = tabEtudCopy.get(n1);          // il est le seul à être logé	dans une chambre 	
		          tabEtudSelectCopy.add(id1);            // Il est rangé dans le tirage de façon definitive
		          tabEtudCopy.remove(n1);           // Oté du tableau 		
		          n1=0; 
                          cpteur++ ;
		   	  } else {
		   		    // la sélection continu même si le nombre de chambre > aux nombres compatibilités, car la sélection s’arrête quand n1=0
		          nb = random.nextInt(n1);              // Choix dans l’intervalle  0 et n
		          id1= tabEtudCopy.get(nb);            // Si id1 retenu, l’étudiant sera sélectionné		            
		          clobalId = id1;                      //clobalId est un string car c'est id1 declaré comme variable clobale		           
		          idRe = recherche(tabEtudInc,clobalId); // id1 dans liste d’incompatibilité ?		          
		          if(idRe == "-1") {		            	
		               // Si oui alors il est ajouté
		           tabEtudSelectCopy.add(id1);   // Il est rangé dans la sélection		            	  
		           tabEtudCopy.remove(nb);           // Oté du tableau pour ne pas retomber sur le même		              
		            cpteur++;
		            n1  = tabEtudCopy.size();		             
 
		            }
		            else {  
 
		            tabEtudSelectCopy.add(id1);   // Il est rangé dans la sélection		            	  
			    tabEtudCopy.remove(nb);           // Oté du tableau pour ne pas retomber sur le même			              
 
			         // suppression des id incompatibles avec id sélectionné
			      idSup="-1";
			      for(int i = 0; i < tabEtudInc.length; i++) {// recherche de l'id dans incompatibilité
			     for(int j = 0; j < 2; j++ ) {
			      if(id1.equals(tabEtudInc[i][j])) { 
			      if(j == 0) { // correspond à id sélectionné
			      idSup = tabEtudInc[i][1];  // correspond à id incompatible
			      }else { // j=1 correspond à id sélectionné
				idSup = tabEtudInc[i][0];  //j=0 correspond à id incompatible
				}
			       	  // suppression dans la liste d’étudiants
			     int h=0;
			     sortir:
			     for(String elem:tabEtudCopy) {  			            				              			            				         
			        h++;
			     if(idSup==elem) {                  // id trouvé
			      	tabEtudCopy.remove(h) ;       //id supprimé
			   	break sortir;
				  }
			         }	    				   		               
			         }			            	  
		  	         }	 	
		                }
 
			       cpteur++;
			      n1  = tabEtudCopy.size();
 
		            }
 
		   	   }  		   		 
 
		         } while((cpteur!=c) && (n1!=0));
 
		      /* récupère la sélection en tableau static si le travail est fini 
		      et tabEtudSelectCopy aura une taille = 2*c   */		      
		      int j = 0;
		      for(String elem:tabEtudSelectCopy) {      
		         tabEtudSelect[j][0] = elem;             // Récupération
		         System.out.println("tabEtudSelect: "+elem);
		         j++;
		      }
		   }
 
		   }

voici le problème initial:

c'est  tiré sur le site web de technoscience :https://www.techno-science.net

<< Supposons que vous organisez des logements pour un groupe de quatre cents étudiants universitaires. L'espace est limité et seulement une centaine d'étudiants recevront des places dans le dortoir. Pour compliquer les choses, le doyen vous a fourni une liste de paires d'étudiants incompatibles, et a demandé qu'aucune paire de cette liste n'apparaisse dans votre choix final. C'est un exemple de ce que les informaticiens appellent un problème NP, puisqu'il est facile de vérifier si un choix donné de cent élèves proposé par un collègue est satisfaisant (c'est-à-dire qu'aucun couple pris dans la liste de votre collègue n'apparaît également sur la liste de le bureau du doyen), mais la tâche de générer une telle liste à partir de zéro semble être si difficile qu'elle est complètement irréalisable. En effet, le nombre total de façons de choisir cent étudiants parmi les quatre cents candidats est supérieur au nombre d'atomes dans l'univers connu ! Ainsi, aucune civilisation future ne pourrait jamais espérer construire un supercalculateur capable de résoudre le problème par la force brute ; c'est-à-dire en vérifiant toutes les combinaisons possibles de 100 étudiants. Cependant, cette difficulté apparente ne peut que refléter le manque d'ingéniosité de votre programmeur. En fait, l'un des problèmes en suspens en informatique est de déterminer s'il existe des questions dont la réponse peut être vérifiée rapidement, mais qui nécessitent un temps incroyablement long pour être résolues par une procédure directe. Des problèmes comme celui énuméré ci-dessus semblent certainement être de ce genre, mais jusqu'à présent, personne n'a réussi à prouver que l'un d'entre eux est vraiment aussi difficile qu'il y paraît, c'est-à-dire, qu'il n'y a vraiment aucun moyen réalisable de générer une réponse à l'aide d'un ordinateur. Stephen Cook et Leonid Levin ont formulé indépendamment le problème P (c'est-à-dire facile à trouver) contre NP (c'est-à-dire facile à vérifier) en 1971 >>

Merci!

-
Edité par sandaff 7 novembre 2022 à 0:23:40