Abonnez-vous à Universalis pour 1 euro

ALGORITHMIQUE

  • Article mis en ligne le
  • Modifié le
  • Écrit par et

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/n) pn 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 :

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

Algorithmes de calcul de p

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.

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

La suite de cet article est accessible aux abonnés

  • Des contenus variés, complets et fiables
  • Accessible sur tous les écrans
  • Pas de publicité

Découvrez nos offres

Déjà abonné ? Se connecter

Écrit par

  • : professeur des Universités
  • : ingénieur de recherche à l'Institut national de recherche en informatique et automatique (I.N.R.I.A.).

Classification

Pour citer cet article

Philippe COLLARD et Philippe FLAJOLET. ALGORITHMIQUE [en ligne]. In Encyclopædia Universalis. Disponible sur : (consulté le )

Article mis en ligne le et modifié le 14/03/2009

Médias

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

Algorithmes de calcul de p

Arbre binaire - crédits : Encyclopædia Universalis France

Arbre binaire

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

Échelle de complexité

Autres références

  • PRIX ABEL 2021

    • Écrit par
    • 1 014 mots
    • 2 médias

    Le prix Abel, qui distingue chaque année un ou plusieurs mathématiciens pour leurs contributions exceptionnelles au développement des mathématiques, a été décerné en 2021 au Hongrois László Lovász et à l’Israélien Avi Wigderson. Dix-neuf ans après la création de ce « prix Nobel des...

  • CALCUL, mathématique

    • Écrit par
    • 1 785 mots
    L'algorithmique s'attache à l'élaboration d'algorithmes efficaces pour résoudre les problèmes reconnus comme calculables. Cette discipline s'organise selon quelques grands principes généraux. Par exemple, pour traiter efficacement des problèmes de recherche d'information de forme complexe, il s'avère...
  • INDE (Arts et culture) - Les mathématiques

    • Écrit par
    • 5 429 mots
    • 3 médias
    À 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...
  • ITÉRATION, mathématique

    • Écrit par et
    • 830 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...

  • Afficher les 10 références