Remerciez-le!

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

Corrigerattrapage2011 12 pdf

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 IL Module ? ? Algorithmique Avancée et Complexité ? ? Date Corrigé de l ? examen de rattrapage Exercice NP-complétude points On considère le problème de décision ISOGRAPHES suivant ? Description deux graphes orientés G V E et G V E de même nombre n de sommets avec V X ? Xn et V Y ? Yn ? Question existe-t-il un isomorphisme f V ??V tel que pour tous i j dans ? n Xi Xj est arc de G si et seulement si f Xi f Xj est arc de G Le but de l ? exercice est de montrer que le problème ISOGRAPHES appartient à la classe de complexité NP Pour ce faire il vous est demandé de trouver un algorithme polynômial de validation pour le problème que vous appellerez validation ig Procédez comme suit Donnez l ? algorithme sous forme d ? une fonction booléenne dont il est important que vous expliquiez les paramètres numérotez les lignes de votre algorithme Calculez le nombre d ? opérations élémentaires de l ? algorithme en fonction d ? une taille n à préciser Appelez ce nombre T n Montrez que T n ? nk pour une certaine constante k à préciser Solution L ? algorithme de validation est comme suit Il est écrit sous forme d ? une fonction booléenne à quatre entrées n C C et c La paire n C C donne le codage de l ? instance du problème L ? instance consiste en deux graphes orientés G et G chacun à n sommets V X ? X n V Y ? Y n C est la matrice d ? adjacence de G de taille nn booléenne o C i j si et seulement si X i X j est arc de G C est la matrice d ? adjacence de G de taille nn booléenne o C i j si et seulement si Y i Y j est arc de G L ? entrée c est un certi ?cat consistant en un tableau de taille n dont les éléments sont tous di ?érents et appartiennent à l ? ensemble ? n le certi ?cat est un tableau de permutation de taille n le certi ?cat représente un isomorphisme f V ??V il doit être interprété comme suit pour tout i n f X i Y c i L ? algorithme de validation retournera VRAI ssi pour tout i allant de à n pour tout j n X i X j est arc de G si et seulement si Y c i Y c j est arc de G en d ? autres termes ssi pour tous i j C i j C c i c j Si un entier est représenté sur p bits la paire n C C peut être vue comme un mot de de longueur p Page sur