ALGORITHME

Informatique et élargissement de la notion d’algorithme

Les travaux de Turing ont joué un rôle fondateur dans la définition des principes théoriques de l’informatique. Mais c’est par la conception, la construction et la diffusion à large échelle des ordinateurs que la pratique informatique a pu pleinement se façonner et contribuer entre autres à l’évolution de la notion d’algorithme. La réalisation physique des ordinateurs a rendu nécessaires des choix techniques bien spécifiques, notamment au regard de l’architecture de ces derniers – c’est-à-dire leur structuration en différents composants, comme la mémoire, le processeur, les caches. Les contraintes matérielles ont imposé l’utilisation d’une représentation (ou codage) en binaire (0 et 1) des données, ainsi que le développement de différents langages de programmation, en relation avec les différentes architectures et les modèles de calcul considérés. Certains langages, comme le C, imposent une gestion explicite de la mémoire, alors que d’autres non – c’est le cas de Python, l’un des langages les plus employés de nos jours pour le développement d’intelligences artificielles. L’ensemble de ces éléments a mis en exergue l’idée que l’informatique traite de deux notions bien distinctes.

Les programmes

Les programmes, assimilables à un texte écrit, sont soumis aux contraintes d’un langage de programmation spécifique – et même, plus précisément, aux contraintes d’une version d’un tel langage, en fonction des mises à jour. Avec le choix du langage, on fixe, comme dans le cas des modèles de calcul, les opérations ou instructions primitives, ainsi qu’une manière spécifique de représenter les données sur lesquelles ces instructions agissent (qui ne sont plus forcément limitées aux entiers naturels, mais peuvent compter aussi les listes, les piles, les arbres, etc.).

Les algorithmes

Comparaison de programmes pour calculer la suite de Fibonacci - crédits : Encyclopædia Universalis France — Comparaison de programmes pour calculer la suite de Fibonacci
Encyclopædia Universalis France

Les algorithmes constituent une abstraction de la notion de programme libérée des contraintes syntaxiques du langage utilisé et de la représentation des données. Ainsi, il est possible d’écrire un programme calculant les éléments de la suite de Fibonacci dans deux langages de programmation différents, comme Python et C, tout en considérant qu’ils sont des réalisations, ou mieux, des implantations du même algorithme. De la même manière, deux programmes distincts écrits dans le même langage de programmation peuvent implanter le même algorithme, par exemple s’ils modifient l’ordre des instructions, si l’un utilise l’instruction « while » là où l’autre utilise l’instruction « for », ou encore si l’un utilise des variables pour enregistrer ses données là où l’autre utilisera un tableau.

Cette idée d’algorithme comme abstraction de la notion de programme apparaît clairement dans la pratique informatique, notamment dans les cours d’algorithmique, avec l’utilisation de ce qu’on appelle le pseudo-code : ainsi, on décrira rarement un algorithme en l’écrivant dans un langage de programmation spécifique, mais on en donnera une description informelle dans un langage plus proche du langage naturel.

Ce point de vue, qui s’appuie sur la pratique informatique, mène à un élargissement de la notion d’algorithme. Tout d’abord, un programme ne calcule pas toujours une fonction, et encore moins une fonction sur les entiers. Un programme peut avoir pour effet la modification de son environnement : modification de la mémoire, affichage sur un écran, gestion de périphériques, etc. Beaucoup de programmes ont également pour objectif la communication entre plusieurs « agents » : un serveur exécute un programme qui ne calcule pas une fonction mais reçoit des signaux externes via un ou plusieurs canaux de transmission d’informations (provenant par exemple d’autres machines) pour les redistribuer via (potentiellement) d’autres canaux. Ainsi, le domaine de ce qu’on appelle l’algorithmique[...]

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écouvrez nos offres

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

Carte mentale
Élargissez votre recherche dans Universalis

Classification

Médias

Illustration allégorique de l’arithmétique - crédits : Wellcome Collection ; CCO — Illustration allégorique de l’arithmétique

Wellcome Collection ; CCO

Alan Turing - crédits : History/ Universal Images Group/ Getty Images — Alan Turing

History/ Universal Images Group/ Getty Images

Max Mathews, Don Kruth, Steve Wozniak et Allan Alcorn - crédits : MediaNews Group/ Bay Area News/ Getty Images — Max Mathews, Don Kruth, Steve Wozniak et Allan Alcorn

MediaNews Group/ Bay Area News/ Getty Images

Afficher les 4 médias de l'article ALGORITHME

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