Abstract
Cet article est une présentation de ce qu'on appelle les algorithmes itératifs en Informatique. Il est destiné aux étudiants de niveau Licence ou Master en Informatique, notamment à ceux préparant un CAPES d’informatique, comme aux enseignants du secondaire qui souhaitent accompagner l’apparition de la discipline Informatique au lycée.
— En guise de préambule, une version formelle de l'algorithme de la multiplication Russe est présentée avec une trace d'exécution.
— La deuxième section définit justement les instructions de base de l'algorithmique pour nos machines.
— La troisième section s'intéresse aux concepts de variants et d'invariants permettant de prouver qu'un algorihtme fonctionne conformément à ses spécifications.
— La quatrième section s'intéresse aux cas des algorithmes utilisant des instructions ou des fonctions qui peuvent avoir des résultats différents pour une même donnée (tout en respectant leur spécification), ce qu'on appelle algorithmes non déterministes.
Il est suivi d'une brève conclusion et d'une annexe contenant quelques implémentations en Python.