Appel de fonctions
Pour résoudre un problème donné par un algorithme, nous pouvons diviser le travail à effectuer en sous-problèmes plus spécifiques, cela renvoie à la fameuse démarche de René Descartes décrite dans son ouvrage Discours de la méthode et que l'on retrouve bien sûr dans d'autres domaines comme en politique chez Machiavel dans son essai d'analyse Le prince destiné à un membre de la famille des Médicis, ou dans le domaine militaire plus précisément aussi décrit chez Lao Tseu, L'art de la guerre.
C'est l'essence même d'un algorithme que de séparer les parties à traiter et créer plusieurs sous-programmes dédiés à une tâche, ainsi réutilisables de manière indépendante de l'ensemble. Montrons sur la résolution de l'équation du second degré comment corriger notre erreur pour le cas $(a=0)$ et aussi comment sa correction nous permet d'écrire une fonction à laquelle on pourra faire appel dans d'autres cas:
[[{"type":"media","view_mode":"media_original","fid":"155","attributes":{"alt":"","class":"media-image","height":"305","typeof":"foaf:Image","width":"526"}}]]
Nous définissons une nouvelle fonction $R$ à trois arguments. Elle résout l'équation du second degré: \[ ax^2+bx+c=0 \] en tenant compte du cas $(a=0)$. La méthode utilisée consiste en un seul test: $(a=0?)$. Le branchement conditionnel est le suivant:
Si $(a=0)$ Alors Lancer Affine$(b,c)$ Sinon Lancer Resolve$(a,b,c)$
Suivant la réponse au test, on appelle une fonction nommée Affine ou Resolve. Quant à la seconde nous l'avons décrite dans le premier article consacré à l'algorithme de résolution des équations du second degré. Quant à la première elle est connue, si $a$ est nul, on en revient à la première section dans le chapitre 1. Résoudre $(bx+c=0)$ en vérifiant uniquement si $b$ est nul puis $c$:
[[{"type":"media","view_mode":"media_original","fid":"156","attributes":{"alt":"","class":"media-image","height":"428","typeof":"foaf:Image","width":"521"}}]]
On rappelle que la sortie doit rester de même nature, c'est-à-dire un affichage. La fonction $R$ renvoie donc un affichage et toute fonction à laquelle elle fait référence doit rendre le même contenu. Ainsi il sera affiché:
- Si $b$ et $c$ sont nuls: $\mathbb{R}$.
- Si $b$ est nul mais pas $c$: $\emptyset$.
- Si $b$ est non nul: $-c/b$.
Amélioration du temps
Ce point fut abordé dans le second article, un algorithme qui résout le problème posé est considéré comme une solution. Mais s'il nécessite un temps très long cela en fait un algorithme de mauvaise qualité. Il existe toute une branche de l'algorithmique qui traite de ce sujet: la complexité. Pour des nombres simples ne dépassant pas les tailles mémoire dédiées à leur stockage, il n'est pas nécessaire de s'attarder sur le calcul des opérations effectuées. Mais s'ils deviennent grands, ou si l'on souhaite appliquer la fonction Resolve à des millions de triplets $(a,b,c)$ la recherche d'économies dans le calcul devient une affaire de premier plan.
Lorsque $(\Delta \geq 0)$ alors nous aurons à calculer $\displaystyle \frac{-b}{2a}$ que le discriminant soit nul ou non. Dans le cas de deux solutions il faudra en plus connaître la valeur de $\displaystyle \frac{\sqrt{\Delta}}{2a}$. Une idée consiste à ouvrir deux nouvelle adresses mémoires et les dédier à ces réels: \[ r=\frac{-b}{2a} \qquad s=\frac{\sqrt{\Delta}}{2a} \] Ceci nous évite de recalculer la racine carrée du discriminant, opération couteuse, mais nous ne gagnons rien en nombre de divisions à effectuer. Pour y remédier une troisième variable est créée que nous définissons par: \[ m=\frac{1}{2a} \] Voici alors l'algorithme Resolve remanié:
[[{"type":"media","view_mode":"media_original","fid":"157","attributes":{"alt":"","class":"media-image","height":"714","typeof":"foaf:Image","width":"763"}}]]
La division par $2a$ n'est effectuée qu'une seule fois. La racine carrée n'est extraite qu'une seule fois. Mais l'on pourrait s'interroger sur la nécessité de définir $s$ avant le test $(\Delta=0)$ car elle deviendrait inutile dans le cas strictement positif.
Question 1
Calculer pour chaque sortie de la fonction $R$ les opérations élémentaires effectuées parmi les affectations, tests, sommes, produits, divisions, racines carrées.
Question 2
Améliorer le cas $(\Delta=0)$
Ecriture de l'algorithme
L'algorithme que nous venons de présenter devient donc:
Resolve$(a,b,c)$
Si $(a=0)$
Alors Affine$(b,c)$
Sinon Resolve$(a,b,c)$
FinSi
Avec comme fonctions:
Affine$(b,c)$
Si $(b=0)$
Alors
Si $(c=0)$
Alors Afficher $\mathbb{R}$
Sinon Afficher $\emptyset$
FinSi
Sinon Afficher $-c/b$
FinSi
Et pour la dernière:
Resolve$(a,b,c)$
$\Delta \leftarrow b^2-4ac$
Si $(\Delta<0)$
Alors Afficher $\emptyset$
Sinon
$\displaystyle m \leftarrow \frac{1}{2a}$
$r \leftarrow -mb$
$s \leftarrow m\sqrt{\Delta}$
Si $(\Delta=0)$
Alors Afficher $r$
Sinon Afficher $r-s$ et $r+s$
FinSi
FinSi
Remarquez que le premier branchement conditionnel englobe tout l'algorithme Resolve sauf la première affectation, la seconde instruction conditionnelle est entièrement incluse dans la première.
Question 3
Que se passe-t-il si au lieu d'affecter $s$ nous écrivons $\Delta \leftarrow m\sqrt{\Delta}$?
Que doit-on modifier par la suite pour garder l'algorithme valable?
Qu'a-t-on gagné avec cette technique? Expliquer pourquoi cela est possible.
Nature de l'entrée-sortie
Un programmeur ne fabrique pas ses fonctions isolémment pour ne s'en servir que dans une situation. Telle que nous venons de décomposer notre résolution, il est possible de réutiliser la fonction Affine chaque fois que la résolution d'une équation affine se présente. De même, si au cours d'un autre algorithme il apparaît une équation du second degré avec un coefficient $a$ déjà connu comme étant non nul, nous pourrons faire appel directement à Resolve sans passer par $R$.
Là intervient un point fondamental de la conception d'un algorithme. Quelle est la nature des objets acceptés en entrées et ceux qui seront en sortie. Dans notre cas, nous avons supposé que l'utilisateur veillera seul à entrer des nombres décimaux. S'il décide de lancer la fonction $R$ ou l'une de ses sous-fonctions avec autre chose que des nombres il recevra un message d'erreur.
Quant à la sortie, elle est décidée par le problème à résoudre. Pour une réutilisation efficace de l'algorithme, il est possible que nous ayons besoin non d'un affichage mais d'une variable portant en elle le résultat. Ainsi on écrirait: \[ X \leftarrow R(1,-2,1) \] dans un autre programme. Ce dernier lancerait $R$ pour calculer la valeur de $X$. Etant donné qu'il y a deux solutions il ne peut choisir de sortir comme valeur un objet $X$ réel mais un tableau à deux cases. La première $X[1]$ sera la plus petite des racines et $X[2]$ la plus grande.
Si le résultat est l'ensemble vide, $X$ peut être décrit par un affichage ou le lancement d'un message d'erreur au cas où la valeur de $X$ serait appelée ailleurs dans le programme, pour préciser à l'utilisateur qu'on ne peut poursuivre puisque $X$ n'existe pas. De même si $X$ reçoit la valeur $R(0,0,0)$ alors il pourrait être utile d'indiquer qu'il n'y pas de valeur fixée pour $X$ et proposer d'en choisir une. Dans le cas où $X$ vaut $(-c/b)$ ou $(mb)$ alors on pourra créer un nombre $X$ recevant cette valeur. Dans ce cas il faut retirer des algorithmes Affine et Resolve l'affichage et y placer une affectation:
Affine$(b,c) \leftarrow -c/b$
Et
Resolve$(a,b,c) \leftarrow mb$