Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.85 KB | None | 0 0
  1. Bonjour,
  2.  
  3. N'ayant pas eu le temps de reposer la question en cours de td, je me permets de vous envoyer ce mail :
  4.  
  5. -> Concernant la séance de lundi, vous disiez qu'il était nécessaire qu'au moins un pays ait une forme particulière et je ne vois pas vraiment pourquoi.
  6. De plus, il y a-t-il un exercice permettant de le vérifier ? Cela a-t-il un rapport avec le théorème des 4 couleurs ?
  7.  
  8. -> Concernant la séance d'aujourd'hui, la notion de NP-Complet (qui intervient dans l'exposé de Turán, le problème de MAX CUT étant un des 21 problèmes NP-Complets) n'est pas évidente :
  9.  
  10. " Un problème P est polynomialement réductible à un autre problème Q s'il existe un algorithme polynomial permettant de ramener la recherche d'une solution de P à celle d'une solution de Q. "
  11.  
  12. Lorsqu'il est question de dire que le problème P est équivalent à SAT (c'est-à-dire qu'il est NP-Complet), cela signifie-t-il à la fois que P est réductible à SAT, et inversement que SAT est réductible à P ? Car sinon je ne vois pas pourquoi le fait de pouvoir résoudre l'un grâce à l'autre permettrait forcément de dire que l'ensemble des 21 problèmes peuvent être définis comme étant P ou NP dès lors qu'un seul d'entre eux est défini (ils sont écrits sous forme de hiérarchie où certains sont réductibles à d'autres, mais il n'est pas fait mention d'une éventuelle réciproque : pour exemple, le problème du sac à dos a été défini comme étant NP-Complet après avoir trouvé une réduction à partir de la couverture exacte :
  13.  
  14. Peut-on dire qu'il s'agit d'une équivalence, ou bien uniquement que si le problème réduit à un autre est NP, alors ce dernier est NP et inversement si le problème d'origine est P alors tout problème que l'on réduit à celui-ci est alors P ?
  15.  
  16.  
  17. -> Concernant l'exposé du groupe 5 sur MAX CUT :
  18.  
  19. J'ai compris l'idée du MAX CUT (à partir d'un graphe (simple et connexe) non orienté de n sommets (dont x sommets marqués) et m arcs reliant les différents sommets, on veut déterminer le nombre d'arêtes p que l'on doit couper (supprimer) tel que l'on isole tout sommet marqué d'un sommet non marqué, et ce dans le pire des cas possibles.
  20. La complexité de ce type de problème est NP-Complet et il est donc inutile de chercher à le résoudre de manière polynomiale.
  21. Il est trop compliqué de trouver la valeur exacte, on cherche donc à l'approcher (d'où 0.8785...). Dans un premier temps on procède en assignant à chaque sommet un marquage aléatoire (une chance sur deux) : pourquoi l'espérance du nombre d'arêtes bicolores est-elle alors forcément plus grande que la moitié du nombre d'arêtes à supprimer dans le pire des cas ? "Par symétrie, avec probabilité > 1/2"
  22.  
  23. Vient alors une méthode géométrique afin de résoudre le problème de manière plus précise, en dehors de l'idée de se ramener à un problème dans une sphère de rayon 1 :
  24. Si on note OBJ le nombre d'arêtes bicolores dans un exemple à trois sommets et trois arêtes, on peut faire une analogie avec la somme des distances au carré des différents sommets sur la sphère notée SDP (sommets qui sont le plus espacé possible, définissant alors le plan où se trouve le graphe), mais uniquement à condition que le produit scalaire des différents vecteurs v1, v2 et v3 (correspondants aux vecteurs du centre de la sphère vers chacun des points du graphe) soit égal à 1 ou -1 selon leur "couleur" (le fait qu'il soit marqué ou non). Cependant pourquoi devrait-il valoir des valeurs aussi particulières sachant qu'ils ne sont pas forcément colinéaires ?
  25.  
  26. v1.v2 = ||v1|| * ||v2|| * cos(v1^v2) = cos(v1^v2)
  27. où v1^v2 représente l'angle entre les deux vecteurs (les points se trouvant sur la sphère, leur norme est donc égale à 1).
  28.  
  29. Il est clair que si on suppose que deux des vecteurs sont colinéaires, on ne se trouve pas dans la situation où ils sont le plus éloignés possibles (ils devraient plutôt être dans une sorte de trièdre).
  30.  
  31.  
  32. De plus, la probabilité qu'une arête soit coupée par le plan définissant le marquage soit égale à arccos(vi.vj)/pi ne semble pas évidente, probabilité nécessaire afin d'arriver à l'approximation de 0.8785... fois la valeur maximale de MAX CUT
  33.  
  34.  
  35. Ces remarques sont principalement nées de l'étude du premier document fourni ( http://images.math.cnrs.fr/Le-decoupage-des-graphes.html ) ainsi que quelques recherches annexes mais un certain nombre d'éléments m'empêchent de comprendre réellement comment le MAX CUT est mis en place (sachant que le travail de l'exposé consiste essentiellement à traduire cette notion en un temps réduit et de manière efficace, il est difficile de synthétiser une idée que l'on a du mal à appréhender).
  36.  
  37. Je ne sais pas exactement quelles types de réponses vous pouvez fournir ou si j'ai bien formulé les différents points me posant problème, mais je vous remercie par avance !
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement