ALGORITHMIQUE

Carte mentale

Élargissez votre recherche dans Universalis

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 ive 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 pn 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 :

et il évalue la limite au moyen de la suite p6, p12, p24, p48... obtenue par doublements successifs du nombre de côtés. Soit un = (1/npn la longueur du côté d'un n-gone ; de propriétés géométriques élémentaires se déduit la récurrence :
laquelle se vérifie trigonométriquement grâce aux relations :
et à la formule générale :

Partant des valeurs connues pour l'hexagone :

on calcule de proche en proche par (1) les valeurs p6, p12, p24... par une succession d'opérations algébriques. Les premières valeurs des approximations πm = p6.2m ainsi obtenues sont présentées dans le tableau.

Algorithmes de calcul de p

Tableau : Algorithmes de calcul de p

Comparaison des approximations fournies par les trois algorithmes de calcul de p. 

Crédits : Encyclopædia Universalis France

Afficher

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

Cela correspond à une spécification complète d'un enchaînement d'opérations élémentaires (+, −, ×, ÷, √) sur les nombres réels.

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 − u2n. Une erreur relative, même faible, sur un entraîne donc une erreur beaucoup plus importante sur u2n. 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 :

par sa quantité conjuguée. Il vient, après simplification, la récurrence :
qui possède des propriétés de « stabilité » numérique (insensibilité aux erreurs d'arrondi) bien supérieures aux formules initiales. Un tel procédé a été en substance découvert par Viète (1593) et lui a permis de déterminer les sept premières décimales de π.

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

qui se vérifie au moyen de formules d'additions trigonométriques. La fonction Arc tg x est calculable par le développement :
L'algorithme de Machin consiste donc à calculer les approximations successives π ′ m de π données par :
où :
On observe sur le tableau que la convergence de π ′ m vers π est environ deux fois plus rapide que la convergence de πm vers π. Le calcul, de surcroît, ne nécessite pas l'extraction de racines carrées. L'algorithme résumé par les formules (4) et (5) pourrait être spécifié sous forme de programme analogue à (3). Il permit à J. Machin de déterminer les cent premières décimales de π.

Algorithmes de calcul de p

Tableau : Algorithmes de calcul de p

Comparaison des approximations fournies par les trois algorithmes de calcul de p. 

Crédits : Encyclopædia Universalis France

Afficher

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 :

où les an, bn sont calculés par les récurrences :
avec :
La justification de l'algorithme de Salamin repose sur la théorie des intégrales elliptiques. La convergence de π ″ m vers π est extrêmement rapide.

Algorithmes de calcul de p

Tableau : Algorithmes de calcul de p

Comparaison des approximations fournies par les trois algorithmes de calcul de p. 

Crédits : Encyclopædia Universalis France

Afficher

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 bas [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 11 pages

Médias de l’article

Algorithmes de calcul de p

Algorithmes de calcul de p
Crédits : Encyclopædia Universalis France

tableau

Arbre binaire

Arbre binaire
Crédits : Encyclopædia Universalis France

dessin

Échelle de complexité

Échelle de complexité
Crédits : Encyclopædia Universalis France

tableau

Afficher les 3 médias de l'article


Écrit par :

Classification

Autres références

«  ALGORITHMIQUE  » est également traité dans :

CALCUL, mathématique

  • Écrit par 
  • Philippe FLAJOLET
  •  • 1 782 mots

Dans le chapitre « Calculabilité et algorithmique »  : […] Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agi […] Lire la suite

INDE (Arts et culture) - Les mathématiques

  • Écrit par 
  • Agathe KELLER
  •  • 5 560 mots
  •  • 3 médias

Dans le chapitre « Mathématiciens à l’échelle du monde »  : […] À l’indépendance, la création de centres d’excellence pour les mathématiques et une école indienne très forte, notamment en algorithmique théorique, placent définitivement l’Inde nouvellement créée sur la carte mondiale des sciences mathématiques. Si un certain nombre de mathématiciens fameux émigrent vers les États-Unis et le Royaume-Uni (notamment Harish-Chandra), des liens particuliers sont au […] Lire la suite

ITÉRATION, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE, 
  • Universalis
  •  • 876 mots

Itérer signifie recommencer, faire à nouveau. Construire les nombres entiers peut être vu comme l'opération consistant à partir de zéro à itérer indéfiniment l'ajout d'une unité. Plus généralement, en mathématiques, lorsqu'une fonction ou opération est disponible, il est fréquent d'en envisager l'itération, celle-ci conduisant soit à de nouvelles fonctions ou opérations, soit à des structures ou p […] Lire la suite

KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)

  • Écrit par 
  • Jean-Luc VERLEY
  •  • 1 416 mots
  •  • 1 média

Dans le chapitre « Mathématiques appliquées »  : […] Kolmogorov a consacré de nombreuses publications aux équations aux dérivées partielles de la physique. Les équations de Navier-Stokes étaient le prototype des équations qui interviennent dans l'étude de la réaction-diffusion, la turbulence et la mécanique statistique. En 1931, Kolmogorov a introduit une vaste classe d'équations aux dérivées partielles dont le champ naturel est l'espace de Hilbert […] Lire la suite

NUMÉRIQUE ANALYSE

  • Écrit par 
  • Jean-Louis OVAERT, 
  • Jean-Luc VERLEY
  •  • 6 645 mots

Dans le chapitre « Le concept d'approximation »  : […] Dans toutes les questions de représentation des nombres et des fonctions, il faut distinguer la recherche de solutions « exactes » de celle d'algorithmes d'« approximation » d'une solution. Mais on notera que le champ du concept d'approximation recouvre non seulement les problèmes issus de l'analyse mais aussi certaines questions purement algébriques. Ainsi, en algèbre linéaire, les méthodes itéra […] Lire la suite

OPÉRATIONNELLE RECHERCHE

  • Écrit par 
  • Georges CULLMANN
  •  • 5 548 mots
  •  • 2 médias

Dans le chapitre « La théorie des graphes »  : […] La théorie des graphes s'introduit avec facilité dans la description de solutions concrètes où existent des combinaisons d'événements ou des successions temporelles (cf.  théorie des graphes ). Ses algorithmes sont de puissants auxiliaires pour l'analyste. D'abord parce que l'algorithme, prescription détaillée des opérations à réaliser pour obtenir avec certitude la solution d'un type de problème […] Lire la suite

PROGRAMMATION

  • Écrit par 
  • Jean-François MONIN
  •  • 7 832 mots

Dans le chapitre « Structures de contrôle et structures de données, systèmes de types »  : […] Un autre élément important en programmation se trouve dans la structuration des données à manipuler. L' algorithmique (science de la conception d'algorithmes) repose pour une bonne part sur la définition de structures de données efficaces et adaptées au problème ciblé. Les données élémentaires sont représentées par des mots mémoire de taille fixe : cela inclut les entiers (bornés), les caractères […] Lire la suite

RÉCURSIVITÉ, logique mathématique

  • Écrit par 
  • Kenneth Mc ALOON, 
  • Bernard JAULIN, 
  • Jean-Pierre RESSAYRE
  •  • 9 371 mots

Dans le chapitre « Définition logique »  : […] La définition arithmétique des fonctions récursives conduit à la définition logique. Soit L le langage de l'arithmétique, dont les symboles non logiques sont + pour désigner l'addition des entiers, × pour la multiplication, ≤ pour l'ordre, = pour l'égalité ; on ajoute, pour chaque entier n un symbole de constante n . Appelons formule de type Σ une formule dans laquelle n'apparaît ni négation, ni […] Lire la suite

RÉELS NOMBRES

  • Écrit par 
  • Jean DHOMBRES
  •  • 15 297 mots

Dans le chapitre « Une construction algorithmique »  : […] Voici enfin une autre construction de R qui ne passe pas par le corps des nombres rationnels, mais utilise une définition algorithmique de la soustraction sur le développement décimal illimité (cf. calcul infinitésimal  – Calcul à une variable, chap. 1). C'est un retour à Bombelli et à Stevin. Soit R l'ensemble de toutes les suites ( x n ) n ∈ Z (doublement infinies, c'est-à-dire indexées par Z […] Lire la suite

Voir aussi

Pour citer l’article

Philippe COLLARD, Philippe FLAJOLET, « ALGORITHMIQUE », Encyclopædia Universalis [en ligne], consulté le 30 novembre 2021. URL : https://www.universalis.fr/encyclopedie/algorithmique/