X Informatique MP 2005

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