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.
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.