CALCUL, mathématique

Carte mentale

Élargissez votre recherche dans Universalis

Calculabilité et algorithmique

Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agit là de l'un des célèbres théorèmes de Kurt Gödel. L'informatique rejoint la logique mathématique puisque l'on montre qu'il y a équivalence entre les mécanismes des langages de programmation décrits plus haut et la notion de calculabilité inventée par les logiciens. De cette unification résulte notamment qu'il ne saurait exister de programme permettant de vérifier tant la correction que la terminaison de tout programme. Le calcul a ses limites !

L'algorithmique s'attache à l'élaboration d'algorithmes efficaces pour résoudre les problèmes reconnus comme calculables. Cette discipline s'organise selon quelques grands principes généraux. Par exemple, pour traiter efficacement des problèmes de recherche d'information de forme complexe, il s'avère utile de superposer aux données un type de graphe particulier qui soit un arbre (en un sens voisin de ce qu'entendent les généalogistes). On crée alors une superstructure artificielle qui guide l'accès rapide aux données : c'est ce que l'on appelle une structure de données. De tels principes permettent d'accéder à des ensembles de données de natures très diverses. Ils sous-tendent également les programmes capables de reproduire certains aspects bien délimités de l'activité humaine, par exemple le jeu d'échec. Une algorithmique mise en place intelligemment permet – sans miracle – d'imiter une petite partie de l'intelligence humaine.

La qualité d'un algorithme ou d'un programme se jauge au nombre d'opérations de base qu'il met en jeu pour parvenir à ses fins, reflété par le nombre d'instructions effectuées par l'ordinateur, lequel dicte le temps d'exécution. La manière dont cette quantité varie avec la taille des données s'appelle fonction de complexité. Pour une tâche déterminée, un algorithme sera d'autant meilleur que sa fonction de complexité est basse. L'analyse d'algorithmes a pour objectif l'évaluation générale de telles fonctions de complexité. Elle permet une classification des méthodes de calcul selon leurs performances, essentielle au développement de l'informatique.

Revenons à π. Par calcul informatique, deux mille chiffres étaient connus en 1950, alors que le record de l'an 2000 s'établissait à deux cents milliards et celui de 2002 à plus de mille deux cent quarante milliards. Un examen approfondi révèle que ces gains sont dus, à parts sensiblement égales, aux progrès en vitesse du matériel et à ceux de l'algorithmique. Grâce aux algorithmes les plus fins, la fonction de complexité du calcul des décimales de π est, de manière surprenante, devenue à peine supérieure à celle d'une addition d'entiers.

Se fondant sur l'algorithmique et les langages de programmation issus de la science informatique, le calcul élargit constamment les domaines auxquels il s'applique. Désormais, sont objets de calcul non seulement les nombres et quelques types de données non numériques simples, mais encore des structures géométriques (courbes et surfaces), les suites spatiales ou temporelles que sont les images et les sons, ou encore des textes en langue naturelle. Les théories du calcul (théories de la calculabilité et de la programmation, algorithmique et analyse d'algorithmes) se sont développées en étroite liaison avec les mathématiques. En retour, l'informatique permet même désormais de traiter des symboles et des formules mathématiques, voire de démontrer mécaniquement certains théorèmes – c'est ce que l'on appelle calcul formel.

Le calcul, d'activité routinière, est finalement devenu objet de la connaissance scientifique, au carrefour de multiples théories et disciplines.

1  2  3  4  5
pour nos abonnés,
l’article se compose de 4 pages

Écrit par :

  • : ingénieur de recherche à l'Institut national de recherche en informatique et automatique (I.N.R.I.A.).

Classification

Autres références

«  CALCUL, mathématique  » est également traité dans :

ACALCULIES

  • Écrit par 
  • Mauro PESENTI
  •  • 985 mots

Dans le chapitre « Approche contemporaine »  : […] Depuis les années 1980 et le développement d'architectures cognitives modélisant les représentations et processus mentaux sous-tendant les troubles acalculiques, l'intérêt pour l'établissement de classifications s'est réduit et a fait place à l'étude des dissociations chez les patients présentant des atteintes de certaines composantes des traitements numériques. Les architectures actuelles (citon […] Lire la suite

ACQUISITION DU NOMBRE ET DU CALCUL

  • Écrit par 
  • Jean-Paul FISCHER
  •  • 2 083 mots

Dans le chapitre « Le calcul »  : […] Les bébés, à peine âgés de quelques mois, possèdent aussi des capacités attentionnelles qui leur permettent de suivre trois objets, le cas échéant en mouvement ou temporairement cachés. On a pu « expliquer » cette capacité en postulant la création de fichiers d’objets. Ces fichiers permettent notamment aux bébés de voir qu’une très petite collection a été amputée ou enrichie d’un élément. Les bébé […] Lire la suite

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 833 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 déterminé. Le terme d' algorithme tire lui-même son origine du nom du mathématicien persan Al Khwārizmī (env. 820) dont […] Lire la suite

LE CALCUL DES FLUXIONS (I. Newton)

  • Écrit par 
  • Bernard PIRE
  •  • 204 mots
  •  • 1 média

En octobre 1666, Isaac Newton (1642-1727) écrit Le Calcul des fluxions qui, sans être immédiatement publié, sera déterminant pour le développement du calcul différentiel. Il y définit le concept de fluxions. Newton décrit une particule parcourant une courbe à l'aide de deux quantités : la vitesse horizontale x' et la vitesse verticale y' qu'il appelle fluxions des quantités fluentes x et y as […] Lire la suite

CALCUL INFINITÉSIMAL - Histoire

  • Écrit par 
  • René TATON
  •  • 11 509 mots
  •  • 3 médias

L'expression « calcul infinitésimal » désigne habituellement l'ensemble des notations et des méthodes fondamentales du calcul différentiel, du calcul intégral et du calcul des variations , tel qu'il a été mis au point au cours des xvii e et xviii e  siècles, instrument merveilleux qui ouvrit aux mathématiques des voies nouvelles, aussi vastes que fécondes, et permit d'aborder l'étude théorique de […] Lire la suite

CALCUL INFINITÉSIMAL - Calcul à une variable

  • Écrit par 
  • Roger GODEMENT
  •  • 11 791 mots
  •  • 6 médias

Créée au xvii e siècle par Newton, Leibniz et leurs prédécesseurs immédiats, transformée au xviii e , par Euler, en un prodigieux instrument de calcul, débarrassée, sous la Restauration, de sa métaphysique par le baron Cauchy, l'analyse infinitésimale a, depuis longtemps, atteint un degré de perfection tel qu'il est devenu possible d'en exposer l'essentiel en moins d'une dizaine de pages. C'est c […] Lire la suite

CALCUL INFINITÉSIMAL - Calcul à plusieurs variables

  • Écrit par 
  • Georges GLAESER
  •  • 5 618 mots

Le calcul infinitésimal des fonctions de plusieurs variables a eu un développement plus tardif que celui des fonctions d'un seul argument. Inauguré avec un siècle de retard, il ne parvient à établir solidement ses fondements qu'au début du xx e  siècle. Ce n'est qu'aux environs de 1930 que sont abordés les problèmes difficiles de cette branche de l'analyse, très utilisée depuis lors. […] Lire la suite

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 627 mots

Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906-1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le calcul avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme – aussi […] Lire la suite

DYSCALCULIE DÉVELOPPEMENTALE

  • Écrit par 
  • Marie-Pascale NOËL
  •  • 1 159 mots

Dans le chapitre « Les difficultés rencontrées »  : […] À l’école, des apprentissages numériques de base tels que lire et écrire des nombres ou résoudre des calculs peuvent déjà poser problème aux enfants présentant une dyscalculie. Ainsi, même devant des calculs simples à un chiffre (par exemple, 5 + 4 ou 8 x 3), ces enfants produisent plus d'erreurs, sont plus lents et utilisent des stratégies de résolution moins matures que leurs pairs : par exempl […] Lire la suite

INTELLIGENCE ARTIFICIELLE (IA)

  • Écrit par 
  • Jean-Gabriel GANASCIA
  •  • 5 076 mots
  •  • 5 médias

Dans le chapitre « Les précurseurs  »  : […] Cette discipline scientifique qu’est l’intelligence artificielle ne surgit pas de nulle part. Elle a emboîté le pas à la cybernétique, science des systèmes complexes et de leur commande, fondée dans les années 1940 et particulièrement active au début des années 1950. Celle-ci aspirait à modéliser la régulation des systèmes biologiques, psychiques, politiques ou sociaux avec des flux d’information […] Lire la suite

Voir aussi

Pour citer l’article

Philippe FLAJOLET, « CALCUL, mathématique », Encyclopædia Universalis [en ligne], consulté le 01 décembre 2021. URL : https://www.universalis.fr/encyclopedie/calcul-mathematique/