L'objectif de cet algorithme est de résoudre toute forme d'équation du second degré. Nous donnons au cours de ce premier exposé quelques principes autour de la fabrication d'un algorithme.
Algorithme de résolution:
[[{"type":"media","view_mode":"media_original","fid":"108","attributes":{"alt":"","class":"media-image","height":"564","typeof":"foaf:Image","width":"536"}}]]
Entrée-Sortie
La fonction est nommée Resolve, elle prend trois arguments qui sont les coefficients $a, b, c$. La première question à se poser lors de la création d'un algorithme est à propos des données. Lesquelles doit-on réclamer de la part de l'utilisateur? Ici nous partons d'une équation: \[ ax^2+bx+c=0 \] Les données existent en entrée et il s'agira donc des trois coefficients, quant aux sorties éventuelles on doit retourner un résultat. La réponse sera l'affichage des solutions si elles existent ou un message indiquant l'impossibilité. Là encore la problématique est récurrente pour la sortie: Que doit-on renvoyer comme résultat? Et cette question pose le problème de la nature des données en sortie. Publie-t-on un message, un nombre, une liste, la valeur d'un test (oui ou non) ?
Le squelette de l'algorithme est présenté en page 13 du livre. L'explication du choix de l'entrée et des sorties sont données aussi dans le cours. Quant à l'entrée, pour rappel, il s'agit simplement du fait que tout polynôme du second degré possède toujours une forme développée. Les sorties sont les suivantes:
- sortie1: il n'y a pas de valeur à fournir, en revanche il peut être utile d'informer l'utilisateur qu'il n'existe pas de solution par un message. On affichera par exemple: "Cette équation n'admet aucune solution".
- sortie2: Le discriminant est nul, il y a une solution et elle est unique. Nous pouvons afficher le message "L'équation admet une unique solution" et fournir sa valeur directement comme résultat d'un calcul sans la stocker. On rajoutera l'instruction: Afficher $-b/2a$.
- sortie3: Lorsque $(\Delta>0)$ il faut indiquer qu'il y a deux solutions et leur valeur. Soit un message et deux affichages supplémentaires: "L'équation admet deux solutions distinctes" puis: \[ \text{Afficher} \quad \frac{-b-\sqrt{\Delta}}{2a} \quad \frac{-b+\sqrt{\Delta}}{2a} \]
Le programme ne conserve pas la valeur des racines. Il effectue un calcul et renvoie la valeur. D'ailleurs on pourra se poser la question d'une amélioration éventuelle pour le cas de la sortie3 puisque nous répétons certaines opérations comme l'extraction de la racine carrée de $\Delta$. Celle-ci est gourmande en opérations comme la division par $2a$. Enfin, le choix de la sortie empêche l'affectation d'une valeur dans un programme externe. Nous ne pouvons définir une nouvelle variable sous la forme d'une affectation: $x=\mathrm{Resolve}(a,b,c)$. Ceci parce que la sortie n'est pas une valeur mais la composée d'un message suivi d'une ou deux valeurs, voire aucune. Ces deux points, la complexité et la nature de la sortie sont abordés plus bas dans les améliorations.
Traitement effectué
La première étape du traitement de l'information saisie en entrée $(a,b,c)$ est une affectation: \[ \Delta \leftarrow b^2-4ac \] Nous définissons dans la mémoire une case nommée $\Delta$ recevant la valeur du calcul: $b^2-4ac$. Il est à noter que pour le calcul de la complexité, nous avons déjà 3 multiplications et une différence à prendre en compte obligatoirement. De plus, il y a déjà trois cases mémoires engagées: les trois coefficients et le discriminant.
La deuxième étape est un test de la part de la machine. Parmi les classiques qu'il est possible de demander il y a le signe, c'est-à-dire les deux questions $(\Delta>0)$ et $(\Delta<0)$. Aussi, le test d'égalité avec une valeur connue comme l'entier zéro: $(\Delta=0)$. La réponse à la question posée donnera un traitement différent, l'outil utilisé est alors une instruction conditionnelle:
Si $(\Delta < 0)$ Alors (sortie1) Sinon (Test2)
L'instruction comporte trois parties:
- La condition à vérifier $(\Delta < 0)$
- L'instruction à exécuter si la condition est vraie: (sortie1)
- L'instruction à exécuter sinon qui est à nouveau un test: (Test2)
Dans le cas d'un discriminant strictement négatif on obtient une sortie nommée sortie1. Sinon on effectue un dernier test:
Si $(\Delta > 0)$ Alors (sortie2) Sinon (sortie3)
Celui-ci constitue une troisième étape en cas de "non" à la première question. Quelle que soit la valeur de ce test on obtient une sortie. La remarque a son importance car elle indique que l'algorithme se termine. C'est un contrôle que l'on doit systématiquement effectuer avant de le transcrire sous forme de programme et surtout de le lancer. Mieux, pour chaque sortie il s'agira d'estimer le coût en mémoire, les calculs de la machine et leur type, une division demande bien plus d'opérations qu'une addition pour un ordinateur. Les chemins empruntés pour chaque sortie sont aussi à connaître, ici on avance sans retour, il n'y a pas de boucles.
Les deux tests sont de type booléen, c'est-à-dire qu'ils donnent une réponse sous la forme "oui" ou "non", et c'est ce type là qu'on étudiera presque systématiquement. L'avantage est l'assurance qu'il ne peut y avoir que l'une des deux réponses. Après le premier test, soit il y a une sortie, soit il y a un autre test. Et après celui-ci il y a nécessairement une sortie. D'où la terminaison de l'algorithme.
Composition
Expliquons à présent les choix effectués. Dans le cours, nous avons vu une méthode donnant l'assurance d'une réponse à la résolution de l'équation du second degré $(ax^2+bx+c=0 )$ . C'est celle du discriminant, et d'ailleurs nous pourrons améliorer l'algorithme par une étape préliminaire consistant à vérifier la nullité des coefficients, pour éviter de lancer des tests et surtout pour éviter de diviser par $a$ si ce dernier est nul.
Le premier outil utilisé est le discriminant. Le nombre est calculé et le signe indique les trois possibilités. Nous commençons donc par le calculer, et puisque nous n'allons pas seulement le tester mais aussi réutiliser le résultat pour d'éventuels calculs (le test supplémentaire, la valeur des racines) alors l'idéal est de conserver sa valeur. Le discriminant ne dépendant directement que des données, son affectation a lieu dès la première étape. Toute autre valeur susceptible d'avoir la même utilité pourrait être calculée dès à présent.
Mais puisqu'il est possible d'avoir une sortie sans le moindre calcul dès lors que $(\Delta < 0 )$ nous évitons toute autre affectation pour le moment. Une fois la valeur de $\Delta$ calculée et enregistrée, elle est testée et trois réponses sont possibles. L'ordre a son importance car si le discriminant est strictement négatif alors il est possible de sortir sans le moindre calcul supplémentaire et ces sorties là sont à rechercher en priorité. Même si dans cette situation le fait de modifier l'ordre des tests ne change rien en moyenne. Par exemple, nous aurions pu faire le test dans l'ordre suivant:
Si $(\Delta>0)$ Alors (sortie3) Sinon ( Si $(\Delta<0)$ Alors (sortie1) Sinon (sortie2) )
Seulement cela est une bonne habitude d'éliminer en premier les éventualités simples, car elle nécessitent peu de traitements et n'apporte rien au reste. Quant aux deux autres possibilités qui sont $(\Delta=0)$ et $(\Delta>0)$ elles ont en commun le calcul de $-b/(2a)$, d'où l'intérêt de les réunir comme nous le verrons sur les améliorations.
Ainsi, puisqu'il faut tester le signe du discriminant pour trouver un profit dans cette méthode, nous commençons par vérifier sa négativité. Dans le cas où le test est positif (Noter la différence entre le test et le signe de la variable testée, le vocabulaire est important.) la sortie1 est renvoyée. Sinon il reste deux cas, on choisit de vérifier là encore le plus simple qui est $(\Delta=0)$. Soit $\Delta$ est déclaré nul et alors la sortie2 est renvoyée, soit on peut en conclure par disjonction des cas qu'il ne reste plus que la dernière possibilité, d'où l'inutilité d'un troisième test. La sortie3 est renvoyée si le dernier test s'avère négatif.
Algorithme bien défini
Nous avons suggeré une méthode de résolution comme celle fournie dans le cours, puis traduit sous forme algorithmique la démarche pour la rendre systématique et donc accessible à une machine. Il reste à vérifier d'abord si son traitement ne risque pas de poser un problème en terme de définition, de boucle infinie, de test incompatible ou tout autre type d'erreurs susceptibles d'apparaître.