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.
1. 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 re […]
… pour nos abonnés, l'article se prolonge sur 10 pages…
