Table des matières
Algorithmes - L'exemple d'Al Kwarizmi
Définition du mot algorithme
Larousse : Ensemble de règles opératoires dont l'application permet de résoudre un problème énoncé au moyen d'un nombre fini d'opérations. Un algorithme peut être traduit, grâce à un langage de programmation, en un programme exécutable par un ordinateur.
Wikipedia : Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre une classe de problèmes.
Académie : Méthode de calcul qui indique la démarche à suivre pour résoudre une série de problèmes équivalents en appliquant dans un ordre précis une suite finie de règles.
L'algorithme est donc une sorte de recette qui énonce clairement la façon de résoudre un problème par une succession d'actions simples. Pour faire une image, on peut voir l'algorithme comme une recette de cuisine :
- si on me dit “faites une pâte brisée”, je ne sais pas faire,
- mais si me dit “prenez 300g de farine, 10g de sel, mélangez-les, ajoutez 150g de beurre…” là je sais.
Rachid Guerraoui, spécialiste d'algorithmie, fait la présentation suivante – je résume un peu : Dans toutes les sociétés où le calcul a pris de l'importance, certains individus sont plus capables que d'autres de faire les calculs et on peut les qualifier de mathématiciens. Certains de ces mathématiciens peuvent être qualifiés d'altruistes parce qu'ils donnent aux autres des méthodes pour résoudre des problèmes. Ainsi, Euclide donne une méthode pour trouver le PGCD de deux nombres. Les utilisateurs de la méthode ne comprennent pas forcément pourquoi la méthode fonctionne mais ils peuvent l'utiliser. Cette méthode est un algorithme.
Al Kwarizmi, inventeur des algorithmes et de l'algèbre
Le mot algorithme, comme le mot algèbre, vient du nom d'un mathématicien perse du IXe siècle, Al Kwarizmi. L'une de ses œuvres principales est Abrégé du calcul par la restauration et la comparaison publié entre 813 et 833.
Ce livre est le point de départ de l'algèbre, Al Kwarizmi y raisonne sur des équations en donnant des méthodes de résolution, c'est à dire des algorithmes.
Exemple d'algorithme proposé par Al Kwarizmi
Problème
On trouve dans l'ouvrage d'Al Kwarizmi la méthode suivante :
Les carrés plus les racines égaux à un nombre, c'est par exemple lorsque tu dis : un carré plus dix racines sont égaux à trente-neuf dirhams, c'est-à-dire que si on ajoute à un carré quelconque une quantité égale à dix racines, le tout sera trente-neuf.
Al Kwarizmi évoque des problèmes concrets, qui peuvent être liés à une somme d'argent, d'où la présence de dirham. Par racine, il faut comprendre l'inconnue $x$ ; par carré, comprendre le carré de l'inconnue $x^2$. Reformulé dans un langage plus moderne, l'exemple devient :
$$x^2 + 10x = 39$$
et le cas général est :
$$x^2 + a\cdot x = b$$
Algorithme proposé
Partage en deux moitiés le nombre des racines ; il vient, dans ce problème, cinq, que tu multiplies par lui-même ; on a vingt-cinq ; tu l'ajoutes à trente-neuf, on aura soixante-quatre ; tu prends la racine qui est huit, de laquelle tu soustrais la moitié du nombre des racines, qui est cinq. Il reste trois, qui est la racine du carré que tu veux, et le carré est neuf.
L'algorithme est donné sur l'exemple. On peut leur reformuler en langage moderne :
ENTRÉES : a et b
SORTIE : solution de x^2 + a * x = b // Exemple du cas x^2 + 10x = 39
DÉBUT
diviser a par 2 // ->
mettre au carré // ->
ajouter b // ->
prendre la racine carrée // ->
soustraire a/2 // ->
RENVOYER résultat // -> RENVOYER ...
FIN
Exercice : Compléter l'exécution de cet algorithme sur le cas exemple.
Version plus moderne
Il n'est pas utile de découper le calcul en 5 étapes, on peut écrire directement
ENTRÉES : a et b
SORTIE : solution de x^2 + a * x = b
DÉBUT
RENVOYER (racine(a^2 + 4*b) - a) / 2
FIN
Classe de problème
Supposez que j'écrive un algorithme pour résoudre seulement l'équation $3x^2 + 4x - 10 = 0$.
Une fois que cet algorithme a été exécuté, le problème est résolu. Il ne sert plus à rien. Ce genre d'algorithme n'a pas forcément grand intérêt.
L'algorithme d'Al Kwarizmi est mieux : il permet de résoudre toutes les équations qui respectent la forme $x^2 + a \cdot x = b$. C'est une classe de problème.
Très important : L'algorithme fonctionne alors même que, au moment de l'écrire, on ne connaît ni $a$ ni $b$ ! On ne connaîtra $a$ et $b$ qu'au moment d'utiliser l'algorithme.
Très important que vous le compreniez car cela revient souvent en programmation. Ici on peut raisonner sur $a$ et $b$ et les calculs que l'on fait avec, sans avoir besoin de connaître leur valeur. Je peux énoncer qu'il faut diviser $a$ par 2 sans connaître $a$. Au moment d'utiliser l'algorithme, je saurais que $a$ vaut par exemple 10 et alors je pourrais faire le calcul $\frac{a}{2} = 5$.
Pas besoin d'ordinateur
Cet algorithme a été inventé au IXe siècle, donc bien avant qu'on ait l'idée et la possibilité d'inventer des ordinateurs. Un algorithme repose sur des instructions élémentaires qui doivent pouvoir être exécutées. Si un humain peut exécuter ces instructions, alors il peut exécuter l'algorithme.
Il sera souvent utile que vous soyez capable d'exécuter mentalement un algorithme, ou avec un papier et un crayon. Parfois, on traduit l'algorithme en programme – ce n'est pas difficile – puis on essaie d'exécuter le programme, alors que l'on n'a même pas encore chercher à comprendre ce que faisait l'algorithme. C'est une mauvaise approche.
Dans le cas de l'algorithme d'Al Kwarizmi, il ne s'agit que de calculs élémentaires et un humain peut donc les faire.
Bien sûr, les algorithmes prennent un intérêt nouveau avec la possibilité de les exécuter sur des machines spécialisées. Les algorithmes pourront alors être vus comme des recettes permettant à des machines sans la moindre intelligence ou imagination, de résoudre des problèmes complexes.
Démonstration
L'algorithme d'Al Kwarizmi répond à un problème mathématique. Il est possible de prouver avec une rigueur mathématique que cet algorithme est juste.
Un algorithme est un objet théorique. Il permet de raisonner théoriquement et de faire des démonstration qui ont, encore une fois, une rigueur mathématique.
Préconditions et Postconditions
Pour que l'algorithme soit juste, il y a des conditions sous-entendues. Pour vous en rendre compte,
Exercice :
- Vérifiez que $-13$ est également solution de $x^2 + 10x = 39$.
- Que se passe-t-il dans le cas de l'équation $x^2 + 10x = -26$ ?
Il y a donc des hypothèses à la fois sur les entrées $a$ et $b$ qui doivent être positives, et sur la solution qui doit l'être également. On peut prouver que si $a$ et $b$ sont des réels positifs, il existe bien une et une seule solution positive et c'est elle que nous renvoie l'algorithme.
ENTRÉES : a et b, réels positifs
SORTIE : solution réelle positive de x^2 + a * x = b
DÉBUT
RENVOYER (racine(a^2 + 4*b) - a) / 2
FIN
- La condition sur les entrées
aetbest une précondition, - la condition sur la sortie est une postcondition.
Version complète
L'algorithme précédent avait des préconditions et une postcondition, c'est à dire qu'il ne donnait pas toutes les solutions et qu'il ne fonctionnait pas pour toutes les valeurs d'entrées. On peut le rendre plus général en adaptant le calcul fait en fonction des cas.
ENTRÉES : a et b, réels
SORTIE : solutions réelles de x^2 + a * x = b, si elles existent
DÉBUT
calculer delta = a^2 + 4*b
SI delta > 0 ALORS
x1 = (-a - racine(delta)) / 2
x2 = (-a + racine(delta)) / 2
RENVOYER x1 et x2
SINON, SI delta = 0 ALORS
x1 = -a/2
RENVOYER x1
SINON
RENVOYER rien
FIN
Exercice : Essayez l'algorithme pour les cas suivants :
- $x^2 + 10x = 39$
- $x^2 + 10x = -25$
- $x^2 + 10x = -26$
Vous avez pu remarquer que tous les algorithmes utilisaient des marges. Par exemple ci-dessus, les marges permettent de savoir les lignes qui vont être exécutées dans le cas delta > 0.
Ces marges sont appelées indentations et sont extrêmement importantes en Python.