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)
                 

É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.