X Informatique MP/PC 2006

Thème de l'épreuve Disque dur à deux têtes
Principaux outils utilisés boucles for, tableaux

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

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES CONCOURS D'ADMISSION 2006 FILIÈRE MP - OPTION PHYSIQUE ET SCIENCES DE L'INGÉNIEUR FILIÈRE PC COMPOSITION D'INFORMATIQUE (Durée : 2 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie. *** Disque dur à deux têtes On attachera une grande importance à la concision, & la clarté, et a la précision de la rédaction. On précisera en tête de copie le langage de programmation utilise". Le temps d'exécution T ( f ) d'une fonction f est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de f. Lorsque ce temps d'exécution dépend d'un paramètre n, il sera noté Tn( f ) On dit que la fonction f s'exécute : en temps O(n°'), S'il existe K > 0 tel que pour tout n, Tn(f) S KnO'. Ce problème étudie des stratégies de déplacement des têtes d'un disque dur afin de minimiser le temps moyen d'attente entre deux requêtes au disque dur (de lecture ou d'écriture). Dans ce problème, le disque dur est représenté par une demi-droite [O,+oo) et possède deux têtes de lecture / écriture. Chacune des têtes peut aller indifféremment a n'importe quelle position sur le disque pour y lire ou écrire une donnée. Les deux têtes peuvent être au même endroit ou encore se croiser. On ne s'intéresse qu'aux temps de déplacement des têtes et non aux temps de lecture / écriture. Les deux têtes ont la même vitesse de déplacement. Le temps de déplacement d'une tête est supposé égal à la distance qu'elle parcourt. Une requête r est un entier positif ou nul représentant l'emplacement du disque auquel l'une des deux têtes doit se rendre. Initialement les deux têtes sont chacune a la position 0. Le disque dur est muni d'une mémoire (appelée cache) qui permet d'enregistrer n requêtes (n > 0) avant de les traiter. À chaque bloc de n requêtes présentes dans le cache, le contrôleur du disque dur doit alors satisfaire ce bloc de requêtes, dans leur ordre d'arrivée, en minimisant le déplacement total des deux têtes. L'ordre importe puisqu'une opération d'écriture peut précéder une autre opération de lecture ou d'écriture. Il faut donc déterminer pour chacune des n requêtes le numéro de la tête a déplacer de manière à minimiser la somme totale des temps de tous les déplacements. Notes de programmation : On supposera que le langage utilisé permet de définir des fonctions qui retournent des tableaux. On pourra aussi supposer que le nombre de requêtes n est une constante du programme. Enfin, une autre constante du programme Inf ini : --1 sera utilisée pour coder l'infini, noté oo dans la Partie H.B. Partie I A. Coût d'une séquence de déplacements Un bloc de 77. requêtes est représenté par une suite de n entiers positifs ou nuls (T1, T2, . . . ...) rangés dans un tableau 7° de taille n. Une séquence de déplacements < (n + 1) représentée par le tableau d'entiers a deux dimensions cout/EUR. L'élément coutHi][j] est égal au coût optimal pour atteindre la configuration (i, j), après avoir satisfait la k'ème requête. On pose coutk[i][jl : oo si cette configuration n'est pas accessible. Question 9 Expliquer comment calculer le coût optimal d'une suite de requêtes {r1,r2, . . . ,rn) a l'aide du tableau correspondant cout... Question 10 Montrer que les matrices (coutk)05kîn satisfont : cout0[0][0] : 0 et coutdi][j] : oo pour tout i # 0 ou j # O; coutk[i][k] est le minimum de W: -- rj| + coutk_1[i][j] pour 0 S j _<_ n; cout;,[k][j] : coutflj][k]g coutk[i][j] : oo si i # lc et j # k. Question 11 Écrire une procédure mettreAJour(cout,r, k) qui met a jour le tableau cout en fonction de la nouvelle requète r;,,, de sorte que si cout contenait les valeurs du tableau coutk_1, alors, après la mise a jour, cout contient les valeurs du tableau coutk. Question 12 En déduire une fonction coutOpt(r) permettant de trouver le coût minimal du bloc de n requêtes r. Donner le temps d'exécution de coutOpt(r) par rapport a n. La matrice cout est très creuse. Après avoir satisfait la k'eme requête, seule la k'eme ligne et la koeme colonne peuvent contenir des valeurs différentes de oo. De plus, comme la matrice cout est symétrique, seule la k'eme ligne est à retenir. Question 13 Écrire une nouvelle fonction coutOpt(r) qui calcule le coût minimal du bloc de n requêtes r en n'utilisant qu'un tableau cout a une dimension de taille n + 1. Évaluer son nouveau temps d'exécution. Indication : On remarquera que pour parvenir à la configuration (i, le), avec i < [EUR ----- 1, nécessai-- rement on doit venir de la configuration (i, le -- 1), en revanche pour la configuration (k -- 1, k) on peut provenir de n'importe quelle configuration (k -- 1,j).

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


 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. Le rapport du jury rappelle que le critère d'évaluation principal des programmes est bien sûr leur correction, mais viennent ensuite l'efficacité des algorithmes (en temps et en espace), la clarté et la modularité. 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 l'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; Le rapport du jury signale qu'il ne fallait pas confondre affichage et valeur de retour. Effectuer deux passes sur le tableau des déplacements pour calculer le coût de chaque tête séparément a été pénalisé. 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 optimale, 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. La théorie des matroïdes 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. D'après le rapport du jury, les questions 1 à 7 ont été bien traitées par la plupart des candidats. Il n'en va pas de même pour les suivantes.