27 novembre 2007

 

Algorithme

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,

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


Libellés :




Links to this post:

Créer un lien



<< Home

This page is powered by Blogger. Isn't yours?