Université BORDEAUX 1 U.F.R. Mathématiques et Informatique
Epreuve de J.Bétréma 19 décembre 2005


Master Informatique 1ère année
INF 300 - Modèles de calcul

Durée: 3 heures
Tous documents interdits.

Exercice 1

Un corrigé est disponible ci-dessous.

A tout entier x on associe sa racine carrée entière, notée r ( x ) , c'est-à-dire le plus grand entier t tel que t2x ; on pose :

φ ( x ) = x - t2 , avec t = r ( x ) .

A tout ensemble d'entiers A on associe l'ensemble B = φ ( A ) défini par :

B = { φ ( x ) | xA } .

  1. Montrer que si A est décidable, alors B est récursivement énumérable.
  2. Soit b un entier donné ; décrire l'ensemble { x | φ ( x ) = b }. Illustrer la réponse pour b = 11.
  3. Soit B un ensemble récursivement énumérable, énuméré par une fonction calculable totale g. Construire un ensemble A récursivement énumérable tel que B = φ ( A ) ; donner la fonction f qui énumère A.

    Note : il y a beaucoup (et même une infinité) de réponses possibles à cette question (expliquer pourquoi) ; donner une réponse aussi simple que possible.

  4. Prouver qu'un ensemble énuméré par une fonction croissante (strictement) est décidable.
  5. Donner plusieurs exemples d'ensembles récursivement énumérables et indécidables.
  6. Soit B un ensemble du type précédent, c'est-à-dire récursivement énumérable et indécidable. Construire un ensemble A décidable tel que B = φ ( A ).

Exercice 2

Un corrigé est disponible ci-dessous.

Une machine de Turing ne dispose pas de mémoire à accès direct (RAM); l'objet de cet exercice est de construire des machines de Turing qui simulent les instructions LOAD et STORE d'un processeur classique. Pour cela on suppose la bande divisée en trois parties :

Les trois parties de la bande sont consécutives, et séparées par le symbole '#'. Pour simplifier les notations, on suppose que l'alphabet utilisé dans le registre de transfert et dans la RAM est constitué des cinq symboles 0, 1, a, b et c. La machine qui simule l'instruction LOAD doit copier les k cellules de la RAM d'adresse de base n (c'est-à-dire les cellules numérotées n, n + 1, … , n + k - 1) dans le registre de transfert ; la machine qui simule l'instruction STORE doit copier le contenu du registre de transfert dans les k cellules de la RAM d'adresse de base n. Les autres cellules doivent être inchangées lorsque la machine s'arrête, à l'exception de l'adresse (dont on autorise la destruction).

Attention : les règles des machines doivent être écrites et commentées très clairement ; une réponse qui ne respecte pas cette consigne risque de ne rapporter aucun point. La position de la tête de lecture en début de programme peut être choisie librement, mais doit être indiquée sur la copie en début de réponse.

  1. Donner les règles d'une machine LOAD, en supposant k = 1 (autrement dit, le registre de transfert contient une seule cellule).
  2. Comment modifier la machine précédente pour la transformer en une machine STORE (toujours avec k = 1) ?
  3. Comment modifier la machine de la question 1 pour traiter le cas général (registre de transfert de taille k) ? Note : on pourra se contenter d'indiquer les principes de la modification, sans écrire explicitement toutes les règles.

Exercice 3

Un corrigé est disponible ci-dessous.

Certains langages de programmation comportent une instruction de filtrage qui permet de raisonner sur un objet selon sa structure. Appliquée à un entier n qui soit vaut 0, soit est le successeur d'un entier m, cette instruction peut s'écrire :

match n with 0 => t | succ m => f ( m ) end

t désigne une expression quelconque, et f une procédure. Attention : ne pas confondre avec une définition récursive — on ne suppose pas que l'expression ci-dessus définit f ( n ). Ecrire un λ-terme match tel que :

match 0 T F → … → T
match 1 T F → … → F 0
match 2 T F → … → F 1
match 3 T F → … → F 2 etc.

quels que soient les λ-termes T et F (la flèche → désigne comme d'habitude une β-réduction). Note : on pourra utiliser le λ-terme pred (prédécesseur) sans le redéfinir ; par contre on évitera si possible d'utiliser le λ-terme iszero (il existe une solution élégante sans lui).

Exercice 4

Un corrigé est disponible ci-dessous.

On rappelle que le problème de la couverture d'un graphe, appelé traditionnellement VERTEX-COVER, est le suivant :

  1. Expliquer pourquoi le problème serait absurde si on ne spécifiait pas la taille de la couverture.
  2. "Un graphe qui possède une couverture de taille k possède une couverture de taille l pour tout l inférieur à k" : cette affirmation est-elle vraie ou fausse ? Note : la réponse doit être justifiée, sinon elle ne rapporte aucun point.
  3. "Γ est une couverture de G si et seulement si l'ensemble complémentaire de Γ est formé de sommets indépendants (c'est-à-dire non liés par des arêtes)" : cette affirmation est-elle vraie ou fausse ? Note : la réponse doit être justifiée, sinon elle ne rapporte aucun point.
  4. Montrer soigneusement que VERTEX-COVER appartient à la classe NP : expliquer en quoi consiste, dans ce cas, un certificat, et évaluer précisément la complexité de l'algorithme de vérification du certificat.
  5. Le théorème de COOK permet-il d'affirmer qu'il existe une réduction polynomiale VERTEX-COVERSAT, ou l'inverse ? Note : la réponse doit être soigneusement justifiée, sinon elle ne rapporte aucun point.
  6. On cherche à associer à une instance de VERTEX-COVER une formule booléenne Φ satisfiable si et seulement si le graphe G possède une couverture de taille k. Pour cela on représente un ensemble Γ de sommets par n variables booléennes x1xn ,xi vaut 1 si le sommet numéro i appartient à Γ, 0 sinon.

    1. Ecrire les clauses qui expriment que Γ est une couverture du graphe G.
    2. Les clauses précédentes ne suffisent pas pour construire Φ : expliquer pourquoi. Expliquer si possible les principes permettant de construire les clauses manquantes (on ne demande pas d'écrire explicitement ces clauses).

Dans la suite on part inversement d'un ensemble Φ de clauses de taille 3, auquel on veut associer une instance de VERTEX-COVER. Pour cela on construit un graphe comme suit :

  • A chaque variable booléenne xi on associe un segment Ui Vi (c'est-à-dire deux sommets reliés par une arête).
  • A chaque clause on associe un triangle A B C.
  • Si par exemple la clause vaut

    x1 ∨ ¬ x3x4 ,

    on relie par des arêtes les sommets U1 , V3 et U4 aux trois sommets du triangle.

Codage d'une clause, cliquer pour agrandir

De façon générale, si la formule Φ comporte m clauses (de taille 3) et n variables, le graphe associé G comporte 3 m + 2 n sommets. Questions :

  1. Compléter le dessin en ajoutant la clause ( ¬ x1x2x4 ). Note : le graphe correspondant comporte donc un second triangle.
  2. Montrer qu'une couverture de G est de taille supérieure ou égale à 2 m + n.
  3. Illustrer, sur l'exemple de la question 7, comment tout choix de valeurs pour les 4 variables booléennes, qui satisfait les deux clauses, correspond à une couverture de G de taille 2 m + n = 8, et vice-versa.
  4. Donner un exemple le plus simple possible de graphe du type étudié dans cet exercice (c'est-à-dire formé de m triangles, de n segments, et d'arêtes reliant les sommets des triangles aux extrémités des segments) et qui ne possède pas de couverture de taille 2 m + n. Note : les variables qui apparaissent dans une clause ne sont pas forcément distinctes.
  5. Montrer que la construction ci-dessus est une réduction polynomiale … → … (compléter). Que peut-on en déduire pour le problème VERTEX-COVER ?

Corrigé.

Remarque sur le barème : les notes entre 10 et 30 ont été ajustées pour que la note finale soit comprise entre 10 et 18.

Exercice 1

Voir l'énoncé ci-dessus.

  1. (2 points) La fonction r est évidemment calculable, donc φ aussi. Si A est décidable, voici une procédure qui énumère les éléments de B :

    for (x = 0; ; x++)
      if (x ∈ A)
        afficher φ(x);
    

    On peut aussi dire qu'un ensemble décidable est récursivement énumérable, et que donc il existe une fonction calculable f qui énumère A ; B est alors énuméré par g = φ ο f .

    Note : le but de l'exercice est de montrer que, paradoxalement, on n'a pas : A décidable ⇒ B décidable ; donc tout argument qui prétend montrer dans cette question que B est décidable, est erroné.

  2. (2 points) φ ( x ) = bx = b + t2 , avec x < (t + 1)2 ! D'où la condition sur t :

    b < 2 t + 1 , soit : ( b - 1 ) / 2 < t .

    Par exemble pour b = 11, la valeur minimale de t est 6, d'où :

    { x | φ ( x ) = 11 } = { 11 + 62 = 47, 11 + 72 = 60, 11 + 82 = 75, … }

    L'essentiel est de comprendre qu'on a φ ( b + t2 ) = b, dès que t est suffisamment grand ! Ce résultat peut se voir directement sur l'exemple ci-dessus ; c'est mieux de savoir calculer la valeur minimale de t, mais ce n'est pas indispensable pour la suite. On peut remarquer aussi que la fonction φ est surjective.

    Note : ces calculs ne demandent pas de connaissance mathématique exceptionnelle ! Commencer par regarder les premières valeurs de φ n'est pas indispensable, mais c'est une bonne idée, bien meilleure en tout cas qu'une liste de formules ou d'affirmations vagues et souvent fausses.

  3. (2 points) La question précédente montre qu'on a toujours φ ( b + b2 ) = b. Une réponse simple à la question posée est donc :

    f (n) = g (n) + g (n)2

    Il y a une infinité d'autres réponses, de la forme g (n) + t2 , dès que t est supérieur à g (n) / 2. En utilisant seulement la surjectivité de φ on peut aussi choisir :

    f (n) = min { x | φ (x) = g (n) }

    Note : certains étudiants ont énuméré l'ensemble φ-1 ( B ) = { x | φ ( x ) ∈ B }, ce qui est possible, à condition de ne pas parler de la fonction inverse de φ (qui n'existe manifestement pas, voir question précédente). Cette interprétation n'est pas dans l'esprit de l'énoncé, qui spécifie construire un ensemble A, et précise qu'il y a beaucoup de réponses possibles ; elle ne permet pas de résoudre la question 6.

  4. (3 points) Exercice classique vu en TD : comme f est croissante, dès que f (n) dépasse x on sait que x n'appartient pas à E = Val ( f ). D'où la procédure qui calcule la fonction caractéristique de E :

    int fc (int x) {
      for (int n = 0; f(n) < x; n++);
      return f(n) == x;
    }
    

    qu'on peut écrire aussi :

    int fc (int x) {
      for (int n = 0; ; n++) {
        if ( f(n) == x) return 1;
        if ( f(n) > x) return 0;
      }
    }
    

    Cette procédure termine toujours, car f est strictement croissante.

  5. (2 points) Le premier exemple d'ensemble récursivement énumérable et indécidable est celui des procédures (sans argument) qui terminent ; ensuite on peut donner des variantes :

    { ( p, x ) | p (x) termine }
    { p | ∃ x : p (x) termine }

    On peut citer aussi l'ensemble des propriétés démontrables en arithmétique (théorème de Gödel). Mais les exemples tirés du théorème de Rice (procédures qui calculent l'identité, procédures qui calculent une fonction totale, etc.) sont souvent faux : ce sont bien des ensembles indécidables, mais ils ne sont pas récursivement énumérables. Ce n'est pas un résultat évident à démontrer, mais on voit mal comment énumérer les procédures qui possèdent telle ou telle propriété pour tout argument x.

    Note : dire que le problème de l'arrêt est indécidable est correct ; mais dire que le problème de l'arrêt n'est pas récursivement énumérable est absurde, strictement parlant : on peut énumérer un ensemble, pas un problème !

  6. (3 points) Il faut utiliser les questions 2, 3 et 4, c'est-à-dire construire A comme à la question 3, en se débrouillant pour que la fonction f qui énumère A soit croissante (ainsi A sera décidable). Notons :

    b0 = g (0) , b1 = g (1) , … , bn = g (n) , …

    les élements de B. On commence par choisir le premier élément de A :

    a0 = f (0) tel que φ ( a0 ) = b0

    Ensuite on choisit a1 = f (1) supérieur à a0 : c'est possible car d'après la question 2 n'importe quel

    a1 = b1 + t12

    vérifie φ ( a1 ) = b1 dès que t1 est suffisamment grand. Et ainsi de suite :

    an = f (n) = bn + tn2

    tn est suffisamment grand pour qu'on ait à la fois φ ( an ) = bn et f (n - 1) < f (n).

Exercice 2

Voir l'énoncé ci-dessus.

  1. (5 points) On suppose que l'état initial est numéroté 0, et que la tête de lecture est positionnée en début de RAM (cellule d'adresse 0). Le principe du programme est d'itérer le traitement suivant : décrémenter l'adresse, et déplacer d'une unité vers la droite une marque dans la RAM. Lorsque l'adresse devient nulle, la cellule marquée est celle dont il faut copier la valeur dans le registre.

    La réponse ci-dessous est complète, et peut être testée sur un simulateur de machine de Turing, mais dans les conditions de l'examen des "etc." peuvent remplacer des traitements similaires (par exemple les états 112 à 115 sont similaires à l'état 111). De même, la présentation des règles peut différer de celle ci-dessous, pourvu qu'elle soit claire.

    Dans ce corrigé, les cinq composants de chaque règle sont codés comme suit :

    Beaucoup d'étudiants ont pensé que la RAM ne contient que des 0 et des 1 ; ils ont utilisé les symboles supplémentaires a, b, c pour marquer la position atteinte dans la RAM, et pour mémoriser le symbole à transférer dans le registre (en se demandant à quoi pouvait bien servir le symbole c…) ; cette interprétation est contraire à la lettre de l'énoncé, mais ne change pas l'esprit de l'exercice, et a l'avantage de raccourcir le programme : elle a donc été considérée comme correcte.

    // Marquer la position dans la RAM
    
    0 a 10 A G
    0 b 10 B G
    0 c 10 C G
    0 0 10 D G
    0 1 10 E G
    0 . 99 . =  // erreur d'adresse
    
    // Retourner en fin d'adresse
    
    10 # 11 # G
    10 - 10 - G
    11 # 20 # G
    11 - 11 - G
    
    // Décrémenter l'adresse
    
    20 0 20 1 G
    20 1 30 0 D
    20 . 100 . D  // adresse nulle
    
    // Aller en début de RAM
    
    30 # 31 # D
    30 - 30 - D
    31 # 40 # D
    31 - 31 - D
    
    // Déplacer la marque dans la RAM
    
    40 A 0 a D
    40 B 0 b D
    40 C 0 c D
    40 D 0 0 D
    40 E 0 1 D
    
    40 - 40 - D
    
    // Itération terminée : atteindre
    // et mémoriser le symbole marqué 
    
    100 # 101 # D
    100 - 100 - D
    101 # 110 # D
    101 - 101 - D
    
    110 A 111 a G
    110 B 112 b G
    110 C 113 c G
    110 D 114 0 G
    110 E 115 1 G
    
    110 - 110 - D
    
    // Ecrire dans le registre
    
    111 # 121 # G
    111 - 111 - G
    121 - 200 a =  // succès
    
    112 # 122 # G
    112 - 112 - G
    122 - 200 b =  // succès
    
    113 # 123 # G
    113 - 113 - G
    123 - 200 c =  // succès
    
    114 # 124 # G
    114 - 114 - G
    124 - 200 0 =  // succès
    
    115 # 125 # G
    115 - 115 - G
    125 - 200 1 =  // succès
    

    Variante équivalente : au lieu de marquer par une majuscule seulement la position courante dans la RAM, on peut marquer toutes les positions jusqu'à la position courante, et effacer toutes les marques (en rétablissant les symboles d'origine) en fin de programme.

  2. (2 points) Le principe est le même, jusqu'à ce que l'adresse devienne nulle (état 100) ; il faut alors lire et mémoriser le registre, puis le copier dans la RAM à l'emplacement marqué (par une majuscule). Voici les nouvelles règles pour les états de numéro supérieur à 100 :

    // Aller en début de registre
    
    100 # 110 # D
    100 - 100 - D
    
    // Lire et mémoriser le symbole
    
    110 a 111 - D
    110 b 112 - D
    110 c 113 - D
    110 d 114 - D
    110 e 115 - D
    
    // Aller en début de RAM
    
    111 # 121 # G
    111 - 111 - D
    112 # 122 # G
    112 - 112 - D
    113 # 123 # G
    113 - 113 - D
    114 # 124 # G
    114 - 114 - D
    115 # 124 # G
    115 - 114 - D
    
    // Atteindre la cellule marquée
    // et copier le registre
    
    121 A 200 a =
    121 B 200 a =
    121 C 200 a =
    121 D 200 a =
    121 E 200 a =
    121 - 121 - D
    
    122 A 200 b =
    122 B 200 b =
    122 C 200 b =
    122 D 200 b =
    122 E 200 b =
    122 - 122 - D
    
    123 A 200 c =
    123 B 200 c =
    123 C 200 c =
    123 D 200 c =
    123 E 200 c =
    123 - 123 - D
    
    124 A 200 0 =
    124 B 200 0 =
    124 C 200 0 =
    124 D 200 0 =
    124 E 200 0 =
    124 - 124 - D
    
    125 A 200 1 =
    125 B 200 1 =
    125 C 200 1 =
    125 D 200 1 =
    125 E 200 1 =
    125 - 125 - D
    

    Bien entendu, inutile sur la copie de traiter en détail les cinq cas similaires, mais il doit être clair que le symbole écrit dépend de l'état — qui dépend lui-même du symbole lu dans le registre — et non du symbole marqué (par une majuscule).

    Note : on peut se passer des états intermédiaires 111 à 115 si l'on suppose le registre de taille 1.

  3. (3 points) Dans l'état 110, il faut à nouveau déplacer la marque (majuscule) ; on remplit le registre avec une boucle : écrire dans le registre, déplacer la marque, écrire dans le registre, et ainsi de suite jusqu'à atteindre la fin du registre (caractère '#'). Dans les conditions de l'examen, aucun étudiant n'a eu le temps de donner les détails, mais les voici (on suppose le registre blanc, sinon ajouter des instructions en début de programme pour le nettoyer) :

    // Atteindre, mémoriser et déplacer
    // le symbole marqué
    
    110 A 109 A D
    110 B 109 B D
    110 C 109 C D
    110 D 109 D D
    110 E 109 E D
    110 - 110 - D
    
    109 a 109 A G
    109 b 109 B G
    109 c 109 C G
    109 0 109 D G
    109 1 109 E G
    109 .  99 . =  // erreur adresse
    
    109 A 111 a G
    109 B 112 b G
    109 C 113 c G
    109 D 114 0 G
    109 E 115 1 G 
    
    // Ecrire dans le registre
    
    111 # 121 # G
    111 - 111 - G
    121 . 121 . G
    121 - 131 - D
    131 - 140 a D
    
    112 # 122 # G
    112 - 112 - G
    122 . 122 . G
    122 - 132 - D
    132 - 140 b D
    
    113 # 123 # G
    113 - 113 - G
    123 . 123 . G
    123 - 133 - D
    133 - 140 c D
    
    114 # 124 # G
    114 - 114 - G
    124 . 124 . G
    124 - 134 - D
    134 - 140 0 D
    
    115 # 125 # G
    115 - 115 - G
    125 . 125 . G
    125 - 135 - D
    135 - 140 1 D
    
    140 # 150 # D  // fin écriture
    140 . 141 . D
    141 . 141 . D
    141 # 110 # D
    
    // rétablir la cellule marquée
    
    150 A 200 a G
    150 B 200 b G
    150 C 200 c G
    150 D 200 0 G
    150 E 200 1 G
    150 - 150 - D
    

Exercice 3

Voir l'énoncé ci-dessus.

(3 points) En utilisant iszero la traduction en λ-calcul est directe :

match = λ n t f . iszero n t ( f ( pred n ) )

Attention aux parenthèses ! On a bien :

match 0 T Fiszero 0 T ( F ( pred 0 ) ) → true T ( F ( pred 0 ) ) → T
match 1 T Fiszero 1 T ( F ( pred 1 ) ) → false T ( F 0 ) → F 0
match 2 T Fiszero 2 T ( F ( pred 2 ) ) → false T ( F 1 ) → F 1 , etc.

Note : cette partie de l'exercice est facile, et pour obtenir les trois points il ne suffit pas de donner la valeur de match, il faut aussi écrire quelques réductions comme ci-dessus.

(2 points) En utilisant la définition d'un entier de Church on peut écrire directement :

match = λ n t f . n ( λ x . f ( pred n ) ) t

On a :

match 0 T F0 M TT

avec M = λ x . F ( pred 0 ) ; ensuite :

match 1 T F1 M TM T → ( λ x . F 0 ) TF 0

avec M = λ x . F ( pred 1 ) → λ x . F 0 ; le terme M représente une fonction constante, qui ignore son argument. De même :

match 2 T F2 M TM ( M T ) → ( λ x . F 1 ) ( M T ) → F 1

avec M = λ x . F ( pred 2 ) → λ x . F 1 (fonction constante, qui ignore son argument).

Note : le terme λ x . f ( pred n ) peut se noter aussi true ( f ( pred n ) ). Plus précisément, pour tout terme G on a :

true G = ( λ x y . x ) G → λ y . G

et ce dernier terme représente la fonction constante égale à G.

Exercice 4

Voir l'énoncé ci-dessus.

  1. (1 point) L'ensemble formé de tous les sommets de G constitue toujours une couverture (de taille n).
  2. (1 point) Affirmation fausse, sinon tout graphe possèderait une couverture de taille 1, ce qui manifestement n'est pas vrai. C'est le contraire qui est vrai : on peut toujours ajouter des sommets à une couverture. Le problème VERTEX-COVER peut être formulé indifféremment comme ici — existe-t-il une couverture de taille k ? ou sous la forme : existe-t-il une couverture de taille au plus k ?
  3. (2 points) Affirmation exacte. Soit Δ l'ensemble complémentaire de Γ ; dire que Δ est formé de sommets indépendants signifie qu'une arête ne relie jamais deux sommets de Δ, autrement dit toute arête possède au moins une extrémité dans Γ. Le problème VERTEX-COVER est donc équivalent au problème suivant (en posant l = n - k ) : existe-t-il un ensemble de sommets indépendants de taille ( au moins ) l ?
  4. (2 points) Un certificat est une couverture Γ. Pour vérifier ce certificat, il faut commencer par compter les éléments de Γ, et vérifier que ce nombre est bien égal à k ; compter les éléments de Γ demande au plus n opérations élémentaires. Ensuite, pour chaque arête de G, il faut vérifier que cette arête a une extrémité dans Γ ; la complexité de cette vérification est proportionnelle au nombre d'arêtes. L'algorithme de vérification du certificat est donc de complexité linéaire.
  5. (2 points) Le théorème de COOK affirme que tout problème de la classe NP peut être réduit en temps polynomial à SAT ; il existe donc une réduction polynomiale VERTEX-COVERSAT.
  6. On représente un ensemble Γ de sommets par n variables booléennes x1xn ,xi vaut 1 si le sommet numéro i appartient à Γ, 0 sinon. On construit alors une formule Φ qui exprime que Γ est une couverture de la façon suivante :

    1. (2 points) Pour chaque arête (i, j), Φ comporte la clause xixj .
    2. (2 points) Il faut aussi exprimer que la taille de Γ est correcte, autrement dit :

      Σ xi = k

      Il faut donc représenter le résultat de n - 1 additions par un ensemble de clauses ; c'est possible en représentant chaque nombre sur m bits, où m est le logarithme binaire de n (arrondi par excès), et en représentant chaque addition par une cascade d'additionneurs élémentaires (comme les électroniciens le font), qui admettent chacun en entrée trois bits (deux plus la retenue) et en sortie deux bits.

  7. (1 point) Voici comment on peut coder les deux clauses :

    ( x1 ∨ ¬ x3x4 ) , ( ¬ x1x2x4 )

    Codage de deux clauses, cliquer pour agrandir

    Note : l'ordre des composantes d'une clause est sans importance (la disjonction est commutative), donc il en est de même pour l'ordre des sommets dans un triangle.

  8. (2 points) Soit Γ une couverture de G ; chaque triangle associé à une clause possède au moins deux sommets dans Γ — pour que chacune des trois arêtes ait au moins une extrémité dans Γ — et chaque segment associé à une variable booléenne possède au moins un sommet dans Γ. Il y a m clauses et n variables booléennes, donc la taille minimale de Γ vaut 2 m + n.
  9. (3 points) Choisissons par exemple x1 = 1, x2 = 0, x3 = 1, x4 = 1 ; la clause :

    x1 ∨ ¬ x3x4

    est satisfaite car x1 = x4 = 1, et la clause :

    ¬ x1x2x4

    est satisfaite car x4 = 1. La couverture correspondante Γ inclut l'ensemble S des sommets U1 , V2 , U3 , U4 : pour chaque variable booléenne xi on choisit Ui si xi = 1, sinon on choisit Vi . Chaque clause est satisfaite, donc chaque triangle possède au moins un sommet relié à un sommet de S, et on place les deux autres sommets dans Γ : sur la figure de la question 7, A1 est relié à S, donc on place les sommets B1 et C1 dans Γ (on aurait pu choisir A1 et B1 , car C1 est lui aussi relié à S ), ainsi que les sommets A2 et C2 (car B2 est relié à S ). Par construction, l'ensemble :

    Γ = { U1 , V2 , U3 , U4 , B1 , C1 , A2 , C2 }

    constitue bien une couverture de G.

    Couverture 1, cliquer pour agrandir

    Inversement, partons par exemple de la couverture :

    Γ = { V1 , U2 , V3 , V4 , A1 , C1 , A2 , B2 }

    Couverture 2, cliquer pour agrandir

    Les valeurs des variables booléennes associées à cette couverture sont : x1 = 0, x2 = 1, x3 = 0, x4 = 0. Comme Γ comporte exactement 2 m + n = 8 sommets, on en déduit que chaque triangle possède un sommet qui n'est pas dans Γ : ici il s'agit respectivement de B1 et C2. Le sommet B1 est relié à V3 ∈ Γ (sinon Γ ne serait pas une couverture) : ceci entraîne que le choix x3 = 0 satisfait la première clause. Le sommet C2 est relié à U2 ∈ Γ : ceci entraîne que le choix x2 = 1 satisfait la seconde clause.

  10. (2 points)

    Il suffit de prendre un graphe constitué d'un seul segment U V et de deux triangles ; les sommets du premier triangle sont tous reliés à U, et ceux du second triangle à V. On vérifie facilement qu'il n'existe pas de couverture de taille 5.

    Ce graphe correspond aux deux clauses (xxx) et x∨¬x∨¬x), qui ne sont pas satisfiables simultanément.

    Graphe sans couverture de taille 5, cliquer pour agrandir
  11. (2 points) Le graphe G construit à partir de la formule Φ comporte 3 m + 2 n sommets, et 6 m + n arêtes : sa taille est donc proportionnelle à la taille de Φ, et la complexité de la construction de G est linéaire. Nous avons donc construit une réduction polynomiale SATVERTEX-COVER, d'où l'on déduit que VERTEX-COVER est NP-complet.