Magazine Histoire

Algorithme

Par Guy Marion

Nom qui vient de « Al Khwarizmi » , surnom du mathématicien arabe Muhammad Ibn Musa (IXè siècle) , né à Khwarizem, en Ousbekistan.

Définition du dictionnaire des Mathématiques de A. Bouvier, M George, F Le Lionnais :

Suite finie de règles à appliquer,

  • dans un ordre déterminé,
  • à un nombre fini de données,
  • en un nombre fini d’étapes
  • pour arriver avec certitude, à un certain résultat et cela indépendamment des données.

Définition donnée par Wikipédia :

Un algorithme est un moyen pour un humain de présenter la résolution par calcul d’un problème à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En effet, un algorithme est un énoncé dans un langage bien défini d’une suite d’opérations permettant de résoudre par calcul un problème. Si ces opérations s’exécutent en séquence, on parle d’algorithme séquentiel. Si les opérations s’exécutent sur plusieurs processeurs en parallèle, on parle d’algorithme parallèle. Si les tâches s’exécutent sur un réseau de processeurs on parle d’algorithme réparti ou distribué.

Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l’époque des Babyloniens, pour des calculs concernant le commerce et les impôts.

L’algorithme le plus célèbre est celui qui se trouve dans le livre 7 des Éléments d’Euclide. Il permet de trouver le plus grand diviseur commun, ou PGCD, de deux nombres.

Soient deux entiers naturels a et b, dont on cherche le PGCD. Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut.

On commence par calculer le reste de la division de a par b, qu'on note r ; puis on remplace a par b, puis b par r, et on ré-applique le procédé depuis le début.

On obtient ainsi une suite, qui vaut 0 à un certain rang ; le PGCD cherché est le dernier reste non nul.

Calculons, par exemple, le pgcd de 1071 et 1029 (égal à 21) par cet algorithme avec les étapes suivantes :

a b r


1071 1029 42

1029 42 21

42 21 0


Vous pourriez être intéressé par :

Retour à La Une de Logo Paperblog

Ces articles peuvent vous intéresser :

A propos de l’auteur


Guy Marion 246 partages Voir son profil
Voir son blog

l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte