X Informatique MP 2000

Thème de l'épreuve Énumération efficace des parties d'un ensemble
Principaux outils utilisés codes de Gray, listes chaînées

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2000/MP_INFO_X_1_2000.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


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.

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2000 -- Corrigé
Ce corrigé est proposé par Lionel Eyraud (ENS Lyon) ; il a été relu par Codrin
Nichitiu (ENS Lyon) et Serge Bellaïche (ENS Ulm).

L'épreuve propose l'étude d'un système de N interrupteurs pour lesquels il faut
tester toutes les configurations possibles. Cece sert de prétexte pour étudier 
les
meilleures stratégies d'énumération de toutes les parties d'un ensemble.
La première partie ne demande que du codage et sert à se familiariser avec les
représentations adoptées dans l'énoncé. La deuxième partie présente une manière
naïve d'effectuer le test ; la troisième propose une stratégie bien plus 
évoluée, fondée
sur un code de Gray. Dans la quatrième partie, qui est nettement plus délicate, 
on
s'intéresse à une généralisation du problème : l'énumération des parties de 
cardinal
inférieur, à une constante fixée à l'avance ; l'énoncé propose une méthode dont 
on
montre qu'elle est optimale.

Indications
2 Il faut parcourir en parallèle les deux listes passées en argument.
4 Comparer avec l'écriture binaire de l'entier e (P).
5.b Chercher une relation de récurrence.
7.a Utiliser la relation A  A =  pour toute partie A.
7.b Remarquer que pour i < 2n - 1, t2n +i = ti
8.a Utiliser la relation de définition de T.
9.b Comparer la parité de i et de Card (Si )
11.a Introduire la différence ln,k - sn,k + 1.
11.b Procéder par récurrence sur n (et non sur k).
13 Essayer de trouver pour le coût minimal d'un test une relation de récurrence
semblable à celle de ln,k .

Première partie

Parties d'un ensemble

1 Pour écrire la fonction card, il suffit de compter les éléments de la partie 
vue
comme une liste.
En Caml, cela peut se faire de façon naturellement récursive :
let rec card = function
|[] -> 0
|(x::xs) -> 1 + (card xs) ;;

En Pascal, on peut l'écrire de façon itérative ; cela permet de bien voir 
comment
on peut parcourir une liste en Pascal :
function card (p : partie) : integer ;
var q : partie ;
res : integer ;
begin
res := 0 ;
q := p ;
while (q<>nil) do
begin
res := res + 1 ;
q := q^.suivant ;
end
card := res ;
end ;
2 La différence symétrique de deux parties P et Q est constituée des éléments 
qui
sont dans P ou dans Q mais pas dans les deux.
La méthode naïve consiste à regarder tous les éléments de P et à ne les
ajouter dans le résultat que s'ils ne sont pas dans Q, puis à faire la même
chose avec Q. Mais cette méthode a une complexité en O (mn), ce qui est
beaucoup trop.
On peut par contre profiter du fait que les listes passées en argument sont 
triées
par ordre croissant, et explorer les deux parties en même temps en appliquant 
la règle
suivante : si dans P on en est à un élément x plus petit que celui de Q, alors 
x 
/Q
et on peut ajouter x au résultat et continuer avec P\{x} et Q, et 
symétriquement.
En Caml, cela donne :
let rec delta p q =
match (p,q) with
|([], _) -> q
|(_, []) -> p
|(x::xs, y::ys) -> if (x < y) then x::(delta xs q)
else if (x > y) then y::(delta p ys)
else (delta xs ys) ;;

Et en Pascal :
function delta (p, q : partie) : partie ;
var r, s
: partie ;
res_debut : partie ;
res_fin : partie ;
tmp
: integer ;
begin
r := p ;s := q ;
res_debut := cree_partie(0, nil) ;
res_fin := res_debut ;
while ((r<>nil) and (s<>nil)) do
begin
tmp := -1 ;
if (r^.valeur < s^.valeur) then
begin tmp := r^.valeur ; r := r^.suivant ; end
else
if (r^.valeur > s^.valeur) then
begin tmp := s^.valeur ; s := s^.suivant ; end
else
begin r := r^.suivant ; s := s^.suivant ; end ;
if (tmp <> -1) then begin
res_fin^.suivant := cree_partie(tmp, nil)
res_fin := res_fin^.suivant ;
end ;
end ;
if (r = nil) then res_fin^.suiv := s
else res_fin^.suiv := r ;
delta := res_debut^.suivant ;
dispose(res_debut)
end ;
La complexité de ces fonctions est bien linéaire en la taille des entrées, 
puisqu'à
chaque appel récursif ou passage dans la boucle while on avance d'un élément 
dans
au moins une des deux listes. Le pire cas arrive lorsque P et Q sont 
d'intersection
nulle, dans ce cas le code est répété exactement n + m fois puisqu'à chaque 
fois on
n'avance que dans une seule des deux listes.
Cette fonction delta crée une nouvelle partie et donc alloue en mémoire
(via l'appel à new dans cree_partie) la place nécessaire. Pour écrire un 
programme complet, il faudrait donc libérer la mémoire ainsi allouée en 
utilisant
la procédure dispose, symétrique de new, comme à la dernière ligne de cette
fonction delta. Par exemple, on pourrait écrire une fonction libere_partie
comme ceci :
procedure libere_partie(p : partie) ;
var q, r : partie ;
begin
q := p ;
while(q<>nil) do
begin
r := q ;
q := q^.suivant ;
dispose(r) ;

end ;
end ;
Cette fonction devrait alors être utilisée à chaque fois que l'on est sûr
qu'une partie ne servira plus. Cependant, il faut aussi veiller à ce que les
parties qu'on libère ne contiennent pas des pointeurs vers d'autres parties que 
l'on va utiliser. Pour cela, il faudrait également remplacer à la fin
de la procédure delta les commandes res_fin^.suivant := r ou s par
res_fin^.suivant := duplique(r) ou duplique(s), où duplique(p) crée
une nouvelle partie (et alloue un nouvel espace mémoire) dont les éléments
sont les mêmes que ceux de p.
3 Pour passer d'une configuration P à une configuration Q, il suffit de commuter
(c'est-à-dire changer de position : relever ceux qui sont baissés, rabaisser 
ceux qui
sont levés) les interrupteurs qui sont dans Q mais pas dans P, ou dans P mais 
pas
dans Q. Cela correspond donc à la différence symétrique  (P, Q).
Pour afficher une liste, il suffit de la parcourir en affichant tous ses 
éléments les
uns après les autres.
En Caml, on définit une fonction auxiliaire qui affiche la liste proprement dite
sans retour à la ligne et que l'on fait suivre à la fin d'un appel à 
print_newline pour
aller à la ligne.
let rec affiche_sur_une_ligne = function
[] -> ()
|x::xs -> ( printf "%d " x ;
affiche_sur_une_ligne xs ) ;;
let affiche p =
( affiche_sur_une_ligne p ;
print_newline() ) ; ;
let test p q = affiche (delta p q) ; ;
Pour pouvoir utiliser la fonction printf, il faut auparavant charger le module
printf par la commande #open "printf";;.
En Pascal :
procedure affiche(p : partie) ;
var q : partie ;
begin
q := p ;
while (q<>nil) do
begin
write (q^.valeur, ' ') ;
q := q^.suivant ;
end ;
writeln ;
end ;
procedure test (p, q : partie) ;
begin