27 novembre 2007
Algorithme
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 |
Libellés : Histoire des mathématiques
