X Informatique MP/PC 2006 -- Corrigé Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par Walter Appel (Professeur en CPGE) et Céline Chevalier (ENS Cachan). Le thème de ce sujet est la répartition des ordres de lecture et écriture entre deux têtes d'un disque dur, de façon à minimiser la distance totale parcourue, donc la durée de ces opérations. Il s'agit surtout d'un prétexte à un exercice intéressant, car le modèle est assez éloigné de la réalité. On y voit un exemple (avec étapes détaillées) de programmation dynamique, qui est une technique classique de programmation. Le sujet est bien équilibré entre questions théoriques et questions de programmation. Contrairement au sujet de l'an dernier, celui-ci est bien détaillé. La difficulté est progressive sur l'ensemble du sujet (on fera attention aux indices dans la dernière sous-partie). Le découpage en sous-parties est surtout un regroupement des quelques questions détaillant un même but. Nous avons rédigé les codes source en Maple, car ce langage est le plus connu en classes préparatoires (par ceux qui ne suivent pas l'option informatique), même s'il est plus destiné au calcul formel qu'à la programmation. D'autres langages sont autorisés pour cette épreuve, dont Caml (Caml Light et OCaml), C, C++, Java et Pascal. Les fonctions écrites n'utilisant qu'une syntaxe simple, le code est compréhensible même si vous ne maîtrisez pas Maple. Indications Première partie 1 Définir deux variables position_tete1 et position_tete2 pour mémoriser la position des têtes, ainsi que resultat pour accumuler la distance parcourue. 2 Considérer une séquence optimale (on montrera qu'il en existe une). Que se passet-il si on échange les deux têtes ? 4 Le premier déplacement est fixé ; examiner les deux cas du second. 5 Comparer les coûts des deux possibilités et renvoyer le tableau correspondant. Seconde partie 6 La règle de décision de la question 5 consiste à satisfaire une requête par la tête la plus proche. 8 Énumérer brutalement toutes les possibilités et renvoyer le tableau correspondant à la bonne. 9 Comme il n'y a pas de contrainte sur la configuration finale, chercher celle qui coûte le moins cher. 10 Remarquer (c'est sous-entendu dans l'énoncé) qu'il est inutile de déplacer une tête après avoir satisfait une requête (on la déplacera s'il le faut lors de la prochaine requête), puis justifier les égalités une à une. Pour la deuxième, quelles étaient les configurations possibles juste avant de satisfaire la k e requête ? Pour la troisième, considérer l'échange des deux têtes. 11 Si l'on fait les mises à jour dans l'ordre de la question 10, on est assuré de ne pas modifier une case avant de la lire. 12 Créer un tableau cout puis utiliser les questions 9, 10 et 11. Précisément, initialiser le tableau cout selon la question 10, en déduire coutn grâce à la question 11 et extraire enfin le résultat comme indiqué à la question 9. 13 À l'étape k, cout[i] contient le coût d'une séquence optimale finissant dans la configuration (i, k). Adapter alors les égalités de la question 10 puis les fonctions mettreAJour et coutOpt. L'ordre des mises à jour est différent de celui de la question 11. Partie I A. Coût d'une séquence de déplacements 1 On définit deux variables position_tete1 et position_tete2, de type entier, pour mémoriser la position courante des têtes, ainsi que resultat qui accumule les distances parcourues. On peut alors lire les requêtes une à une et appliquer la définition du coût. Comme proposé dans l'énoncé, n est une variable globale. coutDe := proc (r,d) local position_tete1, position_tete2, resultat, i; # position initiale des têtes : position_tete1 := 0; position_tete2 := 0; resultat := 0; for i from 1 to n do if d[i] = 1 then resultat := resultat + abs(r[i] - position_tete1); position_tete1 := r[i]; else resultat := resultat + abs(r[i] - position_tete2); position_tete2 := r[i]; fi; od; resultat; end; 2 Justifions tout d'abord l'existence d'une séquence de déplacements optimale. Pour cela, il suffit de constater que le nombre de séquences de déplacements étant fini, l'ensemble des coûts possibles est dès lors également fini : il admet un minimum. Soit d une séquence de déplacements optimale pour un bloc de requêtes donné. Si d commence par 1, il n'y a rien à faire. Dans le cas contraire, d commence par 2. Si l'on échange alors les deux têtes (c'est-à-dire si l'on remplace tous les 1 par des 2 et réciproquement dans la séquence de déplacements), la distance totale est inchangée. On obtient ainsi une nouvelle séquence de déplacements, qui commence par 1. 3 Pour chaque requête, on a le choix entre les deux têtes pour la satisfaire (les deux têtes peuvent se croiser et être au même endroit). Il y a donc 2n possibilités. B. Coût optimal pour deux requêtes 4 Le premier déplacement est fixé (c'est 1) : il ne reste qu'à choisir le second. Pour le bloc h10, 3i, choisir 1 donne un coût supplémentaire de |3 - 10| = 7 tandis que choisir 2 n'ajoute que |3 - 0| = 3. Une séquence de déplacements optimale est alors h1, 2i De la même façon, pour le bloc h3, 10i, la séquence h1, 1i coûte 10 tandis que la séquence h1, 2i coûte 13. Une séquence de déplacements optimale est donc h1, 1i 5 On compare simplement les deux possibilités. La première est h1, 1i et coûte r1 + |r2 - r1 |. La seconde est h1, 2i et coûte r1 + r2 . On renvoie donc la première si |r2 - r1 | est plus petit que r2 , la seconde sinon. On choisit arbitrairement la seconde dans le cas |r2 - r1 | = r2 . coutOpt2 := proc (r1, r2) if abs (r2 - r1) < r2 then array([1,1]); else array([1,2]); fi; end; Partie II A. Coût optimal pour trois requêtes 6 La règle de décision de la question 5 consiste à satisfaire chaque requête par la tête la plus proche. Une telle optimisation locale sans tenir compte de la suite est appelée algorithme glouton. Une théorie permet de caractériser les problèmes où un tel algorithme donne la solution optimale. Par convention, la tête 1 satisfait la requête 20, la tête la plus proche de la requête r2 = 9 est alors la 2, qui satisfera aussi la requête r3 = 1. La séquence cherchée est donc h1, 2, 2i et son coût est 20 + 9 + 8 = 37. 7 Il y a deux possibilités pour chacune des requêtes r2 et r3 . Calculons le coût des quatre possibilités. séquence calcul du coût coût h1, 1, 1i 20 + 11 + 8 39 h1, 1, 2i 20 + 11 + 1 32 h1, 2, 1i 20 + 9 + 19 48 h1, 2, 2i 20 + 9 + 8 37 L'approche de la question 6 donne la séquence h1, 2, 2i alors que la séquence h1, 1, 2i a un coût strictement inférieur. Elle n'est donc pas optimale. 8 Comme suggéré par la question 7, on énumère toutes les possibilités sans chercher plus de finesse. Cette stratégie marche à tous les coups mais est souvent d'une lenteur catastrophique. Elle est donc à réserver aux cas où la taille de l'entrée est petite. Pour le cas général, il faudra trouver mieux, mais l'énoncé détaille ici les étapes.
