ALGORITHMIQUE

L'objet de l'algorithmique est la conception, l'évaluation et l'optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite d'opérations élémentaires obéissant à un enchaînement déterminé.

Le terme d'algorithme tire lui-même son origine du nom du mathématicien persan Al Khwārizmī (env. 820) dont le traité d'arithmétique servit à transmettre à l'Occident les règles de calcul sur la représentation décimale des nombres antérieurement découvertes par les mathématiciens de l'Inde.

Divers algorithmes ont été en fait connus dès l'Antiquité dans le domaine de l'arithmétique ou de la géométrie, parmi lesquels, notamment :

– les règles de calcul de longueur d'arcs et de surfaces des civilisations égyptienne et grecque ;

– plusieurs méthodes de résolution d'équations en nombres entiers, à la suite des travaux de Diophante d'Alexandrie au iv^e siècle ;

– l'algorithme d'Euclide (env. 300 av. J.-C.) qui permet le calcul du plus grand commun diviseur de deux nombres ;

– le schéma de calcul du nombre π dû à Archimède.

Ensuite ont été étudiées les méthodes numériques de résolution d'équations algébriques (algorithme de Newton, méthode d'élimination de Gauss), puis d'équations différentielles. Enfin, l'avènement de calculateurs électroniques, à l'issue de la Seconde Guerre mondiale, a entraîné un renouvellement complet de l'algorithmique, appliquée désormais soit à des problèmes de taille bien supérieure à celle des problèmes traités manuellement (d'où la nécessité de méthodes nouvelles), soit surtout à des types de problèmes nouveaux, comme le tri, la recherche rapide d'informations non numériques (base de données) ou l'optimisation combinatoire.

L'exemple du calcul de π

La question du calcul du nombre π = 3,141 592 6... (rapport de la circonférence au diamètre d'un cercle), étudiée dès l'Antiquité, est caractéristique des problèmes généraux rencontrés en algorithmique.

Historiquement, une fois reconnue l'existence d'un rapport constant entre circonférence et diamètre d'un cercle, la première approche a consisté à déterminer le nombre π par des mesures physiques : l'on obtient de la sorte des valeurs approchées du type 3 (comme dans la Bible), 3 et 1/7 ou 3 et 1/8. Cependant à ce stade, rien n'indique que π soit un nombre calculable, c'est-à-dire qu'une méthode existe qui permette de le déterminer avec une précision arbitrairement grande. Il revient à Archimède (287-212 av. J.-C.) d'avoir le premier proposé un algorithme de calcul de π.

Le principe de l'algorithme d'Archimède est le suivant : Soit p_n le périmètre d'un polygone régulier de n côtés inscrit dans un cercle de rayon 1/2. Archimède observe que :

Partant des valeurs connues pour l'hexagone :

Dans un langage de spécification d'algorithmes, l'algorithme de calcul de π_m s'exprime sous la forme :

Pour un calcul effectif de π, on doit de plus déterminer la relation entre la valeur de m choisie et l'écart |π − π_m| ainsi que la précision nécessaire des calculs intermédiaires.

On observe par exemple que la formule (1) met en jeu la différence de deux quantités très voisines : 1 et √1 − u²_n. Une erreur relative, même faible, sur u_n entraîne donc une erreur beaucoup plus importante sur u_2n. De tels phénomènes sont courants en analyse numérique. On obtient des formules qui ne présentent pas ce caractère de difficulté en multipliant le radical :

Un algorithme d'un type très différent a été proposé par John Machin (1680-1752) et repose sur la formule :

Plus récemment, des formules d'addition du type de la formule de Machin ont servi de base au calcul sur ordinateur de plusieurs centaines de milliers de décimales de π : en 1966, Guilloud et Filliatre ont ainsi déterminé les cinq cent mille premières décimales de π.

Enfin, la méthode de calcul de π qui possède de bonnes propriétés de convergence a été trouvée par Salamin. Une analyse détaillée a montré que cette méthode rendait possible le calcul de plusieurs millions de décimales de π en quelques heures de calcul d'un ordinateur de grosse capacité, au prix cependant d'un effort de programmation important lié à la nécessité de procédures de multiplication générale et d'extraction de racine carrée (de telles procédures sont présentées au chapitre 2).

Dans l'algorithme de Salamin, le m-ième approximant de π s'obtient par la formule :

L'exemple de ce problème classique illustre les deux critères de l'intérêt d'un algorithme nouveau : soit permettre la résolution d'un problème pour lequel aucun schéma de calcul n'était préalablement connu (algorithme d'Archimède), soit permettre un calcul beaucoup plus rapide qu'il n'était possible au moyen des algorithmes précédemment connus.

La classification des diverses solutions algorithmiques à un problème donné s'effectue ainsi sur la base de leur complexité mesurée en nombre d'opérations élémentaires nécessaires à leur exécution. Pour les trois algorithmes précédents, une analyse montre par exemple que le nombre d'itérations nécessaires à l'obtention de π avec une précision de 10⁻ⁿ vaut approximativement :

On simplifie généralement les descriptions de complexité d'algorithmes en ne retenant que les ordres de grandeur correspondants. On utilise pour cela la notation de Landau, qui consiste à écrire :