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