- 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
Algorithmes et théorie de la calculabilité : à l’ombre d’Alan Turing
Au début du xxe siècle, on retrouve l’idée qu’un calcul s’effectue au moyen de manipulations séquentielles de type symbolique dans l’analyse de la notion de calculabilité que propose le mathématicien et logicien britannique Alan Turing (1912–1954). Ce dernier prend comme point de départ de son analyse ce que fait un agent humain lorsqu’il est en train d’effectuer un calcul, et il écrit dans un article en 1936 : « En général, on effectue un calcul en inscrivant certains symboles sur une feuille, que l’on peut supposer divisée en cases comme un cahier d’écolier. » Cette analyse mène Turing à modéliser le calcul au moyen de machines « idéalisées », ce qu’on appelle aujourd’hui les machines de Turing. Elles sont constituées par un ruban infini et divisé en cases, ainsi que par une tête de lecture/écriture qui opère sur une case, en lisant, écrivant ou effaçant un symbole à la fois, le nombre de symboles disponibles étant fini (par exemple, 0 et 1, ce qui permet une représentation positionnelle des entiers en base 2). Elle peut aussi se déplacer à gauche ou à droite d’une case à la fois. Cependant, Turing n’emploie jamais le mot « algorithme ». Il dit plutôt que ses machines permettent de formaliser la notion intuitive de « calculabilité effective » et, plus précisément, ce qu’on appelle les « fonctions effectivement calculables », autrement dit les fonctions (des entiers vers les entiers) dont les valeurs peuvent être calculées sans recourir à aucune forme d’ingéniosité. Il suffit en effet de suivre une méthode dont chaque étape est prédéterminée et définie à partir d’opérations « suffisamment élémentaires pour pouvoir être accomplies de manière exacte et en un temps fini », comme l'affirme l’informaticien américain Donald Knuth (né en 1938), figure majeure de l’algorithmique au xxe siècle, dans l’édition de 1997 de son livre The Art of Computer Programming.
Alan Turing
History/ Universal Images Group/ Getty Images
Max Mathews, Don Kruth, Steve Wozniak et Allan Alcorn
MediaNews Group/ Bay Area News/ Getty Images
En 1937, Alonzo Church (1903–1995), mathématicien et logicien américain qui avait encadré le travail de doctorat de Turing, parle en revanche, au sujet de l’article de celui-ci de 1936, de fonction effectivement calculable lorsqu’« il existe un algorithme pour le calcul de ses valeurs », et considère que les machines de Turing ont l’« avantage de rendre immédiatement évidente l’identification avec l’effectivité au sens ordinaire (non explicitement défini) ». C’est pourquoi plusieurs auteurs ont pensé que l’analyse de Turing pouvait être utilisée pour caractériser de manière formelle la notion d’algorithme. Par exemple, dans un livre sur l’histoire des algorithmes dirigé par Jean-Luc Chabert (1re éd. 1994), on lit : « La machine de Turing se présente donc comme une formalisation de l’idée intuitive que nous nous faisons d’un algorithme de calcul. » Deux types d’arguments semblent toutefois pouvoir contredire ou du moins nuancer cette conclusion.
Premièrement, il existe des machines de Turing qui, pour certaines entrées (inputs), ne s’arrêtent jamais, au sens où elles continuent à calculer à l’infini, sans qu’aucune sortie (output) puisse être atteinte en un nombre fini d’étapes de calcul. Il s’agit de machines calculant des fonctions partielles, dans lesquelles certaines entrées ne sont associées à aucune sortie (comme la fonction qui associe à un entier x l’entier n tel que n2 = x, lorsque celui-ci existe ; par exemple, quand x = 3, il n’existe pas un tel entier n et la fonction n’a donc pas de sortie). Or la notion d’algorithme est souvent associée au respect d’une condition de « terminaison ». Une telle condition, formulée sous le nom de « finitude » est explicitement imposée par Knuth, dans l’ouvrage mentionné précédemment : « Un algorithme doit toujours se terminer après[...]
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
