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.