Eq. scd degré II

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.