L'activité de l'informaticien est l'écriture de la programmation sur un ordinateur. Un ordinateur est un acteur capable d'enchaîner des actions par rapport à un modèle donné (programme). Plus généralement, le problème de la programmation est de décrire le comportement d'un acteur. C'est ce que l'on appelle un algorithme (description du comportement face à une situation donnée).

Exemple :

Le joueur (acteur) entre dans une pièce (situation)
La créature (acteur) attaque le joueur (situation)

 L'écriture d'algorithmes requiert la connaissance de l'acteur et la définition d'un langage algorithmique.





 Il est nécessaire de connaître :

• les objets manipulés, par exemple pour l'acteur joueur nous pouvons imaginer : armes, clés, munitions ...
• l'état de ces objets : l'arme est elle chargée ? combien de munitions ? ...
• les actions élémentaires (ce que sait faire l'acteur) : se déplacer, utiliser une clé, charger une arme, tirer ...

 Un langage est définit par sa syntaxe (forme de la grammaire qui traite de l'arrangement des mots) et sa sémantique (forme de la grammaire qui traite de la signification des mots).

 Le langage algorithmique permet de définir des schémas d'ordonnancement des actions. Il existe trois schémas (appelés aussi structures de contrôle) :

• séquence
• sélection (ou choix)
• répétition

 En pratique, l'algorithme s'écrit au moyen des actions de l'acteur et des trois structures de contrôle.




 La syntaxe d'une action élémentaire est la suivante : VERBE + COMPLEMENT (ex: recharger l'arme, utiliser la clé ...)




 Il existe deux formes de condition :

• Condition simple (une seule interrogation)
• Condition composée (plusieurs interrogations) qui s'écrit en utilisant les opérateurs : NON (négation), ET (et logique), OU (ou logique)

Exemple :

condition simple : arme chargée ? porte ouverte ?
condition composée : NON porte verrouillée, (arme chargée) OU (il reste des munitions), (NON arme chargée) ET (plus de munitions)

 Une séquence est une suite conditionnelle d'actions. Sa syntaxe est la suivante :

action 1; action 2; ... action i; où action i est une action élémentaire de l'acteur ... action n;

 Le symbole ';' est un élément de la syntaxe qui représente un terminateur d'action. Intuitivement nous comprendrons que l'action i se déroule après l'action i-1 et avant l'action i+1. Parfois, l'ordre des actions peut s'avérer important :

Exemple : le joueur  Ramasser les munitions;  Charger l'arme;  Tirer;

 Une action est réalisée en fonction de la valeur d'une condition. Sa syntaxe est la suivante :

SI condition ALORS  action 1; SINON où action 1 et 2 sont des actions de l'acteur  action 2; FIN SI;

 Deux cas peuvent se présenter :

- Si la condition est vérifiée (valeur de condition = VRAI), l'action 1 est réalisée mais pas l'action 2
- Si la condition n'est pas vérifiée (valeur condition = FAUX), l'action 2 est réalisée mais pas l'action 1

Exemple :

SI l'arme est chargée ALORS  tirer sur l'ennemi; SINON  fuir; FIN SI;

 Nous avons un cas particulier pour lequel il peut ne pas y avoir d'action 2, il s'agit alors d'une sélection réduite. Si la condition est vérifiée, l'action est exécutée, sinon il ne se passe rien.

SI condition ALORS  action; FIN SI;

 Une action est répétée tant qu'une condition reste vérifiée :

TANT QUE condition FAIRE  action; FIN TANT QUE;

 Le déroulement de la répétition est le suivant :

1. Évaluation de la valeur de la condition
2. Si la condition est vérifiée, exécution de l'action (sinon, la répétition est terminée)
3. Après l'exécution de l'action, retour à l'évaluation de la condition (retour en 1)

Exemple :

TANT QUE il reste des munitions FAIRE  Tirer sur l'ennemi; FIN TANT QUE;

 Le nombre de munitions étant connu à priori, la boucle se termine car l'action (tirer sur l'ennemi) diminue de 1 le nombre de munitions. Attention si l'arme est défectueuse, la répétition est infinie (l'action tirer sur l'ennemi n'influence plus la valeur de la condition). Avec une répétition, l'action peut être exécutée : 0 fois, 1 fois, n fois ou à l'infini. Pour s'assurer que la répétition n'est pas infinie, il faut que l'action modifie la valeur de la condition.





 Nous avons vu jusqu'à présent qu'une action = une action élémentaire. Maintenant nous allons voir qu'une action peut correspondre à une action composée (séquence, sélection et répétition) :

SI condition ALORS  Action 1; (action composée) SINON  Action 2; (action composée) FIN SI; Ce qui peut s'écrire sous une forme plus détaillée : SI condition ALORS  Action 1.1;  Action 1.2; SINON  TANT QUE condition 1 FAIRE  SI condition 2 ALORS  Action 2.1;  FIN SI;  Action 2.2;  FIN TANT QUE; FIN SI;

Exemple :

Acteur joueur  SI il y a un objet à prendre ALORS  Prendre l'objet; (action composée)  FIN SI; On remplace "prendre l'objet" par :  TANT QUE l'objet est trop loin FAIRE  Avancer vers l'objet;  FIN TANT QUE;  Ramasser l'objet; En combinant les deux :  SI il y a un objet à prendre ALORS  TANT QUE l'objet est trop loin FAIRE  Avancer vers l'objet;  FIN TANT QUE;  Ramasser l'objet;  FIN SI;

Attention à ne pas écrire :  SI il y a un objet à prendre ALORS  TANT QUE l'objet est trop loin FAIRE  Avancer vers l'objet;  FIN TANT QUE;  FIN SI;  Ramasser l'objet; L'action "ramasser l'objet" sera toujours exécutée (car dans une séquence) : s'il n'y a pas d'objet comment pourrait-on le ramasser !?

 Un algorithme transforme les états d'un problème : au départ, avant l'algorithme, on a un état initial. Après exécution on obtient un état final. Il faut donc écrire la spécification des états initial et final de l'algorithme.

Exemple :

• Le véhicule du joueur a besoin d'être amélioré. Quelles améliorations ? définir précisément les améliorations...
• Acteur "personnage architecte" : le joueur souhaite construire une muraille. Le problème de l'architecte est de savoir quel type de muraille ? quelle matière (bois, pierre) ? quelle longueur ?

La réponse à la question QUOI est appelée spécification. On écrira par exemple :

Etat initial : construire une muraille de pierre autour des bâtiments du joueur
Etat final : la muraille encercle les bâtiments du joueur

L'algorithme doit transformer l'état initial en état final.

 L'écriture des algorithmes par raffinages successifs est le développement d'une action complexe en termes d'actions plus élémentaires. Le développement doit être une séquence, une sélection ou une répétition. On répète ce processus de raffinage jusqu'à atteindre le niveau des actions élémentaires de l'acteur (actions non décomposables). Chaque niveau montre un niveau de détail de l'algorithme. D'où la nécessité de faire le plan de l'algorithme.

 Schéma général de constitution d'un algorithme :

Travail de conception (réflexion)	1er niveau de raffinage (plan général de l'algorithme) 2e niveau de raffinage Dernier niveau de raffinage (algorithme détaillé)
Travail de traduction (codage)	PROGRAMME

• Raisonnement de façon descendante : partir du problème pour arriver à la solution
• Documenter l'algorithme au fur et à mesure de son écriture. En particulier, les commentaires doivent être conçus en même temps que le programme. Les commentaires dans un programme sont en fait la trace du raffinage
• Séparation des difficultés : une seule difficulté doit être étudiée à la fois
• Valider l'algorithme au fur et à mesure de sa construction (déroulement manuel de l'algorithme à chaque niveau de raffinage) et si un problème apparaît, remettre en cause le niveau précédent
• Séparation claire entre algorithme et programmation

 Inconvénients :

• Fixer dés le départ certains choix algorithmiques. Si les premiers niveaux sont faux, le reste l'est aussi (ex : écriture d'une séquence à la place d'une répétition)
• Limitation de la méthode pour des applications de grande taille (conception de logiciel)

Exemple : Algorithme de remise à l'heure d'un réveil


 Soit un réveil possédant 3 boutons A, B et C, et deux registres (zone mémoire contenant des valeurs) notés H et M mémorisant respectivement les heures et les minutes du réveil.

 Notice de l'appareil :

• Le bouton A permet de mettre le réveil dans le mode Remise à l'heure
• Une pression sur B permet de modifier les minutes
• Chaque pression sur le bouton C ajoute 1 unité aux minutes (registre M) modulo 60 (sans modifier H)
• Le bouton B stoppe ce processus et autorise la modification de la partie H
• Le bouton C modifie alors les heures (registre H) module 24 (sans modifier la partie M)
• Une pression sur A permet de quitter le mode remise à l'heure. Le réveil est alors en fonctionnement normal.
• L'heure de référence est donnée par une horloge externe et s'obtiendra par l'action ENTRER(HR,MR) où HR désigne l'heure de référence et MR les minutes.

 Problème : écrire un algorithme de remise à l'heure du réveil par un acteur (l'utilisateur) dont les seules actions élémentaires sont :

• ENTER(HR,MR) : Entre l'heure et les minutes de référence
• APPUYER A : Appuyer sur le bouton A
• APPUYER B : Appuyer sur le bouton B
• APPUYER C : Appuyer sur le bouton C

 On suppose que l'acteur sait enchaîner les actions élémentaires en séquences, sélections et répétitions. Il sait comparer les valeurs des registres HR et MR aux registres H et M (grâce aux opérateurs =, /=, >, <, >=, <=). On néglige le temps de manipulation de remise à l'heure.

 Etat initial : réveil en état de marche et heure quelconque
 Etat final : réveil en état de marche et mis à l'heure

Algorithme // Mettre à l'heure le réveil  Mettre le réveil en mode mise à l'heure;  Lire les heures et les minutes de référence;  Modifier les minutes;  Modifier les heures;  Mettre le réveil en mode fonctionnement normal;

Pour les premiers niveaux de raffinage, ne pas écrire l'algorithme dans le langage de l'acteur mais en pseudo-français.

 Dans cet exemple, les actions complexes à détailler pour le second niveau de raffinage sont : "Modifier les minutes" et "Modifier les heures" :

// Mettre à l'heure le réveil  Mettre le réveil en mode mise à l'heure;  Lire les heures et les minutes de référence;  // Modifier les minutes  TANT QUE les minutes ne sont pas à jour FAIRE  Ajouter 1 minute aux minutes;  FIN TANT QUE;  // Modifier les heures  TANT QUE les heures ne sont pas à jour FAIRE  Ajouter 1 heure aux heures;  FIN TANT QUE;  Mettre le réveil en mode fonctionnement normal;

 La phase algorithmique est terminée. Nous pouvons maintenant écrire le programme car les actions de l'algorithme se traduisent simplement dans le langage de l'acteur :

// Mettre à l'heure le réveil  // Mettre le réveil en mode mise à l'heure  APPUYER A;  // Lire les heures et les minutes de référence  ENTRER (HR, MR);  // Modifier les minutes  APPUYER B;  TANT QUE (M /= MR) FAIRE Le symbole /= correspond à "différent"  // Ajouter 1 minute aux minutes  APPUYER C;  FIN TANT QUE;  // Modifier les heures  APPUYER B;  TANT QUE (H /= HR) FAIRE  // Ajouter 1 heure aux heures  APPUYER C;  FIN TANT QUE;  // Mettre le réveil en mode fonctionnement normal  APPUYER A;

Retour en haut de page