Remerciez-le!

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

Université de Dschang-cours sur la notion de NP-complétude TABLE DE MATIERES OB

Université de Dschang-cours sur la notion de NP-complétude TABLE DE MATIERES OBJECTIF PEDAGOGIQUE ................................................................................................................. 3 INTRODUCTION ................................................................................................................................... 4 1. GENERALITES .............................................................................................................................. 5 1.1 Décidabilité ............................................................................................................................. 5 1.2 Machine de Turing .................................................................................................................. 5 1.2.1 Machine de Turing déterministe ...................................................................................... 5 1.2.2 Machine non déterministe ............................................................................................... 7 2. LA CLASSE P ................................................................................................................................. 8 2.1 Définition : .............................................................................................................................. 8 2.2 Exemple de problème dans P : ................................................................................................ 8 3. LA CLASSE NP : .......................................................................................................................... 10 3.1 Définition : ............................................................................................................................ 10 3.2 Certificats et vérifieurs (Vérificateurs) : ................................................................................ 11 3.2.1 Définition : .................................................................................................................... 11 3.3 Réduction Polynomiale : ....................................................................................................... 13 3.3.1 Définition : .................................................................................................................... 13 4. CLASSE CO-NP ........................................................................................................................... 14 4.1 Définition : ............................................................................................................................ 14 5. NP-COMPLETUDE ...................................................................................................................... 15 5.1 Motivation : ........................................................................................................................... 15 5.2 Définitions : ........................................................................................................................... 15 5.2.1 Conséquence : ................................................................................................................ 16 5.2.2 Généralisation : .............................................................................................................. 16 5.3 A quoi sert de prouver la NP-complétude d’un problème ? .................................................. 16 5.4 Méthode pour prouver qu’un problème est NP-complet : ..................................................... 17 5.5 Comment gérer la NP-complétude ? ..................................................................................... 19 5.6 Quelques exemples de problèmes NP-complets .................................................................... 21 5.6.1 Sur les graphes : ............................................................................................................ 21 5.6.2 Sur les entiers : .............................................................................................................. 22 CONCLUSION ..................................................................................................................................... 23 BIBLIOGRAPHIE ................................................................................................................................ 24 FICHE DE TRAVAUX DIRIGES ........................................................................................................ 25 Université de Dschang-cours sur la notion de NP-complétude LISTE DES TABLEAUX ET FIGURES LISTE DES FIGURES Figure 1: exemple de machine de Turing non déterministe .................................................................... 7 Figure 2: chemin acceptant ...................................................................................................................... 7 Figure 3: illustration du problème SAT ................................................................................................. 12 Figure 4: graphe utilisé pour l'algorithme ............................................................................................. 17 Figure 5: gadget ..................................................................................................................................... 18 Figure 6:graphe initial ........................................................................................................................... 20 Figure 7: arbre couvrant ........................................................................................................................ 20 Figure 8:chemin trouvé ......................................................................................................................... 20 LISTES DES TABLEAUX Tableau 1: table de transition .................................................................................................................. 6 Tableau 2:symbole lu en tête de lecture .................................................................................................. 6 Université de Dschang-cours sur la notion de NP-complétude 3 OBJECTIF PEDAGOGIQUE L’objectif de ce chapitre c’est d’être plus précis que le paysage étudié en calculabilité en considérant dorénavant que des problèmes clairement décidables et en se posant la question de savoir, si l’on peut les résoudre efficacement ? Il s’agira donc de distinguer ce qui est raisonnable de ce qui ne l’est pas en temps de calcul. Université de Dschang-cours sur la notion de NP-complétude 4 INTRODUCTION En théorie de la complexité, un problème NP-complet est un problème de décision vérifiant les propriétés suivantes : Il n’a pas encore été trouvé une solution pour le résoudre en temps polynomial dans le pire des cas, Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale. Cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP. Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP- complet, on ne sait pas en trouver une efficacement. C'est le cas, par exemple, du problème SAT ou de celui du coloriage de graphe. Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel à la taille des données d'entrée dans le pire des cas, et sont donc inexploitables en pratique même pour des instances de taille modérée. La seconde propriété de la définition implique que s'il existe un algorithme polynomial pour résoudre un quelconque des problèmes NP-complets, alors tous les problèmes de la classe NP peuvent être résolus en temps polynomial. Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ≠ NP, une question ouverte qui fait partie des problèmes non résolus en mathématiques les plus importants à ce jour. Dans ce Chapitre, nous allons nous intéresser aux classes P et NP, sont-elles différentes ? Nous allons le découvrir en présentant d’abord la notion de décidabilité et machine de Turing en I, la classe P en II, ensuite la classe NP en III la notion de NP-COMPLETUDE en VI et quelques exemples de problèmes NP-complets en V. Université de Dschang-cours sur la notion de NP-complétude 5 1. GENERALITES 1.1 Décidabilité La théorie de décidabilité donne un cadre pour déterminer si un problème mathématique peut être résolu par un ordinateur. Le cas échéant, la théorie de la complexité donne un cadre pour déterminer si ce problème peut être résolu par un algorithme efficace (qui n’utilise qu’une quantité raisonnable de mémoire et qui s’exécute en un temps raisonnable). Un problème de décision est une question mathématique dont la réponse est <<oui>> ou <<non>>. (Vraie ou faux) Exemple : a) Le problème de primalité prime qui permet de savoir pour un nombre donné n s’il est premier ou pas. b) Le problème du circuit hamiltonien qui permet de savoir si pour un graphe G on peut trouver un circuit passant une fois et une seule par tous les sommets. Les objets mathématiques sur lesquels porte le problème sont des instances du problème. Pour le problème de primalité une instance c’est un nombre entier, pour celui du circuit hamiltonien c’est un graphe. On cherche à savoir s’il existe une procédure algorithmique qui permette de calculer pour chaque instance si la réponse est oui ou non. Un problème de décision est décidable s’il existe une machine de Turing déterministe qui accepte les instances ou la réponse est oui. 1.2 Machine de Turing 1.2.1 Machine de Turing déterministe Une machine de Turing déterministe est la donnée : ➢ D’un ruban infini : chaque case contient un élément d’un alphabet fini R qui contient un caractère <<Blank>> ➢ D’une tête de lecture : celle est dans un état à choisir dans un ensemble fini E.il existe un état initial et des états finaux. ➢ D’une fonction de transition, qui à partir de l’état de la tête de lecture et du contenu de la case lue donne le nouvel état de la tête, le nouveau contenu de la case et déplace la tête de lecture d’une case vers la droite ou la gauche. Les données de départ sont inscrites sur le ruban et la tête de lecture est dans son état initial. Université de Dschang-cours sur la notion de NP-complétude 6 Exemple : Ruban 0 et 1 ; 3 états A (initiale), B et C (final) Table de transition : Tableau 1: table de transition 0 1 £ A B, 0, → B, 1, → A, £, → B B, 0, → B, 1, → C, 0, → Tableau 2:symbole lu en tête de lecture A … £ £ 0 1 1 £ £ £ £ … A … £ £ 0 1 1 £ £ £ £ … B … £ £ 0 1 1 £ £ £ £ … B … £ £ 0 1 1 £ £ £ £ … B … £ £ 0 1 1 £ £ £ £ … C … £ £ 0 1 1 0 £ £ £ … NB : cette machine effectue une multiplication par 2 en supposant que c’était un nombre binaire. Soit T une machine de Turing déterministe, le mot d’entrée x est représenté par le mot (fini) écrit sur le ruban au départ de l’exécution de la machine. • Si la machine atteint un état final après un nombre fini d’étapes, on dit que le mot x est accepté et le mot inscrit sur le ruban après l’arrêt s’appelle mot de sortie et est noté T(x). • Si la machine s’arrête sans atteindre un état final ou si la machine ne s’arrête jamais, alors x est rejeté. Université de Dschang-cours sur la notion de NP-complétude 7 1.2.2 Machine non déterministe Le concept de machine de Turing non-déterministe est une variante de la notion de machines de Turing classique déterministe : ➢ La définition d’une machine de Turing non-déterministe est exactement comme celle de la notion de machine de Turing (déterministe) sauf sur un point : • Pour tout état et une lettre lue en face de la tête de lecture donnée, δ ne définit pas un seul triplet de Q x Г x {←, →}, mais un ensemble de triplet • Intuitivement lors d’une exécution la machine a la possibilité de choisir n’importe quel triplet. La différence est qu’une machine de Turing non-déterministe n’a pas une exécution unique sur une entrée w, mais éventuellement plusieurs En fait, les exécutions de la machine sur un mot w donnent lieu à un arbre de possibilités (arbre de dérivation), et l’idée est qu’on accepte un mot si l’une des branches de cet arbre contient une configuration acceptante. Exemple : Figure 1: exemple de machine de Turing non déterministe • Exécutions sur le mot w = 010111 : Figure 2: chemin acceptant On dit que la machine accepte le mot w en Temps T= 7 Université de Dschang-cours sur la notion de NP-complétude 8 Conclusion : On dit donc qu’un mot est accepté par une machine de Turing non- déterministe s’il y’a une exécution sur ce mot partant de l’état initial qui se termine en l’état acceptant. 2. LA CLASSE P La théorie de la complexité cherche à classer les problèmes de décision (ceux qui ont une réponse par oui ou uploads/Litterature/ np-complets.pdf