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 [...]


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 831 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 508 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
  •  • 16 106 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
  •  • 7 436 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 073 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 27 septembre 2020. URL : https://www.universalis.fr/encyclopedie/calcul-mathematique/