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)
           

É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