X Informatique MP/PC 2006

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