Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrige examen 2 Université des Sciences et de la Technologie Houari Boumediène Faculté d ? Electronique et d ? Informatique Département d ? Informatique LMD Master ère Année RSD Module ? ? Algorithmique Avancée et Complexité ? ? Corrigé de l ? examen Exe

Université des Sciences et de la Technologie Houari Boumediène Faculté d ? Electronique et d ? Informatique Département d ? Informatique LMD Master ère Année RSD Module ? ? Algorithmique Avancée et Complexité ? ? Corrigé de l ? examen Exercice NP-complétude On considère le problème de décision -COLORIAGE de -coloriage d ? un graphe ? Description un graphe ? Question Peut-on colorier les sommets du graphe avec trois couleurs distinctes de telle sorte qu ? il n ? y ait pas de n ?uds adjacents de même couleur Deux n ?uds u et v sont adjacents si et seulement si u v ou v u est arc du graphe Donnez un algorithme polynomial de validation pour le problème -COLORIAGE Expliquez la polynomialité de l ? algorithme Réponse L ? algorithme de validation est comme suit Il est écrit sous forme d ? une fonction booléenne à trois entrées n C et couleurs La paire n C donne le codage de l ? instance du problème L ? instance est un graphe G V u ? un est l ? ensemble des sommets de G de cardinal n et E l ? ensemble de ses arcs C est la matrice d ? adjacence de G de taille nn booléenne o C i j si et seulement si ui uj est arc de G L ? entrée couleurs est un certi ?cat consistant en un tableau de taille n dont les éléments appartiennent à l ? ensemble Vert Blanc Rouge Le certi ?cat couleurs associe à chacun des sommets de G une couleur l ? élément couleurs i est la couleur associée au sommet ui L ? algorithme retourne VRAI si et seulement si le certi ?cat couleurs valide l ? instance c ? est-àdire si et seulement si il n ? existe pas de n ?uds adjacents pour lesquels il associe la même couleurs Si un entier est représenté sur p bits la paire n C peut être vue comme un mot de de longueur p les p premiers bits ou coderont le nombre n de sommets de l ? instance les pn suivants coderont la ère ligne de la matrice C ? les pn derniers bits coderont la toute dernière ligne de la matrice C Mais on peut faire mieux voir la paire n C comme un mot de de longueur p C étant booléenne on peut coder chacun de ses éléments avec un unique bit et non avec p bits Page sur CBooléen validation c n C couleurs i while k CRéponse main Lecture de l ? instance de -coloriage le nombre n de sommets et la matrice C d ? adjacence cond max il y a coloriages certi ?cats possibles i while cond i L ? existence d ? un algorithme polynomial de validation pour un problème de décision su ?t-elle pour dire que le problème est NP-complet Expliquez Réponse L ? existence d ? un algorithme polynomial de validation pour un problème de décision ne permet