X Informatique MP 2000

CONCOURS D'ADMISSION 2000

COMPOSITION D'INFORMATIQUE

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée

* * *

Avertissement. On attachera une grande importance à la clarté, à la précision 
et à la conci-
sion de la rédaction.

Introduction. Nous considérons un système commandé par un tableau de bord 
comportant
N 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 2N
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 a N -- 1.

Système
Système
Système

Système

HEDE--LH

©®®®@

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

Notations. Nous appelons partie un sous--ensemble fini de l'ensemble N des 
entiers naturels.
Un élément d'une partie est appelé indice. La différence symétrique de deux 
parties P et Q est
définie par :

PAQ=(P\Q)U(Q\P)=(PUQ)\(P0Q)

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 n positif ou nul, nous notons In 
= {O, .., n -- 1}
l'ensemble des entiers inférieurs strictement à n.

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 Pascal
type indice = integer ;
type indice == int ;; type partie = noeud ;

noeud = record
valeur : indice ; suivant : partie ;
end ;

type partie indice list ;;

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. Ecrire la fonction card qui retourne le nombre d'éléments d'une 
partie.

Caml

value card : partie --> int

Pascal

function card (p : partie) : integer ;

Les candidats composant en Caml devront résoudre cette question sans faire 
appel a 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(m + 71), où m et n sont les cardinaux des 
arguments.

Caml

value delta : partie --> partie --> partie

Pascal

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 a commuter 
pour passer
d'une configuration à une autre.

Caml Pascal
value test : partie --> partie --> unit procedure test (p,q : partie) ;

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

Caml Pascal
printf "%d " i ; write (i,' ') ;
print_newline () ; writeln ;

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

À toute partie P, nous associons l'entier e(P) = ZOEP 2' (avec la convention 
e(@) = 0). Nous
définissons le successeur de P comme l'unique partie dont l'entier associé est 
e(P) + 1.

Question 4. Écrire la fonction succ qui retourne le successeur d'une partie. Le 
nombre d'opé--
rations ne devra pas excéder 0... où l est le plus petit indice absent dans la 
partie donnée en
argument.

Caml Pascal
value suce : partie --> partie fonction suce (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 a la fin du test tous 
les interrupteurs
seront levés.

a) Écrire un programme qui imprime la liste des indices des interrupteurs a 
commuter pour
réaliser la totalité du test pour N interrupteurs et qui examine les 
configurations dans l'ordre
défini par le successeur. L'argument de cette fonction sera l'entier N.

Caml Pascal
value test_incr : int --> unit procedure test_incr (n : integer) ;

b) Exprimer, en fonction de N, le nombre total d'interrupteurs a commuter pour 
réaliser le
test de cette manière.

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

Nous notons (u0, . . . ,ul_1) une suite finie de [ entiers. La concaténation de 
deux suites finies
de longueur [ et l' respectivement est une suite finie de longueur [ + Z' 
définie par

(110, . . . ,u1_1) @ (u6, . . . ,u2,_1) =  0.
b) Montrer que pour tout n > 0 et tout i < 2", on a Sgn+i : S,- A {n -- 1,71}. c) En déduire que pour tout n > 0 l'ensemble Pn = {50,51, . . . ,SQnÎ1} est 
l'ensemble des
parties de In.

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 a la fin du test.

a) Écrire un programme s'inspirant des résultats de cette partie, qui imprime 
une liste
d'indices d'interrupteurs a commuter pour réaliser la totalité du test. 
L'argument de cette
fonction sera le nombre d'interrupteurs N.

Caml Pascal
value test_gray : int --> unit 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
a commuter) ? Peut--on réaliser le test à un coût moindre ?

Question 9. Successeur de Gray. Pour tout i > 0, on note min(S,-) le plus petit 
élément de S,.

&) Donner une expression de ti en fonction de S,» pour i 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 (SÙæg.

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 
fonctionne-
ment de l'alimentation électrique provoque une défaillance dès que plus de K 
interrupteurs sur
les N sont baissés.

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

Caml Pascal
value test_sur : partie --> partie --> unit procedure test_sur (p,q : partie) ;

Question 11. L'inversev d'une suite finie T est obtenue en prenant ses éléments 
dans l'ordre
inverse, nous la notons T. Soit T(n, k) la suite définie pour tout k 2 1 et 
pour tout n > 1 par

T(1,l--c) = {O)
T(n+1,l) = T(n,1)® 1 l'ensemble P...k = {Sk,0,Sk71, . 
. . vSk,l...ki est
l'ensemble des parties de In de cardinal inférieur ou égal à k.

Question 12. Écrire un programme qui affiche une liste de lN,K + 1 
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 N 
et K sont donnés
en arguments.

Caml Pascal
value test_panne : int --> int --> unit procedure test_panne (n,k : integer) ;

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 à 
lN,K + 1.