ED n·6-- Algorithmique et programmation



Objectifs
 

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

Question 2


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

Question 2 Question 3 Question 4 Question 5