pied gauche

 

Sciences

Forum > Sciences > [Article] Comment organiser un planning

Article

Éaque

03/09 (12:13)

avatar

Administrateur

Ce matin, je viens de tomber sur un article qui me sera utile, peut-être le sera-t-il à d'autres...

Article

Extrait :


Après de brillantes études, vous avez été recruté au ministère des Affaires étrangères. Un jour le ministre vous convoque pour vous annoncer la bonne nouvelle : ça y est, il a enfin réussi à convaincre ses homologues de 100 pays à envoyer des ambassadeurs à Paris dans une semaine pour un congrès sur la paix et les échanges culturels. Maintenant c’est à vous d’organiser tout ça. Ce colloque lui tient vraiment à cœur. Il faut que ça soit une réussite, il en va de l’honneur du pays !

Après d’âpres négociations, 30 thèmes ont été retenus. Cet évènement se déroulera sur une seule journée et sera organisé sous forme de réunions d’une heure chacune, dont les noms de code sont R1… R30. Les participants à chaque réunion sont fixés, vous avez la liste. Le ministère a loué un espace avec 30 salles suffisamment grandes pour accueillir tous les participants.

Le ministre s’exclame : « Grâce aux 30 salles de réunions, tout cela va pouvoir se boucler en une seule heure. Ça donnera ensuite aux délégations l’occasion de se rencontrer de manière informelle pour discuter. Excellent, tout ça ! » Visiblement le « patron » n’a pas tout en tête. Vous lui glissez : « M. le ministre, cela ne va pas pouvoir se faire exactement comme vous dites. Par exemple, il est prévu que le diplomate canadien assiste à trois réunions. Il n’est donc pas possible de mettre les 30 réunions toutes en même temps sinon il ne pourra assister qu’à une seule. » Après un instant de réflexion, le ministre vous dit : « En effet… Je vous confie la mission d’établir le planning. » Avant que vous n’ayez pu émettre un son, il a déjà tourné les talons, préoccupé par les déclarations qu’il devra faire devant la presse. L’organisation n’est pas son problème ; c’est le vôtre...


___

« qu'est-ce qui m'échappe? »
Mouton

07/04 (00:57)

nombre messages : 1

Visiteur

Éaque a écrit :

> Ce matin, je viens de tomber sur un article qui me sera utile, peut-être le sera-t-il à d'autres...

En guise de complément / correction : ce qui est présenté dans l'article est un grand classique, on le retrouve dans à peu près toutes les intros sur la théorie des graphes (par exemple dans le TD que je donne à mes étudiant.e.s).

Le problème de la k-coloration (déterminer si un graphe est coloriable avec k couleurs) est un problème effectivement NP-difficile (et trivialement NP, donc NP-complet) pour k > 2. Il y a par contre un algorithme polynomial intéressant pour la 2-coloration (parce qu'un graphe est 2-colorable si et seulement si il ne contient aucun cycle de longueur impaire, je laisse la démo en exercice [:p]). Le rapport avec P = NP est ténu, c'est juste que si tu trouvais un algo polynomial pour la k-coloration, ou si tu montres qu'il n'en existe pas, alors tu montres que P = NP.

Par ailleurs, même en se limitant à cet unique problème, on peut ajouter qu'il existe un algorithme exact plus rapide que celui qui est proposé (en O(n!)) : https://hal.archives-ouvertes.fr/hal-00906946/document cite un algorithme en O*(2^n) en temps et en espace, par exemple (plus des algos approchés meilleurs que "essayer au pif", mais la notion de ratio est pénible à définir, c'est également décrit dans l'article ci-dessus. Pour la blague, un des auteurs de cet article est un ancien joueur et modérateur de Kraland.

Dans ce genre de domaines, on tombe souvent sur des astuces qui permettent de simplifier le graphe qu'on étudie. Par exemple, on peut supprimer tous les sommets de degré 1 ou 2, parce que si on sait colorier sans eux, on peut les remettre et leur donner une couleur qui n'est pas celle de leurs voisins. (la suppression de ces sommets peut créer de nouveaux sommets de degré 1 ou 2, qu'on peut supprimer aussi, etc.). Par exemple, essayer de trouver une coloration optimale sur les départements français irait en fait assez vite à mon avis (mais j'ai pas testé, je le laisse en exercice).

Dans la vraie vie, on n'utiliserait sans doute pas une méthode aléatoire avec raffinement "à la main", mais des heuristiques plus ou moins complexes, qui donneraient sans doute assez souvent la solution optimale dans les cas simples. Certaines de ces heuristiques se basent sur la relaxation du problème de programmation linéaire associé, mais ça nous emmenerait assez loin de décrire ça.

Enfin, donc, signalons que le problème de coloriage de graphe est souvent cité avec le théorème des 4 couleurs (si un graphe est planaire, ie on peut le représenter dans le plan sans arêtes croisées, alors il est 4 coloriable).

Forum > Sciences > [Article] Comment organiser un planning