[TP09] La règle d'Horner - Invariant - [LINFO1103] Introduction à l'algorithmique

Le pseudocode suivant propose une implémentation de la règle d'Horner afin de calculer la valeur d'un polynôme en un point. On vous demande de prouver la correction de l'algorithme en :

traduisant dans un premier temps la boucle for en boucle while,
puis en mettant en oeuvre les différentes étapes de preuve par invariant.

https://inginious.info.ucl.ac.be/course/LINFO1103/S09_5_1_horner/algo.png

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Internal error {} has not a valid extension. {} is too heavy.

Question 1: Définir l'invariant

Pour trouver l'invariant :

Commencez par analyser un exemple simple.
Déterminez l'état des variables après l'initialisation.
Déterminez l'état des variables après chaque itération de la boucle while.

Qu'observez-vous à la fin de chaque itération ?

Sélectionnez, parmi les propositions suivantes, celle(s) qui est (sont) respectée(s) à la fin de chaque itération.

Pour rappel, lorsque l'on transforme une boucle for en boucle while, la dernière instruction dans cette boucle est la mise à jour de la variable de boucle (ici i). Nous nous intéressons donc à l'état de l'algorithme juste après cette mise à jour et donc avant de revenir à l'instruction while.

\(valeur = \sum_{j=0}^{i-1} P[n-1-j]\times j^{n-1-j}\)

La variable valeur contient la valeur du polynôme de degré n-i évalué au point x.

\(valeur = \sum_{j=i}^{n} P[j]\times x^{j-i}\)

La variable valeur contient la valeur du polynôme de degré n évalué au point x.

\(valeur = \sum_{j=0}^{n-1} P[j]\times j\)

\(valeur = \sum_{j=i+1}^{n} P[j]\times x^{j-(i+1)}\)

Question 2: Initialisation

L'invariant est-il vérifié après l'initialisation ?

Pour rappel, lorsque l'on transforme une boucle for en boucle while, l'initialisation concerne aussi celle de la variable de boucle (i = ...). Donc, l'initialisation se réfère à toutes les instructions effectuées avant de tester pour la première fois la condition dans l'instruction while.

Sélectionnez, parmi les propositions suivantes, celle qui répond à la question précédente.

L'invariant est vérifié car la somme porte sur un élément seulement

L'invariant est vérifié car la variable x est multipliée par zéro directement après l'initialisation

L'invariant est vérifié à condition que le dernier élément du tableau P soit différent de zéro

L'invariant est vérifié car le tableau P contient n+1 éléments

L'invariant est vérifié car une somme portant sur un ensemble vide est toujours égale à 0

Question 3: Itération

L'invariant est-il conservé par l'exécution d'une itération ?

Sélectionnez, parmi les propositions suivantes, celle(s) qui est (sont) correcte(s).

Par hypothèse, au début de la boucle, l'invariant est vérifié. Cette valeur est mise à jour (première instruction dans la boucle) : \(valeur = \sum_{j=i+1}^{n} P[j]\times x^{j-i}\). Ensuite, cette valeur est à nouveau mise à jour (deuxième instruction dans la boucle): \(valeur = \sum_{j=i}^{n} P[j]\times x^{j-i}\). Enfin, la dernière instruction de la boucle est de décrémenter la variable i d'une unité. On retrouve donc exactement l'invariant spécifié plus haut.

Par hypothèse, au début de la boucle, l'invariant est vérifié. Cette valeur est mise à jour (première instruction de la boucle) : \(valeur = \sum_{j=i+1}^{n} P[j]\times x^{j-(i+2)}\). Ensuite, cette valeur est à nouveau mise à jour (deuxième instruction de la boucle) : \(valeur = \sum_{j=i+2}^{n} P[j]\times x^{j-(i+2)}\). La dernière instruction de la boucle est de décrémenter la variable i d'une unité. On retrouve donc exactement l'invariant spécifié plus haut.

Par hypothèse, au début de la boucle, l'invariant est vérifié. Cette valeur est mise à jour (première instruction de la boucle) : \(valeur = \sum_{j=i+2}^{n} P[j]\times x^{j-(i+1)}\). Ensuite, cette valeur est à nouveau mise à jour (deuxième instruction de la boucle) : \(valeur = \sum_{j=i+2}^{n} P[j]\times x^{j-(i+2)}\). La dernière instruction de la boucle est de décrémenter la variable i d'une unité. On retrouve donc exactement l'invariant spécifié plus haut.

Par hypothèse, au début de la boucle, l'invariant est vérifié. Cette valeur est mise à jour (première instruction de la boucle) : \(valeur = \sum_{j=i}^{n} P[j]\times x^{j-i}\). Ensuite, cette valeur est à nouveau mise à jour (deuxième instruction de la boucle): \(valeur = \sum_{j=i+1}^{n} P[j]\times x^{j-(i+1)}\). La dernière instruction de la boucle est de décrémenter la variable i d'une unité. On retrouve donc exactement l'invariant spécifié plus haut.

Par hypothèse, au début de la boucle, l'invariant est vérifié. Cette valeur est mise à jour (première instruction de la boucle) : \(valeur = \sum_{j=i}^{n} P[j]\times x^{j-(i+1)}\). Ensuite, cette valeur est à nouveau mise à jour (deuxième instruction de la boucle): \(valeur = \sum_{j=i}^{n} P[j]\times x^{j-i}\). La dernière instruction de la boucle est de décrémenter la variable i d'une unité. On retrouve donc exactement l'invariant spécifié plus haut.

Question 4: Condition de terminaison

Lorsque la condition de terminaison est atteinte, l'invariant définit la post-condition.

Sélectionnez, parmi les propositions suivantes, celle qui correspond à la condition d'arrêt de la boucle.

i \(= n\)

i \(= -1\)

i \(= 0\)

p(x) \(\neq 0\)

i \(= \text{len}(P)\)

La variable valeur est égale à la valeur du polynôme de degré n+1 évalué en le point x

Question 5: Preuve

Si l'on utilise la condition d'arrêt pour mettre à jour l'invariant, la correction de la fonction est prouvée.

Sélectionnez, parmi les propositions suivantes, celle(s) qui prouve(nt) que la fonction est correcte.

Étant donné l'invariant et la condition d'arrêt, la variable valeur est égale à la valeur du polynôme de degré n, avec les coefficients P, évalué en un point x

Étant donné l'invariant et la condition d'arrêt, l'algorithme ne peut pas réaliser de boucle infinie

Étant donné l'invariant et la condition d'arrêt, valeur \(= \sum_{j = 0}^{n} P[j] \times x^j\)

Étant donné l'invariant et la condition d'arrêt, la variable valeur contient la somme de tous les éléments de P multipliés par x

Author(s)	Vincent Branders, Pierre Dupont
Deadline	22/04/2026 14:00:00
Submission limit	No limitation

Information

Sign in