- 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
Toute procédure est-elle algorithmique ?
Pour rendre compte de cette notion élargie d’algorithme telle qu’elle est employée dans la pratique informatique et mathématique contemporaine, il ne faut plus regarder les algorithmes comme étant définis à partir des objets spécifiques sur lesquels ils opèrent, ni à partir des instructions ou des opérations primitives fixées pour manipuler ce type particulier d’objets – par exemple, manipuler des chiffres indo-arabes n’est pas la même chose que manipuler des chiffres romains – mais il faut les considérer d’un point de vue plus général : celui des actions ou des étapes procédurales qu’ils mettent en place, où une action ou étape procédurale n’est pas nécessairement primitive, mais peut comporter l’emploi de plusieurs instructions ou opérations primitives. C’est l’idée qui guide les analyses conceptuelles et les tentatives de définition formelle de la notion d’algorithme entreprises par le mathématicien soviétique Andreï Kolmogorov (1903–1987), avec son élève Vladimir Uspensky (1930–2018), en 1958, et poursuivies plus récemment, dans les années 1990 et 2000, par le logicien et informaticien soviétique puis américain Yuri Gurevich (né en1940) et par le mathématicien et logicien gréco-américain Yiannis Moschovakis (né en 1938). Dans ce cadre, l’action ou l’étape procédurale n'est plus fixée de manière absolue (une fois pour toutes) ; ce qui l’est, c’est plutôt l’unité que nous, les usagers, considérons comme pertinente pour décrire (et comprendre) une procédure algorithmique.
Par exemple, dans le calcul du PGCD, nous pouvons considérer que l’opération consistant à extraire le reste de la division euclidienne correspond à une seule étape de la procédure de calcul, ou bien qu’il s’agit d’une procédure plus complexe impliquant des soustractions itérées (et comportant donc plusieurs sous-étapes). Autrement dit, nous pouvons considérer que le reste de la division de 13 par 4 est obtenu en une seule étape, au moyen de l’opération modulo (mod), à savoir (13 mod 4) = 1, ce qui est naturel dans la pratique informatique actuelle. Mais nous pouvons aussi considérer qu’il s’agit du résultat de plusieurs étapes de soustraction opérées à la suite, à savoir (((13 – 4) – 4) – 4) = 1, ce qui est la manière décrite par Euclide dans les Éléments (livre VII, propositions 1-2). De manière analogue, en géométrie, on peut considérer comme étant élémentaires les opérations qui consistent à tracer un segment ou un cercle, indépendamment de la question de savoir comment est constitué un segment ou un cercle. On peut alors admettre qu’un cercle est composé d’un ensemble infini de points et considérer néanmoins l’action de tracer le cercle comme étant exécutée en une seule étape, même si elle passe par une infinité de points.
Mais alors, si décrire un algorithme revient à expliciter un agencement ordonné (ou structuré) d’actions, indépendamment de la question de savoir si ces actions sont analysables ultérieurement et indépendamment des entités sur lesquelles elles opèrent, pourquoi ne pas considérer une recette de cuisine comme un algorithme ? C’est souvent via cette idée de recette de cuisine qu’on illustre la notion d’algorithme. En effet, les recettes partagent certaines de leurs propriétés caractéristiques, comme l’abstraction de certaines contraintes matérielles concernant leur réalisation : dans le cas des recettes, on remarquera que l’on ne précise pas la marque du four, la longueur du manche du fouet utilisé, etc. Mais comprendre une recette comme un algorithme n’est pas finalement si évident. La spécification de certains détails dans la description de la procédure et de certaines conditions de réalisation (comme la température de la pièce dans laquelle on réalise la recette ou la taille du moule utilisé) peut être nécessaire[...]
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
