Fiche de questions et exercices

Calculabilité et Complexité

1. Quand est-ce qu'un problème est dit de décision?

Définition : Un problème est une relation binaire sur un ensemble d'instances et
un ensemble de solutions.

Un problème est dit de décision si la réponse aux instances du problème est soit
oui soit non.

2. Quand est-ce qu'une procédure est considérée comme effective pour

résoudre un problème?
Pour qu‟une procédure soit considérée comme effective pour résoudre un
problème, il faut
que celle-ci se termine sur toutes les instances du problème.
3. A quoi sert une fonction d'encodage?
On appellera fonction d‟encodage la fonction qui transforme une instance
particulière d‟un
problème en son codage en termes de mot.

4. Définir “Ensemble dénombrables”

Un ensemble est dénombrable (énumérable) s‟il existe une bijection entre cet en
semble et
l‟ensemble des nombres naturels.

5. Démontrer que l'ensemble des nombres pairs est dénombrable

L‟ensemble des nombres pairs est dénombrable.
Voici une bijection qui établit cette propriété: {(0, 0), (2, 1), (4, 2), (6, 3), . . .}

6. Démontrer que l’ensemble des nombres rationnels est dénombrable

L‟ensemble des nombres rationnels est dénombrable. En effet, un nombre
rationnel est caractérise par
une paire de nombres entiers a/b (et les paires de nombres entiers sont
dénombrables). Voici une façon
d‟énumérer les nombres rationnels : {(0 /1, 0), (0/2, 1), (1/1, 2), (0/3, 3), (1/2, 4),
. . .}
7. Quelle différence faites-vous entre dénombrables et comptable
Se dit d‟un ensemble infini qui peut être mis en relation bijective avec
l‟ensemble des nombres
entiers naturels. Se dit parfois de ensemble fini
Et comptable c'est ce qui peut être calculer ou compter

8. Quelle différence faites-vous entre un langage décidé et un langage

accepté
Un langage L est décidé par une machine de Turing M si :
• M accepte L,
• M n‟a pas d‟exécution infinie.
Le langage L(M) accepté par une machine de Turing est l‟ensemble des mots w
tels que
(s, ᵋ,w) ⊢∗ M (q, α1, α2) avec q ∈ F.

9. Quelle différence faites-vous entre un langage récursif et récursivement

énumérable?
Un langage est récursif s‟il est décidé par une machine de Turing.
Un langage est récursivement énumérable s‟il est accepté par une machine de
Turing.

10. Montrer que les fonctions suivantes sont récursives primitives :

1. Addition
La fonction d‟addition plus(n1, n2) peut être définie par recursion primitive :
plus(n1, 0) = π1/1(n1)
plus(n1, n2 +1) = σ(π3/3(n1, n2, plus(n1, n2)))
Ou encore
plus(n1, 0) = n1
plus(n1, n2 +1) = σ(plus(n1, n2))
2. Multiplication
La fonction “produit de deux naturels” est primitive recursive :
prod(n1, 0) = 0
prod(n1, n2 +1) = plus(n1, prod(n1, n2))
3. Puissance
4. Factorielle
5. Signe
11. Quand est-ce qu’un prédicat est primitif récursif ?
Un prédicat est primitif récursif si et seulement si sa fonction caractéristique est
primitive récursive.
12. Montrer que les prédicats suivants sont primitifs récursifs :
1. plus petit que (n < m)
On définit le prédicat plus petit que (n < m) de la façon suivante :
petit(n, m) = sg(m-˙ n)
2. Égal (n=m)
Le prédicat ´égalité est ´également primitif récursif. En effet, m = n ´équivaut `a
¬(m.< n ∨ m >n), ce qui s‟écrit au niveau des fonctions caractéristiques :
egal(n, m) = 1-˙ (sg(m-˙ n) + sg(n-˙ m))
3. différent
13. Montrer que les prédicats obtenus par combinaisons booléennes à partir
de prédicats primitifs
récursifs (g1, g2) sont également primitifs récursifs
Les prédicats obtenus par combinaisons booléennes à partir de prédicats
primitifs récursifs (g1, g2) sont également primitifs récursifs. En effet :
et(g1(ˉn), g2(ˉn)) = g1(ˉn) × g2(ˉn)
ou(g1(ˉn), g2(ˉn)) = sg(g1(ˉn) + g2(ˉn))
non(g1(ˉn)) = 1-˙ g1(ˉn)

14. Enoncer et justifier la thèse de Church au sujet des machines de Turing

La thèse de Church au sujet des machines de Turing est la suivante : Les
langages reconnus
par une procédure effective sont ceux décidés par une machine de Turing.

15. Montrer qu'une machine de Turing peut simuler une machine RAM
La machine de Turing simule alors la machine à mémoire RAM de la façon
suivante :
 Parcourir le ruban représentant la mémoire jusqu‟à trouver l‟adresse
correspondant au
contenu du compteur de programme (PC);
 Lire et décoder l‟instruction se trouvant à cette adresse;
 Le cas échéant trouver les opérandes de cette instruction;
 Exécuter l‟instruction, ce qui implique éventuellement la modification de la
mémoire et/ou des registres;
 Incrémenter le compte de programme (sauf si l‟instruction est une instruction
de
branchement) et passer au cycle suivant.
16. Enoncer la thèse de Turing-Church
≪ Tout traitement réalisable mécaniquement pour etre accompli par une
machine de Turing ≫
17. Une variété d’extensions peuvent être apporter aux machines de Turing
sans changer la classe
des langages qu’elles décident. Citer 3 extensions

-Ruban doublement infini

-Machine à ruban multiples

-Machines à accès direct

18. Montrer qu’une machine déterministe peut simuler toutes les exécutions
d’une machine non déterministe.
La solution est de considérer toutes les exécutions en parallèle mais en
considérant des préfixes
de longueur croissante. D‟abord, tous les préfixes de longueur 1, puis 2, puis 3,
...

19. Expliquez comment on peut faire calculer une fonction de N dans N par
une machine de
Turing

20. Prouvez qu’il existe des fonctions de N dans N qui ne sont pas
calculables par une machine de Turing.

21. Démontrer que le problème de l'arrêt est indécidable

Démonstration par l'absurde :
 Supposons qu'un algorithme H(A,i) existe pour décider le problème de l'arrêt.
 Par définition, H(A,i) est un algorithme prend en entrée un algorithme A et une
instance i
et retourne en un nombre fini d'étapes :
 ≪ oui ≫ si l'algorithme A s'arrête lorsqu'on l‟exécute sur l'instanceI.
 ≪ non ≫ si l'algorithme A ne s'arrête pas.

22. Quand est-ce qu'un problème de décision appartient à la classe NP?

Un problème de décision appartient à NP si

● il existe un algorithme vérifieur (déterministe) A;
● s'il existe, pour chaque instance I dont la réponse
est « oui », un certificat C(I) de taille polynomiale;
● l'algorithme A permet de vérifier que le certificat est
valide ou non en un temps polynomial en la taille de I.

Ou encore

Un problème de décision appartient à NP s'il existe

une machine de Turing non-déterministe
polynomiale qui le résout.

23. Quand est-ce qu'un problème de décision A se réduit en temps

polynomial à un problème de décision B?

Un problème de décision A se réduit en temps

polynomial à un problème de décision B si :
● Il existe une machine de Turing déterministe M qui
transforme en temps polynomial toute instance I
de A en une instance M(I) de B;
● Pour tout I, la solution de I pour A est identique à la
solution de M(I) pour B.

24. Quand est-ce qu'un problème est NP-complet?

Un problème A est NP-complet si :

● A appartient à la classe NP;
● A est NP-difficile
„‟Un problème A est NP-difficile si tous les
problèmes de la classe NP se réduisent
polynomialement à A’’

Exercice 1
Concevoir une machine de Turing qui accepte le langage {anbn | n ≥ 0}
Une machine M qui accepte le langage X est la suivante :
 L‟ensemble des états Q = {0, 1, 2, 3, 4}
 L‟alphabet d‟entrée est £= {a, b}
 L‟alphabet de bande est T= {a,b,A,B,#}
 L‟état initial est q0=0
 Le seul état final est l‟état 4
 L‟ensemble des transitions est décrit par la figure ou le tableau

Déduire une machine de Turing qui accepte le langage {anbn+2 | n ≥ 0}

Exercice 2
Concevoir une machine de Turing qui accepte le langage {anbncn| n ≥ 0}

Exercice 3
Concevoir une machine de Turing qui calcule n-> 3n.
Déduire une machine de Turing qui calcule n-> 3n+3.

Exercice 4
Écrire une machine de Turing qui effectue le complément d'un nombre binaire.
Entrée : un nombre écrit en binaire (entouré de #). Exemple : #01101001#
Sortie : le complément binaire du nombre : Exemple : #10010110#
On supposera que le nombre contient au moins un digit. Au début, la tête de
lecture est positionnée sur
le premier # et doit se trouver, à la fin, sur le # qui précède le résultat.

Solution

Exercice 5
Écrire une machine de Turing qui ajoute 1 à un nombre binaire écrit avec les bits
de poids faibles à
gauche.
Entrée : un nombre écrit en binaire. Exemple : #11101101# = 183
Sortie : le nombre plus 1. Exemple : #00011101# = 184
On supposera que le nombre contient au moins un digit. Au début, la tête de
lecture est positionnée sur
le premier # et doit se trouver, à la fin, sur le # qui précède le résultat.

Solution
Exercice 6
Écrire une machine de Turing qui compte le nombre de 1 dans un chiffre
binaire:
Entrée : un nombre écrit en binaire. Exemple : #11101101#.
Sortie : le nombre de 1. Exemple : #110#
Mêmes consignes que dans les exercices précédents. On supposera que la partie
non visible du ruban est
initialisée avec des #.

Solution

Exercice 7
Comment montrer qu'un problème appartient à la classe P?

Pour montrer qu'un problème appartient à P :

● Proposer un algorithme polynomial;
● Montrer que l'algorithme est correct, c'est-à-dire,
montrer qu'il retourne, pour toutes les instances du
problème, une solution admissible.
● Montrer que l'algorithme est polynomial.
Appliquer sur le problème du calcul du PGCD de deux nombres entiers.

Exercice 8
Expliquer le problème SAT.

● Le problème SAT est un problème de décision.

● Entrée :
– Un ensemble de variables booléennes x1, x2, x3, ... , xn.
– Un ensemble de clauses a1∨a2∨a3∨...∨ak où les ai sont des littéraux, c'est-à-
dire, ai = xj ou xj
● Sortie :
– « oui » s'il existe une affectation des variables booléennes qui satisfait toutes
les clauses;
– « non » sinon.
Montrer que le problème 2SAT est polynomial.
Astuce: le réduire à
un problème de recherche des composantes
fortement connexes d'un graphe.

Exercice 9
Le problème des tâches est formulé comme suit : “Etant donné un ensemble de
tâches, trouver un sous ensemble de tâches de cardinalité maximale qui ne
s'intersectent pas”.
Proposer un algorithme glouton pour la résolution de ce problème.

Algorithme glouton :
● Trier les tâches dans l'ordre croissant des dates de fin.
● Tant qu'il existe des tâches :
– Ajouter la tâches T qui a la plus petite date de fin.
– Supprimer les tâches qui intersectent T.

Exercice 10
On dispose de pièces en nombre illimité de
valeurs 10, 5, 2 et 1, et on souhaite rendre une somme S avec un nombre
minimum de pièces. Proposer un algorithme glouton pour la résolution de ce
problème de rendu de monnaie.

Algorithme :
● On trie les tas de pièces par ordre croissant de valeur.
● Pour chaque valeur (dans cette ordre), on prend le
nombre maximum de pièces possibles.

● Dans une solution optimale :

● On a au plus 1 pièce de 5;
● On a au plus 1 pièce de 1;
● On a au plus 2 pièces de 2;
● On a au plus 3 pièces qui ne sont pas des pièces
de 10 pour un total inférieur ou égal à 9 car
1 x 5 + 1 x 1 + 1 + 2 x 2 = 1 x 10
● Donc une solution optimale contient un nombre de
pièces de 10 maximum (= à l'algo. glouton).
● Il suffit de vérifier que l'algorithme glouton est
optimale lorsque S ≤ 9.
Cet algorithme est-il optimal si on a des
pièces de valeurs 6, 4 et 1 ?

● Non, pour S = 8 :
● L'algorithme glouton :
– 1 pièce de 6,
– 2 pièces de 2.
● La solution optimale :
– 2 pièces de 4.

Exercice 11
Pour l'un des problèmes suivants:
 Le définir
 Donner une idée de la preuve de sa NP-Complétude
 Donner une approche de résolution ou un algorithme
 Donner des applications
Knapsack problem; Art gallery problem; Vertex cover; Job shop scheduling;
Steiner tree problem; Set
packing problem; Exact cover problem; Max-cut problem; Travelling salesman.