Aller au contenu

DS 2 (MP2I 2022-2023) — Correction de programmes

Devoir surveillé · MP2I · 2022-2023 · parties I et II du DS 2 (4 h au total)

Cours : Terminaison · Correction

Autres parties : III. Planifier sa route · IV. Codeglyphes

Tout document interdit. Tout dispositif électronique interdit (calculatrice, cafetière, Francky...)

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles.

Bon courage et à l'abordage ! 🏴‍☠️

À la recherche du M-PIece

Le bateau

Résumé des épisodes précédents

À bord de votre bateau, le Coding Merry, vos coéquipiers et vous, Camel C. Civvy, êtes partis en quête du trésor légendaire : le M-PIece ! Dans ce sujet, vous allez résoudre des problèmes pour y arriver. Et, qui sait, ce trésor se trouve peut-être au CIV.

Ce problème est constitué de quatre parties indépendantes.

Remarque sur le corrigé

Les preuves de correction ou de terminaison présentées ici sont un objectif de rédaction à atteindre. Des réponses partielles ou moins détaillées sont acceptées.

Passer en revue l'équipage

Avant de partir, c'est le moment de passer en revue l'équipage et de s'assurer que tout le monde est qualifié.

Plusieurs membres de l'équipage vous montrent ainsi des programmes qu'ils ont réalisés et vous allez devoir comprendre ce qu'ils font et montrer qu'ils sont corrects.

On considère le programme C suivant :

bool palindrome(char str[]){
    int i = 0,
    j = 0;
    while (str[j] != '\0') {
        j = j + 1;
    }
    j = j - 1;
    while (j >= i) {
        if (str[i] != str[j]) {
            return false;
        }
        i = i+1;
        j = j-1;
    }
    return true;
}

On suppose que str sera toujours une chaîne de caractère valide en C.

Question 1

  1. Dérouler l'exécution de ce programme sur les chaînes "kayak" et "canoe".
  2. Montrer que toutes les boucles terminent.
  3. Montrer que ce programme est correct, c'est-à-dire qu'il renvoie un booléen indiquant si une chaîne est un palindrome.

Indication : On rappelle qu'un palindrome est une chaine de caractère pouvant se lire de la même manière de gauche à droite et de droite à gauche.

Corrigé

  1. Pour "kayak", première boucle :

    \(j\) str[j]
    0 'k'
    1 'a'
    2 'y'
    3 'a'
    4 'k'
    5 0

    ensuite on passe \(j\) à 4 et on entre dans la seconde boucle.

    \(i\) \(j\) str[j] str[i]
    0 4 'k' 'k'
    1 3 'a' 'a'
    2 2 'y' 'y'
    3 1

    Comme on n'est pas sorti avant, on renvoie true.

    Pour "canoe", première boucle :

    \(j\) str[j]
    0 'c'
    1 'a'
    2 'n'
    3 'o'
    4 'e'
    5 0

    ensuite on passe \(j\) à 4 et on entre dans la seconde boucle.

    \(i\) \(j\) str[j] str[i]
    0 4 'e' 'c'

    Ici, on sort tout de suite en renvoyant false.

  2. Comme la chaine est valide, on sait que le caractère '\0' est présent à un indice \(n\). On a alors la quantité \(n-j\) qui est un variant de la première boucle car elle est :

    • entière ;
    • positive tout au long de la boucle vu que la condition implique \(j < n\) quand on boucle ;
    • diminue strictement à chaque itération car \(j\) augmente.

    Ainsi la première boucle termine.

    La seconde termine car la quantité \(j-i\) est un variant :

    • elle est entière ;
    • positive tout au long de la boucle car la condition \(i \le j\) implique \(j-i \ge 0\) ;
    • diminue strictement à chaque itération car \(j-1-(i+1) = j-i - 2 < j-i\).

  3. La première boucle termine et en sortie on a \(j = n\) où \(n\) est la première occurrence de '\0' dans la chaine, c'est-à-dire sa longueur.

    On va montrer que la propriété

    \[ I(i,j) = n-i-1 = j \wedge \forall k \in \range{0}{i-1}, s[k] = s[n-k-1] \]

    est un invariant.

    • Initialisation : au départ, \(i = 0\) donc la plage \(\range{0}{i-1} = \emptyset\) et l'invariant \(I(0,n-1)\) est vérifié.
    • Hérédité : si \(I(i,j)\) est vérifié en début d'itération et qu'on ne sort pas par le return false, on a \(s[i]=s[j]=s[n-1-i]\) donc la propriété d'égalité est vérifiée pour \(k = i\), on a donc \(\forall k \in \range{0}{i}\). De plus, \(n-(i+1)-1 = n-i-1-1 = j-1\) donc \(I(i+1,j-1)\) est vérifié.

    Si on sort par le return false, c'est que \(s[i] \neq s[j] = s[n-1-i]\) donc la chaîne n'est pas un palindrome : le résultat est correct.

    Sinon, l'invariant est validé et en sortie de boucle, on a \(n - i -1 = j < i \iff i > \frac{n-1}{2} \ge \lfloor \frac{n-1}{2} \rfloor\) donc \(i \ge \lfloor \frac{n}{2} \rfloor\) et l'égalité assure ainsi que la première moitié se retrouve à l'envers dans la seconde moitié : c'est un palindrome.

On considère le programme OCaml suivant :

let div a b =
  let q = ref 0 in
  let r = ref a in
  while !r >= b do
    r := !r - b;
    q := !q + 1
  done;
  (!q, !r)

On suppose ici que \(a, b\) sont des entiers naturels et que \(b > 0\).

Question 2

  1. Dérouler l'exécution de ce programme pour \(a = 42\) et \(b=4\).
  2. Montrer que ce programme termine.
  3. Montrer que le couple \((q,r)\) renvoyé vérifie \(a = bq + r\) et \(0 \le r < b\).
Corrigé

  1. Valeurs successives :

    \(q\) \(r\)
    0 42
    1 38
    2 34
    3 30
    4 26
    5 22
    6 18
    7 14
    8 10
    9 6
    10 2

    La fonction renvoie donc (10, 2).

  2. La quantité \(r\) est un variant :

    • elle est entière (uniquement des soustractions) ;
    • elle est positive tout au long de la boucle car si on rentre dans une itération c'est que \(r \ge b\), donc en fin d'itération \(r-b \ge 0\) et c'est la nouvelle valeur de \(r\) ;
    • comme \(b > 0\), elle diminue strictement à chaque itération.

    Ainsi, comme elle admet un variant, la boucle termine.

  3. On a l'invariant \(I(q,r) \equiv a = bq + r\) :

    • Initialisation : \(a = b \times 0 + a\) donc \(I(0,a)\) est vérifié.
    • Itération : si \(I(q,r)\) est vérifié en début d'itération, alors \(a = bq + r = b(q+1) + r-b\) donc \(I(q+1,r-b)\) est vérifié en fin d'itération ce qui correspond aux nouvelles valeurs de \((q,r)\).

    Ainsi, en sortie de boucle, on a \(a = bq+ r\) et comme on est sorti \(r < b\). De plus, on a vu à la question précédente que \(r \ge 0\).

Trouver la bonne vitesse - C

Afin de planifier la route, votre navigatrice, Cami, étudie les données qu'elle a empruntées à d'autres équipages. Elle a ainsi obtenu une suite de \(n\) nombres entiers indiquant la vitesse du bateau à intervalle régulier.

Par exemple, on aurait pu obtenir cette suite exemple de 10 nombres :

\[ 199\quad 200\quad 208\quad 210\quad 200\quad 207\quad 240\quad 269\quad 260\quad 263 \]

Dans toutes les questions, on suppose que cette suite est donnée sous la forme d'un tableau d'entiers du type int v[] et du nombre int n de vitesses enregistrées.

En premier lieu, on va s'intéresser au nombre de moments où le bateau a accéléré, indiqué ici avec une flèche \(\nearrow\) :

\[ 199\nearrow 200\nearrow 208\nearrow 210\searrow 200\nearrow 207\nearrow 240\nearrow 269\searrow 260\nearrow 263 \]

On voit sur cet exemple que le bateau a accéléré 7 fois.

Attention : on considère qu'on accélère quand la vitesse augmente strictement.

Question 3

Écrire une fonction de prototype

int accelerations(int v[], int n);

qui prend un tableau de vitesse en entrée et renvoie le nombre de fois où le bateau a accéléré.

Corrigé 
int accelerations(int v[], int n) {
    int accel = 0;
    for(int i = 0; i < n-1; i++) {
        if (v[i] < v[i+1]) {
            accel = accel + 1;
        }
    }
    return accel;
}

Question 4

Prouvez la correction de votre fonction.

Indication : il sera sûrement nécessaire de s'assurer qu'à tout moment, vous avez compté le nombre de fois où le bateau a accéléré dans la partie étudiée du tableau.

Corrigé

Conformément à l'indication, on remarque que accel contient toujours le nombre d'accélérations du préfixe étudié du tableau.

On considère ainsi le candidat invariant \(I(\texttt{accel},i) \equiv\) le nombre d'accélérations dans \(v[0],\dots,v[i]\) est \(\texttt{accel}\). On va le valider :

  • Initialisation : au départ, \(i = 0\) donc le préfixe contient un seul élément, il ne peut être question d'accélération, et comme initialement \(\texttt{accel} = 0\), on a bien \(I(\texttt{accel},i)\).
    • \(v[i] \ge v[i+1]\), alors il n'y pas de nouvelle accélération et comme on ne change pas \(\texttt{accel}\), on a bien \(I(\texttt{accel},i+1)\).
    • \(v[i] < v[i+1]\), on a alors une accélération de plus et ainsi on a bien \(I(1+\texttt{accel},i+1)\).

    Itération : si \(I(\texttt{accel},i)\) est vérifié en début d'itération, on a deux cas :

    Dans tous les cas, \(I\) est vérifié en fin d'itération.

Ainsi, en sortie de boucle \(I(\texttt{accel},n-1)\) est vérifié donc \(\texttt{accel}\) contient les accélérations du tableau complet.

Question 5

Écrire une suite d'instructions qui pourraient être placées dans la fonction main d'un programme pour :

  • définir le tableau de l'exemple
  • calculer le nombre d'accélérations N avec la fonction précédente
  • afficher une ligne indiquant Le bateau a acceleré N fois où N est affiché sous forme décimale.
Corrigé 
int v[] = { 199, 200, 208, 210, 200, 207, 240, 269, 260, 263 };
int N = accelerations(v, 10);
printf("Le bateau a acceleré %d fois.\n", N);

Dans l'exemple précédent, on peut voir que le bateau accélère au plus trois fois d'affilée avant de ralentir, cela est réalisé deux fois : \(199\nearrow 200 \nearrow 208 \nearrow 210\) et \(200 \nearrow 207 \nearrow 240 \nearrow 269\). Une série d'accélérations sera appelée ici une poussée.

Question 6

Écrire une fonction de prototype

int poussee(int v[], int n, int i);

où \(v\) et \(n\) décrivent un tableau vitesse comme précédemment, \(0 \le i < n\) et qui renvoie le nombre de fois où le bateau a accéléré à partir de la vitesse \(v[i]\).

Dans l'exemple précédent, pour \(i = 0\) on renverra \(3\), pour \(i = 2\) on renverra \(1\) et pour \(i = 3\) on renverra \(0\).

Corrigé 
int poussee(int v[], int n, int i) {
    int j = i;
    while(j < n-1 && v[j] < v[j+1]) {
        j += 1;
    }
    return j-i;
}

Question 7

Prouver la correction de votre fonction, c'est-à-dire que si elle renvoie \(N\) pour \(i\) alors la suite de valeurs \(v[i], v[i+1], ..., v[i+N]\) est croissante et, soit \(i+N+1 = n\) soit \(v[i+N] \ge v[i+N+1]\).

Attention il sera sûrement nécessaire ici de s'assurer de la terminaison.

Corrigé

On remarque rapidement que \(n-j\) est un variant, donc la boucle termine.

On va valider l'invariant \(I(j) \equiv \forall k \in \range{i}{j-1}, v[k] < v[k+1]\).

  • Initialisation : au départ \(j = i\), donc \(\range{i}{j-1} = \emptyset\) et \(I(j)\) est trivialement vérifié.

  • Itération : si on a \(I(j)\) en début d'itération, comme on est resté dans la boucle, c'est que \(j < n-1\) et \(v[j]< v[j+1]\), comme on sait que

    \[\forall k \in \range{i}{j-1}, v[k] < v[k+1]\]

    on en déduit

    \[\forall k \in \range{i}{j}, v[k] < v[k+1]\]

    donc \(I(j+1)\) est vérifié ce qui correspond à la nouvelle valeur de \(j\).

Ainsi, c'est bien un invariant et en sortie de boucle on a

\[\forall k \in \range{i}{j-1}, v[k] < v[k+1]\]

En notant \(N = j-i\), on a alors

\[\forall k \in \range{i}{i+N-1}, v[k] < v[k+1]\]

et,

  • soit \(j = n-1 \iff i+N+1 = n\)
  • soit \(v[j] = v[i+N] \ge v[i+N+1] = v[j+1]\).

Cela correspond donc à la spécification donnée par la question.

Question 8

En déduire une fonction de prototype

int plus_grande_poussee(int t[], int n);

qui renvoie la plus grande valeur de la poussée.

Attention votre fonction devra appeler la fonction précédente.

Corrigé 
int plus_grande_poussee(int t[], int n) {
    int m = 0;
    for(int i = 0; i < n-1; i++) {
        int v = poussee(t, n, i);
        if (v > m) {
            m = v;
        }
    }
    return m;
}

Question 9

Prouvez la correction de la fonction précédente en supposant la fonction poussee correcte.

Corrigé

On remarque qu'il n'est pas question de terminaison vu qu'il s'agit d'une boucle inconditionnelle.

On va valider l'invariant \(I(m,i) \equiv \forall k \in \range{0}{i-1}, m \ge \texttt{poussee}(t,n,k)\).

  • Initialisation : au départ \(m = 0\) et \(i = 0\), donc la plage est vide et la propriété est vérifiée. Ainsi, \(I(0,0)\) est vérifiée.
  • Itération : si \(I(m,i)\) est vérifié en début d'itération, on a deux cas, soit \(\texttt{poussee}(t,n,i) \le m\) et \(m\) ne change pas, soit \(\texttt{poussee}(t,n,i) > m\) et \(m\) devient \(\texttt{poussee}(t,n,i)\). Dans tous les cas la valeur en fin d'itération de \(m\) est plus grande que tous les \(\texttt{poussee}(t,n,k)\) pour \(k \in \range{0}{i}\).

Ainsi, en sortie de boucle, on a \(I(m,n-1)\) vérifié, et comme \(\texttt{poussee}(t,n,n-1) = 0 \le m\), \(m\) est plus grand que toutes les valeurs \(\texttt{poussee}(t,n,k)\).

De plus, \(m\) vaut toujours \(0\) ou l'une des valeurs \(\texttt{poussee}(t,n,k)\) : comme \(0 = \texttt{poussee}(t,n,n-1)\), \(m\) est une valeur atteinte, c'est donc bien le maximum.

Initialiser le maximum courant pour \(i = 0\) ou avec une valeur par défaut ?

Ici, on a fait le choix de l'initialiser à 0 car on sait que la poussée est dans \(\N\). Mais quand on est dans \(\Z\), comme c'est non minoré, il n'y a pas de bonne valeur pour initialiser, et dans ce cas, on place la valeur pour le premier indice comme valeur initiale.

Par contre, cela complique la preuve de correction, donc, quand on peut l'éviter, comme ici, on se contente d'initialiser avec un minimum absolu.

Question 10

Justifiez rapidement que si le tableau comporte \(n\) valeurs, alors la fonction précédente effectue de l'ordre de \(n^2\) opérations élémentaires (affectations, accès mémoire, opérations arithmétiques ou de comparaison).

Corrigé

La fonction poussee effectue une boucle d'au plus \(n-i\) itérations effectuant chacune des opérations élémentaires. Ainsi, chaque appel fait au maximum de l'ordre de \(n\) opérations élémentaires. Comme plus_grande_poussee effectue \(n-1\) appels à poussee on a de l'ordre \(n^2\) opérations élémentaires.

Plutôt que la vitesse instantanée, on va s'intéresser maintenant à la vitesse moyenne sur une suite de mesures, ce qui revient à s'intéresser aux sommes de vitesses. On parle de largeur de fenêtre pour le nombre de mesures que l'on considère.

Ainsi, sur l'exemple précédent et avec une largeur de fenêtre de \(3\), la première somme vaut \(199+200+208 =607\) et la seconde \(618\). Il y avait 10 valeurs dans cet exemple, mais avec une fenêtre de largeur 3, on ne peut calculer que 8 sommes, on obtient ainsi la suite de sommes suivantes :

\[607\quad 618 \quad 618 \quad 617 \quad 647 \quad 717 \quad 769 \quad 792\]

On peut alors considérer de même les accélérations entre ces sommes, moments où la somme augmente strictement. Pour l'exemple on a donc :

\[607\nearrow 618 = 618 \searrow 617 \nearrow 647 \nearrow 717 \nearrow 769 \nearrow 792\]

Question 11

Écrire une fonction de prototype

int accelerations_fenetre(int v[], int n, int k);

qui prend en entrée un tableau de vitesses donné par \(v\) et \(n\) ainsi qu'une largeur de fenêtre \(k\) et renvoie le nombre d'accélérations associé.

Exemple : pour \(k = 3\) et les vitesses de l'exemple précédent, votre fonction renverra la valeur 5.

Indication : il n'y a pas besoin de stocker les sommes de fenêtre dans un tableau, on peut tout faire uniquement avec un nombre fini de variables locales entières.

Corrigé 
int accelerations_fenetre(int v[], int n, int k) {
    if (k+1 > n) // pas de fenetres
        return 0;
    int s = 0;
    for(int i = 0; i < k; i++) {
        s = s + v[i];
    }
    int accel = 0;
    for(int j = 0; j < n-k; j++) {
        int s2 = s - v[j] + v[j+k];
        if(s2 > s) {
            accel += 1;
        }
        s = s2;
    }
    return accel;
}

Question 12

Prouvez soigneusement la correction de votre fonction.

Corrigé

Il est facile de se tromper d'un cran dans la fonction précédente. Il y a un terme consacré pour ces problèmes : off by one. Ici, faire la preuve de correction permet d'être certain de ne pas s'être trompé.

La fonction est directement correcte quand il y a 0 ou 1 fenêtre uniquement, car on renvoie 0 et qu'il y a bien 0 accélération possible.

On remarque rapidement que la structure du compte est la même que dans la fonction accelerations donc, il suffit de vérifier que s contient bien la somme de la fenêtre.

On suppose assez rapidement que la valeur initiale est \(s = \sum_{i=0}^{k-1} v[i]\).

On va ainsi montrer que la propriété \(I(j) \equiv s = \sum_{i=j}^{j+k-1} v[i]\) est un invariant.

Avant la boucle, \(j = 0\) et on a supposé \(I(0)\). Si en début d'itération, on a \(I(j)\), alors \(s = \sum_{i=j}^{j+k-1} v[i]\) donc \(s2 = s - v[j] + v[j+k] = \sum_{i=j+1}^{j+k} v[i]\) et ainsi la valeur de \(s\) en fin d'itération vérifie bien \(I(j+1)\).

En sortie de boucle, on a \(I(n-k)\) vérifié donc \(s = \sum_{i=n-k}^{n-1} v[i]\) est la dernière somme de fenêtre considérée et c'est bien la dernière fenêtre.