Pseudo code

Source : http://isn.codelab.info/ressources/algorithmique/memo-pseudo-codes/

Algorithmique : écriture en pseudo-codes

Le pseudo-code permet de décrire facilement un algorithme avec un vocabulaire simple et sans connaissance à priori du langage de programmation utilisé pour son [itg-tooltip tooltip-content= »<p>implémentation</p> »]implémentation[/itg-tooltip] machine. Ce travail d’algorithmique peut se faire sans ordinateur, sur une simple feuille de papier. En ayant comme connaissances quelques principes de programmation, comme les structures de boucles et les instructions, vous pouvez échanger en pseudo-code avec une autre personne qui utilise un langage de programmation que vous ne maitrisez pas.

Remarques :

• il n’y a pas de standard (et donc pas de normalisation) pour l’écriture d’un algorithme en pseudo-code mais seulement quelques conventions partagées par un grand nombre !
• pour chaque mot clé, nous donnerons son équivalent en anglais.

 

Structure générale d’un algorithme

Voici la structure générale d’un algorithme :

ALGORITHME //identifiant_algo
  <partie déclarations>
  DEBUT
      <partie instructions>
  FIN

(En anglais : ALGORITHM – BEGIN – END)

Comme de nombreux langages impératifs, il est composé de deux parties distinctes : les déclarations et les instructions.

Nous utiliserons dans ce document la convention typographique suivante :

• mots clés (en gras)
  
• identifiants (en italique)
  
• <élément à développer> (entre crochets)
• {élément facultatif} (entre accolades)
• … pour indiquer que la structure en cours peut être répétée.

Règles d’écriture d’un algorithme

Alphabet et lexique – Les « mots » du langage

Comme pour tout langage, il nous faut tout d’abord définir l’alphabet (les caractères utilisés) et les mots qui nous permettrons de construire des énoncés (ici des instructions par exemple). Deux types de mots seront présents dans l’algorithme : les mots clés, mots prédéfinis dans le langage, et les identifiants, mots construits pour « nommer » des variables, des routines… Pour ces derniers il existe des règles de construction.

Règles de construction des identifiants :

Un identifiant (ou identificateur) est un nom déclaré et valide pour :

• une constante,
• une variable,
• une procédure,
• une fonction,
• l’algorithme principal.

Les noms d’identifiants ne peuvent contenir que des caractères compris dans les intervalles suivants :

• ‘a’..’z’
• ‘A’..’Z’
• ‘0’..’9′

On peut également utiliser le caractère _ (souligné/underscore).

Pour construire un identifiant, il faudra respecter les règles suivantes :

• il ne peut en aucun cas commencer par un chiffre ;
• tout identifiant doit avoir été déclaré avant d’être utilisé ;
• un identifiant doit bien entendu être différent d’un mot clé, ceci pour éviter toute ambiguïté ;
• enfin, pour faciliter l’écriture et la lecture des algorithmes, il est très fortement conseillé d’utiliser des identifiants explicites (par exemple : largeur_image et non xi)

Les mots clés

Les mots clés seront utilisés pour construire les algorithmes, les déclarations et les instructions. Ceux-ci sont prédéfinis dans le langage. Comme pour les identifiants, aucune distinction n’est faite entre les majuscules et les minuscules.

Liste des principaux mots clés du langage :

ALGORITHME	PROCÉDURE	CONSTANTES	VARIABLES	DÉBUT	FIN	FONCTION	SI	ALORS
SINON	POUR	TANT_QUE	JUSQU’À	RÉPÉTER	SELON	AUTREMENT	BOOLÉEN	ENTIER
RÉEL	CARACTÈRE	CHAINE	NON	OU	ET	MOD	DIV	PARAMÈTRES

Les séparateurs – Symboles spéciaux

La structure de l’algorithme (déclarations + instructions) est faite de telle manière qu’il n’y a pas besoin de séparateurs particuliers : les différentes parties se suivent, tout simplement. Tout ce qui est commencé est explicitement fini ! Nous utilisons juste la virgule « , » comme séparateur pour les listes de paramètres dans les appels de routines. Un retour à la ligne est cependant nécessaire avant de commencer toute nouvelle instruction ou déclaration.

Un certain nombre de caractères et de combinaisons de caractères ont une signification spéciale pour le langage algorithmique. En voici la liste :

←

^

.

,

:

{

}

[

]

<=

>=

<>

=

+

–

*

/

(

)

Les commentaires

Il est vivement conseillé d’insérer des commentaires dans son algorithme. Les commentaires ne font pas partie de l’algorithme et n’influent pas sur le déroulement de celui-ci, si ce n’est pour sa compréhension ! Les blocs de commentaires seront délimités par les caractères // :

// un commentaire

La partie déclarations

C’est ici que nous allons déclarer tout ce dont nous avons besoin pour l’algorithme : constantes, variables ainsi que les routines (procédures et fonctions).

    <déclarations des constantes>
    <déclarations des variables>
    <déclarations des routines>

L’ordre des déclarations est important, il ne peut être changé. Nous allons voir ici les déclarations des constantes et des variables (les routines font l’objet de la section Les procédures et fonctions)

Déclaration des constantes

CONSTANTES
  ident_constante = <valeur>
  ...

(En anglais : CONSTANTS)

Une constante ne peut être modifiée dans l’algorithme.

Déclaration des variables

Les variables contiennent les données manipulées par l’algorithme. Lors de la déclaration on doit leur attribuer un type. Celui-ci doit être défini (on applique ici une règle très importante valable partout : on ne peut utiliser que ce qui est déjà connu ! Dès lors, lorsqu’on veut utiliser quelque chose, il faut s’assurer que cela est déjà prédéfini dans le langage ou défini par l’utilisateur.

VARIABLES
  ident_type : ident_variable1, ident_variable2, ...
  ...

(En anglais : VARIABLES)

Chaque ligne contient la liste des variables du type spécifié (on peut pour plus de clarté définir plusieurs listes pour un même type).

Les variables

Les types prédéfinis de variables

Les différents types prédéfinis en langage algorithmique que nous utiliserons sont :

ENTIER	nombres entiers signés	42
RÉEL	nombres flottants signés	0.154
BOOLÉEN	énumération définissant les données vrai et faux	vrai
CARACTÈRE	caractère ANSI sur un octet	‘a’
CHAINE	chaîne de caractères	« lapin »

La déclaration des variables

Déclaration :

• variables simples
  

VARIABLES
     ident_type : ident_variable1, ident_variable2, ...

• variables indicées ou tableaux

Les tableaux permettent d’associer dans une même variable plusieurs données de même type avec un indice allant de l’indice minimum <entier1> à l’indice maximum <entier2>.

VARIABLES ident_type : ident_tableau[,] , ...

Un tableau peut comporter plusieurs dimensions délimitées par un point virgule :

VARIABLES
     ident_type : ident_tableau[<entier12>,<entier12>;<entier21>,<entier22>] , ...

Dans ce dernier exemple , il s’agit d’un tableau à 2 dimensions avec un indice pour les lignes (compris entre <entier11> et <entier12>) et un deuxième indice pour les colonnes (compris entre <entier21> et <entier22>).

Utilisation : l’accès à un élément d’un tableau se fait en indiquant la liste des indices correspondant à chaque dimension.

ident_var[<indice1>;<indice2>; ...]

Les instructions

Les expressions

Une expression représente une succession de calculs ; elle peut faire intervenir des constantes, des variables, des fonctions et des opérateurs. Les expressions sont utilisées dans tout l’algorithme : dans les affectations, en paramètre des routines, dans les structures de contrôles…

Expression : syntaxe

Une expression peut être :

une valeur	42
une variable	x
une constante	C
un appel à une fonction	cos(x)
<expression> opérateurBinaire <expression>	32 + x
opérateurUnaire <expression>	non A

Les opérateurs :

– Les opérateurs arithmétiques

• Les classiques :

– (unaire)	Changement de signe
+	Addition
–	Soustraction
*	Multiplication
/	Division flottante

Les opérandes peuvent être du type entier (le résultat est entier) ou réel (le résultat est reel), sauf pour la division flottante, où le résultat sera toujours de type réel.

• La division entière :

DIV	Division entière
MOD	Modulo (reste de la division entière)

Ces deux opérateurs ne fonctionnent qu’avec des entiers.

– Les opérateurs logiques (et binaires)

Les opérandes sont booléennes, on a alors une opération logique. Le résultat est un booléen. Les expressions booléennes sont utilisées comme conditions dans les structures de contrôles.

NON (NOT)	négation logique ( ( neg ) )
ET (AND)	et logique ( ( wedge ) )
OU (OR)	ou logique ( ( vee ) )
OUEX (XOR)	ou exclusif

Rappels : avec a et b des booléens ou des expressions booléennes :

a ET b	n’est vrai que si a est vrai et b est vrai	est faux dès qu’un des deux est faux
a OU b	n’est faux que si a est faux et b est faux	est vrai dès qu’un des deux est vrai
a OUEX b	est vrai si un des deux seulement est vrai	est équivalent à a<>b

Important : Les opérateurs et et ou sont séquentiels : si l’évaluation de la première opérande suffit à donner le résultat, la deuxième n’est pas évaluée. Ainsi, si a est faux, a et b sera faux, sans que b n’ait été évalué.

Note : On utilisera les mêmes opérateurs sur des entiers non signés, on a alors des opérations sur bits. Les opérateurs fonctionnent de la même manière, le vrai correspondant à 1, le faux à 0.

Les opérateurs relationnels

Les deux opérandes doivent être de types compatibles. Le résultat est toujours de type booléen : vrai ou faux.

=	égal
<>	différent
<	inférieur à
>	supérieur
<=	inférieur ou égal
>=	supérieur ou égal

La concaténation de chaînes

L’opérateur « + » peut être utilisé avec les chaînes de caractères et les caractères pour la concaténation.

Règles d’évaluation des expressions

Priorité des opérateurs, par ordre décroissant :

opérateurs unaires	– ; non
opérateurs multiplicatifs	* ; / ; div ; mod ; et
opérateurs additifs	+ ; – ; ou
opérateurs relationnels	= ; < ; <= ; > ; >= ; <> (ou !=)

Les expressions entre parenthèses sont entièrement évaluées avant d’intervenir dans la suite des calculs.

Concordance de type : un opérateur binaire ne peut porter que sur deux valeurs du même type. Une exception a lieu lorsqu’une valeur est réelle et l’autre entière. Dans ce cas la valeur entière est convertie en une valeur réelle. Cette règle s’applique pour les opérateurs arithmétiques (+, -, *, /) et ceux de comparaisons.

L’affectation

Cette instruction permet d’affecter une valeur à une variable. La valeur peut être n’importe quelle expression de type compatible avec la variable.

• Syntaxe :
  

ident_var ← <expression>

avec ident_var : un identifiant de variable

• Fonctionnement

ident_var ← <valeur>

• Une valeur (une expression) ne peut en aucun cas figurer à gauche d’une affectation.
• Une variable figurant à droite d’une affectation (et plus généralement dans toute expression) doit obligatoirement contenir une valeur.

Les appels aux fonctions et procédures

L’appel d’une procédure ou d’une fonction (routine) se fait par son nom suivi, s’il y a lieu, de la liste des arguments placés entre parenthèses. Il faut respecter l’ordre de déclaration des paramètres. Lorsque le passage se fait par adresse (paramètre global), l’argument doit obligatoirement être une variable. S’il est passé par valeur (paramètre local), il peut s’agir d’une expression quelconque. La distinction entre les différents paramètres sera vue en détail dans la partie consacrée aux procédures et fonctions.

Appel de procédure = une instruction

L’appel de procédure est une instruction à part entière :

ident_procedure(param1, param2, ...)

Exemples de procédures : les entrées-sorties

• Les procédures d’affichage : ECRIRE ou AFFICHER

(En anglais : PRINT, DISPLAY)

ECRIRE("Nombre de voitures : ", x)

affiche sur l’écran (ou écrit dans un fichier) la chaîne ‘Nombre de voitures : ‘, suivi du contenu de la variable x.

AFFICHE(12+a)

affiche la valeur de l’expression12+a.

• La procédure de lecture : LIRE

(En anglais : READ)

LIRE(x)

affecte à la variable x la valeur saisie (sur le clavier ou dans un fichier).

Appel de fonction

Une fonction est une routine qui retourne une valeur. L’appel de fonction sera donc utilisable comme n’importe quelle autre valeur (dans une expression, en paramètre d’une routine, …). Par exemple dans une affectation :

ident_var ← ident_fonction(param1, param2, ...)

Note : un appel de fonction seul n’est pas une instruction !

Les structures de choix

L’alternative : SI – ALORS – SINON

• Syntaxe :
  

SI <expression booléenne> ALORS
       <instruction>
       ...
SINON
       <instruction>
       ... 
FIN_SI

(En anglais : IF – THEN – ELSE – ENDIF)

Remarque : la partie SINON <instruction> est facultative.

Attention : Le FIN_SI est obligatoire ! Il en sera de même pour toutes les instructions structurées : cette marque de fin doit être présente même si il n’y a qu’une seule instruction.

• Fonctionnement

Si la condition (exprimée par l’expression booléenne) est vraie alors seule la suite d’instructions placée après le ALORS sera exécutée. Dans le cas contraire, si la partie SINON existe elle sera exécutée, si elle n’existe pas, rien ne se passe.

Choix multiples : SELON

• Syntaxe :
  

SELON <ident_var> 
       <liste_valeur> : <instruction>
            ...     : ...
      {AUTREMENT : <instruction> }
FIN_SELON

(En anglais : CASE… OF – OTHERS – ENDCASE)

<liste_valeur>= une liste de valeurs (séparées par des virgules).

L’expression doit être de type scalaire : les types entiers et le type caractère.

• Fonctionnement

Les instructions exécutées seront celles correspondant à la valeur de l’expression. Si celle-ci n’est pas dans une des liste, alors ce sera la partie autrement (si elle existe) qui sera exécutée.

Structures de répétition

La répétitive : TANT QUE

• Syntaxe :
  

TANT_QUE <expression booléenne> 
       <instruction>
       ...
FIN_TANT_QUE

(En anglais : WHILE – ENDWHILE)

• Fonctionnement :
  

Les instructions sont répétées tant que la condition est vérifiée. Comme le test est au début, les instructions peuvent donc ne jamais être exécutées.

Attention : il est impératif que la condition devienne fausse à un moment. Pour cela il faut que l’expression booléenne contienne au moins une variable qui sera modifiée dans la boucle.

La répétitive : REPETER – JUSQU’A

• Syntaxe :
  

REPETER
       <instruction>
       ...
JUSQU'A <expression booléenne>

(En anglais : REPEAT – UNTIL)

• Fonctionnement :
  

La condition est placée après les instructions, elles sont exécutées donc au moins une fois puis tant que la condition reste satisfaite.

L’itérative : POUR

Elle permet de répéter une série d’instructions un nombre déterminé de fois (donc connu à l’avance).

• Syntaxe :
  

POUR <ident_var> ALLANT_DE <valeur_début> A <valeur_fin> {PAR_PAS_DE <incrément>}
       <instruction>
       ...
FIN_POUR

(En anglais : FOR – TO – ENDFOR)

• Fonctionnement :
  

La variable est nécessairement de type scalaire : entier, caractère ou énumération. Les expressions de début et de fin doivent être compatibles avec elle. Elle prend successivement toutes les valeurs comprises entre les deux bornes, dans l’ordre croisant ou décroissant (si l’incrément est négatif). Elle ne peut pas être modifiée dans la boucle ! La déclaration de l’incrément lorsqu’il est unitaire peut être omise.

La boucle POUR est un cas particulier de la boucle TANT QUE. Si on connait à l’avance le nombre de répétitions à effectuer, la boucle POUR est toute indiquée. A l’inverse, si la décision d’arrêter la boucle ne peut s’exprimer que par un test, c’est la boucle TANT QUE qu’il faut choisir.

Les procédures et fonctions

Les paramètres

Locaux – Globaux

Toute routine peut définir des paramètres, qui sont autant de données en entrée, fournies lors de l’appel à la routine depuis un autre endroit de l’algorithme. La structure de ces paramètres est définie immédiatement après l’entête de la routine. On distingue deux catégories de paramètres : les locaux et les globaux.

• Les paramètres globaux ne gérèrent pas de copie locale du paramètre effectif. Ils ne font qu’un avec la donnée qui leur est passée. En appelant une routine qui a des paramètres globaux, il faut alors fournir pour ceux-ci un nom de variable existante, et non une expression, puisque la routine est susceptible de modifier la variable passée (on parle de passage par variable ou par adresse).
• Les paramètres locaux indiquent que le paramètre effectif passé lors de l’appel à la routine sera en fait copié localement, et que la routine travaillera alors sur la copie locale (on parle de passage par valeur). De la sorte, toute modification effectuée par la routine ne sera pas répercutée sur la donnée passée en paramètre. Ce qui fait qu’un paramètre local peut recevoir une expression comme paramètre effectif, et non pas obligatoirement une variable.

Déclaration des paramètres

La déclaration des paramètres se fait comme une déclaration de variables. Deux parties pour séparer les paramètres locaux des globaux :

PARAMETRES globaux
    ident_type : ident_param1, ident_param2, ...
PARAMETRES locaux
    ident_type : ident_param1, ident_param2, ...
    ...

Note : l’ordre de déclaration n’a pas d’importance, mais il ne peut y avoir qu’une seule déclaration de paramètres locaux et qu’une seule déclaration de paramètres globaux.

Déclaration des routines

Les procédures

Une procédure (ou sous-programme) est une routine (un bloc de code) qui exécute un traitement puis rend la main. On peut ainsi isoler une partie de l’algorithme global et éventuellement l’appeler plusieurs fois en gardant un code structuré et modulaire.

• Syntaxe :
  

PROCEDURE ident_procedure(<liste des paramètres>)
       [<déclarations paramètres>]
       [<déclarations locales>]
  DEBUT
       <instructions>
  FIN

(En anglais : SUBPROCEDURE – BEGIN – END)

Les fonctions

Une fonction est un sous-algorithme effectuant un traitement et qui retourne une valeur.

• Syntaxe :
  

FONCTION ident_fonction(<liste des paramètres>) : ident_type_retourné
       <déclarations paramètres>
       [<déclarations locales>]
  DEBUT>
       <instruction>
	...
  RETOURNE <résultat>
  FIN

(En anglais : FUNCTION – BEGIN – RETURN – END)

La fonction retourne une valeur au moyen de la procédure système RETOURNE. Celle-ci doit donc obligatoirement figurer dans les instructions de la fonction.

La procédure système RETOURNE est « débranchante » : son exécution termine la fonction. Toute instruction placée après ne sera donc pas prise en compte.

Portée des identifiants

La portée d’un identifiant est la partie de l’algorithme dans laquelle cet identifiant est reconnu conformément à sa déclaration, c’est-à-dire l’ensemble des lignes de codes dans lesquelles l’utilisation de cet identifiant fera référence à la donnée qu’il définit.

Un identifiant sera « visible » dans l’algorithme où il a été déclaré et dans tout sous algorithme appelé, mais jamais à un niveau plus haut.

Il est possible d’avoir des « conflits » de portée, c’est-à-dire qu’un niveau d’imbrication de routine déclare un identifiant portant le nom d’un autre identifiant existant à un niveau supérieur. La règle alors est la suivante : la version la plus proche (la plus profondément imbriquée) de l’identifiant a la priorité.