|
|
Exercice 1
Enoncé
Tri par recherche séquentielle d'un tableau T(a..b) d'entiers : on suppose qu'une partie du tableau T(a..i-1) est triée. L'idée est de parcourir le tableau T(i..b) de manière séquentielle à la recherche du plus petit élément (disons T(j)). Il suffit ensuite de permuter T(i) avec T(j) et de recommencer la recherche sur le tableau T(i+1..b).
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 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.
Question 1
Exercice 2
On souhaite inverser un tableau de valeurs boursières. Une valeur boursière est caractérisée par sa dénomination (un sigle de 5 caractères) et sa cotation. Le tableau est préalablement trié selon l'ordre croissant des cotations, on veut le ranger selon l'ordre décroissant.
Question 1