|
|
 |
|
 |
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
Ceci appelle quelques explications.
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
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 :
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 : Il faut se méfier un peu plus du OU. Pour que : 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
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
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
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 :
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
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
Cette petite règle pourrait tout autant être formulée comme suit : Si il ne fait pas trop chaud OU il pleut Alors
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
  Nous vous informons que ce cours constitue une œuvre protégée en France par le Code de la Propriété Intellectuelle, et à l’étranger par les conventions internationales en vigueur sur le droit d’auteur. La violation de l’un des droits d’auteur de l’œuvre est un délit de contrefaçon. Il est donc interdit, à titre privé ou public, de reproduire, copier, vendre, revendre ou exploiter, que ce soit dans un but commercial ou purement gratuit, ce cours, sauf accord exprès et préalable de son auteur. Recherche
|
|
|
|
|
Accueil