Abonnez-vous à Universalis pour 1 euro

CALCUL, mathématique

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

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

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

Classification

Autres références

  • ACALCULIES

    • Écrit par
    • 985 mots
    ...celle(s) préservée(s). Les troubles les plus fréquents concernent le transcodage – c’est-à-dire le passage d'une notation numérique à une autre –, le calcul mental et écrit, y compris l'identification des opérateurs, et, plus rarement, l'accès à la signification des nombres. De nombreuses doubles dissociations...
  • ACQUISITION DU NOMBRE ET DU CALCUL

    • Écrit par
    • 2 067 mots
    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...
  • ALGORITHME

    • Écrit par et
    • 5 919 mots
    • 3 médias
    ...Ouzbékistan. C’est précisément par l’expression « Dixit Algorizmi » (« al-Khwarizmi a dit ») que commence l’une des traductions latines de l’ouvrage Kitab al-hisab al-hindi (Le Livre du calcul indien). Dans ce livre, al-Khwarizmi présente le système de numération qui repose sur les chiffres indiens...
  • ALGORITHMIQUE

    • Écrit par et
    • 6 652 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...

  • Afficher les 19 références