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.

On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction. On précisera en tête de copie le langage de programmation utilisé.

Le temps d'exécution d'une fonction est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de . Lorsque ce temps d'exécution dépend d'un paramètre , il sera noté . On dit que la fonction s'exécute :
en temps , s'il existe tel que pour tout .

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 et possède deux têtes de lecture/écriture. Chacune des têtes peut aller indifféremment à 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 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 à la position 0 .

Le disque dur est muni d'une mémoire (appelée cache) qui permet d'enregistrer requêtes ( ) avant de les traiter. À chaque bloc de 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 requêtes le numéro de la tête à 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
est une constante du programme. Enfin, une autre constante du programme Infini sera utilisée pour coder l'infini, noté dans la Partie II.B.

Un bloc de requêtes est représenté par une suite de entiers positifs ou nuls rangés dans un tableau de taille . Une séquence de déplacements est une suite de entiers, 1 ou 2, rangés dans un tableau indiquant à l'étape qui de la première tête ( ) ou de la deuxième tête ( ) doit se déplacer à la position . Le coût d'une séquence de déplacements est la somme totale des distances parcourues par chacune des têtes.

Ainsi pour le bloc de requêtes , le coût de la séquence de déplacements est , alors que le coût de vaut .

Question 1 Écrire une fonction coutDe( ) qui calcule le coût d'une séquence de déplacements pour le bloc de requêtes .

Le coût optimal d'une suite de requêtes est le plus petit coût des séquences de déplacements satisfaisant le bloc de requêtes .

Question 2 Montrer qu'il existe toujours une séquence de déplacements de coût optimal qui commence par 1, c'est-à-dire commençant par déplacer la première tête.

Question 3 Combien de séquences de déplacements satisfont un bloc de requêtes donné?

Dans cette partie, le cache est de taille . Il n'y a donc que deux requêtes et . Par convention, la première tête sera toujours celle qui bouge sur la première requête.

Question 4 Donner une séquence de déplacements de coût minimal pour chacun des deux blocs de requêtes et .

Question 5 Écrire une fonction coutOpt2( ) qui retourne un tableau , de longueur 2, donnant une séquence de déplacements de coût optimal.

Dans cette partie, le cache est de taille . Il y a donc trois requêtes et . Par convention, la première tête sera toujours celle qui bouge sur la première requête.

Question 6 On suppose que la fonction de la question 5 a été étendue au cas de trois requêtes en appliquant la même règle de décision à la troisième requête qu'à la deuxième requête. L'appliquer en justifiant sur l'exemple .

Question 7 Énumérer toutes les stratégies possibles sur l'exemple de la question précédente. En déduire que l'approche de la question 6 ne fournit pas la solution de coût minimal.

Question 8 Écrire une fonction coutOpt3 qui retourne un tableau donnant une séquence de déplacements de coût optimal.

Dans cette partie, on calcule le coût minimal sans pour autant trouver une séquence de déplacements donnant ce coût. Par commodité, chacune des deux têtes peut effectuer indifféremment le premier déplacement.

On pose pour coder la position initiale des têtes. À un instant donné, la configuration des têtes du disque dur est représentée par une paire codant le numéro des deux dernières requêtes respectivement satisfaites par chacune des deux têtes : la première tête a satisfait en dernier la requête et la deuxième tête la requête. Par convention, la configuration initiale est .

À chaque requête , on associe la matrice représentée par le tableau d'entiers à deux dimensions . L'élément est égal au coût optimal pour atteindre la configuration , après avoir satisfait la requête. On pose si cette configuration n'est pas accessible.

Question 9 Expliquer comment calculer le coût optimal d'une suite de requêtes à l'aide du tableau correspondant cout .

Question 10 Montrer que les matrices satisfont :
et pour tout ou ;
est le minimum de pour ;
;
si et .
Question 11 Écrire une procédure mettreAJour(cout, ) qui met à jour le tableau cout en fonction de la nouvelle requête , de sorte que si cout contenait les valeurs du tableau cout , alors, après la mise à jour, cout contient les valeurs du tableau cout .

Question 12 En déduire une fonction coutOpt( ) permettant de trouver le coût minimal du bloc de requêtes . Donner le temps d'exécution de coutOpt( ) par rapport à .

La matrice cout est très creuse. Après avoir satisfait la requête, seule la ligne et la colonne peuvent contenir des valeurs différentes de . De plus, comme la matrice cout est symétrique, seule la ligne est à retenir.

Question 13 Écrire une nouvelle fonction coutOpt qui calcule le coût minimal du bloc de requêtes en n'utilisant qu'un tableau cout à une dimension de taille . Évaluer son nouveau temps d'exécution.
Indication : On remarquera que pour parvenir à la configuration ( ), avec , nécessairement on doit venir de la configuration ( ), en revanche pour la configuration ( ) on peut provenir de n'importe quelle configuration ( ).

3