X Informatique MP 2005

Thème de l'épreuve Circuits logiques : PLA et additionneurs
Principaux outils utilisés circuits logiques et additionneurs, forme normale disjonctive, programmation impérative

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2005/MP_INFO_X_1_2005.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE FILIÈRE MP
OPTION INFORMATIQUE

CONCOURS D'ADMISSION 2005

COMPOSITION D'INFORMATIQUE

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

***

Circuits PLA et additionneurs

On attache... une grande importance à la concision, à la clarté, et à la 
précision de la rédaction. Les
deaæ parties du problème sont quasi indépendantes.

I. Génération de circuits PLA

Dans ce problème, les booléens sont représentés par 0 pour la valeur faux, et 1 
pour la valeur vraie.
Soit B = {0,1} l'ensemble des booléens. Si a: est un booléen, on notera îv" = 1 
-- a: le complément de 56.
On écrira oe . y pour la conjonction (produit) de a: et y; a: + y pour la 
disjonction de $ et y en posant
0+0=0et0+1=1+0=1+1=1;etoe®ypourleou--exclusifldéfinipar0=0®0=l®1et
1 = 0 GB 1 = 1 619 0.

La représentation binaire (3307 5131, . . .æn_1) de l'entier a: sur n bits (0 S 
a: < 2") est définie par :

w = 50020 + {13121 + - - - + oen_12"_1

où oei est un booléen pour tout i (0 S i < n). Dans le problème, on ne 
considère que des représentations
binaires d'entiers oe vérifiant 56 < 230, et donc représentables comme de 
simples entiers positifs en Pascal
ou Caml. On écrira aussi Æ pour la représentation binaire de a; quand n est 
clair dans le contexte. Les bits
de a: sont les booléens 5120, 501, . . .:13n_1 ; 580 est le bit le moins 
significatif ; æn_1 est le bit le plus significatif.

Enfin, on suppose que les deux langages Pascal et Caml possèdent les opérations 
logiques A, V, GB, "1
sur les entiers positifs définies par : ,

oe /\ y = (330 - y0)20 + (acl -y1)21 + - - - + (oe29 - y29)229 si p = æ020 + 
33121 + - - - + 3329229
33 V y : (OE0 + y0)20 + (OE1 + y1)21 + ' ' ' + (3329 + y29)229 y = 3/020 + y121 
+ ' ° ' + y29229
OE @ y = (5130 @ y0)20 + (961 @ y1)21 + ' ° ° + (3329 @ y29)229

ag: = î020 + îË121 + - - - + î29229

qui s'exécutent en temps constant O(1). Ainsi on autorise les expressions 
arithmétiques de Caml ou Pascal
a être de la forme e/\e', eVe', eEURBe' et +e.

Question 1 Montrer que, si 0 < a: < 230, alors :L' est de la forme m : 217 (p 2 
0) si et seulement si

oeA(æ--1)=O.

La distance de Hamming d(oe, y) entre deux entiers a; et y est le nombre de 
bits dont ils diffèrent dans
leur décomposition binaire :? et ÿ sur 30 bits.

OE1 330 g(£C0,ZIZ1) 5132 5131 330 h(OE0,OE1,OE2)
0 0 1 0 0 0 0
0 1 0 0 0 1 1
1 0 1 0 1 0 0
1 1 1 0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0

FIG. 1: Tables de vérlté de g et h.

Question 2 Écrire la fonction aDistUn qui prend comme argument deux entiers ac 
et y et retourne, en
temps constant, la valeur vrai si et seulement si la distance de Hamming entre 
a: et y vaut 1.

(* Caml *) {Pascal}

aDistUn : int -> int -> bool function aDistUn (m:integer, y:integer) : boolean;

Soit f une fonction booléenne de n arguments booléens; donc f est une fonction 
de B" dans B
(n > 0). Deux exemples de fonctions booléennes sont g et h définies par : 
g(OE0,SI31) = Î0 + æg -a:1, et
h(OE0,SL'1,.ÈB2) = 5130 {B 332. Une fonction booléenne peut être définie par sa 
table de vérité, comme sur la
figure 1. Dans le problème, nous représenterons toute fonction booléenne f par 
l'ensemble des entiers dont
la représentation binaire sur 71. bits est dans f _1( 1), image inverse de 1. 
Ainsi g est définie par l'ensemble
{0,2,3} et h par {1,3,4, 6}.

Un llttéral est une variable a: ou son complément î; on dira que a: est un 
littéral positif et î est un
littéral négatif. Toute fonction booléenne f (330, m, . . . :13n_1) peut être 
mise en forme normale dlsjonctlve
(f.n.d.) en l'exprimant comme une somme de produits de littéraux formés à 
partir de æg, a:1, ...æn_1.
Ainsi g(æ, y) = î - ?} + "51? - y + a: - y = î + a: - y = Îz:' + y s'écrit sous 
trois f.n.d. distinctes.

Question 3 Exprimer h avec une f.n.d. sous forme de la somme de 4 produits.

Pour réduire le nombre de produits dans la f.n.d. de f, on utilisera 
principalement l'identité

æ-p+Ë-p=(ælî)°P=l'P=P
Ainsi g(a:, y) = 573 - ÿ + î - y + a: - y = î- (ÿ + y) + a: - y = "a? + a: - y. 
Remarquons qu'on peut aussi utiliser
l'identité p + p = p et obtenir g(a:, y) = î- ('ÿ + y) + (î + oe) -- y = Î + y. 
Dans cet exemple le nombre de
produits n'est pas plus faible, mais en général cette identité supplémentaire 
permet de le faire baisser. Le

but de cette partie est de trouver efficacement parmi toutes les réécritures de 
la f.n.d. l'une de celles ayant
un nombre de produits minimal, ou presque. On appellera f.n.d. rédulte le 
résultat de notre algorithme.

Question 4 Réduire le nombre de produits dans la f.n.d. de h.

Un ensemble {lg, l1, . . . 'lg._1} d'indices compris entre 0 et 29 (0 5 l;,, < 
30, 0 5 k < EUR) est représentable
par l'entier dont la représentation binaire a des bits à 1 aux seules positions 
lg, l1, . . .ig-1. Un produit de
littéraux mio-33,1 - - -- a:,,_, (0 £ lg < l1 . . . < lg_1 < 30) est représenté 
par un enregistrement contenant deux
entiers : une valeur ?) et un masque m. Le masque m est l'entier désignant 
l'ensemble E = {lg, l1, . . . lg_1} ;
la valeur 1) correspond au sous--ensemble de E où as,-k est un littéral 
positif. Ainsi le produit æg -a:2 -îg - IE4
est représenté par les deux entiers @ = 21 et m = 29 dont les représentations 
binaires respectives (sur 30
bits) sont (1,0,1,0,1,0,. .. 0) et (1,0, 1, 1, 1,0, . . . 0). En abrégé, le 
produit s'écrira 101--1----- - --- ou plus
simplement 101--1.

(* Caml *) {Pascal}

type produit = {V: int; m: int};; type produit = record v, m:integer; end;

Question 5 Écrire les fonctions varEliminable et unifier qui prennent deux 
produits 19 et q en
arguments; et qui, la première, retourne la valeur vrai si p = p' - oe; - p" et 
q = p' - î; - p" ou 10 = p' - ZE; - p' '
et q = p' - a:; - p" ; et qui, la seconde, retourne le produit p' - p" dans le 
cas où la première fonction vaut
vrai.

(* Caml *) {Pascal}

varEliminable : produit --> produit function varEliminable (pzproduit, 
q:produit)
--> bool : boolean;

unifier: produit --> produit function unifier (pzproduit, q:produit)
-> produit : produit;

Quelle est la complexité en temps de ces deux fonctions ?

Une somme (disjoncti0n) de produits est représentée par une liste de produits :

(* Caml *) { Pascal }
type somme = "cellule;
type somme == produit list;; cellule = record contenuzproduit;

suivantzsomme; end;

En Pascal, la liste vide est nil et l'on pourra pour construire les listes 
utiliser la fonction suivante :

function cons(contenuzproduit; suivantzsomme) : somme;
var r:somme; ,
begin new(r); r".contenu := contenu; r".suivant := suivant; cons := r end;

Cette fonction est applicable pour construire les listes du type somme.

Question 6 Ecrire la fonction unique qui prend en argument une somme a; et qui 
retourne la même
somme où chacun des produits n'apparaît qu'une seule fois.

(* Caml *)

unique : somme -> somme

{ Pascal }

function unique (azsomme) : somme;

Quelle est la complexité en temps de cette fonction par rapport a la longueur 
EUR de la somme a ?

Question 7 Ecrire la fonction nouveauxProduits qui prend en argument une somme 
a; et qui retourne
la somme de tous les produits qu'il est possible d'obtenir en éliminant une 
variable inutile entre deux

produits de a.
(* Caml *)

nouveauxProduits : somme --> somme

{ Pascal }

function nouveauxProduits (azsomme) : somme;

Quelle est la complexité en temps de cette fonction par rapport a la longueur 
EUR de la somme a '?

Pour générer une f.n.d. réduite de la fonction booléenne f de n arguments, on 
commence par fabriquer
la somme ao de tous les produits de n variables correspondant a f _1(1), image 
inverse de 1 par f (par
exemple, 00, 01, 11 pour g). Puis on applique la fonction nouveauxProduits a 
ao, donnant la somme
a1. Et on recommence en rappelant cette fonction sur al, donnant une autre 
somme a2, etc. On s'arrête
quand on ne produit plus de nouveaux produits. Ainsi pour 9, on obtient O--, 
--1 pour al, et on s'arrête.

Question 8 Donner la suite des a; obtenus pour h.

Pour le moment, on garde tous les pr0duits. Il est donc plus simple de 
manipuler des listes de sommes
pour stocker (ak, . . . ,a2, a1, ao).

(* Caml *) {Pascal}
type fnd = "celluleS;
type fnd == somme list;; celluleS = record contenuzsomme;

suivantzfnd; end;

Pour construire ces listes, on utilisera la fonction conand analogue de la 
fonction cons.

ÎË--O<}--- 513 ZE()OE1 . . . £Un_1 5131 OE0 + 5171 + . . . OEn_1 æ1

FIG. 2: Trois portes logiques : (a) lnverscar(l entrée a:, 1 sortie Î) ; ( b ) 
porte--ET(n entrées, 1 sortie);
(c} porte-OU(n entrées, 1 sortie}.

Question 9 Ecrire la fonction developper qui prend en argument une somme a; et 
qui retourne la

liste (ak, . . . a2, a1, ao) des sommes obtenues en itérant la fonction 
nouveauxProduits à partir de (a).
(* Caml *) {Pascal}
developper : somme --> fnd function developper (azsomme) : fnd;
Quelle est la complexité de cette fonction par rapport aux longueurs fg, &, . . 
.Ék des listes ao, a1, . . . ak ?

Le résultat de la fonction developper est une liste de listes, ayant beaucoup 
plus de termes que la
somme de départ, et dont on va extraire les produits formant la f.n.d. réduite. 
Cela se fait en éliminant
tous les produits couverts par un autre produit. Ainsi le produit --0 couvre 
les produits 00 et 10; de
même 1-- couvre 10 et 11. Formellement, le produit p' 'p" couvre les produits 
p' - a:.-- -p" et p' - Îz' --p" . En
outre, p couvre p" si 17 couvre p' et p' couvre p" .

Question 10 Écrire la fonction couvertPar qui prend en argument deux produits p 
et q ; et qui retourne
la valeur vrai si 19 est couvert par q.

(* Caml *) {Pascal}
couvertPar : produit --> produit function couvertPar (pzproduit, q:produit)
-> bool : boolean;

Quelle est la complexité en temps de cette fonction ?

Question 11 Écrire la fonction reduire qui prend en argument une f.n.d. s ; et 
qui retourne une f.n.d.
calculant la même fonction où il n'y a plus aucun produit couvrant un autre.

(* Caml *) {Pascal}
reduire : fnd --> fnd » function reduire (szfnd) : fnd;
Quelle est la complexité de cette fonction par rapport aux longueurs lg, &, . . 
.Ëk des listes ao, al, . . . ak
composant la représentation (ak, . . . CL2,CL1,CLO> de s '?

Question 12 Donner une borne supérieure de la complexité du calcul du résultat 
de cette f.n.d. réduite
en fonction du nombre n d'arguments de la fonction f.

La partie combinatoire d'un circuit contient une combinaison de portes--E T , 
portes--OU et inverseurs
représentés sur la figure 2. Les signaux circulant dans les fils des circuits 
sont assimilés aux booléens ()
et 1. Une porte--OU a 77. entrées 5120, 331, ...a:n_1 calcule la somme 
(disjonction) 5150 + 331 + -- - + :rn_1 ; de
même une porte--ET a n entrées 330, 5131, ...a:n_1 calcule le produit 330 - æ1 
- - - æn_1, et l'inverseur à une
entrée :c calcule î.

Cette partie combinatoire des circuits intégrés consiste souvent à calculer une 
fonction f de B" dans
E'" (0 < 77. < 30, 0 < m) a l'aide d'un PLA (Programmablc Logic Array). Un PLA, 
à. n entrées et m
sorties comme indiqué sur la figure 3, calcule sur chaque sortie la fonction 
booléenne fZ-(oe0, 5121, . . . æn_1)
(O 5 'l < m) associée à f en s'appuyant sur sa représentation en f.n.d.. Un PLA 
comporte deux parties :
la partie--ET ne contenant que des portes--E T et quelques inverseurs, et la 
partie--OU ne contenant que

des portes-- 0 U.

partie--E T

partie-- 0 U

FIG. 3: Circuit PLA.

Question 13 Pour une fonction f donnée de B" dans E'" (0 < n < 30, 0 < m)
a) Expliquer le fonctionnement du PLA associé. Dessiner le quand 
f0(OE0,ZE1,OE2) = g(æ0,oel) et

f1(OE0,OE17OE2) = h($0;$1;$2)
b) Déterminer la largeur [EUR du PLA comme indiqué sur la figure 3 permettant 
de calculer sa surface.
Comment réduire cette surface ?

II. Génération de circuits combinatoires

Dans cette partie, nous allons générer d'autres exemples de circuits 
combinatoires calculant des
fonctions booléennes. Ces circuits ne seront composés que d'inverseurs, de 
portes--ET ou portes--OU à
2 entrées (cf. la figure 2), et de bits valant 0 ou 1. Ils seront représentés 
par des arbres donnant la valeur
de la sortie en fonction des valeurs des entrées, c'est-à--dire des bits 
figurant à leurs feuilles. Le type de

ces arbres est le suivant :

(* Caml *) {Pascal}
type circuit = type circuit = "porte; porte = record case indicateur of
Bit of int Bit: (val:integer);
| Et of circuit*circuit Et: (a1:circuit; a2:circuit) ;
| Du of circuit*circuit Du: (a1:circuit; a2:circuit) ;
| Non of circuit;; Non: (a1:circuit) ; end;

On ne se souciera pas du partage possible entre sous--arbres calculant la même 
valeur. Mais on remarquera
que le temps mis par un circuit pour calculer son résultat est proportionnel à 
la hauteur de cet arbre.

Par exemple, on peut calculer en 3 unités de temps le ou--exclusif de a: et y 
comme suit :

(* Caml *) {Pascal}
let oux x y = function oux (x: circuit; y:circuit)z circuit;
Ou (Et (x, Non y), begin oux := nouveau0u (nouveauEt(x, nouveauNon (y)),
Et (Non x, y));; nouveauEt(nouveauNon(x), y)); end;

En Pascal, pour construire ces circuits, on utilisera les fonctions nouveauEt, 
nouveau0u et nouveauNon,
analogues aux constructeurs cons et conand de la partie 1.

Question 14 Écrire les fonctions bitAdd et bitRetenue qui prennent en argument 
trois circuits a:, y et
7" fournissant les valeurs :c' , y' et r' ; et qui, la première, retourne le 
circuit calculant le reste modulo 2 de
r' + y' + T' ; et qui, la seconde, retourne le circuit calculant le quotient de 
la division par 2 de :r' + y' + 7°' .

(* Caml *) {Pascal}

bitAdd : circuit --> circuit --> function bitAdd (oezcircuit; y:circuit;
--> circuit --> circuit r:circuit) : circuit;
bitRetenue: circuit --> circuit -> function bitRetenue (oezcircuit; y:circuit;
--> circuit --> circuit rzcircuit) : circuit;

La représentation binaire 55 de l'entier a: sur n bits (n > O) est à présent 
décrite par un vecteur
(tableau) de n circuits, dont la i--ème entrée vaut le bit a:;, comme indiqué 
dans la partie 1. On appellera
mot machine de longueur 71 ce tableau. Un additionneur série de a? et @? 
effectue l'addition successive des
bits :s; et y; en partant des bits les moins significatifs vers les bits les 
plus significatifs en propageant la
retenue.

Question 15 Écrire la fonction addSerie qui prend en arguments deux mots 
machine :c et y de longeur
n; et qui retourne le circuit calculant le mot machine de longueur n + 1 
représentant 37 + y . Quel est le
temps de calcul de ce circuit ? Donner un ordre de grandeur du nombre de portes 
de ce circuit.

(* Caml *) {Pascal}

type mot = array[0..256] of circuit;
procedure addSerie (var 2: mot; n:integer;
var oe: mot; var y: mot);

type mot == circuit vect;
addSerie : mot --> mot --> mot

En Caml, on supposera que les paramètres a: et y ont une même longueur n. En 
Pascal, la fonction
prend la longueur n effective du mot en argument ; le résultat est retourné 
dans le paramètre z passé par

référence.

Question 16 Ecrire la fonction mux qui prend en arguments un circuit 3 et deux 
mots machines cc et
y; et qui retourne le circuit fournissant la valeur de a: si s' fourni par 3 
vaut 1, et celle de y si 3' vaut 0.

(* Caml *) {Pascal}

procedure mux (var 2: mot; n:integer;

mux: circuit --> mot --> mot --> mot _ _
8: Circuit; var oe: mot; var y: mot);

On peut calculer l'addition plus rapidement en coupant les mots machine a: et y 
a additionner en deux
parties basses oeb, % contenant les bits les moins significatifs et deux 
parties hautes 33h, yh contenant les
bits les plus significatifs. Pour ne pas attendre le résultat de la retenue de 
5125 + 3/5 pour calculer $;; + y...
on peut précalculer les résultats de l'addition de QE}; et yh avec la retenue 
valant 0 et celle valant 1. Puis
le véritable résultat de la retenue de $;; + yb permet de donner le résultat 
voulu pour :13h + yh + 7'.

Question 17 Écrire la fonction addPar qui prend en arguments deux mots machine 
:c et y de longeur n
et un circuit 7° fournissant une retenue 7°' ; et qui retourne le circuit 
calculant le mot machine de longueur
n + 1 représentant 51: + y + 7" . Quel est le temps de calcul de ce circuit ? 
Donner un ordre de grandeur du
nombre de portes de ce circuit.

(* Caml *) { Pascal }

procedure addPar (var 2: mot; n:integer;

addPar : mot -> mot --> circuit --> mot _ ,
var oe: mot; var y: mot; T: c1rcu1t);

Question 18 Pourquoi ne pas utiliser un PLA pour réaliser ces additionneurs ? 
Quels auraient été les
avantages /désavant ages ?

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2005 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Boris Yakobowski (ENS Cachan) et Vincent Puyhaubert (Professeur en CPGE).

Ce sujet traite de logique et fait manipuler des circuits, aussi bien à travers 
une
représentation graphique classique que sous la forme, plus abstraite, d'un type 
et de
fonctions travaillant sur ce type. Il requiert non seulement une bonne 
compréhension
du cours de logique, mais également une part d'intuition et d'adaptation aux 
objets
et méthodes définis par l'énoncé.
Comme c'est souvent le cas à l'X, ce sujet demande d'écrire beaucoup de code,
d'un bout à l'autre. En outre, les fonctions à écrire à la fin de chaque partie 
sont
longues. Enfin, on a besoin des styles fonctionnel comme impératif pour pouvoir
répondre à toutes les questions dans le temps imparti.
Les intentions du sujet n'étant pas toujours claires, il faut avoir une vue 
d'ensemble de l'énoncé pour bien comprendre ce que l'on doit faire dans chaque 
question.
Les deux parties sont indépendantes et doivent être traitées séparément pour 
éviter
toute confusion ; en effet, elles utilisent des concepts proches mais avec des 
définitions
très différentes.
· La première partie manipule des groupes de bits, représentés par des entiers,
et effectue diverses opérations afin de simplifier une formule en forme normale
disjonctive. Elle demande un peu d'astuce.
· La seconde définit un type pour représenter les circuits logiques et fait 
écrire
pas à pas des fonctions qui construisent un additionneur parallèle.
Les objets manipulés sont donc d'assez bas niveau : pas de théorie abstraite 
dans ce
sujet. Il constitue un bon entraînement à la partie logique du programme et 
permet
de vérifier ou d'améliorer ses capacités de programmation, à condition de 
tester ses
fonctions sur machine. On s'assurera ainsi qu'il n'y a pas d'étourderie dans 
les indices
ni d'erreur de syntaxe.
Les objets manipulés (sauf l'algorithme de la première partie) présentent 
également un intérêt culturel : on apprendra ce que sont les circuits PLA et 
l'additionneur
parallèle, qui ont été inclus dans de nombreux circuits intégrés.

Indications
I.

Génération de circuits PLA

2 Utiliser la question précédente. Indication supplémentaire : poser z = x  y.
5 Lire les trois premières lignes du corrigé de cette question (avant la 
remarque) :
il y a une coquille dans l'énoncé. Utiliser la question précédente sur p.v et 
q.v.
6 Trier la liste des produits (selon n'importe quel ordre total).
7 Définir une variable resultat, de valeur initiale ref [], puis comparer les 
produits deux à deux. Seconde indication : pour comparer les produits deux à 
deux,
écrire une fonction auxiliaire qui prend un produit p et une liste l, et 
compare p
à tous les éléments de l.
9 Utiliser une variable a_i qui contient la liste ai courante, ainsi qu'une 
boucle
« while !a_i <> [] do ... ».
10 Voici plusieurs indications. q couvre p si et seulement si l'on obtient q en 
supprimant des littéraux de p. Expliciter ce que cela signifie sur p.m et q.m. 
Remarquer
que pour deux ensembles A et B, A  B si et seulement si A  B = B. Considérer
maintenant le champ v et regarder ce qui se passe sur sa représentation binaire.
Considérer enfin p.v land q.m.
11 Écrire d'abord une fonction générale filtrer qui prend en argument un test
de type 'a -> bool et une liste de type 'a list. L'appel filtrer test liste
renvoie liste privée des éléments a tels que test a est vrai. Ensuite, pour 
chaque
produit p de chaque somme de l'argument fnd, retirer des sommes suivantes les
produits couverts par p grâce à filtrer.
12 Lisez la première dans la correction de cette question. Le pire cas est a1 = 
 (à
justifier).
Considérer la fonction f (x0 , x1 , . . . , xn ) = ¬(x0  x1  · · ·  xn ).
II.

Génération de circuits combinatoires

14 Il y a une retenue dans l'addition x + y + r si et seulement si deux termes 
au
moins sont égaux à 1.
15 Créer une variable resultat de type mot, que l'on remplit petit à petit, et 
une
variable retenue de type circuit ref contenant la retenue courante.
16 Exprimer à l'aide d'une formule logique une version simplifiée de mux 
travaillant
sur des bits.
17 Définir successivement les variables représentant n, n/2, xb , yb , xh , yh 
, xb + yb ,
xh + yh + 0, xh + yh + 1. Deuxième indication : utiliser mux. Troisième 
indication :
écrire addSerie_retenue qui fonctionne comme addSerie mais prend une retenue
comme argument supplémentaire.

I. Génération de circuits PLA
L'énoncé annonce que les booléens seront représentés par 0 pour faux
et 1 pour vrai. Ceci n'est valable que dans le texte en français, les fonctions
demandées utilisent bien le type bool (contrairement au sujet d'informatique
de Centrale 2005 qui utilise maladroitement le type int).
Noter que le bit de poids fort (le plus significatif) est dans ce sujet écrit
à la fin de la représentation binaire, par exemple 4 est représenté par (0, 0, 
1).
Enfin, les opérations arithmétiques admises par le sujet, qui sont définies
comme des opérations logiques bit à bit, existent bien en Caml :
Notation mathématique
Notation Caml

e  e
e land e'

e  e
e  e
¬e
e lor e' e lxor e' lnot e

Il n'est pas exigible de connaître ces fonctions Caml : une copie qui 
utiliserait
la notation mathématique dans le code source des programmes serait tout à
fait acceptable.
1 Soit y = x - 1. Si x est de la forme 2p alors sa représentation binaire est 
de la
forme (x0 = 0, x1 = 0, . . . , xp-1 = 0, xp = 1). Comme
p-1
P

2i = 2p - 1

i=0

celle de x - 1 est (y0 = 1, y1 = 1, . . . , yp-1 = 1, yp = 0). Ainsi x  y = 0.
Réciproquement, soit un x qui ne soit pas une puissance de 2. Il existe donc des
entiers p et z tels que x soit de la forme
x = 2p + z < 2p+1
et donc

avec

z>1

2p+1 > x - 1 = 2p + z - 1 > 2p

Le pe bit de la représentation binaire de x est donc xp = 1, de même que celui 
de
y = x - 1 qui est yp = 1. Ainsi le pe bit de x  (x - 1) est xp · yp = 1, par 
suite
x  y 6= 0.
2 Soit z = x  y. Dans la représentation binaire de z, zi = 1 si et seulement si
xi  yi = 1, c'est-à-dire si xi 6= yi . x et y sont donc à distance de Hamming 1 
si,
et seulement si, il existe un unique i tel que zi = 1, autrement dit si z est 
une
puissance de 2.
Pour écrire la fonction demandée, on écrit d'abord une fonction puissance_de_2
qui teste si son argument est une puissance de 2, en se fondant sur le résultat 
de la
question 1. Il suffit alors de tester si x  y est une puissance de 2.
let puissance_de_2 x =
if x <= 0
then false
else x land (x-1) = 0;;
let aDistUn x y =
puissance_de_2 (x lxor y);;

Rappelons que le correcteur accepte également l'écriture
let puissance_de_2 x =
if x <= 0
then false
else x  (x-1) = 0;;
let aDistUn x y =
puissance_de_2 (x  y);;
L'usage (d'ailleurs recommandé par les concepteurs du langage) en Caml
pour le nom d'une fonction est de séparer les mots par des « _ » et non par des
majuscules. C'est même une erreur de syntaxe en OCaml de commencer le
nom d'une fonction (ou d'une variable) par une majuscule, ce qui est réservé
(et obligatoire) à quelques catégories de noms dont les constructeurs des types
somme et les exceptions.
Les fonctions de ce corrigé que nous avons introduites suivent cette règle.
Cependant, pour ne pas agacer le correcteur, il est déconseillé de modifier le
nom des fonctions introduites dans l'énoncé.
3 On lit dans la table de la figure 1 que h(x0 , x1 , x2 ) = 1 si et seulement 
si
(x2 , x1 , x0 )  {(0, 0, 1), (0, 1, 1), (1, 0, 0), (1, 1, 0)}. On peut donc 
écrire
h(x0 , x1 , x2 ) = x2 · x1 · x0  x2 · x1 · x0  x2 · x1 · x0  x2 · x1 · x0
La table d'une formule peut avoir jusqu'à 2n lignes contenant 1, on risque
donc d'obtenir une expression très longue. Le but du problème est d'essayer
de simplifier cette expression en utilisant des règles simples, de manière à
représenter la formule avec le moins de produits possible.
4 On peut appliquer la réduction proposée sur les deux premiers termes de la
somme, on obtient le produit x2 · x0 . De même, on peut appliquer cette 
identité à
x2 · x1 · x0 et x2 · x1 · x0 , ce qui donne x2 · x0 . Ainsi
h(x0 , x1 , x2 ) = x2 · x0  x2 · x0
On retrouve bien l'expression h(x0 , x1 , x2 ) = x0  x2 donnée par l'énoncé.
5 Il y a une coquille typographique dans l'énoncé. Le produit dont les 
représentations binaires sont v = (1, 0, 1, 0, 1, 0, . . . , 0) et m = (1, 0, 
1, 1, 1, 0, . . . , 0) s'écrit en
abrégé 1-101- · · · - ou plus simplement 1-101.
En effet, x1 et x5 n'apparaissent pas dans le produit x0 · x2 · x3 · x4 donné
comme exemple par l'énoncé. Il serait déraisonnable de noter l'un par « 0 »
et l'autre par « - ». Les exemples donnés aux questions 7 et 9 permettent de
vérifier que l'on note « - » pour un littéral qui n'apparaît pas dans le 
produit,
« 1 » s'il est positif et « 0 » s'il est négatif. On écrit dans l'ordre les 
codes de
x0 , x1 , x2 etc. Ainsi le produit x1 · x2 · x5 s'écrit -11--0.
On peut éliminer une variable entre les produits p et q si et seulement si les 
deux
conditions suivantes sont vérifiées.