| ED
n·4 Algorithmique
et Programmation-------- |
Objectifs
Rappel
Il est très courant de partir d'une
spécification
de problème sous forme de propriétés de la
fonction
à calculer. L'outil mathématique le plus précieux
pour construire l'algorithme est, dans ce cas, le raisonnement par
récurrence.
L'ensemble des propriétés que la
fonction à calculer doit satisfaire est traduit par une hypothèse
de récurrence.
On construit ainsi les programmes de
manière
raisonnée et systématique.
On dit que P est une
propriété
récurrente sur
N si, étant vérifiée
pour un entier a, elle est vérifiée pour tout
entier
supérieur ou égal à a.
La méthode se décompose en quatre étapes:
Première étape
Déterminer une hypothèse de récurrence. Elle formalise l'idée choisie pour construire la solution du problème donné.
Seconde étape
Dégager le sous ensemble ordonné de N à l'intérieur duquel P doit être vérifiée. Cela revient à établir la condition d'arrêt de l'itération.
Troisième étape
Démontrer que si P (i) est
vérifiée
(i appartenant au sous-ensemble ordonné), alors P (suc(i)) est
aussi vérifiée. Cette troisième étape
revient
à construire le corps de boucle. On procède en
fait
ainsi:
1- se rapprocher de la solution
2- retrouver l'hypothèse de
récurrence.
Quatrième étape
Le raisonnement se termine par la preuve que P(1) est vérifiée. Cette quatrième étape correspond à l'initialisation.
En cas de succès du raisonnement, l'hypothèse de récurrence devient l'invariant de l'algorithme. Cet invariant se transforme en un commentaire informatif du programme. Les preuves de correction d'un programme sont facilitées par sa présence.
Exercice 1 : Compaction
d'un
tableau
Un tableau d'entiers contient de nombreuses
occurrences
de 0 et quelques valeurs non nulles. On désire modifier le
tableau
de telle sorte que tous les éléments non nuls soient
regroupés
au début du tableau.
Question 1
Construire l'algorithme en suivant la méthode décrite ci-dessus.
Question 2
Coder l'algorithme.