Blog ENI : Toute la veille numérique !
-25€ dès 75€ sur les livres en ligne, vidéos... avec le code FUSEE25. J'en profite !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique
  3. Itération
Extrait - Algorithmique Raisonner pour concevoir (3e édition)
Extraits du livre
Algorithmique Raisonner pour concevoir (3e édition) Revenir à la page d'achat du livre

Itération

Introduction

Un traitement itératif est un traitement fait ou répété plusieurs fois selon le « Petit Larousse ». Ce terme est synonyme de fréquentatif qui se dit d’un verbe qui marque une action fréquemment répétée, comme clignoter (...). Dans ce chapitre, nous construisons des algorithmes de transformation au cours desquels le système passe de l’état initial à l’état final en traversant une succession finie d’états caractérisés par une propriété commune. Nous montrons comment construire ce type d’algorithmes d’une façon raisonnée et systématique.

La section « Premiers exemples de construction d’itérations » introduit la méthode par quelques exemples simples. La section « Itérer dans un tableau » étudie différentes situations dans lesquelles l’itération est utilisée sur les composantes d’un tableau. La section « Algorithme ou programme ? » est une discussion justifiant la méthode étudiée dans ce livre et propose des exercices d’application au cours desquels il devient possible de donner des solutions itératives à des exercices parfois déjà résolus précédemment....

Premiers exemples de construction d’itérations

Ces exemples sont simples. Le premier, la construction d’une table de multiplication, est même trivial. C’est qu’il s’agit d’un premier exposé pour introduire les raisonnements permettant de construire une itération : il faut éviter de multiplier les difficultés. C’est pourquoi on commence par se concentrer sur les étapes de la construction et du raisonnement sur un problème élémentaire. Le second exemple explore un tableau dont les données sont des instances d’un type structuré. La section se termine ensuite par quelques exercices d’application de même nature.

1. La table de multiplication

a. Le problème

On veut préparer un algorithme qui remplit un tableau avec les résultats de la table de multiplication par un entier n positif ou nul. Il s’agit de préparer une solution qui présente les étapes du calcul des éléments du tableau. Ce tableau est limité à 11 cases, numérotées de 0 à 10, mais il pourrait comporter bien plus de cases, sans que l’algorithme proposé ne s’en trouve modifié. Voyons cela. 

Le tableau des résultats à obtenir est :

... 
constante 
    MIN : ENTIERimages/flechegauche.PNG 0  # Numéro de la première case du tableau 
    MAX : ENTIERimages/flechegauche.PNG 10 # Numéro de la dernière case 
 variable  
    table : TABLEAU[ENTIER][MIN, MAX]  
... 

Ces instructions déclarent un tableau appelé table qui contiendra MAX -  MIN + 1 entiers, entre les cases de numéros MIN et MAX. Pour remplir table avec la table de multiplication par 4, par exemple, nous écrirons :

... ...

Explorer un tableau

Un CLIENT est une PERSONNE identifiée par un numéro entier. Une PERSONNE possède une ADRESSE et une IDENTITÉ. Le diagramme ci-dessous représente ces entités et leurs associations mutuelles.

images/05DP1N.png

Remarquez la nature particulière de l’association entre CLIENT et PERSONNE. On indique ainsi qu’une instance de CLIENT est composée d’une et d’une seule instance de PERSONNE. En toute rigueur, il faudrait utiliser ici l’association d’héritage, mais nous ne sommes pas en algorithmique objet. De plus, la couleur du losange du côté CLIENT indique que, lorsque le client disparaît, la personne disparaît avec lui. La discussion sur les différentes associations et leur signification a déjà été abordée au chapitre « Structures élémentaires », dans la solution de l’exercice n°11, développée dans les éléments en téléchargement disponibles depuis la page Informations générales.

Le type CLIENT est défini par la déclaration :

type 
    CLIENT 
structure 
    numéro : ENTIER 
    p      : PERSONNE 
fin CLIENT 

La déclaration du type PERSONNE est de même :

type 
    PERSONNE 
structure 
    identité : IDENTITÉ 
    âge      : ENTIER 
    adresse  : ADRESSE 
fin PERSONNE 

Enfin, le type ADRESSE a déjà été utilisé au chapitre « Structures élémentaires ».

Un tableau, qui peut contenir jusqu’à 1000 CLIENTS a été déclaré et initialisé :

constante  
    MAX_CLIENTS : ENTIERimages/flechegauche.PNG 1000  
    MIN_CLIENTS : ENTIERimages/flechegauche.PNG 1  
    VIDE   : ENTIERimages/flechegauche.PNG ??? # Numéro d'un client qui n'existe pas 
    EFFACÉ : ENTIERimages/flechegauche.PNG ??? # Numéro d'un client effacé 
...  
variable  
    clients : TABLEAU[CLIENT][MIN_CLIENTS, MAX_CLIENTS]  
... 

Actuellement, toutes les cases n’ont pas nécessairement été initialisées...

Algorithme ou programme ?

Nous en savons suffisamment à présent pour revenir sur quelques notions qui ont déjà été abordées dans les chapitres « Qu’est-ce que l’algorithmique ? » et « Programmes directs ». Qu’est-ce qu’un algorithme ? Qu’est-ce qui le distingue d’un programme destiné à un ordinateur ? Construire un programme et définir un algorithme sont-elles des activités distinctes, chacune développant ses propres méthodes, ou ne constituent-elles que les « deux faces de la même médaille » ? Cette section ne cherche pas à répondre de façon définitive. On y expose seulement quelques idées simples qui complètent la vision partielle des chapitres précédents. La première partie développe un exemple recopié d’un livre qui traite d’algorithmique. La seconde partie expose l’une des solutions préconisées pour le problème.

1. Un exemple édifiant

On a initialisé un tableau de nom marques de 100 composantes réelles positives avec n nombres, 0 ≤ n ≤ 100, dont on veut déterminer la moyenne arithmétique. Dans un livre que je n’aurai pas la cruauté de citer, je lis la solution suivante :

VAR 
    marques  : TABLEAU[1 .. 100] de RÉEL ; 
    nombres  : ENTIER ; 
    somme, i : ENTIER ; 
    moyenne  : RÉEL   ; 
DÉBUT 
    (* Remplir le tableau *) 
    i := 1 ; 
    écrire("Donner un entier : ") ; 
    lire(marque[i]) ; 
    TANT QUE(marques[i] < > - 1) 
      DÉBUT   
        i := i + 1 ; 
        écrire("Quel est l'entier suivant ? ") ; 
        lire(marques[i]) ; 
      FIN ; 
    (* Calculer la moyenne *) 
 ...

Exercices d’application

Cette section propose des exercices d’application variés. Le premier exercice étend l’étude commencée au chapitre « Structures élémentaires ».

Exercice 6 : Historique sur un compte courant

On veut conserver l’histoire des mouvements mensuels sur un compte courant.

1. Modifier le type COMPTE défini au chapitre « Structures élémentaires » pour garder la trace des mouvements sur un compte pendant un mois.

2. Établir le solde en fin de mois d’un compte donné.

Le solde n’est plus un attribut du compte. Il est obtenu en parcourant l’historique mensuel et l’historique annuel qui enregistre le montant du solde du compte pour chaque mois.

3. Refaire les définitions précédentes.

Un tableau clients contient les comptes courants d’un ensemble de clients.

4. Déterminer les clients pour lesquels la moyenne des montants des mouvements est supérieure à une somme donnée.

L’exercice suivant sera complètement résolu au chapitre « Édition d’un nombre ».

Exercice 7 : Édition d’un entier

1. Écrire un algorithme itératif qui transforme un entier n quelconque en sa représentation dans une base B ≥ 2 quelconque.

Lorsque la base est supérieure à 36, on peut utiliser la représentation des chiffres en utilisant la base dix, mais en séparant chaque chiffre de la représentation du nombre en base B par un séparateur convenu, par exemple un point. C’est ce qui est pratiqué pour noter, par exemple, l’adresse IP d’un hôte sur un réseau en IPv4. Ainsi, par exemple, la représentation en base 256 de 3000, exprimée ici en base dix, s’écrira : 11.184256 = 3000dix.

Cet exercice est entièrement résolu au chapitre « Édition d’un nombre ».

Exercice 8 : Analyse d’une chaîne de caractères

On donne une chaîne de caractères dont différentes parties sont séparées par un caractère SÉPARATEUR particulier. L’exemple ci-dessous représente une telle chaîne, dans laquelle le caractère séparateur est le caractère...

Notes bibliographiques

La méthode de construction d’une itération par étape, toujours les mêmes, comme elle est exposée ici doit beaucoup à [ARS80]. Le livre [ARS77] est de la même veine, mais adopte un point de vue plus mathématique et plus formel. Préciser l’invariant et le variant de contrôle d’une itération sous une forme algorithmique a été systématisé par Bertrand MEYER dont la référence [MEY00], qui traite de conception et programmation objet, est un point d’entrée pour aller plus loin.

Résumé

Ce chapitre a présenté la construction raisonnée d’une itération. Une itération est un traitement répété sur un jeu de données qui évoluent, mais qui restent liées par des conditions strictes. Construire l’itération, c’est énoncer clairement l’hypothèse de récurrence sous-jacente pour en déduire les traitements qui assurent les changements d’état du système, les initialisations qui réalisent l’état initial, la condition de terminaison qui décrit l’état final, l’invariant qui énonce une propriété dont les traitements, dans tous les états du système, assurent la permanence et le variant de contrôle qui est une mesure de la distance à l’état final. Les exemples proposés ont montré comment construire une itération selon ce « modèle ». Ils sont empruntés à différents domaines mais ne font jamais appel à d’autres structures de données que le tableau simple ou la chaîne de caractères.

Les chapitres suivants ne sont que des variations sur le thème de la construction d’une itération et de la spécification d’un algorithme.

Bibliographie

[ARS80] Jacques ARSAC : Premières leçons de programmation ; CEDIC/NATHAN, 1980.

[ARS77] Jacques ARSAC : La construction de programmes structurés ; DUNOD, 1977.

[MEY00] Bertrand MEYER : Conception et programmation orientées objet ; EYROLLES, 2000.