Savoir

1. Citer et commenter, dans le cadre du calcul conditionnel, les trois sortes d’informations que peut traiter un ordinateur ;
2. expliquer le principe de construction d’un arbre binaire de décision.

Savoir faire

1. écrire un arbre binaire de dcision pour une alternative simple ;
2. écrire un arbre binaire de décision pour une alternative complexe ;
3. Formaliser des situations d’alternative dans la forme si <condition> alors <action1> sinon <action2> (phrase conditionnelle) et dans un graphe de Nassi-Schneiderman ;
4. écrire une fonction alternative complexe dans le cadre d’un tableur.

Introduction au clavier

Démarre l’application OpenOffice.org Calc et demande une nouvelle feuille de calcul. Suis les indications données dans le tableau ci-dessous.

Enregistre la feuille de calculs sous le nom " intro.sxc ". Nous l'utiliserons plus loin dans la leçon.

Expérimentations

Dans une feuille de calcul vierge, introduis les informations suivantes:

- A propos de cette dernière expression, moi, j'ai bien ma petite idée. Il suffit de voir comment j'ai été malade en sortant du ........., la semaine passée!
Mais, que je sache, on n'a jamais pu forcer un ordinateur à manger un hamburger. Où est donc l'astuce?

- Pour cette comparaison, l'ordinateur n'utilise que l'ordre alphabétique. Aucun autre critère n'intervient. Il n'a aucun accès au sens des informations.

En fonction du logiciel utilisé, il se peut que la convention d’ordre alphabétique diffère. Généralement, les caractères majuscules et minuscules ne sont pas considérés comme équivalents.

En réalité, les caractères ne sont pas représentés en tant que tels dans l’ordinateur. Il n’est capable que de mémoriser des nombres ; chaque caractère s’est donc vu, par convention, attribuer un code numérique.

La convention ASCII (American Standard Code for Information Interchange), par exemple est illustrée ci-dessous.

Les caractères de code inférieur à 32 (code du caractère « espace ») ont des rôles particuliers (retour à la marge, passage à la ligne, ...). Les codes supérieurs à 127 ne sont pas attribués dans le code ASCII original. En fonction de la langue utilisée, les caractères spéciaux peuvent recevoir un code entre 128 et 255. On parle alors de code ASCII étendu.

Les caractères majuscules ont un code plus petit que le code des caractères minuscules. Certains logiciels se basent uniquement sur cette convention pour comparer des chaînes dans l’ordre alphabétique. Dès lors, la comparaison "anatole"="Anatole" pourrait avoir la valeur « VRAI » dans certains logiciels (c'est le cas de Microsoft Excel, par exemple)  ; la réponse dépend du mode de comparaison entre les caractères: codage ASCII strict ou non.

Pour répondre à la question précédente, un test qui ne laisse aucun doute serait d'entrer l'expression logique suivante dans une cellule :

Introduction au clavier

Ouvre le classeur " intro.sxc " produit au début de cette leçon. Introduis-y les informations suivantes :

Conclusion

La conjonction « SI » marque le début d’une alternative.

Le mot « SI » est suivi d’une expression logique, qui est donc vraie ou fausse.

L’ordinateur est capable de reconnaître la situation d’alternative et d’évaluer l’expression logique. Si celle-ci est vraie, la fonction alternative retourne la valeur qui suit l’expression logique. Si l’expression logique est fausse, c’est la deuxième valeur qui est retournée.

Il est souvent commode d’écrire l’alternative sous l’une ou l’autre forme visuellement parlante. Chacune des trois méthodes suivantes peut être utilisée.

Première forme : la phrase alternative

- Dites, cette expression exotique et bizarre "Fin Si", elle est vraiment obligatoire ? Ou bien, c'est pour ceux qui sont un peu miro et qui ne voient pas que c'est la fin ?

- Contrairement à ce que l'on pourrait penser, le " Fin Si " n'est pas seulement esthétique : nous n'allons pas tarder à rencontrer des cas, dans des expressions complexes, où il est intéressante de bien visualiser la fin de l'alternative. Prenons donc l'habitude de l'indiquer.

- Et pour cette barre verticale entre " Si " et " Fin Si ", je vais aussi devoir attendre les expressions complexes pour en apprécier l'intérêt ?

- Exactement ! Le moment de bénir l'existence des traits verticaux n'est pas encore toutà fait arrivé. Encore un tout petit peu de patience.

Deuxième forme: graphe de Nassi-Schneiderman (GNS)

Troisième forme: l'arborescence

L'appellation " arborescence " prendra tout son sens dans les cas d'alternatives complexes.

Exemples :

Première forme :

Deuxième forme :

Troisième forme :

Dans un chapitre précédent du cours, tu as mis au point un "jeu de dés". Il serait intéressant que l'ordinateur lui-même annonce le vainqueur.

La situation inititale se présente donc comme sur l'illustration ci-contre. Dans ce cas, c'est le joueur bleu qui a gagné.

Peux-tu exprimer la situation présentée ci-dessus dans chacune des trois formulations proposées dans ce cours?

Quelle difficulté nouvelle apparaît ici ? Attention, il y a un piège !

Quand tu as rédigé les trois formulations sur une feuille de papier, passe à la suite.

Parmi les façons d'exprimer la situation d'alternative du jeu de dés, on pourrait écrire la représentation en arbre illustrée à droite ou la phrase alternative indiquée ci-dessous  :

Comment formuler ces représentations dans le formalisme imposé par le tableur ?

=SI(Test_logique;Valeur_si_vrai; Valeur_si_faux)

On voit que la situation est relativement simple: il suffit d'écrire :

=SI(B4 > C4; "Le joueur Bleu a gagné" ; "Le joueur Jaune a gagné")

Rappel : il faut mettre des guillemets autour des deux phrases car ce ne sont pas des valeurs numériques.

Reporte dans la cellule C5 de la feuille de calcul du jeu de dés, l'expression de l'alternative construite ci-dessus. Vérifie que le jeu fonctionne correctement dans tous les cas.

Dans quelles circonstances y a-t-il un problème ?

- Ben zut alors, tout ça semblait tellement évident et vlan, un problème se pointe !

- Tu viens de faire l'expérience douloureuse de la difficulté de travailler avec un ordinateur. Comme il est, lui-même, très bête, il faut être deux fois plus intelligent à sa place.
La réflexion approfondie sera toujours une part importante du travail de l'informaticien.

La difficulté rencontrée dans le jeu de dés est bien celle du cas d'égalité. Dans la résolution proposée, le joueur Bleu est proclamé gagnant lorsque son score est meilleur ET s'il y a égalité. Ce n'est pas normal.

Mais le problème est simple à traiter en utilisant une arborescence à deux niveaux, comme dans l'exemple de l'équation du premier degré traité à l'étape précédente.

Remarque qu'il existe plusieurs façons de traiter le problème. On aurait pu utiliser d'autres tests : commencer par vérifier si B4=C4, par exemple.

Peux-tu reformuler l'alternative présentée sous forme d'arborescence dessinée ci-dessus, en utilisant une phrase alternative complexe (si... alors... sinon...) ?

Rédige cette phrase alternative puis passe à la suite.

Énoncé du problème et analyse

On demande de programmer le tableur de manière à lui faire résoudre les équations du premier degré du type ax + b = 0 d'inconnue x.

Ce type de problème est élémentaire au cours de mathématiques : il se résout de la manière suivante.

Il y a ici une situation d'alternative double :

1. Il y a un choix entre deux possibilités ; pour choisir, il faut examiner le coefficient de x (il est nul ou il ne l'est pas).
2. Si a0, il y a encore un choix entre deux possibilités ; pour choisir, il faut examiner le 2ème membre de cette équation (il est nul ou il ne l'est pas).

Résultat attendu et méthode

On attend d’obtenir une feuille de calcul semblable aux exemples ci-dessous.

Pour la facilité, il serait souhaitable de nommer les deux cellules grisées a et b.
Attention ! Suite à un bug dans Excel 2000, il n'est pas possible de donner ces noms aux cellules lorsqu'on utilise ce logiciel. Utiliser impérativement OpenOffice.org Calc.

Alternative dans le tableur

Avant d’écrire le formalisme propre au tableur, nous présenterons l’alternative selon la forme

si <expression logique> alors <action1> sinon <action2>

La fonction alternative s’écrira donc :

=SI(a<>0;-b/a;SI(b<>0;"Impossible";"Indéterminé"))

ou, si l'on utilise les coordonnées plutôt que les noms

=SI(A2<>0;-D2/A2;SI(D2<>0;"Impossible";"Indéterminé"))

Utilise toutes les informations données plus haut pour résoudre le problème de la résolution des équations du premier degré avec le tableur.

Problème

Écrire un programme qui détermine si une année dont on donne le millésime est bissextile.

Une année est bissextile si son millésime est multiple de 4; cependant, les années dont le millésime est multiple de 100 ne sont bissextiles que si c'est aussi un multiple de 400 (1900 n'était pas bissextile, 2000 l'a été).

Il faut bien mettre en évidence toutes les conditions particulières à envisager lors de la résolution du problème. Il faut évaluer si:

• le millésime est un multiple de 4;
• le millésime est un multiple de 100;
• le millésime est un multiple de 400.

Construction d'un arbre binaire de décision

Examine attentivement l'arborescence ci-dessous durant la lecture de l'explication de sa construction.

Choisissons une de ces conditions particulières et voyons ce qu'il convient de faire si elle est vraie et si elle est fausse. Nous commencerons par la condition « multiple de 4 ».

Si la condition est fausse, l'année n'est pas bissextile et c'est fini, sinon, il faut encore travailler.

Quelle question faut-il se poser si le millésime est multiple de 4? Il faut voir si c'est un multiple de 100.

Si la condition est fausse, alors l'année est bissextile et c'est fini, sinon, il faut encore travailler.

Si la condition est vraie, alors l'année est bissextile, sinon, elle n'est pasbissextile. Dans tous les cas, le travail est terminé.

La structure de décision se présente sous la forme d’un arbre inversé, c’est-à-dire dont la racine serait en haut et les branches en bas.

Dans le formalisme Si...Alors...Sinon..., ce tableau pourrait s’exprimer :

Vérifie, à l'aide de l'abre binaire de décision ou de la structure si...alors...sinon, que les années 1930, 2003 et 2100 ne sont pas bissextiles.

Vérifie ensuite que 1980, 1800 et 2400 sont des années bissextiles.

Transpose le formalisme de l'arbre ou de la phrase alternative dans celui qui est propre au tableur.

Le but est de pouvoir proposer un tableau semblable à celui de l'illustration ci-contre pour toutes les années à partir de 1582.

- Bah! Pourquoi 1582?

- Et bien, cherche. ;o)
Il y a suffisamment d'informations sur cette page pour pouvoir trouver aisément la réponse à cette question.

La pratique pose deux problèmes :

1. il faut être capable de déterminer si un nombre est multiple d’un autre ;
2. il faut être capable d’écrire une alternative complexe.

Pour savoir si un nombre est divisible par un autre, il suffit de faire la division et de déterminer la valeur du reste de cette division. Les programmes tableurs mettent généralement une fonction MOD à la disposition des utilisateurs.

Si la cellule qui contient le millésime de l’année est nommée « AN », l’alternative s’écrira alors :

Ce qui s’écrira simplement :

=SI(MOD(AN;4)=0;SI(MOD(AN;100)=0;SI(MOD(AN;400)=0;"Bissextile";"Non bissextile");"Bissextile");"Non bissextile")

dans le formalisme propre au tableur.

Il paraît bien difficile d’écrire cette formule sans réaliser l’analyse complète du problème.

Pour chacun des exercices qui suivent, il est demandé de réaliser une analyse complète et de tracer l’arbre binaire de décision ou d'écrire la phrase alternative, préalablement au travail au clavier.

1. On demande d'établir une feuille de calcul à l'usage d'un employé de banque. Étant donné le solde du compte en banque d'un client et le montant qu'il désire retirer de son compte, le programme doit indiquer le message « retrait accepté », le montant du retrait et le nouveau solde du compte si le compte est suffisamment approvisionné. Si le solde du compte avant retrait est inférieur à –500 €, le retrait est refusé; le nouveau solde du compte après retrait ne peut être inférieur à –500 €, de sorte que le retrait peut, dans certains cas, être limité à un montant tel que cette exigence soit respectée.

2. Établir une feuille de calcul qui indique le plus grand de trois nombres fournis par l'utilisateur.

3. Une entreprise désire établir une feuille de calculs pour déterminer le nombre de jours de congé auxquels ont droit ses employés sachant qu'ils bénéficient de 2 jours de congé par mois de présence durant l'année écoulée et de 10 jours de congé supplémentaires s'ils ont plus de 10 ans de service dans la société.

4. Le règlement d'un club londonien très fermé précise que tout membre doit répondre aux conditions suivantes : il ne peut pas mesurer plus de 1,85 m ni moins de 1,50 m. Cependant, les personnes de plus petite taille (moins de 1,50 m) sont admises à condition de peser plus de 60 kg et d'être âgées de plus de 18 ans. Les personnes de très grande taille (plus de 1,85 m) sont admises si elles pèsent moins de 100 kg, sauf si elles ont plus de 45 ans, cas où elles ne sont jamais admises.

Écrire l'arbre de décision binaire puis l’alternative qui permet de déterminer si une personne est admissible.

5. Établir une feuille de calcul qui détermine si une date donnée entre le 1 janvier 1901 et le 31 décembre 1999 a existé. Pour rappel, dans cet intervalle, toutes les années dont le millésime est multiple de 4 sont bissextiles.

Ex: le 12/06/1978 est une date licite
le 30/02/1989 est une date illicite
le 34/15/1965 est une date illicite

Astuce: il est possible de déterminer séparément si l’année est bissextile. On peut utiliser le résultat du test dans une autre alternative.

6. Établir une feuille de calcul destinée à rédiger des factures chez un grossiste en disques. Celui-ci vend des disques « single » au prix unique de 5€ et des CD au prix de 9€. Le montant de la TVA à appliquer sur les factures est de 21%.

Le client se voit facturer les frais de port (forfait de 5€) au cas où le montant (hors TVA) de sa commande est inférieur à 125 €. Cependant, s'il s'agit d'un bon client (montant des achats supérieurs à 2.500 € au cours de l'année écoulée), les frais de port sont réduits à 1,25 €. La TVA ne s'applique pas sur les frais de port!

7 Les membres de la secte des « mathos-dingos » considèrent qu'un nombre de 4 chiffres est magique si le premier chiffre est pair et que la somme des deux suivants est impaire. Toutefois, si le dernier chiffre est pair, le nombre n'est réellement magique que si le produit des deux médians est un multiple de 3.

Etablis une feuille de calcul qui détermine si une suite de 4 chiffres constitue un nombre magique.

Ex: 2321 est magique ; 4452 ne l'est pas.

La fonction ENT (qui signifie « partie entière ») permet de connaître la partie entière d’un nombre fractionnaire. Le fragment de tableur ci-contre permet d’isoler les quatre chiffres de la cellule en haut et à gauche dans la deuxième colonne.

8 Établir une feuille de calcul pour résoudre les équations du second degré à une inconnue de la forme ax²+bx+c=0.