Cours d'algorithmique N°3 : les tests

Je vous avais dit que l’algorithmique, c’est la combinaison de quatre structures élémentaires. Nous en avons déjà vu deux, voici la troisième. Autrement dit, on a quasiment fini le programme.
Mais non, je rigole.

1. De quoi s’agit-il ?

Reprenons le cas de notre " programmation algorithmique du touriste égaré ". Normalement, notre algorithme ressemblera à quelque chose comme : " Allez tout droit jusqu’au prochain carrefour, puis prenez à droite et ensuite la deuxième à gauche, et vous y êtes ".

Mais en cas de doute légitime de votre part, cela pourrait devenir : " Allez tout droit jusqu’au prochain carrefour et là regardez à droite. Si la rue est autorisée à la circulation, alors prenez la et ensuite c’est la deuxième à gauche. Mais si en revanche elle est en sens interdit, alors continuez jusqu’à la prochaine à droite, prenez celle-là, et ensuite la première à droite ".

Ce deuxième algorithme a ceci de supérieur au premier qu’il prévoit, en fonction d’une situation pouvant se présenter de deux façons différentes, deux façons alternatives d’agir. Cela suppose que l’interlocuteur (le touriste) sache analyser la condition que nous avons fixée à son comportement (" la rue est-elle en sens interdit ? ") pour effectuer la série d’actions correspondante.

Eh bien, croyez le ou non, mais les ordinateurs possèdent cette aptitude, sans laquelle d’ailleurs nous aurions bien du mal à les programmer. Nous allons donc pouvoir parler à notre ordinateur comme à notre touriste, et lui donner des séries d’instructions à effectuer selon que la situation se présente d’une manière ou d’une autre.

2. Structure d’un test

Il n’y a que deux formes possibles pour un test ; la forme de gauche est la forme complète, celle de droite la forme simple.

Si booléen Alors Si booléen Alors Instructions 1 Instructions
Sinon Finsi
Instructions 2
Finsi

Ceci appelle quelques explications.
Un booléen est une expression dont la valeur est VRAI ou FAUX. Cela peut donc être (il n’y a que deux possibilités) :

• une variable de type booléen
• une condition

Nous reviendrons dans quelques instants sur ce qu’est une condition en informatique.

Toujours est-il que la structure d’un test est relativement claire. Arrivé à la première ligne (Si…Alors) la machine examine la valeur du booléen. Si ce booléen a pour valeur VRAI, elle exécute la série d’instructions 1. Cette série d’instructions peut être très brève comme très longue, cela n’a aucune importance. A la fin de cette série d’instructions, au moment où elle arrive au mot " Sinon ", la machine sautera directement à la première instruction située après le " Finsi ". De même, au cas où le booléen avait comme valeur " Faux ", la machine saute directement à la première ligne située après le " Sinon " et exécute l’ensemble des " instructions 2 ".

La forme simplifiée correspond au cas où l’une des deux " branches " du Si est vide. Dès lors, plutôt qu’écrire " sinon ne rien faire du tout ", il est plus simple de ne rien écrire.

Exprimé sous forme de pseudo-code, la programmation de notre touriste de tout à l’heure donnerait donc quelque chose du genre :

Exemple

Allez tout droit jusqu’au prochain carrefour
Si la rue à droite est autorisée à la circulation Alors Tournez à droite
Avancez
Prenez la deuxième à gauche
Sinon Continuez jusqu’à la prochaine rue à droite
Prenez cette rue
Prenez la première à droite
Fin si

3. Qu’est ce qu’une condition ?

Une condition est une comparaison. Cette définition est essentielle !

C’est-à-dire qu’elle est composée de trois éléments :

• une valeur
• un opérateur de comparaison
• une autre valeur

Les valeurs peuvent être a priori de n’importe quel type (numériques, caractères…)

Les opérateurs de comparaison sont : = <> < > =< >=

L’ensemble constitue donc si l’on veut une affirmation, qui a un moment donné est VRAIE ou FAUSSE.

A noter que ces opérateurs de comparaison s’emploient tout à fait avec des caractères. Ceux-ci sont codés par la machine dans l’ordre alphabétique, les majuscules étant systématiquement placées avant les minuscules. Ainsi on a :

"t" < "w" VRAI

"Maman" > "Papa" FAUX

"maman" > "Papa" VRAI

Attention à certains raccourcis du langage courant qui peuvent mener à des non-sens informatiques. Prenons par exemple la condition " Toto est compris entre 5 et 8 ". On peut être tenté de la traduire par : 5 < Toto < 8. Or, une telle expression, qui a du sens en mathématiques, ne veut rien dire en programmation. On va voir tout de suite après comment traduire une telle condition.

4. Conditions composées

Certains problèmes exigent parfois de formuler des conditions qui ne peuvent pas être exprimées sous la forme simple exposée ci-dessus. Reprenons le cas " Toto est inclus entre 5 et 8 ". En fait cette phrase cache non une, mais deux conditions. Car elle revient à dire que " Toto est supérieur à 5 et Toto est inférieur à 8 ". Il y a donc bien là deux conditions, reliées par ce qu’on appelle un opérateur logique, le mot ET.

Comme on l’a évoqué plus haut, l’informatique met à notre disposition trois opérateurs logiques : ET, OU, et NON.

Le ET a le même sens en informatique que dans le langage courant. Pour que :

Condition1 ET Condition2 soit VRAI, il faut impérativement que Condition1 soit VRAIE et que Condition2 soit VRAIE.

Il faut se méfier un peu plus du OU. Pour que :

Condition1 OU Condition2 soit VRAI

Il suffit que Condition1 soit VRAIE ou que Condition2 soit VRAIE. Le point important est que si Condition1 est VRAIE et que Condition2 est VRAIE aussi, Condition1 OU Condition2 est VRAIE. Le OU informatique ne veut donc pas dire " ou bien " (sauf dans certaines formes rares, dénommées OU exclusif et notées XOR).

On représente fréquemment tout ceci dans des tables de vérité :

Le gag de la journée : c’est bien sûr formuler une condition qui ne pourra jamais être vraie. Si c’est pas fait exprès, c’est assez rigolo. Si c’est fait exprès, c’est encore plus drôle, car une condition dont on sait d’avance qu’elle sera toujours fausse n’est pas une condition. Cela peut être par exemple : Si Toto < 10 ET Toto > 15 Alors… Bon, ça, c’est un motif immédiat pour payer une tournée générale, et je sens qu’on ne restera pas longtemps le gosier sec.

Quelques mots pour finir là-dessus. L’opérateur NON, lui, inverse une condition :

Condition VRAI ó NON (Condition) FAUX

NON ( X > 15 ) revient à écrire X =< 15

5. Tests imbriqués

Graphiquement, on peut très facilement représenter un SI comme un aiguillage de chemin de fer (ou un aiguillage de train électrique, c’est moins lourd à porter). Un SI ouvre donc deux voies, correspondant à deux traitements différents. Mais il y a des tas de situations où deux voies ne suffisent pas. Par exemple, un programme devant donner l’état de l’eau selon sa température doit pouvoir choisir entre trois réponses possibles (solide, liquide ou gazeuse).

Exemple

Variable Temp en Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C’est de la glace"
Finsi
Si Temp > 0 Et Temp < 100 Alors
Ecrire "C’est du liquide"
Finsi
Si Temp > 100 Alors
Ecrire "C’est de la vapeur"
Finsi
Fin

Vous constaterez que c’est un peu laborieux. Les conditions se ressemblent plus ou moins, et surtout on oblige la machine à examiner trois tests successifs alors que tous portent sur une même chose, la température (la valeur de la variable Temp). Il serait ainsi bien plus rationnel d’imbriquer les tests de cette manière :

Exemple

Variable Temp en Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C’est de la glace"
Sinon
Si Temp < 100 Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
Finsi
Fin

Nous avons fait des économies au niveau de la frappe du programme : au lieu de devoir taper trois conditions, dont une composée, nous n’avons plus que deux conditions simples. Mais aussi, et surtout, nous avons fait des économies sur le temps d’exécution de l’ordinateur. Si la température est inférieure à zéro, celui-ci écrit dorénavant " C’est de la glace " et passe directement à la fin, sans être ralenti par l’examen d’autres possibilités (qui sont forcément fausses).

Cette deuxième version n’est donc pas seulement plus simple à écrire et plus lisible, elle est également plus performante à l’exécution.

Les structures de tests imbriqués sont donc un outil indispensable à la simplification et à l’optimisation des algorithmes.

6. Variables Booléennes

Jusqu’ici, nous avons utilisé uniquement des conditions pour faire des choix. Mais vous vous rappelez qu’il existe un type de variables (les booléennes) susceptibles de stocker les valeurs VRAI ou FAUX. En fait, on peut donc entrer des conditions dans ces variables, et tester ensuite la valeur de ces variables.

Reprenons l’exemple de l’eau. On peut le réécrire ainsi :

Exemple

Variable Temp en Entier
Variables A, B en Booléen
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
A ï Temp =< 0
B ï Temp < 100
Si A Alors
Ecrire "C’est de la glace"
Sinon B Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
Finsi
Fin

A priori, cette technique ne présente guère d’intérêt : on a alourdi plutôt qu’allégé l’algorithme de départ, en lui faisant recourir à deux variables supplémentaires. Mais :

• une variable booléenne n’a besoin que d’un seul bit pour être stockée. L’alourdissement de ce point de vue n’est donc pas considérable.
• dans certains cas, notamment celui de conditions composées très lourdes (avec plein de ET et de OU tout partout) cette technique peut faciliter le travail du programmeur. Les variables booléennes peuvent également s’avérer très utiles pour servir de flag, technique dont on reparlera plus loin (rassurez-vous, rien à voir avec le flagrant délit des policiers).

7. Quelques jeux logiques

Une remarque pour commencer : dans le cas de conditions composées, les parenthèses jouent un rôle important.

Exemple

Variables A, B, C, D, E en Booléen
Variable X en Entier
Début
Lire X
A ï X < 2
B ï X > 12
C ï X < 6
D ï (A ET B) OU C
E ï A ET (B OU C)
Ecrire D, E
Fin

Si X = 3, alors on remarque que D sera VRAI alors que E sera FAUX.

S’il n’y a que des ET, ou que des OU, en revanche, les parenthèses ne changent strictement rien.

On en arrive à une autre propriété des ET et des OU, bien plus intéressante. Spontanément, on pense souvent que ET et OU s’excluent mutuellement, et qu’un problème donné s’exprime soit avec un ET, soit avec un OU. Pourtant, ce n’est pas si évident.

Quand faut-il ouvrir la fenêtre de la salle ? Uniquement si les conditions l’imposent, à savoir :

Si il fait trop chaud ET il ne pleut pas Alors
Ouvrir la fenêtre
Sinon
Fermer la fenêtre
Finsi

Cette petite règle pourrait tout autant être formulée comme suit :

Si il ne fait pas trop chaud OU il pleut Alors
Fermer la fenêtre
Sinon
Ouvrir la fenêtre
Finsi

Ces deux formulations sont strictement équivalentes. Ce qui nous amène à la conclusion suivante : toute structure de test requérant une condition composée faisant intervenir l’opérateur ET peut être exprimée de manière équivalente avec un opérateur OU, et réciproquement.

Ceci est moins surprenant qu’il n’y paraît au premier abord. Jetez pour vous en convaincre un œil sur les tables de vérité, et vous noterez la symétrie entre celle du ET et celle du OU.

Bien sûr, on ne peut pas se contenter de remplacer purement et simplement les ET par des OU ; ce serait un peu facile. La règle d’équivalence est la suivante (on peut la vérifier sur l’exemple de la fenêtre) :

Si A ET B Alors Si NON A OU NON B Alors
Instructions 1 Instructions 2
Sinon óSinon
Instructions 2 Instructions 1
Finsi Finsi

Posted in: