Centrale Option Informatique MP 2019

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, désigne un entier naturel non nul.
Si désigne .
On note l'opérateur ou exclusif (également appelé ). Il est défini sur par la table suivante :

On prolonge cette définition à de la manière suivante.
Soit vérifiant et où est un entier naturel non nul. On décompose et en base 2 :

où les coefficients et sont des éléments de . On définit alors par :

On cherche à obtenir tous les -uplets composés de 0 et 1 de deux manières différentes.
Ces -uplets seront implémentés à l'aide de listes.
- Dans cette sous-partie, on obtient ces -uplets dans l'ordre lexicographique.
Q 1. Écrire une fonction suivant transformant un -uplet en son suivant dans l'ordre lexicographique. Par exemple, si , après exécution de suivant(t), on a .
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 -uplet suivant, ou bien faux si le -uplet fourni en argument était le dernier. Dans ce dernier cas, la valeur de ce -uplet après exécution de la fonction est non spécifiée.
Q 2. Écrire une fonction affichant tous les -uplets dans l'ordre lexicographique.
On pourra commencer par écrire une fonction affichant les éléments d'un -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 -uplet au suivant ne modifie qu'un seul bit. Dans un brevet de 1953, Frank Gray définit un ordre des -uplets possédant cette propriété.
Pour produire la liste des -uplets dans l'ordre de Gray, un algorithme consiste à partir de la liste des 1-uplets et à construire la liste des -uplets à partir de celles de -uplets en ajoutant un 0 en tête de chaque -uplet puis un 1 en tête de chaque -uplet en parcourant leur liste à l'envers. On obtient ainsi pour , la liste ( ), pour , la liste ( ), etc.
Les -uplets sont représentés par des listes, une liste de -uplets sera donc une liste de listes.
Q 3. Écrire une fonction ajout telle que si est un entier et une liste de -uplets d'entiers, ajout a 1 renvoie une liste contenant les éléments de auxquels on a ajouté en tête.

Q 4. Écrire deux fonctions mutuellement récursives monte et descend prenant en argument un entier et renvoyant les -uplets dans l'ordre de Gray. L'une les renverra de à , 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. - Dans tout ce qui suit, l'expression représentation binaire, désigne la représentation traditionnelle en base 2 . Étant donné , on a de manière unique

La représentation binaire canonique de est (le bit de poids fort, qui est non nul, en premier). On dira que tout -uplet constitué d'un nombre quelconque de 0 suivis de la représentation binaire canonique de est une représentation binaire de .
On définit une fonction sur de la manière suivante. Pour et tel que , on considère la liste dans l'ordre de Gray des -uplets ; on indice cette liste de 0 à est le nombre dont une représentation binaire est le -uplet d'indice .
Par exemple, si on énumère les 3 -uplets selon l'ordre de Gray, on a ( ). Dans cette liste, l'élément d'indice 0 est 000 donc , le 3 -uplet d'indice 7 est 100 donc .
Soit un entier naturel et un entier compris entre et avec .
Q 7. Démontrer que .
Q 8. En déduire que, si la représentation binaire de est et si on pose , la représentation binaire de est où, pour tout entre 0 et .
Q 9. Exprimer, pour en fonction de (à l'aide de ).
Q 10. Montrer que est une bijection de dans et, avec les notations précédentes, exprimer en fonction de .
- On cherche à réaliser les fonctions et 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 :

On se place d'abord dans le cas .
Q 11. Donner un circuit logique à 3 entrées représentant les trois bits d'un entier inférieur ou égal à 7 et à trois sorties représentant les trois bits de .

On pourra utiliser la porte logique XOR.
Q 12. Donner un circuit pour l'opération inverse.
Q 13. Si , donner un circuit permettant de passer d'un nombre à bits à . Faire de même pour l'opération inverse en utilisant le moins possible de portes. Préciser le nombre de portes utilisées.

On souhaite maintenant parcourir toutes les combinaisons de éléments pris dans un ensemble de cardinal avec . On supposera que cet ensemble est celui des premiers entiers naturels. On le note ; . Les éléments d'une combinaison de seront systématiquement considérés dans l'ordre croissant.
II. - On se place dans le cas .

Q 14. Écrire une fonction d'argument affichant les combinaisons de 3 éléments pris dans ; on souhaite que ces combinaisons apparaissent dans l'ordre lexicographique. Par exemple pour , .
II.B - On revient au cas entier quelconque entre 1 et .

Q 15. Donner la première et la dernière combinaison de éléments de lorsqu'on énumère ces combinaisons dans l'ordre lexicographique.
On suppose que est une combinaison de vérifiant , 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. Écrire 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 tel que .

Q 17. En déduire une fonction d'arguments et , énumérant et affichant toutes les combinaisons de éléments de dans l'ordre lexicographique.
Q 18. Déterminer le nombre de combinaisons affichées avant d'arriver à la combinaison .
Q 19. En déduire que tout nombre entier naturel non nul peut s'écrire sous la forme

où . On dira qu'il s'agit d'une décomposition combinatoire de degré pour l'entier .
Q 20. Démontrer que si et sont deux entiers naturels tels que , alors

On pourra commencer par vérifier que, pour entre 0 et .
Q 21. En déduire l'unicité, pour , d'une décomposition combinatoire de degré pour .
II. - On suppose que l'on dispose de objets et d'un sac dont la charge maximale est . Chaque objet a une valeur et une masse . Soit un entier entre 1 et . On veut choisir objets parmi les de façon à ce que la masse totale de ces objets soit inférieure à 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 et entre ).
II.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 éléments pris parmi par un -uplet de 0 et 1 .
Q 25. Modifier les fonctions monte et descend de la question 4 pour qu'elles renvoient les -uplets représentant les combinaisons de éléments pris parmi , dans le même ordre que précédemment.
Q 26. Déterminer le premier et le dernier -uplet renvoyé par l'appel monte n p .
Q 27. Montrer qu'entre deux éléments successifs de la liste de -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 -uplets.
Soit l'un de nos -uplets, et soit son successeur. On admet qu'il existe un unique entier tel que
Q 28. En déduire un algorithme simple pour passer d'un -uplet contenant bits à 1 au suivant. Le décrire et le programmer sous la forme d'une fonction suivant.

Q 29. En déduire un algorithme qui donne un remplissage optimal du sac. Cet algorithme aura comme entrée :

Il rendra en résultat les indices des objets choisis.
On ne demande pas la programmation explicite de cet algorithme.