interrupteurs, chacun pouvant être baissé ou levé. On désire tester ce système (pour le valider ou pour effectuer une opération de maintenance) en essayant mécaniquement chacune des

configurations possibles pour l'ensemble des interrupteurs. Le coût de cette opération, qu'elle soit réalisée par un opérateur humain ou par un robot, sera le nombre total de mouvements d'interrupteurs nécessaires. Nous supposons que chaque fois qu'un interrupteur est commuté le système effectue un diagnostic automatiquement et instantanément. Les interrupteurs sont indexés de 0 à

Figure 1. Pupitre de commande; les interrupteurs 2 et 4 sont baissés.

Notations. Nous appelons partie un sous-ensemble fini de l'ensemble

des entiers naturels. Un élément d'une partie est appelé indice. La différence symétrique de deux parties

est définie par :

On vérifie facilement que la différence symétrique est commutative et associative, ce que l'on ne demande pas de démontrer. Pour tout entier

positif ou nul, nous notons

l'ensemble des entiers inférieurs strictement à

Une partie sera représentée par une liste chaînée d'indices distincts apparaissant dans l'ordre croissant des entiers. On utilisera les types suivants :

Caml

type indice == int ;;
type partie == indice list ;;

Pascal

type indice = integer ;
type partie = `noeud ;
noeud = record
    valeur : indice ; suivant : partie ;
end ;

Les candidats composant en Pascal, pourront utiliser le constructeur suivant :

function cree_partie (v : indice ; s : partie) : partie ;
var p : partie ;
begin new (p) ; p^.valeur := v ; p^.suivant := s ; cree_partie := p end ;

Première partie. Parties d'un ensemble

Question 1. Écrire la fonction card qui retourne le nombre d'éléments d'une partie.

Caml

Pascal

value card : partie -> int

function card (

: partie) : integer ;

Les candidats composant en Caml devront résoudre cette question sans faire appel à la fonction de bibliothèque list_length.

Question 2. Écrire la fonction delta qui réalise la différence symétrique de 2 parties. Le nombre d'opérations ne devra pas excéder

, où

sont les cardinaux des arguments.

Caml	Pascal
value delta : partie -> partie -> partie	function delta (p,q : partie) : partie ;

Nous rappelons que dans toute liste chaînée de type partie les indices sont distincts et doivent apparaître dans l'ordre croissant des entiers.

Question 3. Application au problème des interrupteurs : à chacune des configurations possibles, nous associons la partie formée des indices des interrupteurs baissés.

Écrire un programme qui imprime la liste des indices d'interrupteurs à commuter pour passer d'une configuration à une autre.

Caml

Pascal

value test : partie -> partie -> unit

Pour imprimer un entier i suivi d'un espace ou pour imprimer un saut de ligne, on pourra utiliser respectivement les instructions suivantes :

    Caml
printf "%d " i ;
print_newline () ;

Pascal
write (i,' ') ;
writeln ;

Deuxième partie. Énumération des parties par incrément

À toute partie

, nous associons l'entier

(avec la convention

). Nous définissons le successeur de

comme l'unique partie dont l'entier associé est

Question 4. Écrire la fonction succ qui retourne le successeur d'une partie. Le nombre d'opérations ne devra pas excéder

où

est le plus petit indice absent dans la partie donnée en argument.

Caml Pascal

value succ : partie -> partie fonction succ (p : partie) : partie ;

Question 5. En application de ce mode d'énumération des parties, nous voulons réaliser le test de toutes les configurations d'interrupteurs. Au début et à la fin du test tous les interrupteurs seront levés.
a) Écrire un programme qui imprime la liste des indices des interrupteurs à commuter pour réaliser la totalité du test pour

interrupteurs et qui examine les configurations dans l'ordre défini par le successeur. L'argument de cette fonction sera l'entier

Caml
value test_incr : int -> unit
Pascal
procedure test_incr ( n : integer) ;
b) Exprimer, en fonction de , le nombre total d'interrupteurs à commuter pour réaliser le test de cette manière.

Troisième partie. Énumération des parties par un code de Gray

Nous notons

une suite finie de

entiers. La concaténation de deux suites finies de longueur

respectivement est une suite finie de longueur

définie par

La suite vide, notée

, est la suite de longueur 0 . Une suite finie

est préfixe d'une autre suite finie

s'il existe une suite finie

telle que

(autrement dit

est le début de

). Pour tout entier positif ou nul

, nous considérons la suite finie

de longueur

définie par

Nous avons par exemple

.
Pour tout entier

positif ou nul nous notons

le (

)-ème élément de

s'il existe. Puisque

est préfixe de

, la suite

est définie sans ambiguïté. Enfin, nous posons

et pour tout entier

positif ou nul nous définissons l'ensemble

Question 6.

a) Donner la valeur de

.
b) Donner la valeur de

pour tout

inférieur ou égal à 15 .

Question 7. Nous voulons montrer que les

peuvent être utilisés pour énumérer les parties de

, et ainsi résoudre notre problème d'interrupteurs.
a) Donner la valeur de

pour tout

.
b) Montrer que pour tout

et tout

, on a

.
c) En déduire que pour tout

l'ensemble

est l'ensemble des parties de

Question 8. Application au problème des interrupteurs. Comme dans la Deuxième partie, nous imposons que les interrupteurs soient levés au début et à la fin du test.
a) Écrire un programme s'inspirant des résultats de cette partie, qui imprime une liste d'indices d'interrupteurs à commuter pour réaliser la totalité du test. L'argument de cette fonction sera le nombre d'interrupteurs

    Caml
value test_gray : int -> unit

Pascal procedure test_gray ( n : integer) ;
b) Quel est le coût du test avec cette méthode (c'est-à-dire le nombre total d'interrupteurs à commuter) ? Peut-on réaliser le test à un coût moindre?

Question 9. Successeur de Gray. Pour tout

, on note

le plus petit élément de

.
a) Donner une expression de

en fonction de

pour

impair.
b) Écrire la fonction gray qui prend en argument une partie et retourne celle qui la suit immédiatement dans l'ordre défini par la suite

Caml Pascal

value gray : partie -> partie fonction gray (p : partie) : partie ;

Quatrième partie. Système défaillant

Chaque interrupteur baissé active une composante du système, et un mauvais fonctionnement de l'alimentation électrique provoque une défaillance dès que plus de

interrupteurs sur les

sont baissés.

Question 10. Écrire un programme qui imprime une liste d'interrupteurs à commuter, de taille minimale, permettant de passer d'une configuration non défaillante à une autre sans provoquer de défaillance. Les arguments de ce programme seront la partie de départ et la partie cible.

Question 11. L'inverse d'une suite finie

est obtenue en prenant ses éléments dans l'ordre inverse, nous la notons

. Soit

la suite définie pour tout

et pour tout

par

Soit

un entier strictement positif. Pour tout entier

positif ou nul nous notons

ème élément de

s'il existe. Puisque

est préfixe de

, la suite

est définie sans ambiguïté. Enfin, nous posons

et pour tout entier

positif ou nul nous définissons l'ensemble

.
a) Exprimer la longueur

en fonction de

, de

et du nombre

de parties de

de cardinal inférieur ou égal à

.
b) Montrer que pour tout

et tout

l'ensemble

est l'ensemble des parties de

de cardinal inférieur ou égal à

Question 12. Écrire un programme qui affiche une liste de

interrupteurs à commuter permettant de vérifier toutes les configurations non défaillantes sans provoquer de défaillance, en commençant et en finissant avec des interrupteurs tous levés. Les entiers

sont donnés en arguments.

[

]

Question 13. Montrer que le coût d'un test commençant et en finissant avec des interrupteurs tous levés et ne provoquant pas de défaillance ne peut pas être inférieur à

Caml	Pascal
value succ : partie -> partie	fonction succ (p : partie) : partie ;

Caml	Pascal
value gray : partie -> partie	fonction gray (p : partie) : partie ;