Centrale Informatique optionnelle MP 2019

L-eni

Option informatique O
pl

MP ©

4 heures Calculatrice autorisée ON

Les candidat devront utiliser le langage Caml, à l'exclusion de tout autre, 
pour traiter ce sujet. Ils devront donner
le type de chaque fonction écrite.

Dans tout le problème, n désigne un entier naturel non nul.
Six e {0;1}, x désigne 1 -- x.
On note @ l'opérateur ou exclusif (également appelé XOR). Il est défini sur {0; 
1} par la table suivante :

0 1
00 1
111,0

On prolonge cette définition à N de la manière suivante.
Soit (x,y) EUR N? vérifiant x < 2 et y < 2 où p est un entier naturel non nul. On décompose x et y en base 2: p p Ti S ay2* et y = ÿ bof, k=0 k=0 où les coefficients a; et b, sont des éléments de {0;1}. On définit alors x @ y par: p rOY-- Sax @ by)2f. k=0 I Code binaire de Gray On cherche à obtenir tous les n-uplets composés de 0 et 1 de deux manières différentes. Ces n-uplets seront implémentés à l'aide de listes. IA - Dans cette sous-partie, on obtient ces n-uplets dans l'ordre lexicographique. Q 1. Écrire une fonction suivant transformant un n-uplet en son suivant dans l'ordre lexicographique. Par exemple, si t = (0;1;0;0;1;1;1), après exécution de suivant (t), on at -- (0;:1;0;:1:0;0;0). Cette fonction modifie la liste qu'elle reçoit en argument. De plus elle renvoie un booléen, valant vrai si elle a pu déterminer un n-uplet suivant, ou bien faux si le n-uplet fourni en argument était le dernier. Dans ce dernier cas, la valeur de ce n-uplet après exécution de la fonction est non spécifiée. Q 2. Écrire une fonction affichant tous les n-uplets dans l'ordre lexicographique. On pourra commencer par écrire une fonction affichant les éléments d'un n-uplet : affiche _nuplet : int list -> unit

I.B - Pour certaines applications, par exemple pour éviter des états 
transitoires intermédiaires dans les
circuits logiques ou pour faciliter la correction d'erreur dans les 
transmissions numériques, on souhaite que le
passage d'un n-uplet au suivant ne modifie qu'un seul bit. Dans un brevet de 
1953, Frank Gray! définit un ordre
des n-uplets possédant cette propriété.

Pour produire la liste des n-uplets dans l'ordre de Gray, un algorithme 
consiste à partir de la liste des 1-uplets
(0, 1) et à construire la liste des (n + 1)-uplets à partir de celles de 
n-uplets en ajoutant un 0 en tête de chaque
n-uplet puis un 1 en tête de chaque n-uplet en parcourant leur liste à 
l'envers. On obtient ainsi pour n = 2, la
liste (00, 01, 11, 10), pour n = 3, la liste (000, 001, 011, 010, 110, 111, 
101, 100), etc.

Les n-uplets sont représentés par des listes, une liste de n-uplets sera donc 
une liste de listes.

Q 3. Écrire une fonction ajout telle que si a est un entier et { une liste de 
n-uplets d'entiers, ajout a 1
renvoie une liste contenant les éléments de / auxquels on a ajouté a en tête.

Frank Gray (1887-1969) était un chercheur travaillant chez Bell Labs ; il à en 
particulier produit de nombreuses innovations dans
le domaine de la télévision.

2019-03-18 17:25:07 Page 1/3 (cc) BY-NC-SA
Q 4. Écrire deux fonctions mutuellement récursives monte et descend prenant en 
argument un entier n et
renvoyant les n-uplets dans l'ordre de Gray. L'une les renverra de 00...0 à 
10...0, l'autre en sens inverse.

Q 5. Évaluer la complexité de ces fonctions en termes d'appels à monte et 
descend.
Q 6. Décrire une façon simple d'améliorer cette complexité.
I.C - Dans tout ce qui suit, l'expression représentation binaire, désigne la 
représentation traditionnelle

en base 2. Étant donné k EUR N*, on a de manière unique
P .
k -- da? avec pEN, a EURe{0;1}, a, #0

La représentation binaire canonique de k est aa (le bit de poids fort, qui est 
non nul, en premier). On dira
que tout n-uplet constitué d'un nombre quelconque de 0 suivis de la 
représentation binaire canonique de Æ est
une représentation binaire de k.

On définit une fonction g sur N de la manière suivante. Pour k EUR N et n tel 
que £ < 2", on considère la liste dans l'ordre de Gray des 2" n-uplets : on indice cette liste de 0 à 2° -- T ; g(k) est le nombre dont une représentation binaire est le n-uplet d'indice k. Par exemple, si on énumère les 3-uplets selon l'ordre de Gray, on a (000, 001, 011, 010, 110, 111, 101, 100). Dans cette liste, l'élément d'indice 0 est 000 donc g(0) = 0, le 3-uplet d'indice 7 est 100 donc g(7) = 4. Soit n un entier naturel et & un entier compris entre 2" et 212 1:k=92" +7 avec 0 < r < 2". Q 7. Démontrer que g(k) = 2" + g(27--1--7r). Q 8. En déduire que, si la représentation binaire de k est b,,---0, et si on pose b,,, -- 0, la représentation binaire de g(k) est a,---aÿ où, pour tout j entre 0 et n, a; =b;@b;,1. Q 9. Exprimer, pour k EUR N, g(k) en fonction de k (à l'aide de @). Q 10. Montrer que g est une bijection de N dans N et, avec les notations précédentes, exprimer b; en fonction de az, k 2 j. ID -- On cherche à réaliser les fonctions g et g ! avec des circuits logiques. Une porte logique sera représentée par un rectangle contenant son nom (AND, OR, XOR, NOT) et on indiquera les entrées et sorties par des flèches. Par exemple : AND -- On se place d'abord dans le cas n = 3. Q 11. Donner un circuit logique à 3 entrées représentant les trois bits d'un entier k inférieur ou égal à 7 et à trois sorties représentant les trois bits de g(k). On pourra utiliser la porte logique XOR. Q 12. Donner un circuit pour l'opération inverse. Q 13. Sin > 2, donner un circuit permettant de passer d'un nombre k à n bits à 
g(k). Faire de même pour
l'opération inverse en utilisant le moins possible de portes. Préciser le 
nombre de portes utilisées.

II Enumération des combinaisons

On souhaite maintenant parcourir toutes les combinaisons de p éléments pris 
dans un ensemble de cardinal n
avec 0 < p < n. On supposera que cet ensemble est celui des n premiers entiers naturels. On le note E,, : E, = {0,..,n -- 1}. Les éléments d'une combinaison de Æ, seront systématiquement considérés dans l'ordre Croissant. IT. À - On se place dans le cas p -- 5. Q 14. Écrire une fonction d'argument n affichant les combinaisons de 3 éléments pris dans {0,...,n -- 1}: on souhaite que ces combinaisons apparaissent dans l'ordre lexicographique. Par exemple pour n = 4: 1[0,1,2}, 10, 1,3], [0,2,3), [1,2,3]. II. B --- On revient au cas p entier quelconque entre 1 et n. Q 15. Donner la première et la dernière combinaison de p éléments de E, (p < n) lorsqu'on énumère ces combinaisons dans l'ordre lexicographique. On suppose que Cj---c,_, est une combinaison de Æ,, vérifiant cj < + < c,_1, stockée sous la forme d'un vecteur ou d'un tableau ; on suppose également que cette combinaison n'est pas la dernière. Q 16. Ecrire une fonction comb_suivante permettant de transformer une combinaison en la combinaison suivante dans l'ordre lexicographique. On pourra commencer par chercher le plus petit indice j tel que Cjn > C+lL

2019-03-18 17:25:07 Page 2/3 (Cc)EATE:
Q 17. En déduire une fonction d'arguments n et p, énumérant et affichant toutes 
les combinaisons de p
éléments de Æ,, dans l'ordre lexicographique.

Q 18. Déterminer le nombre de combinaisons affichées avant d'arriver à la 
combinaison c--c,_1.

Q 19. En déduire que tout nombre entier naturel non nul N peut s'écrire sous la 
forme

"y

oOÙÙULN << <--  3) objets 05,0, _, et d'un sac 
dont la charge maximale
est M. Chaque objet o;, a une valeur v, et une masse m,. Soit p un entier entre 
1 et n -- 2. On veut choisir p
objets parmi les n de façon à ce que la masse totale de ces p objets soit 
inférieure à M et leur valeur totale soit
la plus grande possible.

Q 22. De quelle manière peut-on utiliser la fonction ci-dessus pour résoudre ce 
problème ?

Q 23. Évaluer le nombre d'additions effectuées (on ne s'intéressera qu'aux 
additions entre m, et entre v,).

IT. D --- Pour améliorer cet algorithme, on souhaite passer d'une combinaison à 
une autre en ne faisant que
deux modifications.

Q 24. Expliquer comment représenter une combinaison de p éléments pris parmi n 
par un n-uplet de O0 et 1.

Q 25. Modifier les fonctions monte et descend de la question 4 pour qu'elles 
renvoient les n-uplets représen-
tant les combinaisons de p éléments pris parmi n, dans le même ordre que 
précédemment.

Q 26. Déterminer le premier et le dernier n-uplet renvoyé par l'appel monte n p.

Q 27. Montrer qu'entre deux éléments successifs de la liste de n-uplets 
renvoyés par monte ou descend, seuls
deux bits changent. Montrer que cette propriété est également vraie entre le 
dernier et le premier n-uplets.

Soit a l'un de nos n-uplets, et soit a" son successeur. On admet qu'il existe 
un unique entier 7, 1 < 7j < max(p,n -- p) tel que g (a) -- g (a) = 2} mod 2" Q 28. En déduire un algorithme simple pour passer d'un n-uplet contenant p bits à 1 au suivant. Le décrire et le programmer sous la forme d'une fonction suivant. ILE -- Q 29. En déduire un algorithme qui donne un remplissage optimal du sac. Cet algorithme aura comme entrée : -- les valeurs des n objets, -- Jes masses des n objets, dans le même ordre, -- l'entier p, -- Ja masse maximum M. Il rendra en résultat les p indices des objets choisis. On ne demande pas la programmation explicite de cet algorithme. eeeFrINeee 2019-03-18 17:25:07 Page 3/3 (C2) BY-NC-SA