Elaboration d’algorithmes itératifs

Support de cours les algorithmes de la brochure avec Excel et VBA, tutoriel & guide de travaux pratiques algorithmes en pdf.

La démarche

On sait que ce qui caractérise une itération est son invariant. Trouver l’invariant d’une boucle n’est pas toujours chose aisée. L’idée maîtresse de la méthode est de construire cet invariant parallèlement à l’élaboration de l’algorithme et non pas de concevoir l’algorithme itératif pour ensuite en rechercher l’invariant.
Etant donné un problème dont on soupçonne qu’il a une solution itérative, on va s’efforcer de mettre en évidence les étapes suivantes:
[1] Proposer une situation générale décrivant le problème posé (hypothèse de récurrence). C’est cette étape qui est peut être la plus délicate car elle exige de faire preuve d’imagination.
On peut toujours supposer que l’algorithme (on le cherche !) a commencé à «travailler» pour résoudre le problème posé et qu’on l’arrête avant qu’il ait fini: On essaye alors de décrire, de manière très précise, une situation dans laquelle les données qu’il manipule puissent se trouver.
Il est possible, comme on le verra sur des exemples, d’imaginer plusieurs situations générales.
[2] Chercher la condition d’arrêt. A partir de la situation imaginée en [1], on doit formuler la condition qui permet d’affirmer que l’algorithme a terminé son travail. La situation dans laquelle il se trouve alors, est appelée situation finale.
[3] Se «rapprocher» de la situation finale, tout en faisant le nécessaire pour conserver une situation générale analogue à celle choisie en [1].
[4] Initialiser les variables introduites dans la description de la situation générale pour que celle-ci soit vraie au départ ( c’est à dire avant que l’algorithme ait commencé à travailler).
Une fois cette étude conduite l’algorithme aura la structure suivante :
Cette façon de procéder montre comment on prouve la validité de l’algorithme au fur et à mesure de son élaboration.
En effet la situation générale choisie en [1] est en fait l’invariant qui caractérise la boucle tantque.
Cette situation est satisfaite au départ à cause de l’étape [4], elle reste vraie à chaque itération (étape [3]). Ainsi lorsque la condition d’arrêt est atteinte cette situation nous permet d’affirmer que le problème est résolu.
C’est également en analysant l’étape [3] qu’on peut prouver la terminaison de l’algorithme.

Exemples

1) Tri d’un tableau par insertion.
Le premier exemple consiste à établir un algorithme permettant de classer suivant l’ordre croissant un tableau de n nombres.
Essayons de trouver une situation générale décrivant le problème posé.
Pour cela supposons que l’on arrête un algorithme de tri avant que tout le tableau soit classé, on peut imaginer qu’il a commencé à mettre de l’ordre et que par exemple T[1..i] est classé. La notation T[1..i] désigne les i premières composantes du tableau T.
Par hypothèse de récurrence on sait que le tableau est classé entre 1 et i-1, on suppose qu’un algorithme a commencé à travailler et l’élément qui était initialement en i s’est «rapproché» de sa place par des échanges successifs et se trouve en j lorsqu’on a interrompu l’algorithme. Sur le schéma qui suit, l’élément qui était initialement en i est matérialisé par une étoile.
La nuance réside dans le fait que la partie triée est T[1..i-1], et non T[1..i] comme dans la première version. Cette situation est tout aussi acceptable que la précédente. En raisonnant avec celle-ci on obtient un algorithme, certes voisin du précédent, mais comportant plusieurs modifications.
La condition d’arrêt devient i>n, le corps de l’itération consiste à «amener l’élément qui se trouve en i à sa place dans T[1..i-1], puis vient l’incrémentation de i, l’initialisation devient i:=2.
Comme on peut le constater la situation choisie guide totalement l’écriture de l’algorithme.
2) Tri d’un tableau par sélection.
Comme il a déjà été dit et constaté la situation générale n’est pas unique. Par exemple, toujours pour le même problème, on peut faire une hypothèse plus forte sur la partie classée en ajoutant qu’elle est aussi définitivement en place.
Ce qui se traduit formellement par une conjonction de formules logiques:
La première formule indique que le tableau est classé jusqu’à i-1, la seconde formule que cette partie est définitivement en place.

……….