algorithme

Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».

Logique, Philosophie des Sciences

Notion de base de l'algorithmique (celle-ci consiste en la conception et l'optimisation des méthodes de calcul en mathématiques et informatique).

Un algorithme consiste en un schéma de calcul spécifiant une suite finie d'opérations élémentaires à exécuter selon un enchaînement déterminé. En informatique, le mot est synonyme de programme, ou suite de règles bien définies pour conduire à la solution d'un problème en un nombre fini d'étapes.

Divers algorithmes sont connus dès l'Antiquité : les algorithmes des opérations arithmétiques fondamentales comme l'addition ou la multiplication, l'algorithme d'Euclide d'Alexandrie pour calculer le plus grand commun diviseur de deux nombres, plusieurs méthodes de résolution d'équations en nombres entiers à la suite des travaux de Diophante d'Alexandrie, le schéma établi par Archimède pour calculer le nombre π qui exprime le rapport de la circonférence d'un cercle à son diamètre. Plus récemment, les méthodes de résolution numérique des équations algébriques ont conduit à des algorithmes bien connus des mathématiciens : celui de Newton pour approcher la solution d'une équation, celui de Sturm pour calculer le nombre exact de racines réelles d'une équation, la méthode, due à C.F. Gauss, d'élimination de l'indéterminée entre deux équations pour déterminer si ces équations ont au moins une solution commune, etc. Les années 1930 constituent un tournant décisif du point de vue théorique : des problèmes logiques de décidabilité – un énoncé est décidable s'il existe une procédure de démonstration de cet énoncé ou de sa négation – conduisent à la formalisation de la notion d'algorithme sous la double forme des fonctions récursives de Gödel, Herbrand et Church et des fonctions calculables par machine de Turing. L'apparition des ordinateurs après la Seconde Guerre mondiale et leur utilisation généralisée permettent des calculs bien plus longs que les calculs manuels et surtout le traitement de types nouveaux de problèmes, comme le tri, la recherche d'informations non numériques, etc. Les algorithmes sont classés en fonction de leur complexité, c'est-à-dire du temps nécessaire à leur exécution. Seuls ont une efficacité effective, et non pas seulement de principe, ceux dont la complexité s'exprime polynominalement en fonction des données. Les algorithmes dont la complexité est exponentielle donnent lieu à un calcul dont le temps d'effectuation sur ordinateur excède de beaucoup, pour le moment, la durée d'une vie humaine.

Après la création, à la fin du xix^e s., de la théorie des ensembles infinis par G. Cantor, un grand débat a opposé les partisans du calcul numérique et des méthodes algorithmiques aux partisans des méthodes ensemblistes, abstraites et axiomatiques. Les premiers considéraient qu'une entité mathématique n'est définie que si on a indiqué un moyen de la construire, un problème résolu que si sa solution aboutit à un calcul numérique. Les seconds raisonnaient sur des ensembles infinis d'éléments en les caractérisant globalement par leurs structures axiomatiques et prouvaient l'existence d'une solution pour un problème sans forcément donner en même temps un procédé de calcul de ladite solution. Aujourd'hui, avec le développement du calcul formel et d'autres usages essentiels de l'outil informatique, l'opposition entre structure et calcul s'est bien émoussée.

Hourya Sinaceur

→ calcul, décidabilité, récursivité