Université BORDEAUX 1 | U.F.R. Mathématiques et Informatique |
Epreuve de J.Bétréma | 23 janvier 2004 |
Durée: 3 heures
Tous documents interdits.
Un corrigé est disponible ci-dessous.
Dans la suite de l'exercice, on suppose que E est un ensemble d'entiers naturels infini, et on définit la fonction f de la façon suivante :
Questions :
Un corrigé est disponible ci-dessous.
A et B désignent deux ensembles infinis d'entiers, auxquels on associe l'ensemble C défini par :
C = { 2n | n ∈ A } ∪ { 2n + 1 | n ∈ B }
On appelle φ la fonction de numérotation de la question précédente, et on considère l'ensemble E défini par :
E = { 2 φ ( p, x ) | ( p, x ) ∈ H } ∪ { 2 φ ( p, x ) + 1 | ( p, x ) ∈ H' }
(rappel : H' désigne le complémentaire de H ). E est-il récursivement énumérable ? Son complémentaire E' est-il récursivement énumérable ? Note : justifier soigneusement les réponses.
Un corrigé est disponible ci-dessous.
On code un couple par le terme
C = λ x y f . f x y
Un corrigé est disponible ci-dessous.
On suppose donné un algorithme A résolvant le problème de décision SAT. Soit F une formule logique, dont les variables booléennes sont x1…xn ; on suppose que F est satisfiable. Ecrire un algorithme efficace B, qui utilise A pour calculer une suite de n valeurs booléennes b1…bn qui satisfont F ; dans cet exercice, on ne se préoccupe pas de la complexité de A pour évaluer la complexité de B (on considère A comme un oracle, dont l'exécution a un coût constant, indépendant de la taille de son argument) — autrement dit le but de l'exercice est de montrer que trouver une suite de valeurs qui satisfont F, n'est pas plus difficile que de résoudre le problème de décision SAT.
Corrigé.
Note sur le barème : les copies ont été notées sur 30 (8 points pour l'exercice 1, 10 points pour l'exercice 2, 7 points pour l'exercice 3, et 5 points pour l'exercice 4). La meilleure note a été 23, et les notes comprises entre 12 et 23 ont été ajustées pour obtenir des notes comprises entre 12 et 19.
Voir l'énoncé ci-dessus.
Barème : 4 points pour la série des trois premières questions.
Soit E = { a } ; la procédure qui calcule la fonction caractéristique de E s'écrit :
int p (int x) { return x == a; }
Note : il est étonnant, au niveau bac + 4, que la plupart des étudiants écrivent encore (même si ce n'est pas faux) :
int p (int x) { if (x == a) return 1; else return 0; }
Si p et q désignent des procédures qui calculent les fonctions caractéristiques de E et F, voici une procédure u qui décide si x appartient à l'union des deux ensembles :
int u (int x) { return p(x) || q(x); }
ou bien :
int u (int x) { if (p(x)) return 1; return q(x); }
Note : il y a beaucoup de façons de rédiger cette réponse, par exemple on peut écrire que si les prédicats x ∈ E et x ∈ F sont calculables, alors il en va de même pour :
x ∈ E ∪ F = (x ∈ E ) ∨ (x ∈ F ).
Démonstration par récurrence sur le cardinal n de l'ensemble :
Si n = 0, l'ensemble est vide, sa fonction caractéristique est :
int vide (int x) { return 0; }
Barème : 4 points pour la série des trois dernières questions.
Oui, f est totale, car E est infini. De même, pour tout élément x dans E, il existe un entier i tel que x = f ( i ) : i est le rang de x dans E, une fois celui-ci ordonné.
L'ensemble des couples ( p, x ) tels que le calcul p (x) ne termine pas, n'est pas récursivement énumérable. Via la numérotation des procédures et des couples, un tel ensemble peut être vu comme un ensemble d'entiers.
Note : c'est le seul exemple d'ensemble non récursivement énumérable vu en cours, et c'est l'exemple fondamental. Mais on peut en citer d'autres, par exemple l'ensemble des procédures qui calculent l'identité (ou n'importe quelle fonction calculable donnée) : voir le devoir 2003 ou le devoir 2004. On peut aussi donner un argument de dénombrement : les ensembles récursivement énumérables forment un ensemble dénombrable (comme les procédures qui les énumèrent), ce qui n'est pas le cas des ensembles infinis quelconques d'entiers.
La fonction min, qui fournit le plus petit élément d'un ensemble E, n'est en général pas calculable, et donc f non plus. D'ailleurs f énumère E en ordre croissant, et donc si f est calculable, E est décidable (voir la feuille d'exercices du chapitre 4). Inversement, si E est décidable, min et f sont calculables.
Voir l'énoncé ci-dessus.
(2 points). Dans la procédure suivante, else est optionnel, et n/2 désigne le quotient entier de n par 2 :
int h (int n) { if (n % 2 == 0) return 2 * f (n/2); else return 1 + 2 * g (n/2); }
(2 points). Oui, le plus simple est d'utiliser l'équivalence entre récursivement énumérable et semi-décidable :
int scA (int x) { return scC (2 * x); }
La procédure scA calcule la fonction semi-caractéristique de l'ensemble A, à partir d'une procédure similaire pour C. Le cas de B est symétrique.
On peut aussi écrire une procédure d'énumération des éléments de A, construite à partir d'une procédure h qui énumère les éléments de C :
int f (int n) { int x = h (n); if (x % 2 == 0) return x / 2; }
Cette procédure calcule une fonction partielle, mais ce n'est pas gênant pour conclure que A est récursivement énumérable (voir la feuille d'exercices du chapitre 4). Cependant, les règles du langage C entraînent que f ( n ) n'est pas indéfini, mais aléatoire, lorsque h ( n ) est impair ; on peut y remédier en ajoutant une boucle infinie while (1) en fin de procédure. Une solution moins artificielle est de transformer f en une procédure totale, par exemple :
int f (int n) { int x, c = -1; for (i == 0; c < n; i++) { x = h (i); if (x % 2 == 0) c++; } return x / 2; }
(2 points). Non, E n'est pas récursivement énumérable, sinon, d'après la question 2, H' serait récursivement énumérable, ce qui est faux (question 3). Le complémentaire E' de E est obtenu en échangeant les rôles de H et H', donc il n'est pas non plus récursivement énumérable.
Cet exercice montre donc comment fabriquer simplement un ensemble E tel que ni lui ni son complémentaire ne soient récursivement énumérables, à partir d'un ensemble (ici H', mais tout autre exemple conviendrait) dont on sait seulement qu'il n'est pas récursivement énumérable.
Note : beaucoup d'étudiants se sont trompés en calculant E'. Le complémentaire de l'union de deux ensembles est bien l'intersection des complémentaires, mais le complémentaire de :
F = { 2n | n ∈ A }
n'est pas G = { 2n | n ∈ A' }, car les entiers impairs ne sont ni dans F ni dans G ! Le complémentaire F' est constitué de l'union de G et de tous les entiers impairs ; l'oubli est pourtant facile à déceler, car il entraîne qu'on trouve E' … vide, ce qui est curieux (mais ne semble pas déconcerter certains étudiants).
Voir l'énoncé ci-dessus.
(3 points). Cette question fait partie de la feuille d'exercices du chapitre 6 : C est le terme pair, P le terme first, et λ x y . x est le terme true. Revoici une réduction :
P ( C M N ) → ( C M N ) ( λ x y . x ) = C M N ( λ x y . x )
Les parenthèses à gauche sont en effet inutiles, et comme C est une fonction de trois variables, on obtient :
C M N ( λ x y . x ) → ( λ x y . x ) M N → M
(2 points). Il faut considérer un triplet comme un couple, dont le premier élément est lui-même un couple :
T = λ x y z . C ( C x y ) z
(2 points). Pour obtenir le second élément d'un triplet défini comme ci-dessus, il faut sélectionner le premier élément du triplet, qui est lui-même un couple, dont on sélectionne alors le second élément, soit :
second = λ t . S ( P t )
en notant S le jumeau de P, soit S = λ c . c ( λ x y . y ) ; vérifions :
second ( T M1 M2
M3 )
→
S ( P (
T M1 M2
M3 ) )
→
→
S ( P ( C (
C M1 M2 )
M3 ) )
→
S (
C M1 M2 )
→
M2
car, par symétrie avec P (voir première question), S ( C M N ) → N.
(5 points). Voir l'énoncé ci-dessus. Voici l'algorithme B :