WikiPrépaLivrets

Polytechnique Informatique Commune MP PC 2006Sujet, corrigé et rapport du jury

Disque dur à deux têtes

Pas encore noté
  • Algorithmique et complexité
  • Programmation dynamique
  • Récurrence et démonstration
  • Structures de données (tableaux)
Logo concours X

Explorer les annales

BanqueX-ENSAnnée2006FilièreMP/PCMatièreInformatique
Annales X-ENS MP/PC InformatiqueX-ENS MP/PC 2006MP/PC InformatiqueInformatique 2006

Téléchargements

Télécharger le sujet (PDF)
Corrigé (Maple)
Corrigé 2 (Maple)
Corrigé 3 (Maple)
Rapport du juryLire en ligneLaTeXWord

Présentation du sujet

Difficulté moyenne
Disque dur à deux têtes : optimisation du déplacement des têtes de lecture/écriture
Afficher ou masquer la section

Le problème étudie des stratégies de déplacement des deux têtes d'un disque dur afin de minimiser le temps moyen d'attente entre requêtes de lecture ou d'écriture. Il s'agit de calculer, puis de programmer, le coût optimal d'une séquence de déplacements pour un bloc de n requêtes, en construisant progressivement un algorithme de type programmation dynamique.

  1. 1Partie I.A : coût d'une séquence de déplacementsÉcrire une fonction calculant le coût d'une séquence de déplacements donnée pour un bloc de requêtes.
  2. 2Partie I.B : coût optimal pour deux requêtesDéterminer la séquence de déplacements de coût minimal lorsque le cache ne contient que deux requêtes.
  3. 3Partie II.A : coût optimal pour trois requêtesÉtendre l'étude du coût optimal au cas de trois requêtes.
  4. 4Partie II.B : coût optimal pour n requêtesConstruire un tableau de coût et un algorithme de récurrence pour calculer le coût optimal d'un bloc de n requêtes.

Difficulté moyenne. Le problème a été traité jusqu'à la question 11 incluse par une grande partie des candidats, les questions 12 et 13 n'ayant été abordées que par une proportion plus modeste en raison de leur difficulté et de la longueur du sujet.

Ce qu'a observé le jury

4 erreurs relevées
Mauvaise complexité algorithmique · Emploi mal maîtrisé de la structure de boucle Maple · Confusion entre affichage et valeur de retour
Afficher ou masquer la section

Les candidats font peu d'erreurs de syntaxe ; la plus grande partie des erreurs vient des algorithmes employés ou de réponses erronées. Pour la filière PC, les deux dernières questions ont été moins abordées qu'en filière MP, ce qui explique un écart de notes entre les deux séries.

Les erreurs les plus sanctionnées

  1. 1
    Mauvaise complexité algorithmiqueQ1

    Beaucoup de candidats donnent des solutions correctes à la question 1 mais avec plusieurs passes sur la liste des déplacements, alors qu'une seule variable de position suffit.

  2. 2
    Emploi mal maîtrisé de la structure de boucle Maple

    L'usage de la structure for...while, pourtant déconseillée les années précédentes, a conduit certains candidats à des erreurs de terminaison et de complexité.

  3. 3
    Confusion entre affichage et valeur de retour

    La confusion entre affichage et valeur retournée par une fonction persiste chez certains candidats.

  4. 4
    Seconde propriété du tableau coût mal compriseQ10

    La deuxième propriété du tableau coût n'a été comprise que par une minorité de candidats, et sa démonstration n'a été que rarement claire.

Ce qui a été bien réussi

  • Les questions 3 à 6 ont été traitées correctement par quasiment tous les candidats.
  • La question 7 a été correctement traitée par la plupart des candidats.
  • Les démonstrations des propriétés 1, 3 et 4 du tableau coût (question 10) ont convaincu la plupart des candidats qui l'ont abordée.

Conseils du jury

  • Veiller à la conformité du programme aux spécifications de l'énoncé, tant sur la forme que sur le fond.
  • Soigner la clarté et la modularité des programmes plutôt que d'écrire un programme sur une seule ligne.
  • Donner explicitement l'énumération des cas possibles lorsque l'énoncé le demande.
  • Écrire les itérations avec soin, sans omettre de définir correctement les conditions initiales.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

ÉCOLE POLYTECHNIQUE

ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2006

Filière MP - option physique et sciences de lingénieur filliè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 à 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 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é T_n(f). On dit que la fonction f s'exécute :
en temps O(n^α), s'il existe K > 0 tel que pour tout n, T_n(f) ≤ Kn^α.
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 [0, + ∞) 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 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 à 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 à 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 Infini = − 1 sera utilisée pour coder l'infini, noté ∞ dans la Partie II.B.

Partie I

A. Coût d'une séquence de déplacements

Un bloc de n requêtes est représenté par une suite de n entiers positifs ou nuls ⟨r_1, r_2, …r_n⟩ rangés dans un tableau r de taille n. Une séquence de déplacements ⟨d_1, d_2, …d_n⟩ est une suite de n entiers, 1 ou 2, rangés dans un tableau d indiquant à l'étape i qui de la première tête ( d_i = 1 ) ou de la deuxième tête ( d_i = 2 ) doit se déplacer à la position r_i(1 ≤ i ≤ n). 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 ⟨5, 2, 4⟩, le coût de la séquence de déplacements ⟨1, 1, 2⟩ est 5 + 3 + 4 = 12, alors que le coût de ⟨1, 2, 1⟩ vaut 5 + 2 + 1 = 8.
Question 1 Écrire une fonction coutDe( r, d ) qui calcule le coût d'une séquence de déplacements d pour le bloc de requêtes r.
Le coût optimal d'une suite de requêtes r est le plus petit coût des séquences de déplacements satisfaisant le bloc de requêtes r.
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 r donné?

B. Coût optimal pour deux requêtes

Dans cette partie, le cache est de taille 2(n = 2). Il n'y a donc que deux requêtes r_1 et r_2. 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 ⟨10, 3⟩ et ⟨3, 10⟩.
Question 5 Écrire une fonction coutOpt2( r_1, r_2 ) qui retourne un tableau d, de longueur 2, donnant une séquence de déplacements de coût optimal.

Partie II

A. Coût optimal pour trois requêtes

Dans cette partie, le cache est de taille 3(n = 3). Il y a donc trois requêtes r_1, r_2 et r_3. 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 ⟨20, 9, 1⟩.
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 (r_1, r_2, r_3) qui retourne un tableau d donnant une séquence de déplacements de coût optimal.

B. Coût optimal pour n requêtes

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 r_0 = 0 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 (i, j) 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 i^(ième) requête et la deuxième tête la j^(ième) requête. Par convention, la configuration initiale est (0, 0).
À chaque requête r_k, on associe la matrice (n + 1) × (n + 1) représentée par le tableau d'entiers à deux dimensions cout_k. L'élément cout_k[i][j] est égal au coût optimal pour atteindre la configuration (i, j), après avoir satisfait la k^(ième) requête. On pose cout_k[i][j] = ∞ si cette configuration n'est pas accessible.
Question 9 Expliquer comment calculer le coût optimal d'une suite de requêtes ⟨r_1, r_2, …, r_n⟩ à l'aide du tableau correspondant cout _n.
Question 10 Montrer que les matrices (cout_k)_(0 ≤ k ≤ n) satisfont :
cout_0[0][0] = 0 et cout_0[i][j] = ∞ pour tout i ≠ 0 ou j ≠ 0;
cout_k[i][k] est le minimum de |r_k − r_j| + cout_(k − 1)[i][j] pour 0 ≤ j ≤ n;
cout_k[k][j] = cout_k[j][k];
cout_k[i][j] = ∞ si i ≠ k et j ≠ k.
Question 11 Écrire une procédure mettreAJour(cout, r, k ) qui met à jour le tableau cout en fonction de la nouvelle requête r_k, de sorte que si cout contenait les valeurs du tableau cout _(k − 1), alors, après la mise à jour, cout contient les valeurs du tableau cout _k.
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 à n.
La matrice cout est très creuse. Après avoir satisfait la k^(ième) requête, seule la k^(ième) ligne et la k^(ième) colonne peuvent contenir des valeurs différentes de ∞. De plus, comme la matrice cout est symétrique, seule la k^(ième) 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 à une dimension de taille n + 1. Évaluer son nouveau temps d'exécution.
Indication : On remarquera que pour parvenir à la configuration ( i, k ), avec i < k − 1, nécessairement on doit venir de la configuration ( i, k − 1 ), en revanche pour la configuration ( k − 1, k ) on peut provenir de n'importe quelle configuration ( k − 1, j ).
3

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet d'info commune X MP-PC 2006 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet d'info commune X MP-PC 2006 ?

Le sujet porte sur l'algorithmique, la complexité et la programmation dynamique, appliquées à l'optimisation du déplacement des têtes d'un disque dur.

Quelle est la moyenne du sujet d'info commune X MP-PC 2006 ?

La moyenne était de 11,06/20 avec un écart-type de 3,36 pour la filière PC, et de 12/20 avec un écart-type de 3,4 pour la filière MP.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet d'info commune X 2006 ?

Le jury signale une mauvaise gestion de la complexité algorithmique, un usage mal maîtrisé d'une structure de boucle Maple déconseillée, et une confusion entre affichage et valeur de retour d'une fonction.

Le sujet d'info commune X MP-PC 2006 est-il faisable en entier ?

Une grande partie des candidats a traité le problème jusqu'à la question 11 incluse ; les deux dernières questions, plus difficiles, ont été moins abordées, surtout en filière PC.

Pas de description pour le moment