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.

Vérifier son algorithme

Cas d'erreur

Un exemple montrant que notre algorithme ne tient pas compte de tous les cas envisageables:

Question 1
Que se passe-t-il si l'on exécute Resolve(0,1,3)?
Décrire les étapes exactes de l'algorithme dans ce cas.

En revanche, nous considérons que l'utilisateur respecte toujours le type de variables acceptées par l'algorithme. Dans notre cas il s'agit de trois nombres réels. Bien sûr une machine ne sait gérer dans ses calculs que les nombres décimaux, et pour certains langages de programmation le nombre de chiffres pour un nombre donné est fixé à l'avance. De sorte que pour des cas particuliers de calculs complexes il faille définir les nombres sous forme de tableaux.

Terminaison: sortie assurée

Parmi les vérifications obligatoires avant de lancer un algorithme sur machine est sa terminaison. On pose la question de savoir s'il se finit ou non. Sans boucle apparente telle que la classique: Tantque (...) Faire (...) il est assez simple de montrer que notre programme se termine. Il suffit de voir qu'une instruction conditionnelle donne toujours une réponse en oui ou non après un certain temps d'exécution.

Dans notre cas, l'étude du signe des nombres est quasi instantannée, puisqu'ils sont enregistrés dans la mémoire comme tableau. Chaque case représente un bit de données en base 2. C'est-à-dire que la case est occupée par le chiffre 0 ou 1. Ces cases sont structurées en tableaux appelés octets. Un octet possède 8 bits. Enfin lorsqu'on enregistre une variable, elle peut faire appel à plus de place qu'un simple octet. La machine attribue une place dans la mémoire avec un certain nombre d'octets pour enregistrer la donnée. Elle lui attribue une adresse.

Pour en revenir à l'étude du signe, un nombre est découpé suivant plusieurs cases contenant chacune une information. Nous comptons en base 10 et ainsi le nombre 276 est compris comme étant: \[ 276 = 2 \times 10^2 + 7 \times 10^1 + 6 \times 10^0 \] Nous pourrions enregistré ce nombre dans une adresse mémoire avec trois cases occupées par les chiffres 2, 7 et 6 placés dans l'ordre. Seulement la machine ne comprend que le langage binaire, le zéro représentant un courant électrique nul et l'unité pour un courant non nul. Toute case mémoire élémentaire ne peut accepter que ces données. En somme l'ordinateur travaille en base 2. On décompose donc autrement le nombre: \[ 276 = 1 \times 2^8 + 1 \times 2^4 + 1 \times 2^2 \] Ce nombre peut être enregistré sur par exemple deux octets. Un octet est un tableau virtuel de 8 cases. Supposons que la case la plus à gauche enregistre le coefficient accompagnant $2^0$, ainsi la dernière case prend en charge le coefficient pour $2^7$. Il nous faut un second tableau pour insérer le terme en $2^8$. Il nous faut passer en écriture sur 16 bits d'information: \[ \begin{array}{|*{16}{c|}} \hline \\ 2^0 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} & 2^{15} \\ \hline \\ 0&0&1&0&1&0&0&0&1&0&0&0&0&0&0&0 \\ \hline \end{array} \] Ce qui permet d'écrire tous les nombres de 0 à $\displaystyle 2^{16}-1$. On se rend compte que cette méthode ne permet d'enregistrer que les nombres positifs. Pour l'utilisation des autres nombres il suffit d'affecter un bit à la donnée du signe. La première case servira à enregistrer le signe. Il vient alors qu'on peut sauvegarder sur 2 octets toujours autant de nombres mais cette fois-ci sur la plage suivante: \[ -2^{14}+1 \leftrightarrow 2^{14}-1 \]

Question 2
Combien y a-t-il d'entiers entre $-2^{14}+1$ et $2^{14}+1$, bornes comprises?

Question 3
Comment additionne-t-on deux nombres en binaire? Et la multiplication?
Exécuter l'exemple $111+33$ et $47-21$ avec des tableaux.

Cette dernière remarque nous montre alors en quoi consiste l'étude du signe d'un nombre. La machine pointe sur son tableau virtuel à la première case. Si le bit vaut 1 alors le nombre est strictement positif et s'il vaut 0 il est négatif. Il peut être nul, pour vérifier le pointeur se déplacera sur l'ensemble des cases, si un bit non nul apparaît la réponse est "strictement négatif" sinon ce sera "nul". Ceci n'est qu'un exemple, suivant les machines et langages les techniques diffèrent.

En tous les cas, l'étude de signe est simplement une lecture, donc un processus nécessitant peu de ressources car le nombre aussi grand soit-il n'est pas entièrement traité. Puisqu'il s'agit des seules vérifications effectuées, les deux tests se finiront en un temps raisonnables. De même les calculs susceptibles d'être effectués ne dépendent que de la taille des nombres entrés $a,b,c$. La machine disposant des opérations élémentaires arithmétiques ainsi que de l'extraction de la racine carrée, ces instructions se finiront.

Test compatible

Parmi l'ensemble des instructions demandées, des tests concernent le signe d'une expression, le calcul d'une racine carrée, une division... On doit prendre garde de bien vérifier que les objets manipulés correspondent aux types de données sur lesquelles on peut appliquer de telles opérations. Si $a$ est un tableau on ne pourra pas le multiplier. Si $b$ est un nombre on ne pourra pas tester s'il est vrai ou faux...

Coût de l'algorithme

Une fois que l'algorithme semble fonctionner correctement, la question la plus essentielle est son amélioration. A un problème donné (résolution des équations du second degré) plusieurs algorithmes peuvent y répondre. Et ils ne sont pas égaux en consommation de temps et d'espace.

Le temps est le nombre d'opérations élémentaires effectuées, si l'on suppose qu'une addition s'opère en un milliardième de seconde, le temps que l'on cherche est le nombre d'opérations rapportées sous forme d'additions. En effet, concernant les opérations arithmétiques, elles sont toutes des programmes se référant à l'addition. Une fois cette opération de base implémentée dans la machine, les autres en découlent suivant divers algorithmes.

L'espace est la quantité de mémoire nécessaire à l'exécution de l'algorithme en dehors de l'entrée des données. Chaque fois que la machine définira une nouvelle variable, il lui faudra affecter une nouvelle adresse mémoire et donc lui consacrer de la place. Pour quelques octets cela ne pose aucun soucis à nos capacités de stockage actuelles, mais si les nombres sont très grands et/ou si le nombre de variables nouvelles est gigantesque, c'est un problème dont il faut tenir compte.

Type d'opération

Dans notre algorithme, nous faisons appel à l'addition, la soustraction, multiplication, division et extraction de la racine carrée. Chacune dérive de l'addition suivant un algorithme interne à la machine ou que l'on peut soit même définir si l'on estime avoir une méthode plus rapide ou pour des cas très particuliers.

Si l'on considère un nombre de taille $n$ ( $n$ chiffres pour le définir) La multiplication entre deux nombres de cette taille peut nécessiter jusqu'à $n^2$ additions élémentaires. Celles-ci sont les additions d'unités, c'est-à-dire l'addition entre cases mémoire basiques. L'addition requiert $n$ opérations et une retenue éventuelle. Seulement, les algorithmes modernes ont amené la multiplication à avoisiner le temps d'exécution d'une addition. Sur des nombres de valeurs faibles la différence de temps est minime mais sur des grands nombres très utilisés en cryptographie, il subsiste une distinction.

La division euclidienne entre entiers est du même type que l'addition, il n'en est pas de même de la division entre décimaux. Un bon algorithme de division pourra demander 8 fois le temps d'exécution d'une seule multiplication. De même pour l'extraction de racines carrées.

L'affectation consiste à créer une variable si elle n'est pas déjà définie et d'enregistrer sa valeur, soit l'écriture de données sur le tableau virtuel présenté au début de l'article. Cette opération est aussi à prendre en compte dans le calcul de la complexité.

La comparaison entre deux nombres est aussi une opération, mais peu coûteuse, sauf là encore s'il s'agit d'étudier des grands nombres. Cela peut comprendre aussi l'étude du signe puisqu'il faut décider de sa nullité ou non.

Opérations pour chaque sortie

Une première approche consiste à observer ce qui arrive pour chaque sortie. Tout d'abord il y a une étape obligatoire quel que soit le chemin emprunté: l'affectation $\Delta \leftarrow b^2-4ac$. Elle nécessite:

• une affectation. Ouverture d'une adresse pour $\Delta$.
• une initialisation avec le calcul $b^2-4ac$. Trois multiplications et une différence.

La différence est assimilée à l'addition.

sortie1: Elle est atteinte après l'affectation de $\Delta$ et un test positif. Elle comprend en plus l'affichage d'un texte.

sortie2: Une affectation $\Delta$ suivi d'un test négatif puis un test positif. Un affichage de texte et l'affichage d'un nombre nécessitant le calcul de la racine $(-b/(2a))$. Soit une multiplication et une division.

sortie3: Une affectation $\Delta$, deux tests négatifs puis trois affichages. Un texte et deux calculs. Chaque racine nécessite une extraction de racine carrée, une somme, un produit et une division.

Question 4
Quelle est la situation où les calculs sont les plus nombreux? De même pour les comparaisons.
On note $M$ le temps d'exécution d'une addition. On considère que la multiplication prend un temps de $2M$. La division $5M$ et l'extraction d'une racine carré $7M$. Une affectation $M$, une comparaison entre deux nombres $M$. Donner en fonction de $M$ le résultat en temps pour chaque sortie.

Mémoire et calcul

La question est de savoir si pour chaque sortie nous avons la somme d'instructions la plus simple. Pour la sortie1 il sera difficile de faire mieux, pour la sortie2 de même. En revanche, lorsque nous calculons les deux racines en sortie3, l'extraction de la racine carrée de $\Delta$ est effectuée deux fois. Il peut être utile d'affecter un emplacement mémoire à ce calcul temporairement. L'affectation est une opération bien moins couteuse que la racine carrée surtout si les nombres en question sont grands.

De plus pour les sorties 2 et 3 il faut de toute façon calculer le nombre $\displaystyle \frac{-b}{2a}$. Là encore une adresse mémoire peut s'avérer utile. En général, ce qu'on gagne en temps, nous le dépensons en utilisation mémoire à condition que l'algorithme soit bien écrit. Il s'agit alors de trouver le bon compromis entre les deux dimensions temps-espace pour la résolution d'un problème.

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$

Création d'un tableau

L'objectif de cet algorithme est de construire une suite géométrique sur une machine. Nous voulons enregistrer chaque terme, bien sûr pour des raisons de limitations techniques il est impossible de tous les conserver, une suite devient une liste dans la mémoire d'un ordinateur. Choisissons pour notre exemple une liste de taille 11, c'est-à-dire pouvant accueillir 11 valeurs.

Le type de cette donnée est appelé tableau. Comme pour un nombre, il suffit de procéder à une affectation pour le créer, à ceci près qu'il faut préciser sa taille et pour certains langages le préremplir. Nous évitons ces détails et conservons uniquement la notion de taille.

Soit $u$ une suite géométrique de raison $q$ et de premier terme $u_0$ pour réutiliser les notations du chapitre 3. Le terme $u_i$ sera donc la case $u[i]$ dans le tableau, en particulier certains langages demandent aussi à indiquer la valeur du premier indice. On peut très bien le choisir nul comme dans notre cas, ou 1, ou même n'importe quel entier relatif. Les autres indices du tableau sont alors définis en fonction du premier. Un tableau à 11 entrées de premier indice 0 sera de la forme: \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline \\ u_0 & u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & u_7 & u_8 & u_9 & u_{10} \\ \hline \end{array} \] avec des nombres à la place de chaque terme $u_i$. Reste à savoir quelle place mémoire est accordée aux nombres dans le langage utilisé. L'un des plus connus, le langage C consacre de base aux entiers 32 bits d'information. C'est-à-dire 32 cases pour loger un chiffre binaire (0 ou 1) dans chacune d'elles.

Remarque

Avant de proposer quelques résolutions, nous faisons remarquer qu'il s'agit avant tout ici de mettre en évidence l'importance de la complexité dans un algorithme. Deux méthodes aboutissant au même résultat peuvent ne pas avoir la même efficacité. La gestion du calcul et de la mémoire est primordiale, l'exposé cherche avant tout à montrer comment il peut être astucieux de réutiliser un calcul, et comment gérer sa mémoire pour en utiliser le moins possible.

Résolution basique

Présentation

Nous appelons $G$ la fonction qui prend en argument un nombre réel (décimal pour la machine) noté $a$ et un autre réel $q$ pour renvoyer un tableau à 11 compartiments représentant les termes de la suite géométrique $u$ de premier terme $a$ et de raison $q$. La fonction créant un tableau sera notée Tab$(L)(p)$ où $L$ est la taille, $p$ l'indice du premier terme. On suppose qu'elle remplit le tableau avec le nombre 0 par défaut.

La manière forte consisterait à utiliser la formule explicite de la propriété 3.3 du cours. Elle a la même structure pour tout $i$ variant de 0 à 10, il suffit simplement de faire varier l'indice pour exprimer chacun des termes. Ce qui demande une boucle de type: Pour $i$ de 0 à 10 Faire (...) FinPour. Soit l'algorithme:

$G(a,q)$

$u \leftarrow \text{Tab}(11)(0)$

Pour $i$ de 0 à 10 Faire

$u[i] \leftarrow a \times q^{i}$

FinPour

Afficher $u$

Opérations élémentaires

L'algorithme démarre sur la création d'un tableau, il ne nous sera pas possible d'améliorer ceci puisque nous devons renvoyer un tableau, au mieux s'il existe une option permettant de préremplir l'ensemble des mêmes cases par une autre valeur que zéro par défaut, alors nous pouvons choisir de placer le terme $a$ partout et ainsi débuter les opérations sur $u[1]$.

Pour $u[0]$ il est effectué une affectation directe, nous ne tenons pas compte ni de l'opération $q^0$ ni de $(a\times 1)$

Pour $u[1]$ la recherche de $q^1$ est directe, ne nécessite aucune opération et $a\times q$ vaut pour une multiplication.

Pour $u[5]$ nous devons calculer $q^5=q\times q\times q\times q\times q$. Le processus enclenché calculera dans un premier temps $(q\times q)$ puis multipliera le résultat par $q$ et ainsi de suite: \[ \begin{array}{rl} u[i]= \left( (q\times q)\times q\right)\times q & \times q \\ \left( q^2\times q\right) \times q & \times q \\ q^3\times q & \times q \\  \qquad q^4 & \times q \\ & \; \; q^5 \end{array} \] Comptons le nombre d'opérations, il suffit pour cela de voir qu'il y en a autant que de lignes proposées ci-dessus moins un ou que de signes "$\times$" plus simplement. Il y en a quatre, à cela s'ajoute le dernier calcul: $q^i \times a$. Pour $u[5]$ il faut 5 opérations élémentaires de type multiplication.

Pour $u[i]$ avec $i$ variant de 0 à 10 il faut $i$ opérations. Le nombre d'opérations au final est la somme de celles qu'il a fallu effectuer pour chaque $u[i]$. Ceci est un résultat élémentaire applicable à toute boucle de type "Pour...FinPour". D'où le résultat: \[ \sum_{i=0}^{10} i = 0+1+2+3+4+5+6+7+8+9+10 = \frac{10\times 11}{2} \] il s'agit de la somme des dix premiers termes d'une suite arithmétique, et la plus simple qui est celle des entiers, en appliquant la formule vue en propriété 3.8 nous trouvons qu'il faut 55 multiplications.

Algorigramme

Pour représenter graphiquement cet algorithme, plutôt que de créer un élément pour la boucle "Pour(...) Faire(...) FinPour" nous utilisons son équivalent "TantQue(...) Faire(...) FinTantQue" dont voici l'analogie à appliquer:

• La boucle (i allant de 0 à 10) devient la condition (i différent de 11) précédée d'une initialisation (i reçoit 0)
• L'affectation $(u[i] \leftarrow q^ia)$ reste inchangée et on rajoute l'affectation $(i \leftarrow i+1)$

Il ne faut pas s'étonner de voir une variable recevoir en affectation sa propre valeur augmentée de 1. Dans l'affectation $(i \leftarrow i+1)$ le $i$ à gauche est une case mémoire dont le nom est $i$ alors que l'expression à droite $(i+1)$ est un nombre défini comme somme de la valeur contenue dans la case nommée $i$ avec l'entier 1. Une fois la somme effectuée, la nouvelle valeur dans la case $i$ devient l'ancienne incrémentée d'une unité. Chaque fois que l'on agit de la sorte en affectant à une variable une expression faisant intervenir sa valeur actuelle, celle-ci disparaît pour laisser place au résultat du calcul. L'avantage principal du procédé est de minimiser l'occupation de la mémoire. Dès lors qu'une valeur n'a plus d'intérêt pour le programme, l'adresse mémoire affectée peut servir à autre chose.

[[{"type":"media","view_mode":"media_original","fid":"160","attributes":{"alt":"","class":"media-image","height":"578","typeof":"foaf:Image","width":"495"}}]]

La structure de l'algorithme devient:

$G(q,a)$

$u \leftarrow \text{Tab}(11)(0)$

$i \leftarrow 0$

TantQue $i\neq 11$ Faire

$u[i] \leftarrow q^i \times a$
$i \leftarrow i+1$

FinTantQue

Afficher $u$

Optimiser l'algorithme

Voyons comment cet algorithme sera exécuté. Dans un premier temps deux variables sont créées, un tableau $u$ et un entier $i$. Ils sont initialisés directement au moment de l'affectation. Puis une boucle apparaît, elle se produit tant que $i$ est différent de 10. Au premier passage, l'entier vaut 0 et donc elle est enclenchée.

L'élément $u[0]$ reçoit $a$ en mémoire. Le calcul de $q^0$ ne compte pas, la machine possédant un algorithme de calcul de la puissance lui évitant tout calcul inutile, de même $(1 \times a)$ n'est pas effectué. Ensuite, l'indice $i$ est incrémenté, il vaut à présent 1 et la boucle est renvoyée au test.

Le test $(i=10)$ est encore négatif, et on lance les deux affectations: $u[1]$ reçoit le résultat de l'opération $(q\times a)$ et $i$ est incrémenté après ce calcul. On retourne au test, et c'est là qu'il y a un manque d'optimisation dans l'algorithme. L'élément $u[2]$ sera rempli par le résultat du calcul: \[ q \times q \times a \] Peu importe dans quel ordre la machine effectue l'opération, elle fera 2 multiplications alors que le nombre $(q\times a)$ a déjà été calculé.

Mémoriser un résultat

Lorsqu'on sait qu'un calcul intermédiaire peut s'avérer utile dans la suite d'un algorithme il est judicieux de le conserver en mémoire. S'il s'agit d'une ou deux réutilisations ce n'est pas forcément vital, mais supposons que nous ayons à créer un tableau à un million d'élément de $u_0$ à $u_{10^6}$ alors le nombre d'opérations répétées eût été énorme (environ cinq-cents milliards).

Dans notre petit exemple, nous voyons qu'à la fin $u[9]$ est calculé et mémorisé, mais lorsqu'on lance le calcul de l'élément suivant $u[10]$, il suffit de multiplier la valeur $u_9$ par la raison pour avoir le terme suivant de l'indice, au lieu de cela nous recommençons toutes les opérations. C'est un gâchis en temps qu'il faut savoir repérer.

La solution est simple et inscrite dans la définition récursive de la suite $u$: les premières étapes restent inchangées, il faut créer un tableau et initialiser un indice $i$ pour effectuer 11 tâches similaires. Le calcul de $u[i+1]$ consiste en celui de $u[i]$ que l'on multiplie par la raison $q$. Une fois le tableau créé nous initialisons le premier élément avec une affectation directe $(u[0] \leftarrow a)$ et on lance la boucle allant de 0 à 10, puisqu'on traite le terme $u_{i+1}$ lors du passage à l'étape $i$:

$G(a,q)$

$u \leftarrow \text{Tab}(11)(0)$
$u[0] \leftarrow a$
$i \leftarrow 0$

TantQue $i \neq 10$ Faire

$u[i+1] \leftarrow q \times u[i]$
$i \leftarrow i+1$

FinTantQue

Afficher $u$

Le gain en calcul est conséquent. Il n'y a qu'une multiplication par étape, il y a toujours l'addition $(i+1)$ mais sans importance comparé aux opérations possibles si les termes $u_n$ sont de grands nombres. On passe de 55 multiplications à 10 multiplications. Pour $10^{6}$ termes on obtiendrait autant de multiplications contre les $5\cdot 10^{11}$ avec la résolution basique.

Il y a autant d'opérations que d'affectations à exécuter, on en déduit qu'il s'agit de l'algorithme le moins coûteux en temps de calcul. L'objectif recherché de cet article n'était pas tant de résoudre un problème aussi simple mais d'illustrer l'importance du choix des formules de calcul pour atteindre la solution.

[[{"type":"media","view_mode":"media_original","fid":"161","attributes":{"alt":"","class":"media-image","height":"481","typeof":"foaf:Image","width":"544"}}]]