- 1. De la mer d’Aral à Pise : le triomphe du calcul avec les chiffres indo-arabes
- 2. Algorithmes et théorie de la calculabilité : à l’ombre d’Alan Turing
- 3. Informatique et élargissement de la notion d’algorithme
- 4. Les algorithmes dans la pratique mathématique contemporaine
- 5. Toute procédure est-elle algorithmique ?
- 6. Les algorithmes aujourd’hui : des agents sociaux et culturels ?
- 7. Bibliographie
ALGORITHME
Les algorithmes dans la pratique mathématique contemporaine
Cet élargissement de la notion d’algorithme par la pratique informatique s’observe également dans certains usages qu’en font les pratiques contemporaines en mathématiques. Considérons par exemple l’algorithme de calcul du plus grand commun diviseur (PGCD). On peut l’utiliser non seulement sur les entiers, mais plus généralement sur les éléments d’un anneau euclidien quelconque. On est alors en train d’accepter l’idée que l’algorithme du calcul du PGCD s’applique à des entités mathématiques abstraites. En effet, les éléments d’un anneau euclidien ne sont pas identifiés par une représentation symbolique spécifique (comme c’est le cas des entiers), mais plutôt par les opérations fixées par un système d’axiomes qu’on peut leur appliquer.
Un autre exemple est donné par ce qu’on appelle les algorithmes de recherche d’un zéro d’une fonction, c’est-à-dire d’une valeur de x telle que f(x) = 0, dans le cadre de l’analyse numérique telle que l’algorithme de la méthode de calcul de Newton (qui permet par exemple de calculer une approximation de la valeur x telle que 2x – 7 = 0). On retrouve ainsi l’idée d’un algorithme comme étant libéré de la représentation des entités sur lesquelles il opère : ces algorithmes opèrent notamment sur les nombres réels et un nombre réel n’est pas forcément représentable par une suite finie de symboles. De plus, effectuer un calcul sur les réels ne garantit pas a priori la terminaison de l’algorithme utilisé, bien que l’on puisse toujours décider d’arrêter celui-ci et extraire une approximation de la valeur recherchée. Une telle libéralisation de la notion d’algorithme dans la pratique mathématique conduit aussi à qualifier d'algorithmique, de manière quelque peu anachronique, les méthodes de construction géométrique, et plus particulièrement les méthodes de construction euclidienne à la règle et au compas : « La construction euclidienne répond à toutes les exigences d'un algorithme : elle est non ambiguë, correcte et terminante », écrivent Franco Preparata et Michael Shamos dans un livre consacré justement à la géométrie algorithmique (1985). Un exemple emblématique est donné par la construction décrite dans la première proposition du livre I des Éléments d’Euclide : on y donne une méthode pour construire pas à pas un triangle équilatéral à partir de deux actions élémentaires, tracer un segment entre deux points (au moyen d’une règle) et dessiner un cercle à partir de deux points (qui déterminent le rayon du cercle et donc l’ouverture du compas nécessaire pour le dessiner). Mais un segment et un cercle sont des entités qui, bien qu’elles puissent être graphiquement représentables par certaines figures, ne sont pas simplement juxtaposées les unes aux autres, comme le sont en revanche les représentations digitales ou discrètes (par exemple, les chiffres indo-arabes ou les symboles écrits sur une machine de Turing). Au contraire, les figures géométriques peuvent se couper et donner lieu à d’autres figures – par exemple, deux cercles peuvent se couper et donner lieu à des demi-cercles et des points d’intersection. En ce sens, il s’agit d’entités ayant des propriétés de continuité. Accepter l’idée que les constructions euclidiennes sont des algorithmes, c’est accepter l’idée que les algorithmes peuvent opérer sur des entités continues et pas seulement discrètes.
L'exemple de la construction d’un triangle équilatéral soulève par ailleurs un autre point crucial dans l’élargissement de la notion d'algorithme. Cette construction ne correspond pas naturellement au calcul d’une fonction. Si deux sommets du triangle qui est construit correspondent aux extrémités du segment donné comme point de départ de la construction, le troisième sommet de ce triangle[...]
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éjà abonné ? Se connecter
Écrit par
- Alberto NAIBO : docteur en philosophie, maître de conférences en logique à l'Institut d'histoire et de philosophie des sciences et des techniques, université Paris I-Panthéon Sorbonne
- Thomas SEILLER : docteur en mathématiques, université d'Aix-Marseille, chargé de recherche au CNRS
Classification
Médias
Illustration allégorique de l’arithmétique
Wellcome Collection ; CCO
Alan Turing
History/ Universal Images Group/ Getty Images
Max Mathews, Don Kruth, Steve Wozniak et Allan Alcorn
MediaNews Group/ Bay Area News/ Getty Images
Autres références
-
ALGORITHME DE TRANSFORMÉE DE FOURIER RAPIDE (J. W. Cooley et J. W. Tukey)
- Écrit par Bernard PIRE
- 348 mots
La publication en 1965, dans le journal Mathematics of Computation de la Société américaine de mathématiques (AMS), de l’« Algorithme de transformée de Fourier rapide » par les mathématiciens américains James William Cooley (1926-2016) et John Wilder Tuckey (1915-2000) révolutionne l’automatisation...
-
ALGORITHMIQUE
- Écrit par Philippe COLLARD et Philippe FLAJOLET
- 6 654 mots
- 3 médias
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...
-
ALGORITHMIQUE MUSIQUE
- Écrit par Alain FÉRON
- 394 mots
- 1 média
Un algorithme est « une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, sans indétermination, en un nombre fini d'étapes, à un certain résultat et cela indépendamment des données » (Michel Philippot). En mathématiques, l'algorithme d'Euclide (recherche...
-
APPRENTISSAGE PROFOND ou DEEP LEARNING
- Écrit par Jean-Gabriel GANASCIA
- 2 646 mots
- 1 média
En 1957, un psychologue américain, Frank Rosenblatt (1928-1971), met au point un algorithme d’apprentissage pour des réseaux de neurones formels à deux couches qu’il appelle des « perceptrons », car ils reproduisent selon lui les capacités de perception des rétines. - Afficher les 48 références
